Đề bài

Bạn đang đứng trước chiếc két mở, tay cầm một tấm huy chương. Nhưng niềm vui nhanh chóng biến thành tuyệt vọng: một thông điệp trên chiếc cà vạt trong phòng tiết lộ rằng trợ lý đã báo kế hoạch của bạn cho Ủy ban Khoa học. Hai chủ tịch Ủy ban đang ẩn trong tòa nhà để ngăn bạn trốn thoát.

May mắn là bạn còn \(R\) rô-bốt hút bụi sau giao dịch với các thí sinh khác. Bạn muốn dùng chúng để xác định vị trí của hai chủ tịch trong số \(1\,000\) vị trí có thể có. Mỗi rô-bốt có thể được giao thăm dò nhiều vị trí, nhưng chỉ cho biết liệu có ít nhất một chủ tịch ở một trong các vị trí đã thăm dò hay không.

Mỗi rô-bốt cần trọn một giờ để thăm dò rồi quay lại. Vì pin sẽ cạn, mỗi rô-bốt chỉ được cử đi đúng một lần. Bạn muốn biết vị trí hai chủ tịch sau không quá \(H\) giờ; do đó, có thể phải cử nhiều rô-bốt đi cùng lúc trước khi các rô-bốt trước đó trở về. Hai chủ tịch không thay đổi vị trí trong suốt quá trình.

Hãy lập kế hoạch thăm dò và xác định vị trí của cả hai chủ tịch.

Giao tiếp

Đây là bài giao tiếp. Bạn phải nộp mã nguồn C++ cài đặt hàm scout và khai báo giao diện bằng cách #include "avoid.h":

std::pair<int, int> scout(int R, int H);

Với mỗi bộ kiểm thử, trình chấm gọi scout(R, H) đúng một lần. Hàm phải trả về cặp \((a,b)\) với \(1\le a,b\le1\,000\), là vị trí của hai chủ tịch. Hai chủ tịch được phép ở cùng một vị trí, tức là có thể có \(a=b\); thứ tự của \(a\) và \(b\) không quan trọng.

Trong scout, bạn có thể gọi hai hàm do trình chấm cung cấp.

Hàm send

void send(std::vector<int> P);

Hàm này cử một rô-bốt thăm dò các vị trí \(P[0],P[1],\ldots,P[k-1]\), trong đó \(k\) là độ dài của P.

• Mỗi phần tử của P phải nằm trong đoạn từ \(1\) đến \(1\,000\).
• Các phần tử của P phải đôi một khác nhau.
• Có thể gọi send nhiều nhất \(R\) lần trong mỗi bộ kiểm thử.
• Một rô-bốt được cử đi sẽ trở về sau đúng một lời gọi wait tiếp theo.

Hàm wait

std::vector<int> wait();

Hàm này chờ một giờ và trả về một mảng chứa đúng một phần tử cho mỗi rô-bốt đã được cử đi trong giờ vừa qua, tức là bởi các lời gọi send sau lời gọi wait trước đó hoặc sau khi chương trình bắt đầu.

Phần tử thứ \(i\) bằng 1 nếu rô-bốt thứ \(i+1\) trong nhóm đó phát hiện ít nhất một chủ tịch tại các vị trí nó thăm dò, và bằng 0 nếu không. Có thể gọi wait nhiều nhất \(H\) lần trong mỗi bộ kiểm thử.

Nếu một lời gọi không thỏa các yêu cầu trên, chương trình bị dừng ngay và bộ kiểm thử đó bị chấm sai.

Không được đọc từ đầu vào chuẩn hoặc ghi ra đầu ra chuẩn. Làm vậy có thể nhận kết quả Security violation!. Bạn được phép ghi ra luồng lỗi chuẩn (stderr).

Phân nhóm

• Subtask 1 (10 điểm): \(R=10\), \(H=1\) và hai chủ tịch ở cùng một vị trí.
• Subtask 2 (5 điểm): \(R=H=20\).
• Subtask 3 (10 điểm): \(R=30\), \(H=2\).
• Subtask 4 (75 điểm): \(R=75\), \(H=1\).

Trong Subtask 4, điểm thực nhận phụ thuộc vào số rô-bốt lớn nhất \(r_{\max}\) được cử đi trên mọi bộ kiểm thử của subtask. Điểm là hàm tuyến tính từng đoạn đi qua các mốc sau:

Với \(r_{\max}\le26\), bạn nhận đủ \(75\) điểm. Giữa hai mốc liên tiếp, điểm giảm tuyến tính; số điểm chính xác cho từng giá trị nguyên được cung cấp trong tệp score_table.txt của bộ đính kèm chính thức.

![Đồ thị điểm thành phần theo số rô-bốt lớn nhấthttps://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_7_ce6afdb9.png

Ví dụ giao tiếp

Xét một bộ kiểm thử có \(R=75\), \(H=20\), trong đó hai chủ tịch ở vị trí \(13\) và \(37\). Trình chấm gọi scout(75, 20). Một phiên giao tiếp có thể diễn ra như sau:

Trả về {37, 13} cũng được chấp nhận.

Các truy vấn trong ví dụ thực ra chưa đủ để xác định chắc chắn hai vị trí: chẳng hạn, cả hai chủ tịch cùng ở vị trí \(37\), hoặc một người ở \(13\) và người kia ở \(100\), đều phù hợp với mọi kết quả wait. Vì vậy, trình chấm cũng có thể bác bỏ chiến lược này bằng cách lựa chọn vị trí thích nghi khác.

Trình chấm mẫu

Để thử chương trình cục bộ, liên kết lời giải với sample_grader.cpp và avoid.h.

Trình chấm mẫu đọc bốn số nguyên \(R\), \(H\), \(a\), \(b\), trong đó \(a,b\) là hai vị trí cố định, rồi gọi scout(R,H) và in biên bản mọi hàm mà chương trình gọi. Khi kết thúc, nó in một trong các thông báo:

• Invalid input: dữ liệu cho trình chấm không đúng định dạng.
• Invalid send: đối số của send không hợp lệ.
• Out of robots: chương trình gọi send quá \(R\) lần.
• Out of time: chương trình gọi wait quá \(H\) lần.
• Wrong answer: cặp trả về không phải hai vị trí của chủ tịch.
• Correct: r robot(s) used, h hour(s) passed: câu trả lời đúng, chương trình đã gọi send \(r\) lần và wait \(h\) lần.

Trình chấm chính thức chỉ trả về Not correct, Security violation! hoặc thông báo thành công. Trình chấm chính thức có tính thích nghi: vị trí hai chủ tịch có thể phụ thuộc vào hành vi của chương trình trong lần chạy hiện tại cũng như các lần chạy trước. Cả trình chấm mẫu lẫn trình chấm chính thức đều tự động dừng chương trình ngay khi phát hiện lỗi.