Zadanie

Na matfyze sa v rámci prestavby začali vymieňať všetky okná. A to zahŕňa aj KSPácku miestnosť T2. A aby sme uvoľnili miesto robotníkom, musíme ju celú vypratať. Problém však je, že v T2 sa nachádza všetko. A tím myslím naozaj všetko. Od gitary, počítačov, hlavnovedúcovskej tyče, soba, masky Darth Vadera, cez chemikálie, terčovnicu, vŕtačku, papuče, po pílku na železo, hasiaci prístroj, TODO list a nič.1 Naviac má každá z týchto vecí iný objem a keďže sa tu nachádza všetko, pre každé prirodzené číslo existuje v T2 jeden predmet s takýmto objemom.

Našťastie ako informatici máme dobrý komprimovací prístroj, ktorý dokáže bezstratovo zmenšiť objem ľubovoľného objektu s objemom väčším ako \(1\). Tento komprimátor funguje tak, že ak mal predmet pôvodne objem \(a\), po skomprimovaní bude mať tento predmet objem \(b\), kde \(b\) je počet jednotiek v binárnom zápise čísla \(a\). Ak sa napríklad \(a=19_{10}=10011_2\), tak \(b=3\). Teraz je snáď jasné, prečo sa predmet s objemom \(1\) nedá komprimovať. Táto komprimácia sa dá samozrejme opakovať, čím dostávame stále menšie a menšie predmety, až kým sa dostaneme na objem \(1\). Pre \(a=19\) musíme komprimáciu opakovať \(3\) krát, pričom dostanem postupne objemy \(3\), \(2\) a \(1\).

Avšak skôr ako sa komprimátor začal používať, nadšení a akciechtiví prváci vypratali časť T2 a zostali v nej len predmety, ktorých objemy sú medzi \(l\) a \(h\) vrátane. Všetky tieto predmety chceme teraz skomprimovať na objem \(1\), musíme si však dať pozor, aby sme ich vedeli dekomprimovať. Dôležité je, aby sme každý predmet dekomprimovali presne toľko krát, koľko krát sme ho komprimovali. Všetky veci (v tom čase už s objemom \(1\)) si teda uložíme do krabíc tak, aby veci, ktoré potrebovali rovnaký počet komprimácii, kým skončili s objemom \(1\), boli v tej istej krabici. Dopredu by sme však chceli vedieť, aké veľké krabice si máme pripraviť na ktorú sadu predmetov.

Úloha

Pre čísla \(l\), \(h\) a \(k\) určite počet takých predmetov s objemom medzi \(l\) a \(h\) vrátane, že na ich skomprimovanie na veľkosť \(1\) je potrebných práve \(k\) komprimácií.

Formát vstupu

Na prvom riadku vstupu je číslo \(t\) (\(1 \leq t \leq 1\,000\)) – počet vstupných testov.

Nasleduje \(t\) riadkov, každý obsahujúci tri čísla \(l\), \(h\) a \(k\) (\(2 \leq l \leq h \leq 10^{18}\), \(1 \leq k \leq 10^6\)).2 \(l\) a \(h\) udávajú interval objemov, z ktorého vyberáme a \(k\) je žiadaný počet komprimácií.

Formát výstupu

Pre každý z \(t\) testov vypíšte jedno číslo – počet takých čísiel medzi \(l\) a \(h\), že sa skomprimujú na \(1\) po práve \(k\) komprimáciách.

Bodovanie

Vstupy sú rozdelené do \(10\) testovacích sád. Jednotlivé sady majú svoje obmedzenia a väčšinou platí, že vyriešiť skoršiu sadu je jednoduchšie. Zároveň by riešenia niektorých nižších sád mali pomáhať pri vymýšľaní zložitejších riešení.

  • Pre sadu \(01\) platí, že \(t=100\), \(b\leq 10^6\), \(b-a \leq 1\,000\)
  • Pre sadu \(02\) platí, že \(t=100\), \(b\leq 10^{18}\), \(b-a \leq 1\,000\)
  • Pre sadu \(03\) a \(04\) platí, že \(t=1\,000\), \(b\leq 10^{18}\), \(b-a \leq 10^6\)
  • Pre sadu \(05\) a \(06\) platí, že \(t=1\,000\), \(a=2\), \(b\leq 10^{18}\)
  • Pre zvyšné sady neplatia žiadne špeciálne podmienky.

Príklad

Input:

2
4 11 2
4 11 3

Output:

4
2

  1. Možno si myslíte, že niektoré z týchto vecí som si vymyslel pre lepší epický tón rozprávky. Mýlite sa. Toto všetko sa naozaj nachádza v T2. A verte mi, je toho ešte oveľa viac.↩

  2. Z obavy vytvorenia čiernej diery sa neodvažujeme komprimovať predmety s objemom väčším ako \(10^{18}\), pretože hmotnosť sa zachováva.↩

Možno ste si všimli, ale tento príklad bol zároveň aj posledný príklad v kategórii O. Vo vzorových riešeniach tejto kategórie nájdete celé riešenie tohto príkladu, tu je uvedená len časť “rekapitulácia”.

Ako teda vyzerá celé riešenie pokope? Na začiatku načítame vstup a spravíme nejaké predrátania. Presnejšie, zrátame odpoveď pre prvých \(63\) čísiel a predpočítame si Pascalov trojuholník do hĺbky \(63\). Ten nám bude slúžiť na to, aby sme vedeli rýchlo povedať hodnotu jednotlivých kombinačných čísiel. Stačí nám to počítať do dvojrozmerného poľa postupne od malých hodnôt k väčším, klasickým prístupom – sčítame dve susedné z predošlého riadku.

Pokračujeme tým, že vyrátame výsledok pre horné ohraničenie \(h\). Toto číslo si zmeníme na binárne. Potom prechádzame prvých \(63\) čísiel a vždy, keď vidíme, že nejaké číslo \(a\) má riešenie \(k-1\) komprimácií, zistíme počet čísiel menších ako \(h\), ktoré obsahujú \(a\) jednotiek v binárnom zápise. Toto zistíme tradičným dynamickým programovaním cez jednotlivé cifry.

Od výsledku odrátame výsledok pre horné ohraničenie \(l-1\) a máme výsledok pôvodnej úlohy. Zostáva už len odhadnúť časovú a pamäťovú zložitosť. Nebudeme sa tváriť, že \(63\) je konštanta, lebo to vzniklo ako logaritmus čísla \(h\) a tak to aj budeme označovať. Pamätať si musíme binárny zápis čísla \(h\) a Pascalov trojuholník, ktorý je kvadratický, takže pamäťová zložitosť bude \(O(\log^2 h)\). A časová zložitosť bude úplne rovnaká, keďže pre najviac \(\log h\) čísiel pustíme dynamiku so zložitosťou \(O(\log h)\).

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.