ŠIOM — Bėgimas su kliūtimis

Laiko ribojimas: 1s

Atminties ribojimas: 256MB

Duomenų failas: steeplechase.in

Rezultatų failas: steeplechase.out

Language:
Source file:
Jei norite pateikti savo sprendimą - prisijunkite.

Bėgimas su kliūtimis

Martynas neseniai susidomėjo sportu. Po ilgų paieškų atrado jam labiausiai patinkančią sporto šaką - bėgimą su kliūtimis. Prieš pradėdamas treniruotes nusprendė pirmiausia apskaičiuoti, per kiek mažiausiai laiko yra įmanoma prabėgti jo suplanuotą trasą. Martynas pats neišmano programavimo, todėl prašo jūsų pagalbos!

Martyno trasa - tai eilė iš $n$ langelių, kur kiekvienas langelis yra vienas iš dviejų simbolių:

. - kelias, kuriuo galima bėgti.
# - kliūtis, per kurią bėgti negalima.

Martynas pradeda bėgti pirmame langelyje su greičiu $0$ ir finišuoja paskutiniame langelyje. Kiekvienu momentu Martynas gali:

Perbėgti į gretimą langelį, jei jis nėra kliūtis # ir pagreitėti vienu greičio vienetu bei sugaišti $1$ laiko vienetą.
Peršokti per $m$ langelių (kai $m$ - dabartinis Martyno greitis) ir išlaikyti greitį $m$ bei sugaišti $1$ laiko vienetą. Šokdamas Martynas atsiranda langelyje $p+m+1$ , kur $p$ yra dabartinė jo pozicija. Atkreipkite dėmesį kad Martynas gali šokti ir kai jo greitis yra 0 - tokiu atveju jis pajudės per vieną langelį į priekį, o jo greitis nepakis.

Pirmas ir paskutinis langeliai trasoje yra visada laisvi ir perbėgti trasą visada įmanoma.

Užduotis

Parašykite programą, kuri nuskaičius trasą pasakytų kiek mažiausiai laiko Martynas užtruks kol pasieks finišą.

Pradiniai duomenys

Pirmoje eilutėje pateikiamas vienas skaičius $n$ - trasos ilgis.

Antroje eilutėje $n$ simbolių - trasos duomenys.

Rezultatai

Išveskite vieną skaičių - kiek mažiausiai laiko Martynas užtruks kol pasieks finišą.

Pavyzdžiai

Pradiniai duomenys	Rezultatai	Paaiškinimas
5 .....	3	Martynas perbėga į antrą langelį, tada nušoka į ketvirta, ir galiausiai perbėga į penktą.
8 ..#..#..	4	Martynas perbėga į antrą langelį, peršoka į ketvirtą, perbėga į penktą, ir nušoka į aštuntą.
20 ....#.#.###..##.#...	7	Martynas tris laiko vienetus bėga, o po to atlieka keturis šuolius.

Ribojimai