Zadatak: Zig Zag

Županijsko 2025., 7.razred, 3. zadatak

U dalekom kraljevstvu Algoritama, mudri kralj Nikola je osmislio tajanstvenu igru s riječima Zig i Zag. Onaj tko pronađe najviše ispravnih podnizova zadanog niza riječi, postat će kraljev nasljednik! Jednog dana.

Podniz zadanog niza riječi je ispravan:

• ako u podnizu nema riječi Zig; • ako se u podnizu neposredno nakon svake riječi Zig nalazi riječ Zag.

Tvoj zadatak je za zadani niz od N riječi prebrojati koliko on ima ispravnih podnizova. Napomena: Podniz niza je dio niza koji se sastoji od jednog ili više njegovih uzastopnih elemenata.

ULAZNI PODACI

U prvom je retku prirodan broj N (1 ≤ N ≤ 106 ), broj riječi u nizu riječi iz teksta zadatka. U drugom je retku N riječi odvojenih razmakom od kojih je svaka ili Zig ili Zag.

IZLAZNI PODACI

U prvi redak ispiši koliko podnizova zadanog niza riječi je ispravno.

BODOVANJE

U primjerima vrijednima 9 bodova vrijediti će da je N ≤ 200. U primjerima vrijednima 21 bodova vrijediti će da je N ≤ 5000. U primjerima vrijednima 12 bodova u zadanom nizu će se nalaziti točno 1 riječ Zig. U primjerima vrijednima 15 bodova u zadanom nizu će se nalaziti točno 2 riječi Zig.

Ulaz:

2
Zig Zag

Izlaz:

2

Ulaz:

4
Zig Zig Zag Zag

Izlaz:

5

Ulaz:

5
Zag Zag Zig Zag Zag

Izlaz:

12