COCI 2016/2017 - Contest 1 - Jetpack

View as PDF

Submit solution

Points: 0.70 (partial)
Time limit: 1.0s
Memory limit: 64M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2016/2017 - Contest 1
Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Bé Mirko đã được bố mẹ tặng một chiếc điện thoại nhân dịp sinh nhật. Giống như những đứa trẻ khác, cậu nhanh chóng tải về những tựa game đình đám nhất trên điện thoại về để chơi, trong đó có tựa game Jetpack Joyride.

Trong tựa game này, ta sẽ điều khiển nhân vật chính có tên là Barry chạy trên một vùng tạo bởi các ô vuông có diện tích bằng nhau gồm ~10~ hàng và ~N~ cột . Khởi đầu, Barry sẽ xuất phát ở ô dưới cùng của cột ~1~. Barry sẽ liên tục chạy về bên phải với tốc độ ~1~ ô vuông/giây. Ngoài ra, anh ta sẽ phải tránh những chướng ngại vật cản đường.

Trong khi chơi game, nếu Mirko bấm giữ màn hình điện thoại, Barry sẽ kích hoạt gói phản lực đặc biệt super-duper của mình và sẽ bay chéo lên một góc 45°. Với gói phản lực này, nếu Barry chạm đến đường biên trên (hàng ~1~) mà Mirko vẫn giữ màn hình, anh ấy sẽ bay tiếp sang phải. Khi Mirko thả tay khỏi màn hình điện thoại, Barry sẽ rơi xuống dần dần theo đường chéo, khi Barry rơi xuống mặt đất anh ấy sẽ chạy tiếp sang phải. Biết rằng tốc độ của Barry khi chạy trên mặt đất, lúc bay và lúc rơi xuống đều không đổi và bằng ~1~ ô vuông/ giây.

Sau khi lên Youtube để xem video hướng dẫn, Mirko đã biết để hoàn thành tựa game này ta sẽ cần đi đến cột thứ ~N~ của mỗi màn chơi. Mirko mới tập chơi game nên còn rất bỡ ngỡ, vì vậy cậu ấy đã nhờ bạn giúp mình "phá đảo" tựa game này. Mirko sẽ cung cấp cho bạn cách bố trí của các ô trong mỗi màn chơi và bạn hãy giúp Mirko bằng cách đưa ra các nước đi mà cậu ấy cần đi để giành chiến thắng.

Input

  • Dòng đầu tiên chứa số nguyên ~N \ (1\leq N\leq 10^5)~ là kích thước của vùng di chuyển.

  • ~10~ dòng tiếp theo mỗi dòng chứa ~N~ kí tự . hoặc X mô tả cách bố trí của các ô trong màn chơi. Với X là chướng ngại vật và . là các ô có thể di chuyển được.

Output

  • Dòng đầu in ra số nguyên ~P \ (0 \leq P \leq 50000)~ là số nước đi mà Mirko cần đi để dành chiến thắng.
  • ~P~ dòng tiếp theo mỗi dòng chứa ~2~ số nguyên ~t_{i}~ và ~x_{i}~ với ~t_{i}~ là thời điểm Mirko cần bấm vào màn hình và ~x_{i}~ biểu thị cho số giây Mirko cần bấm giữ màn hình.

Dữ liệu in ra cần đảm bảo in ra theo thứ tự thời gian tức là ~t_{i} + x_{i} \leq t_{i+1}~, đồng thời không còn nước đi nào sau khi Barry đã đến cột ~N~ của màn chơi ~(t_{i} < N)~. Đề bài đảm bảo luôn tồn tại ít nhất một cách để di chuyển đến cột thứ ~N~.

Sample 1

Input
11
.....XX...X
....XX...XX
...XX...XX.
...........
....XXX....
...........
.....X.....
....XX...X.
...XX...XX.
...X...XX..
Output
2
1 4
7 2

Sample 2

Input
20
X..................X
.X................X.
..X..............X..
...X............X...
....X..........X....
.....X........X.....
......X......X......
.......X....X.......
........X..X........
.........XX.........
Output
1
8 10

Giải thích ở ví dụ đầu tiên

Con đường mà Barry phải đi được kí hiệu bằng * và được mô tả như sau:

.....XX...X
....XX...XX
...XX...XX.
...........
....XXX....
.....*...*.
....*X*.*.*
...*XX.*.X.
..*XX...XX.
**.X...XX..

Comments

Please read the guidelines before commenting.


There are no comments at the moment.