Državna razina / Primjena algoritama OŠ 2022. / Osnovna škola (7. razred) - 1. zadatak

Na brzoj cesti Primošten-Vodice u smjeru Vodica u koloni vozi N automobila. Svaki automobil je jedinstveno označen nekim prirodnim brojem od 1 do N. Nadzorne kamere bilježe koji je poredak automobila u svakom trenutku. Snimka nadzorne kamere sastoji se od niza slika iz kojih se lako iščita poredak automobila. Poznati haker Mirko ne voli brzu vožnju, a još manje voli pretjecanja. Najmanje voli bezobraznike. Neki vozač je bezobraznik ako postoji trenutak za koji je do tog trenutka razlika brojeva koliko puta je on pretjecao i koliko puta je bio pretjecan veća od 5. Mirko je uspio doći u posjed snimki nadzornih kamera te želi među vozačima prepoznati one koji su sigurno bezobraznici. Nažalost, unatoč hakerskim vještinama, brojanje mu baš i ne ide pa tebe moli za pomoć

Ulazni podaci

U prvom je retku prirodan broj N (2 ≤ N ≤ 100), broj iz teksta zadatka i prirodan broj K (2 ≤ K ≤ 100), broj slika od kojih se sastoji snimka nadzorne kamere. U sljedećih K redaka nalaze se nizovi od N različitih prirodnih brojeva od 1 do N koji redom predstavljaju poredak automobila u trenucima koje je kamera zabilježila. Poredci su dani redom kojim su bili zabilježeni. Prvi broj u redu predstavlja oznaku prvog automobila u koloni

Izlazni podaci

Ispiši riječ od N slova. Ako je vozač automobila s oznakom i sigurno bezobraznik i-to slovo mora biti 'B', a inače 'N'

Bodovanje

U testnim primjerima ukupno vrijednima 10 bodova vrijedit će K=2

Primjer zadatka

Ulaz

10 2
8 6 2 10 9 3 7 1 5 4
1 8 9 6 5 7 3 10 2 4

Izlaz

BNNNNNNNNN

Ulaz

11 3
7 1 2 8 6 11 3 5 9 4 10
1 11 10 3 7 5 4 2 9 6 8
5 6 2 10 1 11 9 4 7 8 3

Izlaz

NNNNBNNNNBN

Ulaz

3 2
2 3 1
1 2 3

Izlaz

NNN

Opis prvog probnog primjera:

U koloni je deset automobila, a dva su trenutka zabilježena. Vozač s znakom 1 je pretekao vozače s oznakama 7, 3, 9, 10, 2, 6, 8, dakle ukupno sedam vozača, dok njega nije pretekao niti jedan vozač. Dakle, pretekao je 7 vozača više nego što je preteklo njega, a 7 je strogo veći od 5 pa je zbog toga bezobraznik.

Opis drugog probnog primjera:

U ovom primjeru su bezobraznici vozači s oznakama 5 i 10. Za vozača s oznakom 5 to možemo zaključiti tek kad vidimo sve tri slike. Naime, od trenutka kad je snimljena prva do trenutka kad je snimljena druga slika on je pretekao vozače s oznakama 6, 8 i 2 dok je njega pretekao vozač s oznakom 10. Od trenutka kad je snimljena druga slika do trenutka kad je snimljena treća pretekao je vozače s oznakama 7, 3, 10, 11 i 1, a njega nije pretekao nijedan vozač. Dakle, ukupno je pretekao 8 vozača, što je za 7 više nego što je preteklo njega, a 7 je strogo veće od 5 pa je to dovoljno da ga haker Mirko proglasi bezobraznikom.