1. Zábava musí byť vzorové riešenie

Zadanie

Pilný študent Slavo sa rozhodol dať si pauzu od každodenného kolobehu a vybral sa do zábavného parku. Zistil totiž, že tam budú mať aj jeho obľúbenú disciplínu – strieľanie zo zbraní. Slavo je už starý harcovník, čo sa (aj) strieľania týka a je teda odhodlaný vyhrať akúkoľvek súťaž, čo sa tam bude organizovať.

Keď Slavo prišiel do parku, hneď sa zastavil pri tej najväčšej tabuli široko ďaleko:

Chceš byť ako kovboj z Divokého Západu? Vystrieľaj si výhru!

No, musíte uznať, že to¹ znie dosť dobre.

Vybral sa teda na strelnicu. Zistil, že sa strieľa z pušky a z brokovnice. S oboma už mal tú česť, takže v tom by problém nemal byť. Ba čo viac, všimol si, že vzdialenosť medzi jednotlivými terčmi je taká, že na jeden výstrel brokovnice dokáže trafiť aj dva terče vedľa seba. Už to len nedokašľať!

Terče na strelnici sú usporiadané zvláštnym spôsobom. Z pozície, odkiaľ sa strieľa, vidí strelec \(n\) terčov umiestnených v pravidelných rozostupoch vedľa seba. Za každým z týchto terčov môže (ale nemusí) byť ešte niekoľko iných terčov, akoby v zástupe. Ich počet je strelcovi dopredu známy. Z vtáčej perspektívy to celé môže vyzerať napríklad takto:

Keď sa Slavo spýtal na pravidlá, dozvedel sa nasledovné:

• Terče sú labilné, teda pri zasiahnutí terču tento (tieto) padne² a odkryje sa ďalší za ním (ak tam ešte nejaký je).

• Strelec má k dispozícii neobmedzené množstvo nábojov do oboch zbraní a môže ich ľubovoľne kombinovať a striedať.

• Cieľom hry je zhodiť všetky terče na čo najmenej výstrelov.

Ako má Slavo skombinovať pušku s brokovnicou aby potreboval čo najmenej výstrelov? Kam strieľať čím? Chce vyhrať. Musí vyhrať. Chce byť ako z Divokého Západu. Pomôžte mu!

Úloha

Pre dané počty terčov v jednotlivých zástupoch zistite, koľko výstrelov bude Slavo potrebovať, aby vyhral. Zaujíma nás teda najmenší možný počet výstrelov, na ktorý vie Slavo zasiahnuť (a zhodiť) všetky terče.

Predpokladajte, že Slavo nikdy neminie cieľ. Puškou vie trafiť ľubovoľný terč, na ktorý vidí (nezakrýva ho iný terč). Brokovnicou dokáže trafiť ľubovoľné dva terče stojace v susedných zástupoch (oba terče musí byť vidno).

Formát vstupu

V prvom riadku je jedno celé číslo \(n\) (\(1 \leq n \leq 100\,000\)) – počet radov terčov (teda počet terčov viditeľných na začiatku). Na ďalšom riadku je \(n\) medzerou oddelených kladných celých čísel \(1 \leq t_i \leq 10^9\) – \(i\)-te číslo udáva počet terčov v \(i\)-tom rade (dokopy, vrátane toho terča, ktorý vidíme).

Formát výstupu

Na výstup vypíšte jediné celé číslo – počet výstrelov, ktoré Slavo vykoná pri najlepšej možnej stratégii.

Dávajte si pozor na veľkosť čísel, s ktorými pracujete. Všimnite si, že keď budete napríklad sčítavať čísla zo vstupu, výsledok sa vám nemusí zmestiť do 32-bitovej premennej. Odporúčame preto použiť long long v C++ a Int64 v Pascale.

Príklady

Input:

3
1 6 1

Output:

6

Vstup predstavuje 3 rady terčov. V prvom a treťom rade je po jednom, v druhom rade je 6 terčov za sebou. Správna stratégia je napríklad vystreliť najprv puškou 4-krát do druhého radu a potom brokovnicou do prvých dvoch a druhých dvoch. Existujú aj iné, rovnako dobré stratégie.

Input:

5
5 1 8 5 5

Output:

18

Tento vstup zodpovedá obrázku v zadaní. Slavo strelí 8-krát puškou do stredného radu. Následne si vymení zbraň a 5-krát to brokovnicou napáli naraz na posledné dva rady. Zase si vymení zbraň, a 4-krát vystrelí na prvý rad. Nakoniec posledný krát vystrelí brokovnicou na prvý. Lepšie to nejde, no možností je opäť viac.

Input:

6
1 5 5 5 5 3

Output:

13

---

1. Až na toho kovboj-a.↩

2. Toto platí dupľom, keďže strieľa Slavo.↩

Riešenie tejto úlohy sa síce dalo ľahko vymyslieť a aj ľahko a rýchlo naprogramovať, no dôležité bolo správne odargumentovať správnosť vášho riešenia.

Nezáleží na poradí operácií

Zostreľovanie terčov si môžeme predstaviť ako zoznam operácií, v ktorom sa dá každá operácia zapísať ako px – puška zostrelí jeden terč na pozícii \(x\), alebo bx – brokovnica zostrelí po jednom terči na pozíciách \(x\) a \(x+1\).

Pre každú pozíciu \(1, 2, \dots, n\) si môžeme spočítať, koľko výstrelov na ňu dopadne pri konkrétnom zozname operácií. Napríklad pri zozname p1, b3, p4 dopadne po jednom výstrele na pozície 1, 3, dva výstrely na pozíciu 4 a žiadny výstrel na pozíciu 2.

Vďaka takémuto pohľadu na našu úlohu si môžeme uvedomiť, že ak v nejakom zozname preusporiadame poradie použitých operácií, na každú pozíciu dopadne stále rovnaký počet výstrelov ako pred preusporiadaním. Zoznamy operácií p1, b3, p4 a napríklad b3, p4, p1 budú mať teda rovnaký výsledný efekt.

Pri hľadaní riešenia nás teda nebude zaujímať poradie operácií, ale len to, koľkokrát musíme pozíciu \(x\) zasiahnuť puškou a koľkokrát brokovnicou, teda len počet operácií bx a px pre každé \(x\).

Ako vymyslieť riešenie?

Puška zhodí v jednej operácii jeden terč, no brokovnica dva. Keďže chceme minimalizovať celkový počet použitých operácií, chceli by sme čo najviackrát použiť brokovnicu (a zasiahnuť tak dva terče naraz v čo najviac operáciách). Pri rozmiestňovaní výstrelov si ale musíme dať pozor, aby sme sa nepripravili o možnosť použiť brokovnicu.

Predstavme si, že na každej z pozícií \(1,2,3,4\) stojí jeden terč. Všetky terče vieme zostreliť dvoma operáciami, napríklad b1, b3. Ak by sme ale brokovnicou strelili do stredu (použijeme b2), tak pri zostreľovaní zvyšných terčov nám už brokovnica nepomôže a potrebujeme aspoň 3 operácie (terče 1 a 4 zostrelíme puškou). Problém vznikol tým, že sme skupinku terčov vedľa seba (rozostavenie, ktoré sa dobre zostreľuje brokovnicou), rozdelili jednou dierou na dve skupinky, ktoré boli ďaleko od seba a už sa pre ne brokovnica nedala použiť.

Ako využiť potenciál brokovnice naplno? Ako dobrý nápad sa môže zdať, že budeme zostreľovať terče zľava doprava, pričom brokovnicou strieľame, kým sa dá (kým na pozícii \(x\) aj \(x+1\) sú terče) a ak sa náhodou minú terče na pozícii \(x+1\) skôr ako terče na \(x\), zvyšok terčov na \(x\) zostrelíme puškou. Takto nikdy nevytvoríme žiadnu dieru navyše a použijeme brokovnicu čo najviackrát.

Ako dokázať správnosť riešenia?

Naša predošlá úvaha nás síce doviedla k riešeniu, no vysvetlenie, prečo toto riešenie nájde minimálny počet operácií je trochu nejasné. Ukážeme si však, ako jasne dokázať, že riešenie je správne.

Ak na prvej pozícii stojí \(k\) terčov, v ľubovoľnom (teda aj v tom najlepšom) zozname operácií, ktorý má zhodiť všetky terče, musí byť práve \(k\) operácií, pri ktorých \(x = 1\). Čo najviac z týchto terčov zostrelíme brokovnicou, a keď už brokovnicu nemôžeme použiť (lebo už nie sú terče na pozícii 2), zvyšok terčov zostrelíme puškou. Takto sa dostávame do stavu, kde na prvej pozícii nezostal žiadny terč, použili sme najmenší počet operácií, ktoré boli nutné na zostrelenie všetkých \(k\) terčov na pozícii 1 a zároveň sme použili brokovnicu najviackrát ako sa dalo.

Dôležitý bod zamyslenia je, že síce sme použili brokovnicu najviackrát pri zostreľovaní terčov na prvej pozícii, no nemohli by sme dosiahnuť celkovo lepšie riešenie (celkovo väčší počet výstrelov brokovnicou a menší počet operácií), ak by sme na prvú pozíciu použili brokovnicu menejkrát? Nie. Ak by sme použili brokovnicu menejkrát, na zvyšných \(n-1\) pozíciách by tak celkovo zostalo viac terčov ako v našom riešení. Na zostrelenie zvyšných terčov by tak bolo potrebných aspoň toľko operácií ako v našom riešení a tak vieme, že sa naše riešenie určite nedá zlepšiť.

Keďže na pozícii 1 už nezostáva žiadny terč, môžeme sa na našu úlohu pozrieť tak, ako keby sme ju riešili už len pre \(n - 1\) terčov a použiť znova tú istú úvahu: Nech je na pozícii 2 \(m\) terčov, potrebujeme aspoň \(m\) operácií, čo najviac z nich chceme spraviť brokovnicou, atď.

Implementácia po lopate

Postupne prechádzame rady terčov od \(i=1\) po \(i=n\): Pre rad \(i\) použijeme brokovnicu kým sa dá (kým je v rade \(i+1\) aspoň jeden terč), a potom dorazíme ostatné terče v rade \(i\) puškou. Pokračujeme na ďalší rad. Toto sa dá implementovať jedným cyklom.

Časová zložitosť je teda lineárne závislá od počtu radov terčov a ničoho iného: \(O(n)\).

Pamäťová zložitosť bude kvôli pamätaniu počtu terčov v jednotlivých radoch tiež: \(O(n)\).

n = int(input())
A = [int(x) for x in input().split()]

vystrelov, vysledok = 0, 0
for x in A:
    # kolko novych striel spravim v tomto kole?
    # ratam s tym, ze uprednostnujem brokovnicu, teda co najviac
    # z tych, co som vystrelil v minulom kole zasiahlo aj tento rad
    if x < vystrelov:
        vystrelov = 0
    else:
        vystrelov = x - vystrelov
    # pripocitame pocet vystrelov v ramci spracovavania radu
    vysledok += vystrelov

print(vysledok)

Všímaj, že pamäť ušetriť môžeš!

Ešte raz si prečítajte predchádzajúci odsek. V každom momente sa pri výpočte pozeráme len na práve spracovávaný a nasledujúci rad terčov, teda nám stačí pamätať si len počty terčov v týchto dvoch radoch, čím dostávame konštantnú pamäťovú zložitosť: \(O(1)\).

#include <iostream>
#include <algorithm>

using namespace std;

int main () {
  // a = predchadzajuci, b = terajsi
  long long n, a, b, pocet_vystrelov = 0LL, vystreli = 0LL;
  cin >> n >> a;

  for (int i = 0; i < n - 1; ++i) {
    cin >> b;
    // brokovnica
    vystreli = min(a, b);
    a -= vystreli;
    b -= vystreli;
    pocet_vystrelov += vystreli;
    // puska ak treba
    if (a > b) {
      pocet_vystrelov += a;
    }
    // terajsi bude dalej ako predchadzajuci
    a = b;
  }
  pocet_vystrelov += a; // dorazime este posledneho puskou, tento by sa inak nespracoval

  cout << pocet_vystrelov << endl;
}

Iné riešenie(a)

Optimálnych riešení tu je viac (keďže nezáleží na poradí operácií). Napr. by bolo rovnako správne najprv všetko čo sa dá postrieľať brokovnicou a potom všetko ostatné doraziť puškou. Toto by však nešlo s konštantnou pamäťovou zložitosťou.