[COCI1617 - Contest 03] Bài 3: Kronican

Xem PDF

Nộp bài

Điểm: 100 (thành phần)
Thời gian: 1.0s
Bộ nhớ: 1G
Input: bàn phím
Output: màn hình

Tác giả:
Dạng bài

Mirko vừa có một chiếc điện thoại mới cho ngày sinh nhật! Giống như tất cả trẻ em ngày nay, cậu bé nhanh chóng tải xuống tất cả các trò chơi di động phổ biến, bao gồm cả Jetpack Joyride. Trong trò chơi, nhân vật chính Barry đang chạy qua một khu vực gồm 10 hàng và N cột ô vuông có kích thước bằng nhau. Ban đầu, Barry được đặt ở trung tâm của ô vuông ở góc dưới bên trái. Barry liên tục chạy sang phải với tốc độ một ô vuông mỗi giây. Bên cạnh đó, cậu ấy phải né tránh những chướng ngại vật trên đường đi.

Khi Mirko nhấn vào màn hình điện thoại, Barry kích hoạt phản lực siêu việt đặc biệt của mình và bắt đầu bay lên với tốc độ một ô vuông mỗi giây (vẫn di chuyển sang phải, bây giờ di chuyển theo đường chéo lên một góc 45 °, cho đến khi chạm đến trần nhà, khi đó cậu ấy sẽ tiếp tục di chuyển sang phải cho đến khi Mirko nhả màn hình). Khi Mirko nhả màn hình điện thoại, Barry bắt đầu rơi xuống với tốc độ một ô vuông mỗi giây (bây giờ di chuyển theo đường chéo một lần nữa, nhưng lần này hướng xuống, cho đến khi chạm đến sàn nhà, khi đó cậu ấy sẽ tiếp tục di chuyển sang phải).

Mirko mới bắt đầu chơi trò chơi gần đây và cậu ấy vẫn chưa giỏi. Cậu ấy thấy trên YouTube rằng ai đó đã hoàn thành trò chơi bằng cách vượt qua tất cả ~N ~ cột, vì vậy cậu ấy đang yêu cầu sự giúp đỡ của bạn. Mirko sẽ cung cấp cho bạn bố cục của các ô trong trò chơi, và bạn phải đưa ra các nước đi mà cậu ấy phải thực hiện để giành chiến thắng.

Input

  • Dòng đầu tiên chứa số nguyên ~N (1 ≤ N ≤ 10^5)~, kích thước của khu vực.
  • Mỗi trong 10 dòng tiếp theo chứa ~N~ ký tự ‘.’ và ‘X’, bố cục của khu vực trong trò chơi. Ký tự ‘X’ biểu thị chướng ngại vật và ‘.’ là các ô có thể đi lại.

Output

  • Dòng đầu tiên của đầu ra phải chứa số nguyên ~P (0 ≤ P ≤ 5⋅10^4)~, số nước đi mà Mirko phải thực hiện.
  • Trong P dòng tiếp theo, hãy đưa ra bất kỳ chuỗi P nước đi nào, mỗi nước đi trên một dòng riêng, sao cho nó giải quyết vấn đề của Mirko từ bài toán. Một nước đi được xác định bởi hai số nguyên ~t_i~ và ~x_i~, trong đó ~t_i~ biểu thị giây mà Mirko phải nhấn vào màn hình và ~x_i~ biểu thị thời gian cậu ấy cần giữ màn hình. Chuỗi các nước đi phải được sắp xếp theo thứ tự thời gian. Nói cách khác, ~t_i + x_i ≤ t_{(i+1)}~. Ngoài ra, không có nước đi nào bắt đầu sau khi trò chơi kết thúc, ~t_i~ < N. Dữ liệu đầu vào sẽ đảm bảo rằng chắc chắn sẽ có một giải pháp.

Sample Input

11
.....XX...X
....XX...XX
...XX...XX.
...........
....XXX....
...........
.....X.....
....XX...X.
...XX...XX.
...X...XX..

Sample Output

2
1 4
7 2

Bình luận đầu tiên

Bình luận

Không có bình luận nào.