Mê cung bí ẩn của Minotaur
Đề bài
Mô tả
Đây là bài toán tương tác.
Mê cung Crete là một công trình tinh xảo và rối rắm do nghệ nhân huyền thoại Daedalus thiết kế và xây dựng cho vua Minos của đảo Crete tại Knossos. Mục đích của nó là giam giữ Minotaur, sinh vật thần thoại có đầu và đuôi bò, thân người.
Dù Minotaur đã không còn từ lâu, mê cung vẫn còn đó, với những bức tường ma thuật liên tục dịch chuyển để đánh lừa bất kỳ ai dám bước vào. Bạn, một nhà thám hiểm gan dạ, đã bị mắc kẹt trong mê cung cổ xưa này, bao quanh bởi những hành lang kỳ bí luôn biến đổi.
Mê cung gồm một dãy các căn phòng xếp thành một vòng tròn. Trong mỗi phòng có đúng một ngọn đuốc phép thuật, đang cháy hoặc đã tắt. Tuy nhiên, bạn không biết số phòng . Tại mỗi thời điểm, bạn chỉ quan sát được trạng thái ngọn đuốc trong phòng mình đang đứng và không biết gì về các ngọn đuốc ở những phòng khác.
Để thoát khỏi mê cung, bạn phải tìm ra , số căn phòng trên vòng tròn. Mỗi bước, bạn có thể sang phòng kế bên theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ, quan sát trạng thái ngọn đuốc, và thay đổi nó nếu muốn. Nhưng hãy cẩn thận: bạn chỉ có bước để xác định số ngọn đuốc trước khi mê cung dịch chuyển lần nữa và giam bạn mãi mãi.
Tương tác
Trạng thái mỗi ngọn đuốc được mã hóa bằng một số: là đuốc đã tắt, là đuốc đang cháy.
Đầu tiên, chương trình của bạn đọc số (): số bộ test. Với mỗi bộ test, chương trình tương tác với trình chấm theo vòng lặp sau:
- Trước tiên, trình chấm in ra một số ( hoặc ): trạng thái ngọn đuốc ở phòng bạn đang đứng.
- Sau đó, chương trình của bạn thực hiện một truy vấn bằng cách in ra một trong các dòng sau:
- "> " ( hoặc ): đặt ngọn đuốc hiện tại về trạng thái rồi sang phòng kế bên theo chiều kim đồng hồ. Vòng lặp tiếp tục.
- "< " ( hoặc ): đặt ngọn đuốc hiện tại về trạng thái rồi sang phòng kế bên ngược chiều kim đồng hồ. Vòng lặp tiếp tục.
- "! ": trả lời rằng mê cung có phòng, kết thúc tương tác cho bộ test hiện tại.
Với mỗi bộ test, câu trả lời được chấp nhận nếu chương trình của bạn thỏa mãn cả hai điều kiện:
- trả lời đúng , và
- trước khi trả lời, đã thực hiện không quá truy vấn. Truy vấn trả lời không tính vào giới hạn này.
Tổng trên tất cả các bộ test không vượt quá .
Số phòng và trạng thái ban đầu của mọi ngọn đuốc được cố định trước khi tương tác bắt đầu, và chỉ thay đổi theo các truy vấn của chương trình bạn.
Sau mỗi dòng in ra, nhớ flush luồng ra: fflush(stdout) hoặc cout.flush() trong C++, System.out.flush() trong Java, stdout.flush() trong Python.
Ràng buộc
- , tổng trên tất cả các bộ test không vượt quá
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 1 0 1 1 0 1 1 0 0 |
> 0 > 1 < 0 < 1 > 0 ! 3 < 0 < 0 ! 4 |
Cột Input là những gì chương trình đọc được, cột Output là những gì chương trình in ra; ví dụ chỉ minh họa cách tương tác, không cho thấy cách suy ra đáp án. Bộ test 1: , các ngọn đuốc theo chiều kim đồng hồ là 101 và bạn đứng ở ngọn đầu tiên. Sau các truy vấn > 0, > 1, < 0, < 1, > 0, trạng thái lần lượt là 001, 011, 010, 010, 010. Bộ test 2: . |
| 1 0 1 0 |
> 1 > 0 ! 1 |
Ví dụ thêm: , ngọn đuốc duy nhất đang tắt. Đi theo chiều kim đồng hồ đưa bạn quay lại chính căn phòng đó, nên lần nào bạn cũng thấy lại đúng giá trị vừa đặt. Câu trả lời được đưa ra sau truy vấn. |
Bình luận