Trò chơi bài liên tiếp
Đề bài
Mô tả
GSPVH đang tham dự một sự kiện trò chơi bài. Anh sẽ chơi trò "Những lá bài trong hộp đen". Nếu thắng, anh sẽ nhận được một giải thưởng cực lớn như một giải jackpot!
Trò chơi diễn ra như sau. Ban đầu, người dẫn chương trình đưa ra một hộp đen không có lá bài nào bên trong. Sau đó, người dẫn bỏ vào hộp lá bài, trên mỗi lá ghi một số nguyên; các số ghi trên lá bài là . Tiếp theo, người dẫn công bố một số nguyên dương .
Bây giờ GSPVH chơi một vòng khởi động:
- GSPVH nói với người dẫn một số nguyên dương .
- Người dẫn lấy ngẫu nhiên lá bài ra khỏi hộp đen.
- Nếu trong các lá bài được lấy ra có lá ghi số nguyên liên tiếp thì GSPVH thắng vòng này. Nói cách khác, GSPVH thắng nếu tồn tại số nguyên sao cho với mọi số nguyên từ đến (tính cả hai đầu), có một lá bài ghi giá trị được lấy ra. Ngược lại GSPVH thua vòng này.
- Nếu GSPVH thua, trò chơi kết thúc ngay và GSPVH không nhận được giải thưởng nào. Nếu GSPVH thắng, mọi lá bài đã lấy ra được bỏ lại vào hộp đen và trò chơi tiếp tục.
Nếu trò chơi vẫn tiếp tục, GSPVH sẽ chơi thêm vòng liên tiếp, đánh số từ đến . Vòng thứ diễn ra như sau:
- Người dẫn công bố ba số nguyên , và .
- Với mỗi số nguyên từ đến (tính cả hai đầu), người dẫn lấy ra khỏi hộp đen tất cả các lá bài ghi giá trị và đốt chúng đi vĩnh viễn, rồi bỏ vào hộp đen đúng lá bài mới ghi giá trị . Nói cách khác, sau bước này, với mỗi số nguyên từ đến có đúng lá bài ghi giá trị .
- GSPVH nói với người dẫn một số nguyên dương .
- Người dẫn lấy ngẫu nhiên lá bài ra khỏi hộp đen.
- Nếu trong các lá bài được lấy ra có lá ghi số nguyên liên tiếp thì GSPVH thắng vòng này. Ngược lại GSPVH thua vòng này.
- Nếu GSPVH thua, trò chơi kết thúc ngay và GSPVH không nhận được giải thưởng nào. Nếu GSPVH thắng, mọi lá bài đã lấy ra được bỏ lại vào hộp đen và trò chơi tiếp tục.
GSPVH chỉ nhận được giải thưởng nếu thắng tất cả vòng này. Lưu ý rằng:
- Ở mỗi vòng, số GSPVH nói ra phải nhỏ hơn hoặc bằng số lá bài đang có trong hộp đen.
- Ở mỗi vòng, GSPVH quyết định số lá bài được lấy ra nhưng không thể điều khiển chính xác những lá bài nào được lấy ra.
- Giá trị không đổi trong suốt trò chơi.
- Ở mỗi vòng, nếu GSPVH thắng, mọi lá bài được lấy ra đều được bỏ lại vào hộp đen trước vòng tiếp theo. Do đó, ở mỗi vòng, tập các lá bài trong hộp đen không phụ thuộc vào việc những lá bài nào đã được lấy ra ở các vòng trước.
Vì giải thưởng rất lớn, GSPVH muốn chắc chắn thắng. Cụ thể, ở mỗi vòng, GSPVH muốn chọn số lá bài được lấy ra sao cho dù người dẫn lấy ra những lá nào thì GSPVH cũng chắc chắn thắng. Đồng thời, GSPVH muốn số mình nói ra nhỏ nhất có thể.
Hãy giúp GSPVH xác định, ở mỗi vòng, số lá bài nhỏ nhất cần lấy ra để GSPVH chắc chắn nhận được giải thưởng!
Dữ liệu vào
- Dòng đầu tiên chứa ba số nguyên , và (, , ).
- Dòng thứ hai chứa số nguyên ().
- Dòng thứ trong dòng cuối chứa ba số nguyên , và (, ).
Dữ liệu đảm bảo ở mọi vòng, trước khi GSPVH nói ra một số, hộp đen có chứa các lá bài ghi số nguyên liên tiếp.
Dữ liệu ra
In ra số nguyên, lần lượt là số lá bài nhỏ nhất cần lấy ra để chắc chắn thắng ở vòng khởi động và ở vòng tiếp theo. Mỗi số in trên một dòng.
Ràng buộc
- , ,
- ,
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 2 2 1 2 4 5 8 8 1 6 7 1 |
3 4 5 |
Vòng khởi động: hộp có lá ; lấy lá thì chắc chắn có cả và hoặc cả và . Vòng : hộp có , cần lá. Vòng : hộp có ; lá chưa đủ vì có thể lấy ra , còn lá thì chắc chắn thắng. |
| 8 3 3 1 2 3 3 5 6 6 6 4 4 2 10 12 1000000000 -1000000000 1000000000 1 |
8 9 2000000009 1333333335 |
Vòng khởi động: có thể lấy lá mà không có ba giá trị liên tiếp. Vòng : mọi giá trị từ đến có đúng một lá. |
Bình luận