Za prirodan broj kažemo da je lep ukoliko je u njemu rastojanje između svake dve iste cifre bar 10. Rastojanje između dve cifre jednako je broju cifara između njih + 1 (recimo, u broju 12342, rastojanje između cifara '2' je 3).
Imamo početni broj od n cifara i želimo da od njega napravimo lep broj. U jednom potezu moguće je obrisati bilo koju cifru početnog broja i na njeno mesto upisati neku drugu cifru. Koliko je najmanje poteza potrebno da bi dobili lep broj?
Ulaz.
(Ulazni podaci se učitavaju sa standardnog ulaza) U prvom redu ulazne datoteke nalazi se jedan prirodan broj n koji predstavlja broj cifara početnog broja (1 ≤ n ≤ 106). U sledećem redu se nalazi početni broj. Između cifara ne postoji razmak i broj može imati vodeće nule.
Izlaz.
(Izlazni podaci se ispisuju na standardni izlaz) U prvom i jedinom redu izlazne datoteke ispisati najmanji broj poteza potrebnih da se od datog broja dobije lep broj.
Primer 1.
standardni ulaz | standardni izlaz | |
---|---|---|
8 00346731 |
2 |
Objašnjenje. Ukoliko obrišemo cifru 0 na drugoj poziciji i umesto nje napišemo cifru 2 i obrišemo cifru 3 na sedmoj poziciji i napišemo cifru 5, dobijamo lep broj 02346751. Moguće je dobiti i druge lepe brojeve ali ne u manjem broju poteza.
Comments