3. Zaujímavé kŕmenie strašidelnej príšery (vzorové riešenie)

Zadanie

Kým ste prázdninovali, kúpali sa, plávali, KSPáci svedomito pracovali. Kolektívne spisovali príklady, ktorými sa po konci slnečných prázdnin potrápite. Samozrejme, príklady sa spravili počas prvých pár piatkov. Krátko potom prišla prázdnota.

“Kam sa počneme po spravení príkladov?” premýšľali.

“Pôjdeme sa kúpať? Prechádzať sa po kopcoch? Spoznávať krásy sveta? Programovať? Kŕmiť pestrofarebné papagáje poletujúce po parku?”

“Kdeže, kúpime si príšeru!” prehlásil Peter. Každý súhlasil.

Po kúpe príšery prišli prvé problémy. Príšeru potrebovali pravidelne kŕmiť. Samozrejme, potrebovali pre príšeru pekné priestory. Príšera potrebuje pohodlie. Posledný problém, ktorý súvisí s pohybom príšery, spôsobili KSPáci kŕmením.

Poznatky KSPákov súvisiace s prirodzeným prostredím príšer sú slabé. Skúšali kartónovú krabicu, plastové poháre, sklenenú karafu, sivú prútenú klietku, komoru skrytú pod kamenným stolom, plesnivú pivnicu, plechový kváder pokrytý strieborným plátnom, ktoré kedysi patrilo svetoznámemu kinu. Príšera pohrdla každým spomenutým priestorom. Správna potrava pre príšery? Príšerne podpriemerné poznatky prebývajú pod kučerami KSPáckych kotŕb. Sprvu sa KSPáci pokúšali kŕmiť príšeru kvasenou kyslou kapustou. Ktovie, prečo práve kyslú stravu skúsili KSPáci prvú. Pokus kŕmiť príšeru kapustou skončil katastrofou. Príšera sa priotrávila. Krátko potom stratila schopnosť korigovať smer svojho pohybu. Smutný príbeh. KSPáci potrebovali kompletne pozmeniť prístup. Snáď sa stav príšery polepší.

Po poradení sa s profesionálom posadili KSPáci svoju príšeru pod podlhovastú skrinku pokrývajúcu severnú stenu prastarej kúpeľne. Kopa prachu pod skrinkou poskytuje príšere príjemné pohodlie. Kúpeľňa sa prestala používať pred storočiami, preto se stala príbytkom poriadneho počtu pavúkov. Pavúky sú skvelým krmivom pre pažravú príšeru, pretože sú plné sviežich substancií. Krása. Sen pre pažravé príšery, ktoré sa snažia pribrať. Podlahu kúpeľne pokrýva \(k\) krát \(s\) kachličiek (\(s\) stĺpcov, každý s \(k\) kachličkami). Poniektoré kachličky sú prázdne, poniektoré sa pýšia pavúkom sediacim prostred kachličky.

Srstnaté končatiny príšery spôsobujú pavúkom strach. Keď sa príšera prvýkrát pozrie spod skrinky, poškrabká svojou krivou paprčou studenú kachličku, pavúky sa preľaknú. Každý pavúk sa pustí strečkovať smerom ku ktorejsi stene. Keď pribehnú ku kraju kúpeľne, schovajú sa pod podlahu. Preto príšera potrebuje pochytať pavúky počas svojej prvej prechádzky. Kvôli pokazenej koordinácii pohybov (spôsobenej priotrávením sa kyslou kapustou) stratila príšera schopnosť kráčať kľukato. Preto sa pohybuje po polpriamke kolmej so severnou stenou kúpeľne.

Príšera sa pohybuje súčasne s pavúkmi. Keď príšera spraví krok, pavúky spravia krok. Keď príšera prejde kachličku, pavúky prejdú kachličku.

Poznáte pozície pavúkov. Poznáte smer pohybu každého pavúka. Pre každý stĺpec kachličiek spočítajte počet pavúkov, ktoré príšera stretne, keď stĺpcom pôjde.

Úloha

Ako ste určite pochopili z predošlého textu, vedúci KSP si kúpili príšeru, ktorú ubytovali v starej opustenej kúpeľni. V tejto kúpeľni žijú pavúky a príšera by chcela nejaké z nich zjesť.

Kúpeľna obdĺžnikového tvaru je rozdelená na mriežku kachličiek rozmerov \(k\times s\). V kúpeľni je \(p\) pavúkov, každý sa nachádza uprostred niektorej kachličky. O každom pavúkovi viete jeho počiatočnú pozíciu a tiež smer jeho pohybu. Smer môže byť na sever, východ, západ alebo juh.

Príšera si vyberie nejaký zo stĺpcov a vykukne spod skrinky severne od prvej rady kachličiek. Potom sa bude pohybovať smerom na juh rovnako rýchlo ako pavúky. Kým sa dostane doprostred prvej kachličky, pavúky akurát prejdú vzdialenosť jednej kachličky. Vždy, keď stretne nejakého pavúka, zožerie ho a pokračuje ďalej v pohybe.

Pre každý stĺpec vypíšte, koľko pavúkov príšera zje, ak si vyberie daný stĺpec.

Formát vstupu

V prvom riadku vstupu sú tri čísla \(p\), \(k\) a \(s\) udávajúce počet pavúkov a rozmery kúpeľne.

Nasleduje \(p\) riadkov, na \(i\)-tom z nich sú dve čísla \(k_i\), \(s_i\) (\(1\leq k_i\leq k, 1\leq s_i\leq s\)) a písmeno. Pavúk sedí na začiatku v riadku \(k_i\) a stĺpci \(s_i\). Podľa toho, či je písmeno S, V, J alebo Z sa bude pavúk pohybovať na sever, východ, juh alebo západ. Smerom na juh stúpajú čísla riadkov a smerom na východ stúpajú čísla stĺpcov.

Pre jednotlivé vstupné sady platia nasledovné obmedzenia:

Číslo sady	1	2	3	4
Maximálne \(k\), \(s\), \(p\)	\(50\)	\(1\,000\)	\(100\,000\)	\(500\,000\)

Formát výstupu

Vypíšte jeden riadok, na ktorom bude \(s\) čísel oddelených medzerami. Za posledným číslom nevypisujte medzeru. \(i\)-te z týchto čísel má byť počet pavúkov, ktoré by príšera zjedla, keby sa vybrala \(i\)-tym stĺpcom.

Príklad

Input:

Output:

0 1 0 0 2

Každý pavúk môže stretnúť príšeru najviac v jednom stĺpci a to najviac raz. Vieme pomerne jednoducho spočítať, či pavúk vôbec dokáže stretnúť príšeru a ak áno, tak v ktorom stĺpci ju stretne.

Ak sa nám toto podarí zistiť, odpoveď na úlohu zistíme tak, že najprv vyrobíme pre každý stĺpec počítadlo (na začiatku s hodnotou 0) a následne cyklom prejdeme všetky pavúky. Pre každého pavúka vypočítame stĺpec, v ktorom pavúk stretne príšeru a ak taký stĺpec existuje, zvýšime si počítadlo daného stĺpca. Na konci len vypíšeme počítadlá pre každý stĺpec.

V programe budeme rozlišovať pavúky podľa toho, ktorým smerom sa hýbu. Pavúky, ktoré idú na juh (dolu) príšeru nestretnú nikdy, pretože sú vždy pred ňou. Pavúky, ktoré idú na sever (hore) stretnú príšeru v tom stĺpci, v ktorom sa nachádzajú.

Pavúky, ktoré idú na západ (vľavo), môžu stretnúť príšeru len vtedy, keď sa príšera ocitne v rovnakom riadku, pretože tieto pavúky idú stále po tom istom riadku. To, kedy to bude, vieme ľahko vypočítať: príšera sa do \(k\)-teho riadku dostane po \(k\) sekundách. Takže pavúk, ktorý ide na západ a začína na pozícii \((k_i, s_i)\) môže stretnúť príšeru iba po \(k_i\) sekundách od začiatku pohybu. A vtedy sa pavúk bude nachádzať v stĺpci \(s_i - k_i\) (alebo už bude schovaný pod podlahou, ak \(s_i - k_i < 1\)). Preto tento pavúk buď stretne príšeru v stĺpci \(s_i - k_i\), alebo ju nestretne vôbec (ak \(s_i - k_i < 1\)).

Podobne pavúky, ktoré idu na východ (doprava) stretnú príšeru v stĺpci \(s_i + k_i\) alebo vôbec, ak \(s_i + k_i > s\).

Časová zložitosť riešenia je \(O(p + s)\). Načítanie vstupu a výpočet pre každého pavúka zaberie \(O(p)\) času. Výpis výstupu \(O(s)\). Pamäťová zložitosť je \(O(s)\).

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define For(i, n) for(int i = 0; i<(n); ++i)

int S[500001];
int pocet,k,s,ki,si;
char c;

int main(){
    // Precitame pocet pavukov, riadkov a stlpcov
    cin >> pocet >> k >> s;
    For(i, pocet) {
        // Pre kazdeho pavuka nacitame jeho poziciu a smer
        cin >> ki >> si >> c;

        // Ak ide na juh, nestretne priseru, v ostatnych pripadoch spocitame,
        // kde ju stretne a zvysime pocitadlo daneho stlpca
        if (c == 'S') S[si]++;
        if (c == 'Z' && si-ki > 0) S[si-ki]++;
        if (c == 'V' && si+ki <= s) S[si+ki]++;
    }
    // Pre kazdy stlpec vypiseme pocitadlo. Pozor na medzeru za poslednym cislom.
    For(i, s) cout << S[i+1] << char((i==s-1)?'\n':' ');
}

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

3. Zaujímavé kŕmenie strašidelnej príšery vzorové riešenie