Zadanie

Písal sa koniec roka 2019, keď si Korporácia Snímkovacích Podvodníkov vysúťažila tender na letecké osnímkovanie Egypta a následné počítačové spracovanie snímkov. “Však čo, letecké snímkovanie zvládneme ľavou zadnou, a na počítačové spracovanie snímok nám sem dva krát do roka chodí približne \(36\) stážistov. Niekto z nich to určite naprogramuje”, hovoril si Krtko, hlavný Snímkovací Podvodník. Avšak, stalo sa to, čo nikto nečakal. Prišla pandémia, a žiadne stáže sa nekonali. Korporácia na tento tender už takmer zabudla, až včera prišiel mail o tom, že deadline na dodanie snímkov a dát sa blíži. “Čo teraz? Snímky máme, ale treba ich vyhodnotiť. Peniaze čo sme za tender dostali už nemáme, minuli sme ich na kofolu v akcii 1”, uvažoval Krtko. “Musíme si nájsť niekoho, kto to urobí zadarmo.”, rozhodol sa Krtko a začal čítať malé písmenká na zmluvách pracovníkov KSP, a hľadať takých, ktorí to podľa zmluvy musia urobiť zadarmo.

A tak si Krtko niekoho našiel. Vás. Napíšte program, ktorý z každého snímku zistí aká vysoká pyramída je na ňom. Ale poponáhľajte sa, lebo podľa malých písmenok na zmluve Vám Krtko môže dať preplatiť pokutu z omeškania.

Úloha

Na vstupe dostanete leteckú snímku pyramídy zjednodušenú do textu. Vypíšte koľko poschodí má pyramída, ktorá sa na fotke nachádza. Každá pyramída sa skladá z niekoľkých obdĺžnikových poschodí. Každé poschodie okrem spodného stojí celé na nejakom poschodí, žiadna jeho časť “nepretŕča”. Každé poschodie je zo všetkých \(4\) strán aspoň o \(1\) menšie ako poschodie pod ním

Formát vstupu

Na prvom riadku vstupu sa nachádza číslo \(n\), počet riadkov, ktorý má text reprezentujúci fotku. Nasleduje \(n, 1 \leq n \leq 50\) rovnako dlhých riadkov.

Každý riadok má najviac \(50\) znakov a skladá sa len zo znakov ., ktoré označujú piesok, znakov |, ktoré reprezentujú ľavú alebo pravú stranu pyramídy na fotke, a znakov -, ktoré označujú vrchnú alebo spodnú stranu pyramídy. Každé poschodie má tvar obdĺžnika. V rohoch pyramídy sa nachádza znak ., teda piesok.

Formát výstupu

Vypíšte jediné číslo, počet poschodí, ktoré má pyramída na fotke. Nazabudnite za ním vypísať znak konca riadku. Je zaručené, že sa na každej fotke nachádza pyramída s aspoň jedným poschodím.

Príklad

Input:

6
......
..--..
.|..|.
.|..|.
..--..
......

Output:

1

Táto pyramída má len jedno poschodie.

Input:

12
.............
.............
..--------...
.|........|..
.|.-----..|..
.||.--..|.|..
.|||..|.|.|..
.|||..|.|.|..
.||.--..|.|..
.|.-----..|..
..--------...
.............

Output:

3

Táto pyramída má \(3\) poschodia.

  1. Viete koľko litrov kofoly sa zmestí do bežného nákupného košíka? Približne 120. Ak chcete vedieť ako sme na na to prišli, spýtajte sa Sabinky, Krtka alebo Marcela :) ↩︎

Snažíme sa spočítať, koľko poschodí pyramídy sa na vstupe nachádza. Vieme, že každé poschodie je z každej strany ohraničené stenou (na ľavej a pravej strane poschodia je znak | a znak - na vrchnej a spodnej). Asi najjednoduchší spôsob, ako zistiť počet poschodí je nájsť taký riadok vstupu, kde je najväčší počet bočných strán poschodí (keďže každé poschodie má práve dve bočné steny). Rovnako dobre by to fungovalo aj pre každý stĺpec vstupu, ale príjemnejšie sa to zisťuje pre riadok. Počet výskytov nejakého znaku v reťazci môžeme zistiť napríklad tak, že prechádzame riadok vstupu znak po znaku a vždy keď nájdeme ten znak, tak si zväčšíme nejaké počítadlo.

Iný spôsob je využiť funkciu programovacieho jazyka, ktorá počíta počet výskytov nejakého znaku.1

Toto môžeme urobiť pre každý riadok. Potom stačí nájsť, pre ktorý z nich je tento počet najväčší. Počet poschodí pyramídy ale samozrejme nie je počet stien pyramídy, ale len polovica toho počtu keďže každé poschodie sme započítali \(2\) krát (raz jeho začiatok a raz jeho koniec).

Takže, zrekapitulujme si riešenie: postupne načítavame riadky, a pre každý riadok spočítame, koľko bočných stien poschodia sa na ňom nachádza. Na konci vypíšeme polovicu tohoto maximálneho počtu.

Takéto riešenie má časovú zložitosť \(O(n^2)\), keďže pre každý z \(n\) riadkov prejdeme celý od začiatku po koniec. Pamäťová zložitosť je \(O(n)\), keďže okrem niekoľko málo premenných si nám stačí pamätať iba aktuálny riadok vstupu.

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

int main(){
    int n=0, max_stien=0;

    cin>>n;

    string riadok;

    for(int i=0; i<n; i++){
        cin>>riadok;
        max_stien=max(max_stien, (int)count(riadok.begin(), riadok.end(), '|'));
    }

    cout<<max_stien/2<<endl;

    return 0;
}
#!/usr/bin/env python3
n = int(input())
riadok = ''
max_stien = 0

for i in range(n):
    riadok = input()
    max_stien = max(max_stien, riadok.count('|'))

print(max_stien//2)

  1. Vo väčšine programovacích jazykov sa zvykne volať count, alebo nejako podobne.↩︎

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