Počet bodov:
Popis:  6b
Program:  4b

KSPáci majú radi jedlo – to vie hádam každý. A tak si počas posledných príprav pred sústredkom objednali do T2 pizzu, aby mali dosť síl na pobalenie kufrov. Keď odchádzali na sústredko, každý niečo niesol, ale krabice od pizze ostali tam – za ten týždeň, čo tu nebudeme, ich určite niekto vyhodí…

Sústredko prebehlo a všetci sa plní zážitkov vrátili do T2, kde s hrôzou zistili, že krabice od pizze sú stále tam. Adam si všimol, že krabica od jeho veľkej pizze má dvakrát takú dlhú stranu ako krabice od malých pízz a vložil 4 menšie krabice vedľa seba do jednej veľkej. Takéto šetrenie miesta sa mu zapáčilo. Zobral si do ruky meter a začal merať veľkosti všetkých krabíc. S prekvapením zistil, že dĺžka strany každej krabice bola nejaká mocnina dvojky. Do najväčšej krabice povkladal teda tak veľa menších, koľko sa dalo. Potom rovnako pokračoval so zvyškom. Zistite, koľko krabíc musel nakoniec Adam odniesť do kontajnera.

Úloha

Máte zadané dĺžky strán všetkých krabíc. Každá krabica je štvorcová a dĺžka jej strany je mocnina dvojky.

Do každej krabice vieme vkladať len menšie krabice. Do krabice s dĺžkou strany \(2^k\) vieme vložiť vedľa seba najviac \(4\) krabice s dĺžkou strany \(2^{k-1}\). Ak zostáva v krabici voľné miesto, môžeme ho vyplniť aj menšími krabicami. Jednoducho, celková plocha krabíc, ktoré sú uložené vedľa seba, nemôže byť väčšia ako plocha vonkajšej krabice.

Vašou úlohou je zistiť, koľko krabíc ostane po tom, ako ich optimálne povkladáme do seba.

Formát vstupu

V jednom riadku je 20 čísel \(a_0, a_1, \dots, a_{19}\) oddelených medzerami (\(0 \leq a_i \leq 1\,000\,000\)). Číslo \(a_i\) hovorí o tom, koľko máme krabíc s dĺžkou strany \(2^i\).

Na pamätanie si veľkých čísel1 môžete použiť 64-bitové premenné typu long long v C++, Int64 v Pascale.

Formát výstupu

Vypíšte jedno číslo – počet krabíc, ktoré ostanú na konci.

Príklad

Input:

0 0 5 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Output:

2

Ostane krabica so stranou dlhou \(8\) (v ktorej sú 4 krabice s dĺžkou \(4\)), a jedna krabica s dĺžkou \(4\), ktorá sa tam už nezmestila.

Input:

0 0 13 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Output:

1

Balíme trinásť krabíc s dĺžkou strany \(4\), jednu s dĺžkou \(8\) a jednu s dĺžkou \(16\). Môžeme ich pobaliť nasledovne: Najprv do krabice s dĺžkou strany \(8\) zabalíme jednu štvorkovú. Potom sa krabica \(8 \times 8\) a 12 krabíc \(4 \times 4\) presne vojdú do krabice \(16 \times 16\).

Input:

0 0 20 4 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Output:

5

Zostanú 4 najmenšie krabice a 1 najväčšia.


  1. Približne v rozsahu \(-2^{63}\)\(2^{63}\).

Odovzdávanie

Na odovzdávanie sa musíš prihlásiť

Otázky a diskusia

Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.