Zadanie
Ešte pred pár mesiacmi všetky firmy menili svoje pravidlá narábania s osobnými údajmi. Preto všetci chceli, aby obyčajní používatelia ako Denis tieto nové pravidlá odsúhlasili. V tom čase to Denis vôbec neriešil. Teraz sa však rozhodol, že už nezaklikne ani jedno políčko. Veď tým nebude zbytočne strácať čas! A preto vymyslel geniálny ťah. Vytvorí program, čo to zaňho odklikne. No uvedomil si dôležitý fakt. Keď to dá ako úlohu do KSP nemusí to ani len programovať!
Úloha
Napíšte Denisovi program, ktorý v texte nájde políčko, ktoré vyzerá presne takto:
+-+
| |
+-+a zakreslite doň veľké písmeno X.
Formát vstupu
Na začiatku vstupu sa nachádza číslo \(n\) – \(3 \leq n \leq 1000\) – počet riadkov na vstupe. Nasleduje \(n\) riadkov textu. Na každom riadku sa nachádza \(m\) znakov – \(1 \leq m \leq 100\). Medzi nimi sa bude nachádzať práve jedno políčko na zaškrtnutie. Znaky, ktoré sa v texte budú nachádzať, budú znaky z ASCII tabuľky. Konkrétne, pre každý znak \(c\) platí, že je z rozsahu \(32 \leq c \leq 126\) alebo je znakom nového riadku (\(10\)).
Formát výstupu
Na výstup vypíšte rovnaký text, aký ste dostali na vstupe (bez prvého riadku, v ktorom sa nachádza \(n\)), s tým rozdielom, že políčko bude zaškrtnuté.
Príklady
Input:
15
V zmysle zakona Slovenskej republiky
c. 18/2018 Z. z. o ochrane osobnych
udajov a o zmene a doplneni niektorych
zakonov, ktory najma v $19-30 upravuje
prava dotknutej osoby v oblasti
spracovania osobnych udajov, vyjadrujem
suhlas so spracovanim poskytnutych osobnych
udajov.
+-+
| |
+-+
Uvedeny suhlas sa tyka aj poskytnutia
uvedenych udajov tretim stranam za ucelom
mierenych reklam na iste druhy pracich
prostriedkov.Output:
V zmysle zakona Slovenskej republiky
c. 18/2018 Z. z. o ochrane osobnych
udajov a o zmene a doplneni niektorych
zakonov, ktory najma v $19-30 upravuje
prava dotknutej osoby v oblasti
spracovania osobnych udajov, vyjadrujem
suhlas so spracovanim poskytnutych osobnych
udajov.
+-+
|X|
+-+
Uvedeny suhlas sa tyka aj poskytnutia
uvedenych udajov tretim stranam za ucelom
mierenych reklam na iste druhy pracich
prostriedkov.Input:
13
Tymto potvrdzujem, ze nie som robot
ani program na zaklikavanie policok
+-+ +_+
| | | |
+_+ +-+
a navyse suhlasim so vsetkymi podmienkami
ktore som si precital v prilozenych
47 stranach legalneho balastu
click +-+ here
to | | accept
terms +-+ & conditions
Output:
Tymto potvrdzujem, ze nie som robot
ani program na zaklikavanie policok
+-+ +_+
| | | |
+_+ +-+
a navyse suhlasim so vsetkymi podmienkami
ktore som si precital v prilozenych
47 stranach legalneho balastu
click +-+ here
to |X| accept
terms +-+ & conditions
Riešenie tejto úlohy rozdelíme na dve časti.
Načítavanie vstupu
Prvou komplikovanejšou úlohou je správne načítať vstup. Ak používate C++, pravdepodobne na načítavanie vstupu používate cin. Ten však načíta iba časť textu po najbližší tzv. ‘whitespace’ znak, teda medzeru. Preto sa na načítanie vstupu doporučuje použiť príkaz getline(cin, string). Tento načíta všetky znaky až po prvý znak nového riadku ('\n'). Ešte si treba dať pozor, že keď zo vstupu načítame počet riadkov \(n\) ako číslo, tak za ním ostane znak konca riadku. Tento znak príkaz getline zachytí, a teda načíta prázdny string. Treba teda getline zavolať ešte raz po načítaní \(n\).
Ak používate napríklad Python, tak príkaz input(), ktorý bežne používate na načítanie vstupu, načíta celý riadok, takže tu problém nie je. Rovnako by nemal byť problém v ostatných jazykoch, ktoré testovač podporuje.
Hľadanie políčka
Teraz, keď máme text v pamäti, môžeme začať hľadať správne políčko. Hľadanie políčka môžeme vždy začínať od jeho ľavého horného rohu, stačí skontrolovať všetkých 9 znakov, či sa zhodujú – buď manúalne overíme každý znak, alebo si vytvoríme vlastnú kópiu políčka, ktoré hľadáme, a overíme či sa všetky znaky zhodujú v štvorčeku \(3x3\) pomocou dvoch cyklov.
Treba si pritom dávať pozor na to, aby sme neskúsili pozrieť na neexistujúci index niektorého reťazca, keďže susedné riadky môžu byť rôzne dlhé.
Čo všetko si potrebujeme pamätať?
Keď sa zamyslíme nad tým ako hľadáme políčka, uvedomíme si, že keď skontrolujeme trojicu riadkov, údaje z prvého z nich už nikdy nebudeme potrebovať. Preto nám stačí pamätať si iba tri riadky, v ktorých aktuálne hľadáme políčko, teda pamäťová zložitosť tohto riešenia je \(\text{O}\left(m\right)\), kde \(m\) označuje počet znakov v jednom riadku.
Zhrnutie
Postupne načítame riadky. Pre každý načítaný znak skontrolujeme či sa “pod ním” nenachádza políčko. Ak sa nachádza políčko zaškrtneme, inak hľadáme ďalej. Takýmto postupom spravíme pre každý znak iba konštantný počet operácií. Teda časová zložitosť je lineárna od veľkosti vstupu \(\text{O}\left(n \cdot m\right)\)
#include <iostream>
#include <string>
using namespace std;
string empty_line;
string line[3];
string look_at[] = {"+-+", "| |", "+-+"};
bool success = false, failure = false;
int n;
//funkcia kontrolujuca ci sa na policku i vobec moze nachadzat policko
bool make_sense(int i){
if(i+2 < line[0].size() && i+2 < line[1].size() && i+2 < line[2].size()) return true;
return false;
}
int main(){
//najprv nacitame pocet riadkov a odstranime medzeru co ostala za tymto cislom
cin >> n;
getline(cin, empty_line);
//nacitame prve dva riadky
getline(cin, line[0]);
getline(cin, line[1]);
//rovno vypyseme prvy riadok
cout << line[0] << '\n';
for (int i = 0; i < n-2; i++) {
//nacitame postupne vsetky riadky
getline(cin, line[2]);
//skontrolujeme ci sa na i-tej pozicii na riadku nenachadza policko
for (int i = 0; make_sense(i) && !success; i++) {
failure = false;
for (int j = 0; j < 3 && !failure; j++) {
for (int k = 0; k < 3 && !failure; k++) {
if(line[j][i+k] != look_at[j][k]) {
failure = true;
}
}
}
//ak najdeme policko zaskrtneme ho
if(!failure) {
line[1][i+1] = 'X';
success = true;
}
}
//vypiseme riadok v ktorom uz urcite nenastane zmena
cout << line[1] << '\n';
//presunieme si este relevantne riadky
swap(line[0], line[1]);
swap(line[1], line[2]);
}
//vypiseme posledny riadok
cout << line[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ť.