Županijska razina / Primjena algoritama OŠ 2020. / Osnovna škola (8. razred) - 2. zadatak

Sve više IT tvrtki odlučuje kupiti biljarski stol kako bi se programeri osjećali ugodno za vrijeme pauza na poslu.

Biljar je igra u kojoj igrači pokušavaju u što manje poteza pospremiti sve svoje kuglice u šest rupa.

Postoji 15 kuglica. Na svakoj od njih piše jedan prirodan broj između 1 i 15.

Za sedam kuglica kažemo da su “pune” (to su kuglice s brojevima od 1 do 7), za sedam da su “prazne” (to su kuglice s brojevima od 9 do 15) i za jednu da je “crna”, to je kuglica s brojem 8.

Međutim, programeri troše previše vremena na preslagivanje kuglica iz nekog trenutno zadanog rasporeda u neki od dva dozvoljena rasporeda u što je moguće manje poteza.

Na slici 1. prikazana su jedina dva dozvoljena rasporeda.

Kuglice u kojima je upisan znak “X” označavaju “pune” kuglice, crno obojena kuglica označava “crnu” kuglicu, a ostale su “prazne” kuglice

U jednom potezu oni mogu zamijeniti kuglice na bilo koje dvije pozicije. Pozicije su numerirane kao na slici 2.

Kako se ne bi morali mučiti s rješavanjem problema i na pauzama, zamolili su tebe da im napišeš program koji ispisuje poteze kojima mogu iz zadanog rasporeda dobiti neki od dozvoljenih rasporeda.

Ulazni podaci

U prvom je retku 15 prirodnih brojeva koji opisuju trenutni raspored kuglica.

Na i-tom mjestu nalazi se broj koji piše na kuglici koja se nalazi na poziciji i (slika 2.).

Svaka od 15 kuglica bit će na nekoj poziciji.

Izlazni podaci

U prvi redak ispiši broj poteza potreban da se kuglice poslože u neki od dozvoljenih rasporeda.

Zatim ispiši poteze, svaki u svoj redak, u obliku “A B” (bez navodnika) gdje su A i B prirodni brojevi manji ili jednaki 15 i A je različito od B.

Taj potez znači da zamjenjuješ kuglice na pozicijama A i B.

Primjer zadatka

Ulaz

15 7 1 12 8 11 6 10 3 4 14 5 13 9 2

Izlaz

1
14 15

Ulaz

5 9 11 2 6 1 15 14 13 12 4 3 8 10 7

Izlaz

2
5 13
12 8

Objašnjenje

Opis drugog probnog primjera: Na slikama su prikazani rasporedi kuglica na početku, nakon prve zamjene i nakon druge zamjene. Uoči da završni raspored odgovara desnom rasporedu sa slike 1.