Mèo bông
Đề bài
Mô tả
Bạn đang phát triển trò chơi di động mới tên là Fluffy Cat. Với lối chơi đơn giản nhưng hấp dẫn, chắc chắn nó sẽ trở thành một trò chơi di động hàng đầu!
Trong trò chơi này, một người chơi điều khiển một chú mèo trên một lưới ô vuông vô hạn. Có một con chuột ẩn ở đâu đó trên lưới. Để thắng, người chơi phải bắt được chuột. Trò chơi gồm nhiều lượt. Trong mỗi lượt:
- Người chơi di chuyển mèo tối đa hai bước (có thể là không bước nào). Mỗi bước, mèo đi một đơn vị độ dài theo một trong các hướng lên, xuống, trái, phải. Cụ thể hơn, trong một bước, mèo có thể đi từ điểm hiện tại đến một trong điểm , , và .
- Nếu mèo và chuột ở cùng một điểm, chuột không được di chuyển, trò chơi kết thúc ngay lập tức và người chơi thắng.
- Ngược lại, chuột di chuyển đúng một đơn vị độ dài theo một trong các hướng lên, xuống, trái, phải. Chuột di chuyển theo một thuật toán viết sẵn mà người chơi không biết.
- Nếu mèo và chuột ở cùng một điểm, trò chơi kết thúc ngay lập tức và người chơi thắng. Ngược lại, trò chơi tiếp tục sang lượt tiếp theo.
Cuối mỗi lượt, người chơi được cho biết bình phương khoảng cách Euclid giữa mèo và chuột. Nếu khoảng cách này bằng thì trò chơi đã kết thúc và người chơi đã thắng. Nếu mèo ở điểm và chuột ở điểm thì bình phương khoảng cách Euclid giữa chúng là .
Nếu người chơi không bắt được chuột trong vòng lượt, người chơi thua. Nhiệm vụ của bạn là thắng trò chơi dù chuột chơi thế nào.
Tương tác
Trong mỗi lượt:
- Đầu tiên, chương trình của bạn in ra một số nguyên (): số bước bạn muốn mèo đi, theo sau là một dấu cách và ký tự, mỗi ký tự là một trong
L,R,U,D(trái, phải, lên, xuống), cho biết các hướng mèo đi. HướngLgiảm ,Rtăng ,Utăng ,Dgiảm . - Sau đó chương trình đọc một số nguyên : bình phương khoảng cách Euclid giữa mèo và chuột. Nếu , bạn đã thắng và chương trình phải kết thúc ngay.
Ban đầu, bình phương khoảng cách Euclid giữa mèo và chuột không vượt quá . Mèo phải bắt được chuột trong vòng lượt.
Trình chấm có tính thích nghi: chương trình chấm có thể di chuyển chuột theo các chiến lược khác nhau, tùy vào những gì chương trình của bạn in ra.
Sau mỗi lần in, hãy flush đầu ra (ví dụ cout << endl hoặc cout.flush() trong C++, sys.stdout.flush() trong Python), nếu không trình chấm có thể không nhận được dữ liệu.
Ràng buộc
- Ban đầu bình phương khoảng cách giữa mèo và chuột nằm trong khoảng .
- Tối đa lượt.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 0 |
0 2 RR |
Cột Output là những gì chương trình in ra, cột Input là những gì chương trình đọc được. Mèo ở , chuột ở và luôn đi sang phải. Lượt : mèo đứng yên, chuột sang , khoảng cách là . Lượt : mèo đi sang phải hai bước đến và bắt được chuột. Đề gốc minh họa một cách chơi khác với cùng con chuột: in 2 RL (mèo sang rồi quay về ; mèo chỉ đi ngang qua chỗ chuột nên chưa bắt được chuột), đọc ; in 2 RU, đọc ; in 2 RR, đọc ; in 1 D, đọc và thắng. Trình chấm không dùng chiến lược "luôn đi sang phải" này. |
| 9 4 0 |
0 2 UU 2 UU |
Ví dụ bổ sung (không có trong đề gốc). Mèo ở , chuột ở và luôn chạy ra xa mèo. Lượt : mèo đứng yên, chuột lên , khoảng cách . Lượt : mèo lên , chuột lên , khoảng cách . Lượt : mèo lên và bắt được chuột. |
Bình luận