Cuộc phiêu lưu mới
Đề bài
Mô tả
"Hunter" (thợ săn) là một nghề có giấy phép, dành cho những người chuyên đi tìm các sinh vật quý hiếm hoặc kho báu bí mật.
Gon đã bắt đầu một hành trình mới để trở thành Hunter. Hôm qua, Gon đến Hà Nội để tham dự Kỳ thi Hunter, kỳ thi hằng năm mà ai muốn trở thành Hunter cũng phải vượt qua.
Hội trường thi được bao quanh bởi một con đường hình tròn. Ta mô hình hóa con đường thành đường tròn đồng tâm, đánh số từ đến từ ngoài vào trong. Mỗi đường tròn được chia thành cung, đánh số từ đến theo chiều kim đồng hồ; các đường chia cung của mọi đường tròn nằm trên cùng các bán kính, nên cung thứ của mọi đường tròn nằm trong cùng một hình quạt. Cung thứ của đường tròn thứ được ký hiệu là . Gon đang đứng ở cung .
Trên đường có các xe máy. Mỗi cung có không quá một xe máy, và cung không có xe máy. Ví dụ, với và , có thể có xe máy, một chiếc ở cung và một chiếc ở cung .
Mọi xe máy đều chạy với tốc độ không đổi cung mỗi giây, theo chiều kim đồng hồ và không bao giờ dừng. Cụ thể, nếu ở giây thứ một xe máy ở cung thì ở giây thứ nó ở cung .
Gon cần đi tới Hội trường thi nằm bên trong đường tròn thứ . Mỗi giây, Gon có thể đứng yên tại vị trí hiện tại, hoặc di chuyển sang một cung kề. Hai cung là kề nhau nếu chúng có chung ít nhất hai điểm, tức là hai cung liên tiếp trên cùng một đường tròn (cung và cung cũng liên tiếp), hoặc hai cung cùng số thứ tự trên hai đường tròn liên tiếp. Từ một cung bất kỳ của đường tròn thứ , Gon có thể đi vào Hội trường thi (mất giây).
Vì Gon di chuyển nhanh hơn một chút so với các xe máy nên:
- Nếu Gon di chuyển từ cung sang cung :
- Gon sẽ không bị đâm bởi các xe máy đi vào cung .
- Gon sẽ bị đâm bởi các xe máy đi ra từ cung hoặc đi vào cung .
- Nếu Gon đứng yên ở cung , Gon sẽ bị đâm bởi các xe máy đi vào cung .
Ví dụ, với , và hai xe máy ở cung và như trên, Gon có thể đi như sau:
- Ở giây thứ : Gon đi sang cung , hai xe máy đi tới cung và .
- Ở giây thứ : Gon đi sang cung , hai xe máy đi tới cung và .
- Ở giây thứ : Gon đi vào Hội trường thi, hai xe máy đi tới cung và .
Lưu ý:
- Nếu ở giây thứ Gon đi sang cung , Gon sẽ bị đâm bởi xe máy đi từ cung sang cung .
- Nếu ở giây thứ Gon đứng yên ở cung , Gon cũng sẽ bị đâm bởi xe máy đi từ cung sang cung .
Kỳ thi Hunter sắp bắt đầu mà Gon vẫn chưa biết cách băng qua con đường. Hãy giúp Gon tính thời gian ít nhất để tới Hội trường thi mà không bị xe máy nào đâm.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên dương và ().
dòng tiếp theo, dòng thứ chứa đúng ký tự mô tả đường tròn thứ . Ký tự thứ của dòng thứ là G, M hoặc dấu chấm, lần lượt cho biết cung là nơi Gon đứng, có một xe máy, hoặc trống (ở giây thứ ).
Ký tự đầu tiên của dòng đầu tiên luôn là G, và đây là ký tự G duy nhất trong dữ liệu vào.
Dữ liệu ra
In ra đúng một số nguyên là thời gian ít nhất (tính bằng giây) để Gon tới Hội trường thi. Nếu Gon không thể tới Hội trường thi, in ra .
Ràng buộc
- và .
- Mỗi dòng mô tả đường tròn gồm đúng ký tự thuộc G, M và dấu chấm; ký tự G duy nhất nằm ở đầu dòng đầu tiên.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 8 GM...... ......M. ........ |
3 | Đây là ví dụ được mô tả trong đề: Gon đi thẳng vào trong qua các cung , rồi vào Hội trường thi. |
| 2 2 G. M. |
-1 | Ví dụ bổ sung (không có trong đề gốc). Xe máy ở đường tròn thứ lần lượt đi qua hai cung của đường tròn này, nên mỗi khi Gon muốn đi sang một cung của đường tròn thứ , xe máy hoặc đang ở cung đó hoặc sẽ đi vào cung đó. |
Bình luận