Paramecij

Osnovne informacije

Omejitve
  • Čas: 2,0 s
  • Spomin: 128 MB
Avtor:
  • Jan Berčič
  • UPM 2013

Pošlji rešitev



Tvoji rezultati.
Nisi poslal še nobene rešitve.
Več »

Prehranjevanje enoceličarjev je sila zanimivo področje modernega rač… biologije. Če se s tem ne strinjaš, tega nikar ne omenjaj biologu Čestimiru, ki se je ravno prejšnji mesec intenzivno poglabljal v endocitozo pri paramecijih in amebah.

Z mikroskopiranjem se je ukvarjal toliko časa, da se mu je na koncu že tako bledlo, da ni bil več sposoben ločiti med enimi in drugimi enoceličarji. Njegovo zadnje upanje je podjetje Uglašeni in Prebrisani Mikrokontrolerji (UPM), katerega uslužbenec si – hočeš nočeš – tudi ti. Vodja oddelka je že prepričal direktorja, da je absolutno potrebno izdelati povsem novo linijo luksuznih kontrolnih sistemov za digitalne mikroskope, na tebe pa je zvalil programiranje firmware-a.

Po nekaj urah pogovarjanja z zmedenim Čestimirom je dežurni matematik uspel ugotoviti le, da je vizualna razlika med paramecijem in amebo zgolj konveksnost – paramecij je ves čas svojega življenja konveksen, ameba pa ne nujno. Ker že vnaprej veš, da vodja oddelka ne bo pristal na nič drugega kot le najcenejše CCD senzorje, si nalogo poenostavi takole: celica C je konveksna, če in samo če

\forall (x_1,y_1),(x_2,y_2)\in C: ( (x_1=x_2 \land y_1\not=y_2) \lor (x_1\not=x_2 \land y_1=y_2) ) \Rightarrow ([x_1, x_2]\times[y_1, y_2] \subseteq C)

In še pojasnilo za navadne smrtnike: Za vsako navpično ali vodoravno daljico s krajišči v celici C so v celici C tudi vse točke na tej daljici; predpostavljamo diskreten koordinatni sistem).

Naloga

Tvoj firmware naj za dano sliko s senzorja poskuša ugotoviti, katerega enoceličarja je nič hudega sluteči uporabnik postavil pod lečo mikroskopa.

Vhodni podatki

V prvi vrstici sta naravni števili W (širina slike v pikslih) in H (višina slike v pikslih), naslednjih H vrstic pa predstavlja sliko, ki jo tvoj firmware prebere s senzorja. V vsaki vrstici je W znakov: vsak znak je bodisi '.' (prazen piksel) bodisi '#' (del celice).

Omejitve vhodnih podatkov

  • 1 \leq W, H \leq 2500

Čestimir kljub duševnim stiskam ni slep, zato lahko privzameš, da je v vhodnih podatkih vedno vsaj en '#'.

Izhodni podatki

Firmware naj na zaslonček na mikroskopu izpiše 'paramecij?', če je celica konveksna, oz. 'AMEBA!', če celica ni konveksna.

Primeri

Vhod

7 5
.......
.#####.
.#####.
.###.#.
.......

Izhod

AMEBA!

Vhod

7 5
.......
....##.
.#####.
.#####.
.......

Izhod

paramecij?
Tip: Log in to
  • submit and test your solution
  • post or read questions and answers about this task