Ngân sách phép toán

Bối cảnh và bài toán

Trước khi cho một chương trình chạy trên hệ thống chấm, nhóm kỹ thuật muốn có một bộ lọc sơ bộ để loại những phương án có khối lượng công việc quá lớn. Bộ lọc không mô phỏng thời gian thực tế; nó chỉ dùng một mô hình số bước đơn giản dựa trên lớp độ phức tạp.

Với mỗi kịch bản, hệ thống biết kích thước dữ liệu n, số lần lặp lại toàn bộ tác vụ q, ngân sách tối đa B bước và một mã type mô tả lớp công việc:

• O1: f(n) = 1;
• OLOGN: f(n) = 1 + floor(log2(n));
• ON: f(n) = n;
• ONLOGN: f(n) = n * (1 + floor(log2(n)));
• ON2: f(n) = n * n.

Tổng số bước ước lượng của kịch bản là q * f(n).

Đây là mô hình học tập để luyện đọc complexity và whole workload; không phải phép quy đổi Big-O thành mili-giây.

Yêu cầu

Với mỗi kịch bản, in ACCEPT nếu tổng bước ước lượng không vượt quá B, ngược lại in REJECT.

Input

• Dòng 1: số kịch bản T.
• T dòng tiếp theo: n q B type.

Output

Với mỗi kịch bản, in một dòng ACCEPT hoặc REJECT.

Ràng buộc

• 1 <= T <= 2 * 10^5
• 1 <= n, q <= 10^6
• 1 <= B <= 10^18
• Với mọi kịch bản, q * n * n <= 10^18.

Chấm điểm

Ví dụ 1

Input

4
100000 1 200000 ON
100000 1 10000000 ON2
1000 100 2000000 ONLOGN
1 100 99 O1

Output

ACCEPT
REJECT
ACCEPT
REJECT

Giải thích. Kịch bản 1 cần 100000 bước. Kịch bản 2 cần 10^10 bước nên vượt ngân sách. Với n=1000, ta có 1+floor(log2 1000)=10, nên kịch bản 3 cần 100*1000*10=10^6 bước.

Ví dụ 2

Input

2
8 10 40 OLOGN
8 10 39 OLOGN

Output

ACCEPT
REJECT

Giải thích. 1+floor(log2 8)=4, nên mỗi kịch bản cần 10*4=40 bước. Ngân sách 40 vừa đủ, còn 39 thì không.

Thông tin bài tập

Nguồn: FULLHOUSE DEV — Self-generated.