Zadanie

Určite ste o ňom už počuli. Neuveriteľný chlapec, ktorého prezývajú Turista, sa narodil v neďalekom Bielorusku. Už ako jedenásťročný sa zúčastnil IOI (Medzinárodná olympiáda v informatike) a získal striebornú medailu. Ďalších 6 rokov mal samozrejme zlato, z čoho trikrát bol úplne prvý. Vyhral už asi každú súťaž, ktorú mohol (napr. Google Code Jam, Yandex.Algorithm, Facebook Hacker Cup). V Topcoderovi sa mu podarilo vyriešiť úlohu za 43 sekúnd (prečítanie zadania, naprogramovanie riešenia a submitnutie).

Pýtate sa ako je to možné? Po prvé, je to génius a po druhé, má doma veľa čokolády. A práve čokoláda bude pravdepodobne veľmi dôležitá pri jeho nasledujúcej súťaži.

Čas, ktorý Turista potrebuje na vyriešenie úlohy nezávisí od jej obtiažnosti ale od toho, ako veľmi je unavený. Prvú úlohu vyrieši za minútu, druhú za dve minúty, tretiu za tri minúty a tak ďalej. Avšak namiesto riešenia úloh sa môže kedykoľvek rozhodnúť zjesť čokoládu a obnoviť si energiu. Zjesť čokoládu mu trvá \(c\) minút. Po tom, ako zje čokoládu, mu bude vyriešenie ďalšej úlohy trvať opäť len jednu minútu, no začne sa rýchlejšie unavovať. Po prvej čokoláde mu budú úlohy trvať postupne \(1\), \(3\), \(5\)… minút a po druhej čokoláde \(1\), \(4\), \(7\)… Po zjedení \(k\) čokolád stúpa čas riešenia úloh o \(k + 1\).

Úloha

Na súťaži je \(n\) úloh, ktoré musí Turista vyriešiť.

Vyriešenie prvej úlohy trvá Turistovi \(1\) minútu. Vyriešenie úlohy tesne po tom ako zjedol čokoládu mu trvá \(1\) minútu. Ak Turista práve nezjedol čokoládu, ale už predtým ich zjedol \(k\) a predošlú úlohu vyriešil za \(x\) minút, ďalšia úloha mu zaberie \(x + k + 1\) minút. Zjedenie čokolády mu trvá \(c\) minút.

Pre dané \(n\) a \(c\) zistite, kedy má Turista zjesť čokolády, aby mu vyriešenie všetkých úloh dokopy trvalo čo najkratšie.

Formát vstupu

Na vstupe je jediný riadok obsahujúci dve celé čísla \(n\) a \(c\), \(1\leq n, c\leq 1\,000\,000\).

Formát výstupu

Na prvý riadok výstupu vypíšte najmenší možný čas, za ktorý môže Turista vyriešiť všetky úlohy. Na druhý riadok vypíšte počet čokolád \(k\), ktoré by mal počas toho zjesť. Na tretí riadok vypíšte \(k\) čísel oddelených medzerami, udávajúce, po koľkých vyriešených príkladoch by mal Turista zjesť čokoládu.

Pokiaľ je možných riešení viacero, vypíšte ľubovoľné z nich.

Príklady

Input:

10 4

Output:

37
2
5 8

Input:

10 47

Output:

55
0

V prvom príklade, keď po 5. a 8. úlohe zje čokoládu, riešenie mu bude trvať \(1+2+3+4+5+4+1+3+5+4+1+4 = 37\) minút. V druhom príklade sa mu neoplatí jesť čokoládu.

Na zistenie odpovede, t.j. celkový čas riešenia, počet čokolád a časy, v ktorých Turista zjedol čokolády, nám stačí vedieť, akú najdlhšiu dobu strávil riešením úlohy a koľko úloh riešil takto dlho. Z týchto dvoch údajov ľahko zrekonštruujeme odpoveď na úlohu, rozmyslite si ako. Taktiež po prečítaní tohto návodu bude ľahké ukázať, že tieto dve čísla sú jednoznačné.

 

Teraz si ukážeme ako tieto čísla zistiť, ak by sme vedeli, koľko presne čokolád Turista zjedol. Zistíme totiž časy riešenia všetkých úloh, len nebudeme vedieť poradie. Budeme vedieť, koľko úloh mu trvalo minútu, koľko úloh mu trvalo dve minúty, atď.

Majme niekoľko aritmetických postupností, \((i+1)\)-ta vyjadruje, ako dlho budú turistovi trvať príklady po \(i\)-tej čokoláde.

\(a_0 = 1,2,3,4,5,6,7,\dots\)

\(a_1 = 1,3,5,7,9,11,\dots\)

\(a_2 = 1,4,7,10,13,\dots\)

\(a_3 = 1,5,9,13,\dots\)

\(\dots\)

Keď vieme, že turista zje \(k\) čokolád, tak skupina optimálnych časov je \(n\) najmenších čísel (tie sa môžu opakovať) z \(a_0\) až \(a_k\). Napríklad \(8\) najmenších čísel z prvých \(4\) postupnosti je \(1,1,1,1,2,3,3,4\). Ale ako vieme nájsť najmenších \(n\) čísel z nekonečných postupností? Zjavne nebudeme nikdy brať čísla väčšie ako \(n\), tým pádom môžme všetky postupnosti orezať aby mali len čísla do \(n\) vrátane. Potom všetky čísla jednoducho nahádžeme do (maximovej) prioritnej fronty, zahodíme všetky okrem \(n\) najmenších a potom vyberieme tie. Čisel je dokopy \(n+n/2+n/3+n/4+n/5+\cdots\) čo je rádovo \(n\log n\).

 

Ale my predsa nevieme koľko je \(k\). To nevadí – vyskúšame všetky možnosti. Avšak nebudeme prvých \(n\) čísel z aritmetických postupností počítať vždy odznova, vieme totiž, že najmenších \(n\) čísel z \(a_0\dots a_{k+1}\) vieme poskladať z \(a_{k+1}\) a najmenších \(n\) čísel z \(a_0\dots a_k\).

Celý algoritmus bude vyzerať nasledovne. Nahádžeme do prioritnej fronty prvých \(n\) čísel z \(a_0\). Postupne zvyšujeme \(k\) až po \(n\) a pri každom zvýšení spravíme toto: Hádžeme do fronty čísla z \(a_k\), kým číslo ktoré vhadzujeme je menšie ako maximum v prioritnej fronte. Vždy, keď je v prioritnej fronte viac ako \(n\) čísel, vyhodíme maximum. Po skončení vhadzovania skontrolujeme, či sme dosiahli najlepší celkový čas a ak áno zapamätáme si dve dôležité hodnoty (najväčšie číslo v prioritnej fronte a počet toho čísla vo fronte).

Na konci len zrekonštruujeme odpoveď ktorú treba vypísať.

Pri rozumnej implementácii (prioritná fronta bude obyčajné pole, kde si na \(i\)-tej pozícii pamätáme počet prvkov \(i\) vo fronte) bude celková časová zložitosť \(O(n \log n)\), pretože najviac toľko čísel dokopy spracujeme. Pamäťová zložitosť je \(O(n)\).

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ť.