DRŽAVNO NATJECANJE 2013. – Prvi dan natjecanja / Srednja škola, II. podskupina (3. i 4. razred) - 1. zadatak

Tomislav je ljubitelj barkodova, smislenih nizova uskih i širokih vertikalnih linija koje omogućavaju elektronskoj opremi zapisivanje i očitavanje kratkih informacija.

U posebnoj klasi barkodova kojom je Tomislav trenutno očaran, informacija je niz dekadskih znamenki, a svaka je znamenka zapisana s točno 5 uzastopnih linija koje mogu biti uske ili široke.

U nastavku ćemo uske linije označavati nulom, a široke jedinicom. Prikaz znamenki dan je u sljedećoj tablici:

Dakle, znamenki '3' odgovara kod '11000', znamenki '8' kod '10010' itd.

Kako bi bila moguća provjera ispravnosti zapisivanja i očitavanja barkodova, na kraj svakog niza znamenaka kojeg treba kodirati najprije dodaju se dvije zaštitne znamenke, C i K, koje se računaju na sljedeći način:

• C se računa tako da se krene od prve znamenke niza (gledano s lijeva) te se redom zbroje umnošci pozicije pojedine znamenke u nizu i njene vrijednosti (prva znamenka u nizu ima poziciju 1, druga 2, itd.). Zaštitna znamenka C je ostatak pri djeljenju gornje sume s 10. Tako, na primjer, za niz '345' vrijednost znamenke C će biti ostatak od 13+24+3*5 pri djeljenju s 10 što je jednako 6. Znamenka C se nakon računanja dodaje na kraj niza.

• K se računa tako da se krene od kraja niza nastalog u prethodnom koraku (dakle niz sadrži i netom izračunati znak C), s desna na lijevo, i zbroji vrijednost svake druge znamenke (bez množenja s pozicijama!). Zaštitna znamenka K je sada ostatak pri dijeljenju dobivene sume s 9 te nju također dodajemo na kraj niza (desno od zaštitne znamenke C).

Nakon izračuna zaštitnih znamenki, sve se znamenke u nizu zamjene pripadnim kodovima i takav niz nula i jedinica tvori barkod početnog niza.

Ukoliko nam je dan određeni barkod, njegovu ispravnost možemo provjeriti tako da ga pretvorimo u niz znamenki, odbacimo dvije zaštitne znamenke s desna (C i K), ponovo izračunamo njihove prave vrijednosti, a zatim provjerimo jesu li one jednake vrijednostima za C i K koje smo na početku odbacili.

Napišite program koji vrši opisanu provjeru zaštitnih znamenaka zadanog niza.

Zadani barkod (niz znamenaka '0' i '1') će uvijek biti duljine djeljive s 5 te će, kada se niz rastavi na grupe od po 5 binarnih znamenaka, svaka grupa odgovarati nekoj dekadskoj znamenki prema gornjoj tablici.

Ukoliko su obje zaštitne znamenke C i K ispravne, potrebno je ispisati niz dekadskih znamenki koji odgovara zadanom barkodu (uključujući i znamenke C i K).

U suprotnom je potrebno ispisati nazive zaštitnih znamenki koji ne odgovaraju zaštitnim znamenkama dobivenim provođenjem opisanih zaštitnih algoritama.

Ulazni podaci

U prvom retku ulaza nalazi se prirodni broj N (15 ≤ N ≤ 1000), broj binarnih znamenki koje čine barkod.

U drugom retku ulaza nalazi se niz od N znakova '0' (nula) i '1' (jedinica) – zadani barkod čije kontrolne znamenke treba provjeriti.

Izlazni podaci

Ukoliko je ulazni barkod ispravan, u prvi i jedini redak izlaza potrebno je ispisati znamenke predstavljene njime (uključujući zaštitne znamenke).

Inače, ako točno jedna od zaštitnih znamenki nije ispravna, u jedini redak izlaza potrebno je ispisati njezin naziv (veliko slovo 'C' ili 'K'), a ukoliko su kodovi za oba zaštitna znaka neispravni potrebno je ispisati velika slova 'CK'.

Primjeri test podataka

Ulaz

25
1100000101101000110010001

Izlaz

34561

Ulaz

25
1100000101101000000101100

Izlaz

CK