Đây là một bài toán giao tiếp. Lưu ý rằng chỉ có C++ được phép sử dụng cho bài toán này.
Takina và Chisato đang ở một hội chợ trái cây. Sau một ngày chụp ảnh với những người hóa trang thành trái cây yêu thích, họ tình cờ gặp một gian hàng trò chơi.
Các quy tắc của trò chơi như sau: Có $n$ loại trái cây, mỗi loại có một nhãn phân biệt từ $1$ đến $n$. Chính xác một trong số các loại trái cây là chanh, nhưng cả Takina và Chisato đều chưa biết đó là loại nào. * Takina sẽ được đưa cho tất cả $n$ loại trái cây lần lượt từng cái một. Mục tiêu của cô là truyền đạt nhãn của quả chanh cho Chisato (người bị bịt mắt trong quá trình này).
Trước khi nhận bất kỳ loại trái cây nào, Takina được cung cấp một mảng $p$, đại diện cho thứ tự xuất hiện của các nhãn trái cây. $p[1]$ sẽ là nhãn của quả trái cây đầu tiên, $p[2]$ sẽ là nhãn của quả trái cây thứ hai, và cứ tiếp tục như vậy. Sau đó, Takina sẽ viết ra một chuỗi nhị phân $b$ chỉ chứa các số $0$ và $1$. Chuỗi này không được dài quá $5000$ ký tự, nhưng có thể để trống. Gọi $x$ là độ dài của $b$.
Sau đó, các loại trái cây được đưa cho Takina lần lượt từng cái một theo thứ tự đã nêu. Khi nhận mỗi loại trái cây, Takina được thông báo liệu đó có phải là quả chanh hay không. Nếu trái cây đó không phải là chanh, Takina có thể chọn ăn hoặc không ăn nó. Quyết định này phải được đưa ra trước khi nhận quả trái cây tiếp theo và không thể thay đổi. Nếu trái cây đó là chanh, Takina không được ăn nó.
Gọi $y$ là tổng số trái cây mà Takina đã ăn.
Cuối cùng, Chisato nhận được chuỗi $b$ và danh sách các nhãn của những loại trái cây chưa được ăn (đã được sắp xếp). Sử dụng thông tin này, Chisato phải xác định nhãn của quả chanh.
Takina và Chisato đã quyết định chơi trò chơi này $t$ lần. Hãy thiết kế một chiến lược để họ xác định đúng quả chanh trong khi tối thiểu hóa cả $x$ và $y$.
Chi tiết cài đặt
Đây là một bài toán giao tiếp. Không đọc từ đầu vào chuẩn (standard input) hoặc ghi ra đầu ra chuẩn (standard output).
Bạn cần cài đặt ba thủ tục.
Đối với Takina, bạn nên cài đặt:
std::string init(int subtask, int n, std::vector<int> p)subtask: chỉ số của nhiệm vụ con mà trường hợp kiểm thử thuộc về.n: số lượng trái cây.p: một mảng có độ dài $n + 1$ trong đó:- $p[0] = 0$, và
- với mỗi $1 \le i \le n$, $p[i]$ là nhãn của quả trái cây thứ $i$ sẽ được đưa cho Takina.
- Thủ tục này được gọi $t$ lần cho mỗi trường hợp kiểm thử, một lần vào đầu mỗi trò chơi.
Thủ tục này nên trả về chuỗi $b$, với độ dài từ $0$ đến $5000$ bao gồm cả hai đầu, chỉ chứa các số $0$ và $1$. Nếu một chuỗi có độ dài hoặc định dạng không hợp lệ được trả về, bạn sẽ nhận được kết quả Wrong Answer.
bool receive_fruit(int id, bool is_lemon)id: nhãn của quả trái cây được đưa cho Takina.is_lemon:truenếu trái cây được đưa là chanh,falsenếu ngược lại.- Thủ tục này được gọi $n$ lần cho mỗi trò chơi trong số $t$ trò chơi, một lần cho mỗi quả trái cây.
Thủ tục này nên trả về true nếu trái cây đó nên được ăn, và false nếu ngược lại. Nếu true được trả về khi is_lemon là true, bạn sẽ nhận được kết quả Wrong Answer.
Đối với Chisato, bạn nên cài đặt:
int answer(int subtask, int n, std::string b, std::vector<int> uneaten)subtask: chỉ số của nhiệm vụ con mà trường hợp kiểm thử thuộc về.n: số lượng trái cây.b: chuỗi được trả về bởiinit.uneaten: vectơ đã sắp xếp có độ dài $n - y + 1$ chứa các nhãn của những loại trái cây không bị Takina ăn, trong đó:uneaten[0] = 0, vàuneaten[i]là nhãn nhỏ thứ $i$ trong số các loại trái cây chưa ăn.
- Thủ tục này được gọi $t$ lần cho mỗi trường hợp kiểm thử, một lần vào cuối mỗi trò chơi.
Thủ tục này nên trả về một số nguyên, là nhãn của quả chanh. Nếu giá trị trả về không khớp với nhãn đúng, bạn sẽ nhận được kết quả Wrong Answer.
Trong quá trình chấm điểm thực tế, một chương trình gọi các thủ tục trên sẽ được chạy hai lần:
1. Trong lần chạy đầu tiên, các bước sau được thực hiện $t$ lần:
init được gọi một lần.
receive_fruit được gọi $n$ lần, theo thứ tự các loại trái cây được đưa cho Takina.
Chương trình của bạn có thể lưu trữ và giữ lại thông tin qua các lần gọi liên tiếp.
2. Trong lần chạy thứ hai, thứ tự của các trò chơi có thể khác với lần chạy đầu tiên. Đối với mỗi trò chơi trong số $t$ trò chơi:
answer được gọi một lần. Ngoài các tham số được truyền vào answer, chương trình của bạn không được truy cập thông tin từ lần chạy đầu tiên.
Vì thủ tục có thể được gọi nhiều lần, bạn nên chú ý đến ảnh hưởng của dữ liệu còn lại từ lần gọi trước đối với lần gọi hiện tại.
Nhiệm vụ con
Đối với tất cả các trường hợp kiểm thử, dữ liệu đầu vào sẽ thỏa mãn các giới hạn sau: $1 \le t \le 10\,000$ $n = 500$ $1 \le p[i] \le n$ với mọi $1 \le i \le n$ Có chính xác một quả chanh.
Đối với mỗi nhiệm vụ con, chương trình của bạn sẽ được chấm điểm khác nhau dựa trên độ dài của chuỗi Takina viết, $x$, và số lượng trái cây cô ấy ăn, $y$. Điểm số của bạn cho mỗi trường hợp kiểm thử được tính bằng cách sử dụng giá trị lớn nhất của $x$ trong tất cả $t$ trò chơi và giá trị lớn nhất của $y$ trong tất cả $t$ trò chơi.
| Nhiệm vụ con | Điểm số |
|---|---|
| 1 | Nếu $y > 2$, điểm của bạn là 0. Ngược lại, điểm của bạn là $10 \times \min \left( \frac{288}{x}, 1 \right)$. |
| 2 | Nếu $y > 9$, điểm của bạn là 0. Ngược lại, điểm của bạn là $30 \times \min \left( \frac{30}{x}, 1 \right)$. |
| 3 | Điểm của bạn là $60 \times \min \left( \frac{20}{x+y}, 1 \right)$. |
Ví dụ
Xét một trò chơi đơn lẻ ($t = 1$) với $n = 4$. Lưu ý rằng điều này không thỏa mãn các giới hạn đầu vào và chỉ được sử dụng ở đây cho mục đích minh họa.
Dữ liệu vào 1
(Dữ liệu ví dụ không được cung cấp trong tài liệu gốc, đây là cấu trúc mẫu)
Dữ liệu ra 1
(Kết quả ví dụ không được cung cấp trong tài liệu gốc, đây là cấu trúc mẫu)
Ghi chú
Trong ví dụ này, Takina ăn các loại trái cây có nhãn $3$ và $2$, vì vậy các loại trái cây chưa ăn là $\{1, 4\}$. Vectơ uneaten được truyền vào answer do đó là [0, 1, 4]. Sử dụng $b$ và uneaten, thủ tục answer trả về $4$, là nhãn của quả chanh. Chiến lược này đã có thể xác định đúng quả chanh với $x = 3$ và $y = 2$.
Testing
Bạn có thể tải xuống trình chấm điểm mẫu (grader.cpp), tệp tiêu đề (lemon.h) và mẫu giải pháp (lemon.cpp) trong phần đính kèm. Hai tệp đầu vào được cung cấp để bạn kiểm tra là sample1.txt và sample2.txt. Bạn có thể sử dụng các tập lệnh compile.sh để biên dịch và run.sh để chạy giải pháp của mình để kiểm tra.
Các bài kiểm tra người dùng CMS không được hỗ trợ cho bài toán này.
Sample Grader
Một trình chấm điểm mẫu được cung cấp để giúp bạn kiểm tra việc triển khai cục bộ. Không giống như trình chấm điểm chính thức, trình chấm điểm mẫu chỉ chạy chương trình của bạn một lần và không thay đổi thứ tự các bài kiểm tra đối với Takina và Chisato.
Input Format
Dòng đầu tiên của đầu vào chứa một số nguyên subtask.
Dòng thứ hai của đầu vào chứa một số nguyên t.
$t$ dòng tiếp theo của đầu vào, mỗi dòng mô tả một trò chơi. Mỗi trò chơi được mô tả bởi:
một dòng chứa hai số nguyên cách nhau bởi dấu cách $n$ và $l$, đại diện cho số lượng trái cây và nhãn của quả chanh, và
một dòng chứa $n$ số nguyên cách nhau bởi dấu cách $p[1], p[2], \dots, p[n]$.
Output Format
Trình chấm điểm mẫu xuất ra một số thực duy nhất đại diện cho phân số điểm được tính từ các giá trị của $x$ và $y$ trên tất cả các trò chơi.
Ghi chú
Các thông báo chẩn đoán bổ sung có thể được in ra lỗi chuẩn (standard error). Trình chấm điểm mẫu không mô phỏng hành vi của trình chấm điểm chính thức.