Ferkovi sa sníval hrozne zvláštny sen. Vo sne šoféroval po hrboľatej diaľnici. Za oknami sa mihala ubiehajúca krajina a Ferko uháňal na plný plyn. Potom zrazu niekde zastal, vytiahol lopatu a začal rovno pri ceste kopať. Za chvíľu vykopal truhlicu a v nej bol obrovský zlatý poklad.
Keď sa Ferko zobudil, bolo mu jasné že ten sen musí byť prorocká vízia. Vytiahol atlas, našiel v ňom najbližšiu diaľnicu a pustil sa hľadať, kde by ten poklad mohol byť. Ale ako to pri snoch bohužiaľ býva, všetky detaily okamžite zabudol a zostali mu v pamäti len hmlisté obrysy.
Pomôžte Ferkovi spomenúť si, kde má kopať!
Mapa hrboľatej diaľnice je rozdelená na $n$ kilometrov. O každom kilometri mapa hovorí, aký je strmý, čiže o koľko metrov stúpne alebo klesne naša nadmorská výška ak ním prejdeme. Tiež o každom kilometri vieme, či tam diaľnica vedie cez les alebo cez pole.
Ferko vo sne prešiel nejaký súvislý úsek diaľnice. Ale vôbec si nevie spomenúť, koľko kilometrov dokopy prešiel, na akom mieste začal, ani kde skončil. Pamätá si iba zopár vecí:
Išiel smerom preč od svojho mesta (nie v protismere).
Začiatok aj koniec boli pri nejakom diaľničnom stĺpiku, čiže na celočíselnej pozícii.
Na začiatku sna išiel presne jeden kilometer cez les. Odvtedy už nikdy znova nešiel cez les.
Na konci cesty bola Ferkova nadmorská výška presne o $s$ metrov vyššie, ako na začiatku. (Ak je $s$ záporné, skončil nižšie.)
To ešte stále nemusí byť jednoznačné. Preto spočítajte počet možností, kde sa mohol sen odohrať.
Dve možnosti považujeme za rôzne, ak začínajú alebo končia na inom mieste.
Na prvom riadku je celé číslo $s$ udávajúce, o koľko dokopy stúpla/klesla Ferkova nadmorská výška počas jeho vysnívanej cesty.
Na druhom riadku je kladné celé číslo $n$ udávajúce celkovú dĺžku diaľnice v kilometroch.
Ďalej nasleduje $n$ riadkov obsahujúcich dve celé čísla $v_i$ a $k_i$. $v_i$ určuje zmenu nadmorskej výšky na $i$-tom kilometri. $k_i$ sa rovná buď $1$ ak je na $i$-tom kilometri les, alebo $0$ ak je tam pole.
V jednotlivých sadách platia nasledujúce obmedzenia:
| Sada | 1 | 2 |
|---|---|---|
| $1 \leq n \leq$ | $100$ | $100\,000$ |
| $s \geq$ | $-10\,000$ | $-10^{11}$ |
| $s \leq$ | $10\,000$ | $10^{11}$ |
| $v_i \geq$ | $-100$ | $-10^6$ |
| $v_i \leq$ | $100$ | $10^6$ |
Ak programujete v jazyku C++, dajte si pozor na veľkosť číselných
premenných. Použite radšej long long ako
int.
Vypíšte jedno nezáporné celé číslo: počet rôznych úsekov diaľnice, ktoré sa mohli Ferkovi snívať.
Input:
9
10
1 0
8 0
4 1
5 0
7 1
1 0
20 1
-11 0
0 0
2 0
Output:
3
Vo sne mohol prejsť tretí a štvrtý kilometer ($4+5=9$), alebo siedmy a ôsmy kilometer ($20-11=9$), alebo siedmy až deviaty kilometer ($20-11+0=9$).
Input:
5
8
2 1
3 0
4 0
0 0
-4 0
0 0
3 1
5 1
Output:
4
Možnosti sú $2+3=5$, $2+3+4+0-4=5$, $2+3+4+0-4+0=5$ alebo $5=5$.
Input:
0
3
0 0
0 0
0 0
Output:
0
Diaľnica vedie po rovine, čo by síce sedelo, ale ide iba cez polia – les nikde. Predsalen to nebol prorocký sen.
Hľadáme nejaký neprázdny súvislý podúsek vstupu $i$ až $j$, kde o hodnotách $v_{i\ldots j}$ platí, že majú súčet $v_i+\ldots+v_j = s$, a o hodnotách $k_{i\ldots j}$, že prvá je 1 (les) a všetky ostatné sú 0 (pole).
Nemá zmysel skúšať všetkých $n\cdot(n+1)/2$ možností – každý možný začiatok a koniec. Keď sa pozrieme na ľubovoľné miesto kde by sme mohli skončiť, zjavne jediný začiatok čo prichádza do úvahy je najbližší predošlý les. A ak ešte žiaden les nebol, toto miesto nemôže byť koniec. Takže potenciálnych začiatkov+koncov, ktoré by sa zišlo vyskúšať, je maximálne $n$.
Keby sme od každého konca išli naspäť, hľadali najbližší začiatok a spravili zakaždým nový súčet všetkých prvkov medzi nimi, tiež by sme sa zbytočne namakali.
Radšej proste prejdeme vstupom a budeme si pamätať tri veci: priebežný súčet výšok $v_i$ od posledného lesa, počet možností čo sme zatiaľ objavili, a či už sme vôbec videli aspoň jeden les. Každý prvok vybavíme v konštantnom čase. Vždy, keď priebežný súčet výšok dosiahne hodnotu $s$, a už sme videli les, zvýšime počet možností o jedna.
Toto riešenie má časovú zložitosť $O(n)$, a pamäťovú zložitosť $O(1)$, lebo si ani len nemusíme vopred načítať všetky riadky vstupu do poľa. Môžeme každý riadok spracovať okamžite po tom, čo ho načítame.
s = int(input())
n = int(input())
vyska = 0
videl_les = False
moznosti = 0
for i in range(n):
v, k = map(int, input().split())
if k == 1:
vyska = 0
videl_les = True
vyska += v
if vyska == s and videl_les:
moznosti += 1
print(moznosti)
#include <iostream>
using namespace std;
using ll = long long;
int main() {
ll s, n;
cin >> s >> n;
ll vyska = 0;
bool videl_les = false;
ll moznosti = 0;
for (ll i = 0; i < n; i++) {
ll v, k;
cin >> v >> k;
if (k == 1) {
vyska = 0;
videl_les = true;
}
vyska += v;
if (vyska == s && videl_les) {
moznosti++;
}
}
cout << moznosti << endl;
}
Korešpondenčný seminár z programovania zastrešuje občianske združenie Trojsten.
Trojsten, o.z.
FMFI UK, Mlynská dolina
842 48 Bratislava
Programátorská súťaž pre základoškolákov
Materiály a úlohy na výučbu programovania
Intenzívny programátorský zážitok v lete