Trò chơi của Hongcow
Đề bài
Mô tả
Đây là một bài toán tương tác (interactive).
Hệ thống giữ một ma trận bí mật kích thước , hàng và cột được đánh số từ đến . Mọi phần tử thoả , và với mọi .
Với mỗi hàng , hãy tìm giá trị nhỏ nhất trên hàng đó không kể phần tử nằm trên đường chéo chính, tức là .
Để làm việc đó, bạn được đặt tối đa truy vấn. Một truy vấn là một tập chỉ số phân biệt với và . Hệ thống trả lời số nguyên, số thứ bằng .
Câu trả lời của một truy vấn có tính cả phần tử đường chéo khi thuộc tập chỉ số, nên với hàng bạn chỉ dùng được những truy vấn mà tập chỉ số không chứa .
Bạn sẽ nhận kết quả sai nếu đặt quá truy vấn, nếu tập chỉ số có phần tử trùng nhau, nếu nằm ngoài đoạn , hoặc nếu câu trả lời cuối cùng không đúng.
Dữ liệu vào
Dòng đầu tiên chứa một số nguyên ().
Sau mỗi truy vấn, đọc một dòng chứa số nguyên là câu trả lời của hệ thống.
Dữ liệu ra
Để đặt một truy vấn, in số nguyên trên một dòng, rồi in chỉ số phân biệt trên dòng tiếp theo.
Khi đã sẵn sàng trả lời, in trên một dòng, rồi in số nguyên trên dòng tiếp theo: số thứ là giá trị nhỏ nhất của hàng sau khi bỏ qua phần tử đường chéo. In câu trả lời cuối cùng không được tính là một truy vấn.
Sau mỗi lần in, bạn phải flush output (ví dụ cout << flush trong C++, flush=True trong Python).
Ràng buộc
- với mọi
- Tối đa truy vấn
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 0 9 7 0 |
1 1 1 2 -1 7 9 |
Ma trận bí mật là . Truy vấn trả về cột là , truy vấn trả về cột là . Hàng chỉ được phép dùng truy vấn nên đáp án là ; hàng chỉ được phép dùng truy vấn nên đáp án là . |
| 3 0 5 0 3 0 8 0 0 4 2 7 0 |
2 1 3 1 2 2 1 2 1 3 -1 2 5 4 |
Ma trận bí mật là . Hàng có các phần tử ngoài đường chéo là nên nhỏ nhất bằng ; hàng được ; hàng được . Bốn truy vấn ở đây tương ứng với việc tách chỉ số theo hai bit thấp nhất. |
Bình luận