Državno natjecanje 2014. / Osnovna škola (6. razred) - 3. zadatak

U zoološkome vrtu postoji N kaveza u kojima držimo N zmija: svaku zmiju u svome kavezu.

Iz eksperimentalnih razloga, za mjesec dana promijenit ćemo raspored zmija po kavezima, ali tako da i dalje bude jedna zmija u svakom kavezu.

Zadano je u koji ćemo kavez premjestiti koju zmiju.

Svaki kavez osvijetljen je posebnom svjetlošću koja može biti tipa A, tipa B ili tipa C.

Tvoj je zadatak kavezima dodijeliti osvjetljenja A, B, C tako da:

1. svaka zmija za mjesec dana promijeni osvjetljenje, tj. ode u kavez osvijetljen različito od kaveza u kojemu se trenutno nalazi;
2. osvjetljenja budu ravnopravno zastupljena, tj. broj kaveza A, broj kaveza B i broj kaveza C međusobno se razlikuju najviše za jedan.

Ako je zadovoljen samo uvjet 1, dobivaš polovinu bodova za taj test podatak.

ULAZNI PODATCI

U prvome retku nalazi se prirodan broj N (2 ≤ N ≤ 300 000), broj zmija i kaveza. Kavezi su označeni brojevima od 1 do N.

U sljedećih N redaka nalazi se po jedan prirodan broj. Značenje je tih brojeva sljedeće: ako se u K-tom od tih redaka nalazi broj L, zmija iz kaveza K prijeći će u kavez L (vrijedit će K ≠ L). Dvije zmije neće prijeći u isti kavez.

IZLAZNI PODATCI

Ispiši niz sastavljen od znakova A, B i C, bez razmaka, takav da K-ti znak u tome nizu označava osvjetljenje dodijeljeno kavezu K.

Ako postoji više rješenja, ispiši bilo koje.

PRIMJERI TEST PODATAKA

Ulaz

2
2
1

Izlaz

AB

Ulaz

3
3
1
2

Izlaz

ABC

Ulaz

4
4
3
2
1

Izlaz

ACBC