Hành hương
Đề bài
Mô tả
Jack cùng vài người bạn đang đi bộ một chặng đường dài theo con đường hành hương cổ từ Vézelay đến Santiago de Compostela. Jack giữ tiền chung cho cả nhóm. Cách quản lý của anh rất đơn giản. Mỗi khi cần chi một khoản (chẳng hạn euro) cho việc chung, anh trả khoản đó và ghi vào sổ: PAY 60.
Khi cần, Jack yêu cầu mỗi thành viên trong nhóm, kể cả chính anh, góp một khoản (chẳng hạn euro) vào quỹ chung, và ghi vào sổ: COLLECT 50. Nếu nhóm có người, anh thu được tổng cộng euro.
Không may, một số thành viên không thể đi hết cả chặng đường. Vì vậy có lúc nhóm đông thêm, có lúc nhóm ít đi. Jack xử lý tiền chung thế nào khi có người đến và người đi? Ví dụ, giả sử nhóm có người và Jack đang giữ euro tiền mặt, tức euro cho mỗi thành viên. Nếu hai thành viên rời nhóm, mỗi người nhận lại euro, và Jack ghi vào sổ: OUT 2. Nếu trong cùng hoàn cảnh đó có ba thành viên mới đến, mỗi người phải góp euro, và Jack ghi: IN 3.
Trong các trường hợp trên, số tiền mặt chia đều được, không có phần lẻ. Thật trùng hợp, điều này luôn xảy ra trong suốt chuyến đi: Jack chưa bao giờ phải tính toán với số euro lẻ (mỗi lần có IN hoặc OUT, số tiền mặt đang có chia hết cho số người trong nhóm ngay lúc đó).
Gần cuối chuyến đi, tất cả bạn đồng hành đều đến nhập nhóm với Jack, không ai muốn bỏ lỡ chặng kết thúc rực rỡ. Đến lúc đó Jack mới cố nhớ lại số người của nhóm trong từng phần của chuyến đi, nhưng anh không nhớ được.
Cho một trang trong sổ của Jack, hãy xác định số người của nhóm ở đầu trang đó.
Dữ liệu vào
Dữ liệu gồm nhiều bộ test. Mỗi bộ test là một dãy các dòng trong sổ của Jack. Dòng đầu tiên của mỗi bộ test chứa số , số dòng tiếp theo. dòng sau có dạng <từ khoá> <số>, trong đó từ khoá là một trong PAY, COLLECT, IN, OUT, và số là một số nguyên dương với các giới hạn sau:
IN k: .OUT k: .COLLECT k: .PAY k: .
Sau bộ test cuối cùng là một dòng chứa một số .
Dữ liệu ra
Với mỗi bộ test, in một dòng mô tả số người của nhóm ở đầu phần chuyến đi được ghi trong bộ test đó. Dòng này chứa:
- Từ
IMPOSSIBLE, nếu dữ liệu mâu thuẫn. - Một số duy nhất là số người của nhóm ngay trước các dòng trong sổ, nếu số này được xác định duy nhất từ dữ liệu.
- Nhiều số theo thứ tự tăng dần, cách nhau bởi dấu cách, là các số người có thể có của nhóm, nếu số khả năng là hữu hạn nhưng không duy nhất.
- Một dòng dạng
SIZE >= Xcho biết cận dưới của số người, nếu có vô số khả năng. Lưu ý rằng bất đẳng thứcSIZE >= 1luôn đúng, vì ít nhất Jack đi hết cả chuyến đi (nhóm luôn có ít nhất người).
Ràng buộc
- .
- Các số trong sổ là số nguyên dương thoả các giới hạn ở trên.
- Mỗi file có không quá bộ test.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 IN 1 PAY 7 IN 1 PAY 7 IN 1 7 IN 1 COLLECT 20 PAY 30 PAY 12 IN 2 PAY 30 OUT 3 3 IN 1 PAY 8 OUT 3 1 OUT 5 0 |
IMPOSSIBLE 2 3 7 SIZE >= 6 |
Bộ 1: ở lần IN thứ hai nhóm phải có người (số tiền đã chi phải chia hết cho số người), nhưng ở lần IN thứ ba nhóm có người và không chia hết cho . Bộ 2: nhóm ban đầu người; lúc IN 2 nhóm có người, đã chi ; lúc OUT 3 nhóm có người, đã chi . Bộ 3: nhóm có người phải chia hết và sau OUT 3 còn ít nhất người, nên hoặc . Bộ 4: chỉ biết nhóm có ít nhất người. |
| 7 COLLECT 5 PAY 3 IN 2 PAY 40 PAY 20 OUT 4 PAY 7 4 OUT 3 IN 10 PAY 5 COLLECT 7 3 IN 1 PAY 97 OUT 1 2 PAY 5 IN 1 0 |
3 4 8 10 13 18 28 58 SIZE >= 4 96 SIZE >= 1 |
Ví dụ tự thêm. Bộ 1: khoản PAY 3 trước lần IN đầu tiên không ràng buộc gì vì không biết số tiền ban đầu; nhóm có người phải chia hết , và sau OUT 4 còn ít nhất người nên . Bộ 2: không có khoản chi nào giữa hai lần IN/OUT, chỉ biết . Bộ 3: chia hết và nên . Bộ 4: chỉ biết . |
Bình luận