Zadanie

Táto úloha sa dá nahradiť riešením sady variables_cpp na Liahni (betaliahen.ksp.sk) . Ak chceš, aby ti namiesto bodov za riešenie tejto úlohy boli započítané body získané riešením spomínanej sady, na stránke odovdzaj pdf-ko s prezývkou, ktorú používaš na Liahni.

Ak máte akékoľvek otázky ohľadom tejto úlohy napíšte Michalovi ‘Žabovi’ Anderlemu na

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.

Mocniny 2

Mocniny čísla 2 sú postupne čísla 1, 2, 4, 8, 16, 32 … Každú ďalšiu mocninu dostaneme, ak predchádzajúcu vynásobíme dvojkou. Zápis \(2^k\) predstavuje číslo, ktoré získame, ak číslo 1 \(k\)-krát vynásobíme číslom 2. Napríklad \(2^3 = 8\) alebo \(2^0 = 1\).

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}\) až \(2^{63}\).↩

Aby sme vyriešili túto úlohu, stačí nám robiť to, čo robil Adam v rozprávke v zadaní. Začneme od najväčších krabíc – vždy do nich vložíme toľko menších, koľko sa zmestí, pričom zvyšné krabice musia zostať vonku.

Aby sme si v našom riešení udržali poriadok, v jednej premennej mozem_zabalit si budeme pamätať, koľko aktuálne spracúvaných krabíc vieme zabaliť do väčších. Môžeme si všimnúť, že aj keď sú v krabici \(8 \times 8\) štyri krabice \(4 \times 4\), stále sa tam zmestí 16 krabíc \(2 \times 2\). Teda väčšie krabice neovplyvňujú tie menšie, ak sú spoločne v jednej krabici. Na spočítanie, koľko menších krabíc vieme zabaliť, nám preto stačí vynásobiť premennú mozem_zabalit štyrmi .

Postupovať budeme od najväčších krabíc po najmenšie a v každom kroku bude našou úlohou “zabaliť krabice s hranou dĺžky \(2^i\)”. Zakaždým spočítame, koľko takýchto krabíc musí zostať vonku a koľko miesta bude pre menšie krabice.

Krabíc zabalíme najviac mozem_zabalit. Ak sa všetky krabice zmestia do väčších, veľkosť voľného miesta pre ešte menšie krabice bude 4 * mozem_zabalit. Ak sa niektoré krabice nezmestia dnu, zostávajú vonku a teda ich pripočítame ku krabice_vonku. Tiež ale vytvoria nový priestor pre ešte menšie krabice, teda menších krabíc budeme vedieť zabaliť 4 * (mozem_zabalit + ostali_vonku).

Krabice jednej veľkosti “zabalíme” v konštantnom čase \(O(1)\), teda ak máme \(k\) veľkostí krabíc, riešenie bude potrebovať \(O(k)\) času. Keďže vstup spracúvame odzadu, musíme ho celý načítať do poľa, teda aj pamäťová zložitosť bude \(O(k)\). V tejto úlohe boli ale všetky vstupy s \(k=20\), tak ste mohli tvrdiť, že beh programu nezávisí od veľkosti čísel na vstupe a prehlásiť časovú zložitosť za konštantnú (ale 1. takéto tvrdenie je vždy potrebné vysveliť, 2. časový odhad \(O(k)\) je informatívnejší).

#include <iostream>

using namespace std;

int main(){
  int pocty[20];
  for(int i = 0; i < 20; i++)
    cin >> pocty[i];
  int krabice_vonku = 0;
  long long mozem_zabalit = 0;
  
  for(int i = 19; i >= 0; i--){
    if (pocty[i] > mozem_zabalit){
      krabice_vonku += pocty[i] - mozem_zabalit;
      mozem_zabalit += pocty[i] - mozem_zabalit;
    }
    mozem_zabalit *= 4;
  }
  cout << krabice_vonku << endl;
}

Niektorí z vás skúšali aj opačný prístup – vkladať krabice od najmenšej. Často ste si ale nevšimli, že nám vonku ostávajú krabice rôznych veľkostí. Ak totiž príde veľká krabica (napr. taká, do ktorej sa zmestia všetky menšie), počet tých, ktoré zostanú vonku sa nedá vyrátať bez toho, aby sme sa pozreli na každú menšiu velkosť zvlášť.

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