Phân Loại Số Bí Mật

Description

Xác định số nguyên bí mật trong đoạn từ $2$ đến $100$ là số nguyên tố hay hợp số chỉ bằng các câu hỏi chia hết.

Trạng thái cần tìm được bộ tương tác chọn trước khi phiên bắt đầu và không thay đổi trong suốt phiên. Lời giải không được đọc trực tiếp trạng thái này; mọi thông tin chỉ đến từ các phản hồi hợp lệ của giao thức bên dưới.

Interaction

Mỗi dòng chỉ chứa một số cần hỏi hoặc từ kết luận $prime/composite$. Lời giải phải flush sau mỗi dòng gửi đi.

Với truy vấn $q$, bộ tương tác trả yes nếu $q$ chia hết $x$, ngược lại trả no. Sau kết luận hợp lệ, phiên kết thúc ngay.

Kết luận đúng nhận AC; kết luận sai nhận WA. Truy vấn sai cú pháp, sai miền hoặc vượt $20$ câu hỏi nhận lỗi giao thức. Khi nhận $-1$ hoặc khi luồng vào kết thúc bất thường, chương trình phải dừng ngay. Mọi dòng truy vấn và đáp án đều phải được đẩy khỏi bộ đệm, chẳng hạn bằng endl hoặc cout.flush() trong C++.

Constraints

• Số bí mật $x$ thỏa $2\le x\le 100$. Lời giải được hỏi nhiều nhất $20$ số nguyên trong đoạn $2,\dots ,100$ trước khi kết luận.

Scoring

• Subtask small - $50$ điểm: mười hidden session đầu dùng kích thước nhỏ để kiểm tra mô hình giao thức và các trường hợp biên cơ bản.
• Subtask full - $50$ điểm: mười hidden session còn lại dùng toàn bộ giới hạn, gồm ít nhất hai session $upper-tail$ bổ sung cho nhau khi contract có nhiều đại lượng kích thước.
• Mỗi hidden session có giá trị $5$ điểm. Một session chỉ được tính điểm khi toàn bộ cuộc hội thoại kết thúc với verdict AC.

Example interaction

Mẫu E01

Lời giải -> Bộ tương tác: 2
Bộ tương tác -> Lời giải: yes
Lời giải -> Bộ tương tác: 3
Bộ tương tác -> Lời giải: no
Lời giải -> Bộ tương tác: 5
Bộ tương tác -> Lời giải: no
Lời giải -> Bộ tương tác: 7
Bộ tương tác -> Lời giải: no
Lời giải -> Bộ tương tác: 11
Bộ tương tác -> Lời giải: no
Lời giải -> Bộ tương tác: 13
Bộ tương tác -> Lời giải: no
Lời giải -> Bộ tương tác: 17
Bộ tương tác -> Lời giải: no
Lời giải -> Bộ tương tác: 19
Bộ tương tác -> Lời giải: no
Lời giải -> Bộ tương tác: 23
Bộ tương tác -> Lời giải: no
Lời giải -> Bộ tương tác: 29
Bộ tương tác -> Lời giải: no
Lời giải -> Bộ tương tác: 31
Bộ tương tác -> Lời giải: no
Lời giải -> Bộ tương tác: 37
Bộ tương tác -> Lời giải: no
Lời giải -> Bộ tương tác: 41
Bộ tương tác -> Lời giải: no
Lời giải -> Bộ tương tác: 43
Bộ tương tác -> Lời giải: no
Lời giải -> Bộ tương tác: 47
Bộ tương tác -> Lời giải: no
Lời giải -> Bộ tương tác: 4
Bộ tương tác -> Lời giải: no
Lời giải -> Bộ tương tác: 9
Bộ tương tác -> Lời giải: no
Lời giải -> Bộ tương tác: 25
Bộ tương tác -> Lời giải: no
Lời giải -> Bộ tương tác: 49
Bộ tương tác -> Lời giải: no
Lời giải -> Bộ tương tác: prime
Kết quả: AC

Giải thích: Số bí mật của phiên mẫu là 2: chỉ truy vấn 2 nhận yes, còn mọi số khác trong danh sách đều nhận no. Bộ đếm nhỏ hơn hai nên lời giải kết luận prime và được chấp nhận.