TLE-oj Cup Round 7 - Đoán số (Interactive)

Điểm: 1700 (thành phần)

Thời gian: 2.0s

Bộ nhớ: 256M

Input: bàn phím

Output: màn hình

Tác giả:

Sunlight

Dạng bài

Trong máy tính có hai số nguyên dương $A$ và $B$ , và bạn chỉ biết được số $B$ , nhưng bạn biết được rằng $A, B \le 2 \times 10^5$ . Bạn cần tìm số $A$ trong không quá $3$ thao tác giao tiếp với máy chấm. Với mỗi thao tác, bạn cần đưa ra một số $m \le 2 \times 10^{6}$ , và máy chấm sẽ trả về giá trị $A^B$ sau khi đã chia lấy dư cho $m$ .

Bài nộp của bạn được chấm qua các testcases. Trong mỗi testcase có thể có nhiều subtest, các subtest này được chấm điểm riêng biệt.

Hướng dẫn cách giao tiếp với máy chấm

Để câu trả lời của bạn có thể đến được với máy chấm, bạn cần phải flush output của mình ra. Sau đây là cách flush output ở một vài ngôn ngữ phổ biến

C++: cout << endl;.
Pascal: flush(output).
Python: stdout.flush().
Java: System.out.flush().

Để hiểu rõ hơn, bạn có thể đọc blog của codeforces tại đây: https://codeforces.com/blog/entry/45307

Lưu ý: Một số test/submit có thể có verdict Time limit exceed khi cả chương trình của bạn và máy chấm đều cùng muốn nhập input. Lúc này máy chấm và chương trình của bạn đều chờ output của nhau và sẽ hết thời gian.

Lưu ý: Bạn có thể chạy thử chương trình interactive trên máy của chính mình.

Input, Output và Subtasks

Interaction: (stdin / stdout)

Đầu tiên, chương trình của bạn cần nhập vào số nguyên dương $T \le 25$ - số subtest.
Với mỗi subtest, các hành động sau sẽ xảy ra:
- Đầu tiên, chương trình của bạn cần nhập vào số nguyên dương $b$ .
- Tiếp theo, bạn cần phải in ra một trong hai loại truy vấn ? m - được gọi là truy vấn hỏi - hoặc = a - được gọi là truy vấn trả lời, trong đó, ? m là truy vấn hỏi kết quả của phép tính $A^B \mod m$ , còn = a là truy vấn trả lời kết quả là $a$ .
- Nếu truy vấn bạn vừa xuất ra là truy vấn trả lời, bạn sẽ đến với subtest mới. Ngược lại, bạn cần nhập vào một số nguyên dương là kết quả phép tính $A^B \mod m$ và quay trở lại bước 2.

Scoring

Trong mỗi subtest:
- Bạn sẽ được tính $100\%$ số điểm của subtest đó khi trả lời đúng số $a$ và dùng $1$ truy vấn hỏi.
- Bạn sẽ được tính $20\%$ số điểm của subtest đó khi trả lời đúng số $a$ và dùng $2$ truy vấn hỏi.
- Bạn sẽ được tính $4\%$ số điểm của subtest đó khi trả lời đúng số $a$ và dùng $3$ truy vấn hỏi.
- Nếu đã dùng hết $3$ truy vấn hỏi trong một subtest, bạn phải đưa ra câu trả lời. Nếu dùng đến truy vấn hỏi thứ tư hoặc output không đúng format bạn sẽ bị tính $0$ điểm cả testcase.
- Nếu trả lời sai số $a$ , bạn sẽ không có điểm cho subtest đó.
Điểm của testcase sẽ là điểm trung bình của tất cả các subtest. Nếu số điểm của testcase bàng $1$ thì sẽ có verdict Accepted, ngược lại sẽ có verdict Wrong answer.

Có $20\%$ số testcase, mà trong đó, ở mỗi subtest, $B = 1$ .
Các testcase còn lại $(80\%)$ không có giới hạn gì thêm.

Sample

Interaction: (stdin / stdout)

Máy chấm	Chương trình nộp	Giải thích
`2`		$T=2$ , testcase này có 2 subtest.
`3`		Ở subtest đầu tiên, $B=3$
	`? 5`	Bạn thử với $m = 5$
`3`		$A^3 \mod 5 = 3$
	`= 2`	Bạn đoán $A = 2$ , và may mắn đúng. Bạn được $100\%$ số điểm của subtest đầu tiên.
`2`		Ở subtest thứ hai, $B=2$
	`? 5`	Bạn thử với $m = 5$
`0`		$A^2 \mod 5 = 0$
	`? 7`	Bạn thử với $m = 7$
`2`		$A^2 \mod 7 = 2$
	`= 10`	Bạn đoán $A = 10$ , và may mắn đúng. Bạn được $20\%$ số điểm cho subtest thứ hai.

Chung cuộc bạn được $60\%$ số điểm của testcase.

Bình luận

Không có bình luận nào.