Problem C
Biosalong
Axel och Beatrice ska gå på bio tillsammans. De vill sitta på samma rad och allra helst brevid varandra. Om det inte finns två lediga platser brevid varandra vill de ha två platser så nära varandra som möjligt.
För att hitta den bästa raden att sitta på ber de dig om hjälp. Givet en beskrivning av vilka stolar som är lediga på en viss rad, hitta det kortaste avståndet mellan två lediga stolar. Avståndet är antal stolar mellan de två lediga stolarna.
Indata
Den första raden innehåller ett heltal $1 \le N \le 1\, 000\, 000$ – antalet stolar i raden vi betraktar.
Den andra raden innehåller en sträng med $N$ tecken, där det $i$:te tecknet är ’#’ ifall den $i$:te stolen på raden är upptagen och ’.’ om stolen är ledig. Det är garanterat att minst två stolar är lediga, dvs minst två tecken är ’.’.
Utdata
Skriv ut ett heltal – det kortaste avståndet mellan två lediga stolar.
Poängsättning
Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.
|
Grupp |
Poängvärde |
Gränser |
|
$1$ |
$60$ |
$1 \le N \le 1\, 000$ |
|
$2$ |
$40$ |
$1 \le N \le 1\, 000\, 000$ |
Exempelfall
| Sample Input 1 | Sample Output 1 |
|---|---|
5 #.##. |
2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
7 .##.#.# |
1 |
| Sample Input 3 | Sample Output 3 |
|---|---|
13 #.####.###.## |
3 |
| Sample Input 4 | Sample Output 4 |
|---|---|
6 #..##. |
0 |
