Župšanijsko natjecanje 2016. godine za 3. i 4. razred Srednje Škole - 4. zadatak

Frane je smislio novi način sažimanja podataka te pokušava analizirati svojstva svojeg algoritma. Osnovna ideja njegovog sažimanja je da se uklone nizovi znakova koji se više puta uzastopno ponavljaju.

Uzorak je niz od jednog ili više malih slova engleske abecede. Složenost uzorka je broj parova susjednih znakova u uzorku koji su različiti. Tako su, na primjer, složenosti uzoraka “aaa”, “abbba” i “baabaa” redom 0, 2 i 3. Poduzorak nekog uzorka je podniz uzastonih znakova određen nekom početnom i završnom pozicijom u uzorku.

Sažetak je niz znakova koji se definira na sljedeći način:

• Svaki uzorak je ujedno i sažetak.

• Ako su s1 i s2 sažetci, onda je niz koji dobijemo njihovim spajanjem — “s1s2” — također sažetak.

• Ako je s sažetak onda je i niz znakova “p(s)” također sažetak, gdje je p prirodni broj veći od jedan zapisan bez vodećih nula. Drugim riječima, od sažetka možemo dobiti novi sažetak tako da ga stavimo u zagrade te ispred otvorene zagrade napišemo prirodni broj.

Tako su, na primjer, “ab”, “2(ab)” i “2(2(ab)3(bab))” sažetci dok “(a)”, “2b” i “abc)” nisu.

Zadani sažetak se proširuje nizom koraka gdje u svakom koraku odaberemo jedan podniz sažetka oblika “p(s)”, takav da niz s ne sadrži zagrade, te ga zamijenimo sa p uzastopnih primjeraka niza s. Tako se, na primjer, sažetak “2(2(ab)3(bab))” može najprije proširiti do “2(abab3(bab))” pa zatim do “2(ababbabbabbab)” te na kraju do ababbabbabbabababbabbabbab. Ako na kraju ovog postupka dobijemo uzorak u onda kažemo da je s sažetak od u odnosno da je u proširenje od s.

Zadan je sažetak s, te dva prirodna broja a i b. Neka je p proširenje od s, pronađite složenost poduzorka od p počevši od a-te pozicije pa sve do b-te pozicije (uključivo) u uzorku p.

ULAZNI PODACI

U prvom redu nalazi se niz od najvše 1000 malih slova engleske abecede, znamenki te znakova zagrada “(” i “)” – zadani sažetak. Za svaki prirodni broj p u strukturi sažetka vrijedi 2 ≤ p ≤ 1000. Označimo sa n ukupnu duljinu proširenja zadanog sažetka. Za broj n vrijedi 1 ≤ n < 2^31 .

U drugom redu nalaze se prirodni brojevi a i b (a ≤ b ≤ n), početna i završna pozicija poduzorka

IZLAZNI PODACI

U prvi red ispišite jedan cijeli broj – traženu složenost.

PRIMJERI TEST PODATAKA

ulaz

2(2(ab)3(bab))
5 18

izlaz

10

ulaz

m2(i2(s))i2(p)i
2 9

izlaz

5

ulaz

1000(1000(333(aba)c))
1 1000000000

izlaz

667999999

Objašnjenje

Pojašnjenje drugog primjera: Sažetak “m2(i2(s))i2(p)i” se proširuje na sljedeći način: m2(i2(s))i2(p)i ⇒ m2(iss)ippi ⇒ mississippi Poduzorak od 2. do 9. znaka je “ississip” čija je složenost jednaka 5.