Županijsko NATJECANJE 2015 / Srednja škola, II. podskupina (3. i 4. razred) - 3. zadatak

Mirko i Slavko su na satu logike dobili neistinit logički izraz pa ga pokušavaju 'popraviti' da bude istinit.

Logički izraz je niz znakova koji se sastoji od nula i jedinica, zagrada te logičkih operacija '&', '|' i '^' (redom logičko I, ILI, ekskluzivno ILI).

Vrijednost logičkog izraza je broj 0 ili 1.

Preciznije, ispravne logičke izraze te njihove vrijednosti rekurzivno definiramo na sljedeći način:

• '0' je logički izraz, njegova vrijednost je 0
• '1' je logički izraz, njegova vrijednost je 1
• Ako su a1, a2, …, an dva ili više logičkih izraza onda je:
  • '(a1|a2|...|an)' logički izraz, njegova vrijednost je 1 ako je vrijednost barem jednog od izraza ai 1, a inače je 0.
  • '(a1&a2&...&an)' logički izraz, njegova vrijednost je 0 ako je vrijednost barem jednog od izraza ai 0, a inače je 1.
  • '(a1^a2^...^an)' logički izraz, njegova vrijednost je 0 ako paran broj izraza ai ima vrijednost 1, a inače je 1.

Tako su, na primjer, '1', '(0|1|0)' i '(1&(1^1))' logički izrazi čije su vrijednosti redom 1, 1 i 0, dok '0|1', '(0|1&0)', '((1&1))' i '(0&(1))' nisu logički izrazi.

Kada Mirko i Slavko dobiju izraz, oni pokušavaju markerom i olovkom neke nule pretvoriti u jedinice i neke jedinice pretvoriti u nule tako da na kraju dobiju istinit logički izraz.

Točnije svaku znamenku u izrazu oni mogu promijeniti u suprotnu znamenku, ali za to moraju platiti određenu cijenu - za svaku znamenku u izrazu unaprijed je poznato kolika je ta cijena.

Napišite program koji će odrediti kolika je najmanja moguća ukupna cijena koju je potrebno platiti da promjenom odgovarajućih znamenki izraz postane istinit tj. da njegova vrijednost bude 1.

Ulazni​ podaci

U prvom redu nalazi niz od najmanje jednog i najviše 1000 znakova - logički izraz prema pravilima iz teksta zadatka. U izrazu će se pojavljivati samo znamenke '0' i '1', zagrade '(' i ')' te znakovi '|' (ASCII 124), '&' (ASCII 38) i '^' (ASCII 94).

U drugom redu nalazi se N prirodnih brojeva manjih ili jednakih od 1000, gdje je N broj znamenki u logičkom izrazu iz prvog reda. K-ti broj predstavlja cijenu promjene K-te znamenke s lijeva u logičkom izrazu.

Izlazni podaci

U prvi red potrebno je ispisati jedan cijeli broj - najmanju ukupnu cijenu skupa znamenki čijom promjenom izraz postaje istinit, tj. dobiva vrijednost 1.

Primjeri test​ podataka

Ulaz

(0&1)
1 2

Izlaz

1

Ulaz

((0&0)|(0&0&0&1))
3 3 2 1 2 7

Izlaz

5

Objašnjenje

Pojašnjenje drugog primjera: optimalno je promijeniti treću, četvrtu i petu znamenku. Sve tri su nule i promjenom postaju jedinice, ukupna cijena je 2 + 1 + 2 = 5.

Ulaz

(((1|0)|1)^(1|1|1)^((1^1)&0&0))
1 1 1 1 1 1 1 1 1 1

Izlaz

2

Objašnjenje

Pojašnjenje trećeg primjera: optimalno je promijeniti prvu (iz 1 u 0) i treću (iz 1 u 0) znamenku. Ukupna

cijena je 1 + 1 = 2.