Občas je tým najdôležitejším v živote správne sa narodiť – a farmárovi Bohdanovi sa to nie tak celkom podarilo. Tak ako jeho rodičia, súrodenci, susedia a krajania, aj Bohdan vyznáva lokálne náboženstvo, ktorého bohovia sú známi tým, že sú tak trochu mimo. No dobre, nalejme si čistého vína… sú proste úplne šialení.
Tak napríklad: farmárom trvalo niekoľko generácií, kým prišli na to, akým presným spôsobom sa majú k bohom modliť, aby tí pochopili, že ich žiadajú o dážď, ktorý by zavlažil ich úrodu… a že v tom daždi má pršať voda, a nie piesok, žaby, kobylky alebo traktory. Podrobnosti správneho rituálu pre stručnosť zadania vynecháme, ale zrejme je jeho podstatnou časťou stojka na hlave s rukami namierenými do správnych svetových strán… pretože vždy keď zaprší, stane sa to iba na úzkom páse poľa. Mohli by ste sa pýtať, prečo by to malo dávať zmysel. Bohdan už sa radšej nepýta.
Asi teda nikoho neprekvapí, že Bohdan, ako každý v okolí, mešká s odvádzaním daní zo svojej úrody – nie je ľahké byť farmárom, keď vaša pšenica rastie každý deň iba na malom pásiku poľa, a všade inde smutne čaká na závlahu. Preto sa rozhodol, že raz za čas proste zožne kúsok poľa, ktorý už stihol narásť dostatočne, namiesto toho, aby čakal celú sezónu a nakoniec zožal celé pole naraz.
Výborne, takže teraz má okrem meškajúcich daní ešte aj poriadny zmätok v tom, koľko pšenice mu zostáva na ktorých kúskoch poľa… Pomôžte mu!
Pole tvorí mriežka rozmerov $s \times v$, na začiatku je všade nulové množstvo pšenice. Občas sa stáva, že zaprší na každé políčko určitého riadku alebo stĺpca, a pšenica na daných políčkach vyrastie o nejaký počet jednotiek. Tiež sa stáva, že Bohdan pšenicu na nejakom (práve jednom) políčku zožne. Vtedy ho zaujíma, koľko pšenice z daného políčka dostane.
Na prvom riadku dostanete zadané prirodzené čísla $s$ (šírku mriežky), $v$ (výšku mriežky) a $q$ (počet dotazov) oddelené medzerami.
Nasleduje $q$ riadkov, každý popisuje jednu udalosť:
| x j – zaprší na každé políčko v stĺpci $1 \leq x \leq s$, pšenica na nich vyrastie o $1 \leq j \leq 10^9$ jednotiek,- y j – zaprší na každé políčko v riadku $1 \leq y \leq v$, pšenica na nich vyrastie o $1 \leq j \leq 10^9$ jednotiek,? x y – Bohdan zožne všetku pšenicu na políčku v stĺpci $x$ a riadku $y$ – a zaujíma ho, koľko jej tým získa.Pre každú udalosť typu ? odpovedzte jedným číslom – množstvom zožatej pšenice z daného políčka – na samostatnom riadku.
Na udalosti typu ? musíte odpovedať online – teda ďalší kúsok vstupu dostanete až potom, čo odpoviete.
Existujú štyri testovacie sady, vo všetkých platí $1 \leq s, v \leq 10^6$ a $1 \leq q \leq 10^5$. V jednotlivých sadách však platia nasledovné dodatočné obmedzenia:
Odporúčame zavolať funkciu flush po každom vypísanom riadku,
aby program nečakal, kým sa operačný systém rozhodne vyprázdniť zásobník štandardného výstupu
(čo sa kvôli efektivite deje menej často, než by bolo pre túto úlohu vhodné).
V C++ môžete zavolať std::cout.flush(),
alebo jednoducho vypisovať nové riadky pomocou std::endl namiesto \n.
V Pythone stačí pridať argument funkcii print(..., flush=True).
Pokiaľ váš program odpovie príliš malým počtom riadkov, dostane ako odpoveď TLE – Prekročený časový limit.
Pokiaľ bude riadkov príliš veľa, zobrazí sa vám PRV – Chybný formát.
5 5 4
- 1 5
| 2 7
? 2 1
? 2 2
12
7
Do riadku $1$ najskôr zaprší $5$ jednotiek dažďa, potom do stĺpca $2$ zaprší $7$ jednotiek. Na políčku $2,1$ teda narástlo $12$ jednotiek pšenice, na políčku $2,2$ ale iba $7$ jednotiek.
5 5 4
- 1 5
? 2 1
| 2 7
? 2 1
5
7
Keďže políčko $2,1$ zožne Bohdan už po prvom daždi, po druhom daždi z neho získa už iba pšenicu, ktorá narástla medzitým.
V úlohe simulujeme tabuľku a musíme podporovať tri typy operácií:
Najjednoduchšie možné riešenie je, že si vyrobíme v pamäti tabuľku a pre každé políčko si budeme pamätať, koľko pšenice je na ňom aktuálne. Tretiu operáciu tak zvládneme konštantne rýchlo, proste sa pozrieme na správne políčko a vynulujeme jeho hodnotu.
Lenže prvé dve operácie budú trvať $O(S)$ a $O(V)$ času, keďže pri nich musíme prejsť všetky políčka riadku alebo stĺpca a ku každému pripočítať množstvo zrážok. Za takéto riešenie teda dostaneme maximálne $2$ body za prvú sadu.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int S, V, Q; cin >> S >> V >> Q;
// Vytvoríme si vynulované 2D pole (s rozmermi väčšími o 1, aby sme nemuseli riešiť indexovanie od 0)
vector<vector<ll>> squares(S + 1, vector<ll>(V + 1));
for (int q=0; q < Q; q++){
char type; cin >> type;
ll a, b; cin >> a >> b;
if (type == '?'){
cout << squares[a][b] << endl; // Proste odpovieme aktuálne zapamätanú hodnotu...
squares[a][b] = 0; // ...a vynulujeme ju
}
else if (type == '-') for (int i = 1; i < S + 1; i++) squares[i][a] += b; // Pridáme na všetky políčka v riadku
else for (int j = 1; j < V + 1; j++) squares[a][j] += b; // Pridáme na všetky políčka v stĺpci
}
}
Poďme sa teda zamyslieť nad zjednodušeniami v druhej a tretej sade, a možno nám pomôžu zistiť, ako vyriešiť úlohu optimálne.
Keďže pole má šírku iba jedného políčka, bude prvá operácia rýchla aj pri použití triviálneho riešenia. Problém je, že pri druhej operácii musíme stále prejsť $V$ políčok. Do všetkých z nich ale chceme pridať tú istú hodnotu, to by sme mohli nejako využiť.
Konkrétne tak, že si budeme samostatne pamätať množstvo zrážok, ktoré dopadlo na každé políčko, keď pršalo do riadku, a samostatne jedno číslo – množstvo zrážok, ktoré spadli do stĺpca. Celkové množstvo zrážok je potom jednoduchý súčet dvoch čísel, teda všetky operácie podporujeme v konštantnom čase.
Ešte si musíme dať pozor, že na to, aby sme po zožatí vynulovali nejaké políčko, nestačí nastaviť jeho hodnotu na nulu – musí mať hodnotu mínus celkového množstva v stĺpci, aby spolu s ním dalo súčet nula.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int S, V, Q; cin >> S >> V >> Q;
if (S > 1){ // Použijeme triviálny algoritmus, ktorý je dosť rýchly pre prvú sadu
// Vytvoríme si vynulované 2D pole (s rozmermi väčšími o 1, aby sme nemuseli riešiť indexovanie od 0)
vector<vector<ll>> squares(S + 1, vector<ll>(V + 1));
for (int q=0; q < Q; q++){
char type; cin >> type;
ll a, b; cin >> a >> b;
if (type == '?'){
cout << squares[a][b] << endl; // Proste odpovieme aktuálne zapamätanú hodnotu...
squares[a][b] = 0; // ...a vynulujeme ju
}
else if (type == '-') for (int i = 1; i < S + 1; i++) squares[i][a] += b; // Pridáme na všetky políčka v riadku
else for (int j = 1; j < V + 1; j++) squares[a][j] += b; // Pridáme na všetky políčka v stĺpci
}
} else { // Vyriešime prípad s jedným stĺpcom efektívnejšie
ll common = 0; // Koľko napršalo na celý stĺpec, teda všetky políčka
vector<ll> line(V + 1); // Koľko napršalo na každý riadok (políčko) zvlášť, mínus koľko sme z neho už zožali
for (int q=0; q < Q; q++){
char type; cin >> type;
ll a, b; cin >> a >> b;
if (type == '?'){
cout << line[b] + common << endl; // Koľko pršalo v stĺpci a koľko pršalo a zožali sme v riadku
line[b] = - common; // V riadku bude teraz záporná hodnota, aby sa vynulovala s hodnotu v stĺpci
}
else if (type == '-') line[a] += b; // Prší v riadku, teda na jednom políčku
else common += b; // Prší v stĺpci, teda všade
}
}
}
Táto sada nám sľubuje, že nikdy nebudeme žať viackrát v jednom riadku alebo stĺpci. To vlastne znamená, že vôbec nemusíme uvažovať o vynulovávaní políčok, pretože sa nikdy nepozrieme na rovnaké políčko viackrát.
Stačí nám teda pamätať si množstvo zrážok pre každý celý stĺpec a pre každý celý riadok. Keď chceme zistiť, koľko pšenice Bohdan zožne, proste tieto dve čísla sčítame. Namiesto tabuľky nám teda stačia dve polia s $S$ a $V$ číslami a všetky operácie sú konštantne rýchle.
#!/usr/bin/env python3
def main():
S, V, Q = map(int, input().split())
# Pre každý riadok a stĺpec si pamätáme množstvo zrážok
rows = [0 for _ in range(V + 1)]
cols = [0 for _ in range(S + 1)]
for _ in range(Q):
type, a, b = input().split()
a, b = int(a), int(b)
if type == '?':
print(cols[a] + rows[b], flush=True)
# Žneme toľko, koľko na políčku narástlo od začiatku
# Nemusíme riešiť, koľko sme zožali doteraz, pretože sa už nikdy nebudeme pýtať na to isté políčko
elif type == '-': rows[a] += b # Prší v riadku
else: cols[a] += b # Prší v stĺpci
main()
Skúsme túto jednoduchú myšlienku upraviť tak, aby sme vyriešili aj poslednú sadu bez obmedzení:
Tak ako v riešení tretej sady, aj tu si budeme pamätať pre každý riadok a stĺpec, koľko zrážok v ňom zapršalo. Musíme však podporovať aj vynulovávanie políčok. Budeme si teda pre každé políčko pamätať nie to, koľko naň napršalo, ale koľko sme z neho zožali. Vďaka tomu, že žatie vždy mení iba jedno políčko, nebudeme musieť upravovať viac hodnôt naraz. Na zistenie hodnoty konkrétneho políčka nám stačí sčítať hodnoty riadka a stĺpca a odčítať už zožaté množstvo pre dané políčko. Vďaka tomu bude aj tretia operácia konštantne rýchla.
Infromáciu o množstve zožatej úrody si môžeme pamätať napríklad v 2D poli, podobne ako pri riešení prvej sady. Ak chceme pamäťovo efektívnejšie riešenie, môžeme použiť slovník, kde kľúče budú dvojice súradníc. Časovú zložitosť práce so slovníkom nie je jednoduché presne stanoviť (keďže používa hashovanie), ale pre jednoduchosť môžeme predpokladať, že je pre jednotlivé operácie konštantná.
Dostaneme teda riešenie s časovou aj pamäťovou zložitosťou $O(S + V + Q)$ ($S$ a $V$ času zaberie len vyrobiť polia pre riadky a stĺpce, $Q$ je počet otázok, teda aj najväčší možný počet zožatých políčok, ktoré si uložíme do slovníka).
#!/usr/bin/env python3
def main():
S, V, Q = map(int, input().split())
# Pre každý riadok a stĺpec si pamätáme množstvo zrážok
rows = [0 for _ in range(V + 1)]
cols = [0 for _ in range(S + 1)]
# Pre každé zožaté políčko (x, y) si pamätáme, koľko pšenice sme z neho už zožali
removed = dict()
for _ in range(Q):
type, a, b = input().split()
a, b = int(a), int(b)
if type == '?':
# Žneme toľko, koľko na políčku narástlo od začiatku, mínus koľko sme doteraz z neho zožali
print(cols[a] + rows[b] - removed.get((a, b), 0), flush=True)
# Aktualizujeme doteraz zožaté množstvo
removed[(a, b)] = cols[a] + rows[b]
elif type == '-': rows[a] += b # Prší v riadku
else: cols[a] += b # Prší v stĺpci
main()
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