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

Mirko je upravo nabavio najnoviju PC igru: Simulator sela 2013.

Prilikom instalacije shvatio je da na svom tvrdom disku nema slobodnih M megabajta koji su potrebni za instalaciju, pa sada ubrzano pokušava osloboditi prostor kako bi što prije započeo s igrom.

Mirkov tvrdi disk organiziran je u D direktorija označenih jedinstvenim prirodnim brojevima od 1 do D te F datoteka označenih jedinstvenim prirodnim brojevima od D+1 do D+F.

Za svaki direktorij i zadana je oznaka njegovog roditelja Ri (direktorija u kojem se nalazi) te vrijeme potrebno za brisanje Bi.

Za svaku datoteku zadana je oznaka njenog roditelja Ri (direktorija u kojem se nalazi), vrijeme potrebno za brisanje Bi te veličina u megabajtima Vi.

Direktorij s oznakom 1 je vršni direktorij i nema roditelja, što označavamo s R1 = 0.

Mirko može u svakom koraku obrisati jednu datoteku ili jedan direktorij.

Ako Mirko briše datoteku i, nakon Bi vremena će ona nestati te će biti oslobođeno Vi megabajta te tada Mirko opet može brisati novu datoteku ili direktorij.

Za brisanje direktorija i potrebno je Bi vremena, a kada je brisanje završilo, nestaje taj direktorij zajedno sa svim direktorijima i datotekama koji se direktno ili indirektno u njemu nalaze te je broj oslobođenih megabajta prostora jednak sumi veličina svih u tom koraku obrisanih datoteka.

Naravno, ako se neka datoteka ili direktorij obrišu, oni nestaju s tvrdog diska i nije ih moguće obrisati ponovo.

Napišite program koji određuje najmanje moguće vrijeme brisanja određenih direktorija i datoteka tako da se njihovim brisanjem oslobodi barem M megabajta prostora na tvrdom disku.

Test podaci će biti takvi da rješenje uvijek postoji, odnosno zbroj veličina svih datoteka će biti veći ili jednak od M.

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

10 1 2
0 6
1 2 5
1 3 5

Izlaz

5

Ulaz

10 1 3
0 6
1 3 5
1 4 6
1 5 7

Izlaz

6

Ulaz

10 2 1
0 8
1 9
1 7 10

Izlaz

7