Zadanie

Hyperoptimalizácia makroskopického dátoveho centra

Počet bodov: 65

Keď Jakub videl koľko AI startupov sa na svete zakladá, ktoré pomáhajú firmám využívať veľké (makroskopické) jazykové modely, rozhodol sa, že aj on si jeden založí. Však to predsa nemôže byť zložité: Nájde si firmu ktorej zamestnanci ešte nepoužívajú chatbota, dotrénuje model od Deepseeku na základe ich interných dát a potom začne prevázdkovať ich interného chatbota. Ale kde na to zoženie výkonné počítače s dobrými grafickými kartami? Prenajme si dátové centrum. A keďže prvotriedne dátové centrá sú zatiaľ mimo Jakubov rozpočet, spravil zmluvu s menším dátovým centrom, ktoré však má netradičný cenník.

Na veľké Jakubové prekvapenie, v dátovom centre mu účtujú za všetko. Napríklad, už len keď bude chcieť dostať váhy jazykového modelu na všetky počítače, ktoré si prenajal, bude musieť platiť aj za prenos súborov v rámci dátového centra. A podľa cenníka mu bude prenos jeho 100GB jazykového modelu z počítača s číslom $i$ na počítač s číslom $j$ účtovaný sumou $i \oplus j$ centov. (Operácia $\oplus$ označuje bitový XOR.) Keďže Jakub zatiaľ žiadne peniaze nezarobil, rozmýšla ako túto operáciu zoptimalizovať. Pomôžete mu?

Úloha

Jakub na začiatku model nahrá na jeden z počítačov podľa jeho výberu. Potrebuje aby na konci bol model na všetkých počítačoch ktoré sú očíslované od $0$ po $n-1$. Môže na to použiť niekoľko prenosov. Prenos z počítača $i$ na počítač $j$ ho stojí $i \oplus j$ centov. Vypíšte koľko najmenej centov bude musieť zaplatiť za prenosy tohto modelu medzi počítačmi.

Bitový XOR

Bitový XOR (exkluzívny OR) je operácia, ktorá porovnáva dve binárne čísla bit po bite od poslednej cifry. Pre každý bit výsledku platí nasledovné pravidlo: - Ak sú bity rôzne (jeden je 0 a druhý je 1), výsledný bit na danej pozícii je 1. - Ak sú bity rovnaké tak výsledný bit je 0.

Príklad

Bitový XOR čísel 37 (v binárnej sústave 100101) a 12 (v binárnej sústave 1100) je 41 (v binárnej sústave 101001).

  1 0 0 1 0 1   (= 37)
      1 1 0 0   (= 12)
--------------
  1 0 1 0 0 1   (= 41)

Bitový XOR môžeme takmer v každom programovacom jazyku vypočítať pomocou operátora ^. Napríklad v Pythone príkaz print(37^12) alebo v C++ cout<<(37^12)<<endl; vypíše 41.

Vstup a Výstup

Na jedinom riadku vstupu je číslo $1 \le n \le 10^{15}$.

Na jediný riadok výstupu vypíšte koľko najmenej centov bude Jakub musieť zaplatiť ak chce aby sa model preniesol na všetky počítače.

Hodnotenie

• Pre 1. sadu vstupov za 10b platí: $n \leq 10$
• Pre 2. sadu vstupov za 10b platí: $n \leq 1000$
• Pre 3. sadu vstupov za 15b platí: $n \leq 10^5$
• Pre 4. sadu vstupov za 15b platí: $n \leq 10^6$
• Pre 5. sadu vstupov za 15b platí: $n \leq 10^{15}$

Príklady

Input:

4

Output:

4

Jakub vie napríklad najprv model nahrať na počítač s číslom 3 a potom z neho za $2$ centy prekopírovať na počítač 1 ($3\oplus 1=2$). Z počítaču 1 ho za $1$ cent prekopíruje na počítač 0 ($1\oplus 0=1$) a z počítaču 3 ho za 1 cent prekopíruje na počítač 2 ($3\oplus 2=1$). To ho bude spolu stáť $4$ centy.

Input:

5

Output:

8

Postup z predchádzajúceho príkladu vieme rozšíriť tým, že Jakub prekopíruje model z počítača 0 na počítač 4 za ďaľšie $4$ centy.

Input:

7

Output:

11

Postup z predchádzajúceho príkladu vieme rozšíriť tým, že Jakub prekopíruje model z počítača 4 na počítače 5 a 6 za ďaľšie $3$ centy.