trang chủ / đề bài / icpcwf06_g

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 60 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 50 euro) vào quỹ chung, và ghi vào sổ: COLLECT 50. Nếu nhóm có 7 người, anh thu được tổng cộng 350 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ó 7 người và Jack đang giữ 140 euro tiền mặt, tức 20 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 20 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 20 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ố N, số dòng tiếp theo. N 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: k≤20.
  • OUT k: k≤20.
  • COLLECT k: k≤200.
  • PAY k: k≤2000.

Sau bộ test cuối cùng là một dòng chứa một số 0.

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 >= X cho biết cận dưới X của số người, nếu có vô số khả năng. Lưu ý rằng bất đẳng thức SIZE >= 1 luôn đúng, vì ít nhất Jack đi hết cả chuyến đi (nhóm luôn có ít nhất 1 người).

Ràng buộc

  • 1≤N≤50.
  • 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á 10000 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ó 7 người (số tiền 7 đã chi phải chia hết cho số người), nhưng ở lần IN thứ ba nhóm có 8 người và 7 không chia hết cho 8. Bộ 2: nhóm ban đầu 2 người; lúc IN 2 nhóm có 3 người, đã chi 42; lúc OUT 3 nhóm có 5 người, đã chi 30. Bộ 3: nhóm có s+1 người phải chia hết 8 và sau OUT 3 còn ít nhất 1 người, nên s=3 hoặc s=7. Bộ 4: chỉ biết nhóm có ít nhất 6 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ó s+2 người phải chia hết 60, và sau OUT 4 còn ít nhất 1 người nên s+2≥5. Bộ 2: không có khoản chi nào giữa hai lần IN/OUT, chỉ biết s−3≥1. Bộ 3: s+1 chia hết 97 và s≥1 nên s=96. Bộ 4: chỉ biết s≥1.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0