ŠKOLSKO NATJECANJE 2013. / Srednja škola, I. podskupina (1. i 2. razred) - 1. zadatak

Slavko voli zemljopis, a Mirku se tijekom zajedničkog trčanja pohvalio kako je zapamtio broj stanovnika svakog naselja svih zemalja svijeta. Mirko je na to predložio izazov: odabrati će jednu zemlju, a ako Slavko uspije na papiru ispisati broj stanovnika svih naselja te zemlje, Mirko će ga nagraditi velikom Mikado čokoladom od riže. Mirko ne zna zemljopis, pa teško može provjeriti jesu li svi Slavkovi brojevi točni, ali Mirko voli matematiku! Nedavno ga je oduševio Benfordov zakon, koji u svom pojednostavljenom obliku kaže:

„Ako imamo puno brojeva koji na neki način dolaze iz prirode i društva (na primjer,
broj stanovnika svakog naselja jedne zemlje) te ako pogledamo prve znamenke svih
tih brojeva, među njima će najviše biti jedinica, zatim dvojki, a zatim trojki i tako
dalje, dok će najmanje brojeva počinjati sa znamenkom 9.“

Mirko sumnja da će ga Slavko pokušati prevariti pa mu treba vaša pomoć. Napišite program koji će provjeriti zadovoljava li niz od N zadanih brojeva stanovnika ovaj zakon. Točnije, vaš program treba odrediti vrijedi li C1 ≥ C2 ≥ C3 ≥ … ≥ C9, gdje je C1 broj zadanih brojeva koji počinju znamenkom 1, C2 broj zadanih brojeva koji počinju znamenkom 2 i tako dalje, te, u slučaju da to ne vrijedi, naći najmanje znamenke K i K+1 koje narušavaju ovo svojstvo, te odgovarajuće brojeve CK i CK+1.

Ulazni podaci

Prvi red ulaza sadrži prirodni broj N (1 ≤ N ≤ 1000) - broj naselja odabrane zemlje. Svaki od sljedećih N redova sadrži jedan prirodni broj manji od 100,000,000 - broj stanovnika jednog naselja odabrane zemlje.

Izlazni podaci

Ako niz zadovoljava svojstvo opisano u zadatku tada prvi i jedini red ulaza treba sadržavati broj 0. U suprotnom, potrebno je u prvi red ispisati tri prirodna broja K, CK i CK+1 gdje je K najmanja znamenka takva da je CK manje od CK+1.

Primjeri test podataka

Ulaz

6
456
1110
1053
303001
22
2005

Izlaz

0

Ulaz

6
456
1110
1053
303001
3000
2005

Izlaz

2 1 2