Tương tác (cơ bản)
Xem dạng PDFĐây là một bài toán tương tác với máy chấm
Bạn cần tìm một số nguyên dương ~x~ có giá trị nằm trong đoạn ~[1,10^9]~. Bạn được phép hỏi máy chấm một số câu hỏi. Với mỗi câu hỏi, bạn đưa ra hai số nguyên dương ~l,r\ (1\le l\le r\le 10^9)~, sau đó máy chấm sẽ trả về 1 nếu như số ~x~ cần tìm nằm trong đoạn ~[l,r]~; ngược lại, máy chấm trả về 0.
Dữ liệu vào
Mỗi test bao gồm nhiều trường hợp thử nghiệm. Dòng đầu tiên gồm một số nguyên dương ~t\ (1\le t\le 69)~ là số trường hợp thử nghiệm. Sau đó là mô tả của các trường hợp thử nghiệm.
Tương tác
Để thực hiện một câu hỏi, in ra dữ liệu trên duy nhất một dòng theo định dạng ? l r ~(1\le l\le r\le 10^9)~. Sau đó, bạn cần nhập từ chương trình chấm một trong hai kết quả sau:
- Nếu số ~x~ cần tìm nằm trong đoạn ~[l,r]~, bạn sẽ nhận về giá trị
1. - Nếu số ~x~ cần tìm không nằm trong đoạn ~[l,r]~, bạn sẽ nhận về giá trị
0.
Để đưa ra kết quả, in ra dữ liệu trên một dòng có dạng ! x ~(1\le x\le 10^9)~. Sau đó, bạn cần nhập từ chương trình chấm một trong hai kết quả sau:
- Nếu số bạn đưa ra bằng chính xác số ~x~ cần tìm, bạn sẽ nhận về giá trị
1. Khi đó, chương trình của bạn sẽ chuyển sang trường hợp thử nghiệm tiếp theo hoặc kết thúc nếu như bạn đã trả lời chính xác hết các trường hợp thử nghiệm. - Nếu số bạn đưa ra không phải số ~x~ cần tìm, bạn sẽ nhận về giá trị
0. Lúc này, bạn cần dừng chương trình ngay lập tức và phải nhận ~0~ điểm cho test đó.
Sau khi thực hiện thao tác hỏi hoặc trả lời, chương trình cần flush (đẩy) dữ liệu (lệnh tương tác) ra luồng đầu ra chuẩn trước khi đọc câu trả lời từ máy chấm. Lệnh flush dữ liệu cho một số ngôn ngữ được cho trong bảng dưới đây:
| Ngôn ngữ | Lệnh flush |
|---|---|
| C++ | fflush(stdout); hoặc cout << flush; hoặc cout << endl; |
| C | fflush(stdout); |
| Python | sys.flush (stdout) (lưu ý cần import sys trước) |
| Java | stdout.flush () |
| Pascal | Flush (output); với output là phần dữ liệu bạn cần xuất ra |
Lưu ý: Trình chấm của bài này mang tính thích ứng. Nói một cách khác, giá trị ~x~ cần tìm sẽ không được cố định trước với mọi trường hợp thử nghiệm của từng test. Tuy nhiên, với cách trả lời của máy chấm, sẽ luôn tồn tại ít nhất một số ~x~ thỏa mãn tất cả đáp án mà máy chấm trả về.
Cách tính điểm
Giả sử test có tối đa ~1~ điểm.
Nếu như bạn đưa ra kết quả sai trong một trường hợp thử nghiệm của một test, bạn sẽ nhận được ~0~ điểm của toàn bộ test đó. Ngược lại, cách tính điểm như sau:
- Với mỗi trường hợp thử nghiệm, gọi ~cnt~ là số lần bạn thực hiện thao tác hỏi. Khi đó, điểm của trường hợp thử nghiệm đó sẽ là ~min(1,(\frac{69-cnt}{42})^2)~.
- Điểm của một test bằng trung bình cộng tổng điểm của tất cả trường hợp thử nghiệm của test đó.
Ví dụ
| Chương trình | Máy chấm | Giải thích |
|---|---|---|
1 |
Bộ test chỉ có ~1~ trường hợp thử nghiệm. Trong trường hợp thử nghiệm này, bạn cần đoán số ~x=6~ | |
? 6 9 |
Bạn hỏi xem ~x~ có nằm trong đoạn ~[6,9]~ không | |
1 |
Do ~x=6~ nằm trong đoạn ~[6,9]~ nên máy chấm trả về 1 |
|
? 2 4 |
Bạn hỏi xem ~x~ có nằm trong đoạn ~[2,4]~ không | |
0 |
Do ~x=6~ không nằm trong đoạn ~[2,4]~ nên máy chấm trả về 0 |
|
! 6 |
Bạn đoán giá trị ~x~ cần tìm bằng ~6~ | |
1 |
Do bạn đã đoán chính xác giá trị ~x~ cần tìm nên máy chấm trả về 1. Chương trình kết thúc do bạn đã trả lời đúng tất cả trường hợp thử nghiệm |
Với test này, trong trường hợp thử nghiệm duy nhất, chương trình đã thực hiện ~2~ câu hỏi nên điểm của trường hợp thử nghiệm đó (cũng là điểm của test) sẽ bằng ~min(1,(\frac{69-2}{42})^2)=min(1,(\frac{67}{42})^2)=min(1,2.5447...)=1~.
Lưu ý: Test ví dụ chỉ minh họa cách hoạt động của máy chấm, không mang tính gợi ý bất kỳ điều gì liên quan đến cách giải bài toán này.
Bình luận