Pac-men
Trò chơi Pacmen với một sân chơi gồm $N$ ô vuông liên tiếp nhau. Tại một số ô có chứa Pacman, một số ô khác chứa chấm pac, một vài ô khác thì rỗng.
Pacman có thể di chuyển từ một ô sang ô kề cạnh nó trong 1 đơn vị thời gian. Nếu có một dấu chấm pac ở ô mà nó di chuyển đến, Pacman sẽ ăn nó. Pacman sẽ không tốn thời gian khi ăn một dấu chấm pac.
Khi thời gian bắt đầu, tất cả các Pacman bắt đầu di chuyển. Mỗi Pacman đều có thể thay đổi hướng đi của nó không giới hạn số lần, tuy nhiên không được di chuyển ra khỏi $N$ ô. Pacman không bị ảnh hưởng khi di chuyển qua các Pacman khác.
Hãy tìm thời gian ngắn nhất để các Pacman ăn hết các dấu chấm pac.
Dữ liệu
- Dòng đầu tiên chứa số nguyên $N \ (1\le N\le 10^5)$;
- Dòng tiếp theo chứa $N$ kí tự - với kí tự thứ $i$ là dấu chấm (.) khi ô thứ $i$ rỗng, là dấu sao (*) khi ô thứ $i$ chứa dấu chấm pac; là chữ cái p khi ô thứ $i$ chứa 1 Pacman.
Dữ liệu đảm bảo có ít nhất một Pacman và một dấu chấm pac.
Kết quả
- Kết quả bài toán.
Ví dụ
Ví dụ 1
input
7
..p*p*
output
1
Ví dụ 2
input
10
.**pp.*p.*
output
2
Comments