Pháo đài cổ (THT TQ 2013)

Xem PDF

Điểm: 250 (p) Thời gian: 10.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Trong những ghi chép cổ xưa có những thông tin về một pháo đài cổ ở thành Vinh trên bản đồ phẳng với hệ tọa độ Descartes vuông góc Oxy. Nền pháo đài có dạng hình chữ nhật với các cạnh song song với một trong hai trục tọa độ. Những khảo sát gần đây tại vị trí \((x_0, y_0)\) đã khẳng định chắc chắn vị trí \((x_0,y_0)\) nằm trong pháo đài cổ xưa.

Em được yêu cầu xác định vị trí ban đầu của nền pháo đài cổ bằng một robot hoạt động theo quy trình sau. Tại mỗi bước, em yêu cầu robot đào sâu xuống khảo sát tại một vị trí do em lựa chọn. Robot sẽ báo cáo có tìm thấy dấu vết của pháo đài cổ tại vị trí đó hay không? Vì chi phí của mỗi lần khảo sát khá lớn nên em cần yêu cầu robot khảo sát tại càng ít vị trí càng tốt.

Nhiệm vụ của em là viết một chương trình có tên CITADEL.*, sử dụng các lệnh được cung cấp để thực hiện khảo sát các vị trí, nhận kết quả khảo sát và đưa ra đánh giá về vị trí chính xác của khu pháo đài cổ.

Input

  • Hai số \(x_0, y_0\) được cho đầu chương trình.

Interaction

Để tương tác với máy chấm, em hãy in mỗi lệnh trên từng dòng. Câu trả lời sẽ được máy chấm in ra trên một dòng khác, và em đọc vào. Lưu ý, nhớ flush luồng ra chuẩn sau mỗi dòng được in ra bằng lệnh fflush(stdout) hoặc cout << endl;

Các lệnh được sử dụng:

  • find x y

Em chỉ được phép dùng lệnh này tối đa một triệu lần. Máy chấm in ra \(0\) hoặc \(1\):

+ 0 tương ứng với ***không*** tìm thấy dấu vết tại vị trí có tọa độ $(x,y)$. Nói cách khác là vị trí $(x,y)$ nằm phía ngoài nền pháo đài cổ.
+ 1 tương ứng với ***có*** tìm thấy dấu vết tại vị trí có tọa độ $(x,y)$. Nói cách khác là vị trí $(x,y)$ nằm ở phía trong hoặc trên biên nền của pháo đài cổ.
+ Nếu lệnh này được dùng quá một triệu lần, chương trình sẽ bị ngắt và ghi nhận $0$ điểm với test em đang chạy.
  • answer x1 y1 x2 y2

Lệnh này chỉ được in ra đúng 1 lần trước khi kết thúc chương trình để cho biết về kết quả mà em xác định được; trong đó \((x_1, y_1)\) là tọa độ góc trái dưới của nền pháo đài, \((x_2, y_2)\) là tọa độ góc phải trên của nền pháo đài.

Chương trình bắt buộc phải in lệnh answer một lần duy nhất, nếu không sẽ bị 0 điểm. Sau khi em in ra lệnh này, chương trình sẽ được ngắt.

Scoring

Bài thi của em được chấm trên \(20\) test, mỗi test tối đa \(5\) điểm.

  • Trong các test \(1,2,3,..,6\): tọa độ của pháo đài có giá trị tuyệt đối không vượt quá \(200\)
  • Trong các test \(7,8,9,...,13\): tọa độ của pháo đài có giá trị tuyệt đối không vượt quá \(2 \times 10^5\)
  • Trong các test còn lại \(14,14,15,...,20\): tọa độ của pháo đài có giá trị tuyệt đối không vượt quá \(2 \times 10^9\)

Với mỗi test, nếu chương trình của em in ra lệnh answer với các tham số không chính xác, chạy quá thời gian quy định hoặc gặp các lỗi dẫn tới dừng chương trình, bài làm sẽ nhận \(0\) điểm cho test đó. Ngược lại, bài làm sẽ nhận được số điểm trong khoảng từ \(1\) đến \(5\) cho test đó phụ thuộc vào số lần sử dụng lệnh find nhiều hay ít.

Example

Test 1

Input
3 1
1
0
0
1
1
1
0
0
0
Output
find 3 -1
find 3 -2
find -4 -1
find -1 1
find -3 1
find 8 2
find 9 3
find 9 1
find 7 3
answer -3 -1 8 2
Note


Bình luận

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