Thi nhìn là một cuộc đấu kinh điển về khả năng giữ bình tĩnh: hai người nhìn vào mắt nhau trong khi giữ nét mặt điềm nhiên, tự tin. Mục tiêu là duy trì giao tiếp bằng mắt lâu hơn đối thủ. Cuộc đấu kết thúc khi một người mất bình tĩnh, thường là do nhìn đi chỗ khác, mỉm cười, nói chuyện hoặc bật cười.
Là huấn luyện viên đội tuyển quốc gia môn thi nhìn, bạn cần xác định khả năng giữ bình tĩnh của từng người trong số \(n\) thành viên để chuẩn bị cho vòng chung kết thế giới sắp tới. Vận động viên thứ \(i\) có thể duy trì giao tiếp bằng mắt trong đúng \(a_i\) giây, nhưng ban đầu bạn chưa biết các giá trị này. Chẳng hạn, đội của bạn có thể gồm \(n=3\) thành viên:
| \(i\) |
Tên |
\(a_i\) |
| \(1\) |
Anna |
\(431\) |
| \(2\) |
Esther |
\(623\) |
| \(3\) |
Tony |
\(121\) |
Khi vận động viên \(i\) và \(j\) thi đấu, cuộc đối đầu kéo dài đúng \(\min(a_i,a_j)\) giây. Khi đó, người yếu hơn mất bình tĩnh và cả hai bắt đầu mỉm cười, bật cười gần như ngay lập tức. Chẳng hạn, nếu Anna thi đấu với Esther thì cuộc đấu kéo dài \(431\) giây. Điều quan trọng là người quan sát bên ngoài không thể xác định ai thực sự thắng cuộc đối đầu (trong trường hợp này là Esther), mà chỉ đo được thời lượng cuộc đấu.
Mục tiêu của bạn là ước lượng các giá trị \(a_1,\ldots,a_n\) bằng ít cuộc đấu nhất có thể. Rõ ràng không thể xác định được sức mạnh của vận động viên mạnh nhất, nên bạn được phép ước lượng thấp hơn giá trị thực đối với một trong các \(a_i\).
Giao diện lập trình
Bài này sử dụng giao diện hàm C++17. Hãy nộp mã nguồn có #include "staringcontest.h" và cài đặt hàm sau; tệp tiêu đề staringcontest.h được cung cấp kèm bài:
C++std::vector<int> estimate_skills(int n);
Bộ chấm gọi estimate_skills(n) đúng một lần cho mỗi bộ kiểm thử, với \(n\) là số vận động viên. Trong khi thực hiện hàm này, bạn có thể gọi hàm do bộ chấm cung cấp:
C++int stare(int i, int j);
Mỗi lần gọi stare(i, j) tổ chức một cuộc đấu và trả về \(\min(a_i,a_j)\) dưới dạng int. Hai chỉ số được đánh số từ 1, phải thỏa mãn \(1\le i,j\le n\) và \(i\ne j\). Bạn được phép hỏi lại cùng một cặp; mỗi lần gọi vẫn tính là một truy vấn. Bộ chấm không thích nghi: các giá trị \(a_1,\ldots,a_n\) đã được xác định trước khi gọi estimate_skills.
Để kết thúc, estimate_skills phải trả về một std::vector<int> gồm đúng \(n\) giá trị ước lượng \(b_1,\ldots,b_n\), theo thứ tự vận động viên: phần tử ở chỉ số i - 1 chứa \(b_i\). Bài nộp đúng nếu \(b_i=a_i\) với mọi vận động viên \(i\), ngoại trừ nhiều nhất một người mà bạn được phép ước lượng thấp hơn. Chính xác hơn, phải có \(b_i\le a_i\) với mọi \(1\le i\le n\), và được phép có \(b_k\ne a_k\) với nhiều nhất một chỉ số \(k\). Không có cận dưới bổ sung cho các ước lượng kiểu int; một giá trị âm được phép nếu toàn bộ đáp án vẫn thỏa mãn quy tắc này. Không bắt buộc phải gọi stare nếu bạn đã có đáp án đúng. Trả về đáp án không tính là một truy vấn.
Không cài đặt main, không đọc stdin, không ghi stdout và không chèn mã nguồn bộ chấm vào bài nộp. Chỉ gọi stare trong lúc estimate_skills đang chạy. Chỉ số không hợp lệ, hai chỉ số bằng nhau hoặc lời gọi sau khi đã dùng \(3000\) truy vấn làm bộ chấm kết thúc chương trình ngay lập tức và bộ kiểm thử nhận \(0\) điểm; lời gọi đó không trả về giá trị báo lỗi và không ném ngoại lệ để bạn bắt. Trả về vector sai kích thước, có ước lượng lớn hơn giá trị thật hoặc có hơn một ước lượng thấp hơn cũng khiến bộ kiểm thử nhận \(0\) điểm. Sau khi hàm trả về, bộ chấm kiểm tra đáp án, tính điểm rồi kết thúc chương trình; bạn không cần gọi hàm kết thúc nào khác.
Giới hạn thực tế của bộ chấm: bạn phải trả về đáp án sau nhiều nhất 2999 lần gọi stare. Lần gọi thứ \(3000\) với chỉ số hợp lệ vẫn trả về thời lượng cuộc đấu, nhưng sau đó đáp án trả về từ estimate_skills bị từ chối và bộ kiểm thử nhận \(0\) điểm. Lần gọi thứ \(3001\) bị từ chối ngay lập tức. Quy tắc này áp dụng cho mọi nhóm kiểm thử.
Ràng buộc
- \(2\le n\le 1500\).
- \(1\le a_i\le 86\,400\) với mọi \(1\le i\le n\); các giá trị \(a_i\) đôi một khác nhau.
- Giới hạn công bố ban đầu là \(3000\) truy vấn, không tính việc trả về đáp án. Với bộ chấm dùng ở đây, đáp án chỉ được chấp nhận khi \(q<3000\), tức nhiều nhất \(2999\) lần gọi
stare, như giải thích ở trên.
Phân nhóm
Các bộ kiểm thử được chia thành các nhóm, mỗi nhóm có một số điểm. Để nhận được điểm của một nhóm, chương trình phải giải đúng tất cả các bộ kiểm thử trong nhóm đó. Điểm cuối cùng là điểm cao nhất của một lần nộp bài.
- \(9\) điểm: \(n\le 50\).
- \(11\) điểm: \(n\le 1000\).
- Từ \(0\) đến \(80\) điểm: \(1000<n\le 1500\).
Đối với nhóm 3, điểm của nhóm là điểm nhỏ nhất trong các bộ kiểm thử của nhóm. Điểm của mỗi bộ kiểm thử phụ thuộc vào số truy vấn đã dùng; dùng càng ít càng tốt. Công thức công bố ban đầu dưới đây dùng \(q\) là số truy vấn và giả sử đáp án đúng:
- Nếu \(q\le n+25\), bạn nhận đủ \(80\) điểm.
- Nếu \(q>3000\), bạn nhận \(0\) điểm.
- Trong các trường hợp còn lại, bạn nhận \(118.2-12\cdot\ln(q-n)\) điểm, làm tròn đến số nguyên gần nhất.
Ví dụ tính điểm ban đầu: với \(n=1500\) và \(q=3000\), công thức cho \(30\) điểm. Tuy nhiên, bộ chấm dùng ở đây từ chối đáp án ở \(q=3000\), nên trường hợp này thực tế nhận \(0\) điểm. Với \(n=1500\) và \(q=2999\), một đáp án đúng được chấp nhận và nhận \(30\) điểm. Do đó, công thức trên chỉ được áp dụng cho các đáp án hợp lệ với \(q\le 2999\); từ \(3000\) truy vấn trở lên, bộ kiểm thử luôn nhận \(0\) điểm.
Ví dụ gọi hàm
Trong bản ghi dưới đây, Bộ chấm gọi: chỉ lời gọi hàm của bạn; Bạn gọi: chỉ lời gọi stare; Bộ chấm trả về: chỉ kết quả của lời gọi đó; Bạn trả về: chỉ vector trả về cuối cùng của estimate_skills, viết theo cú pháp C++. Các nhãn chỉ để minh họa, không phải dữ liệu cần đọc hoặc in.
Ví dụ gọi hàm 1
Bộ chấm gọi: estimate_skills(3)
Bạn gọi: stare(1, 2)
Bộ chấm trả về: 431
Bạn gọi: stare(1, 3)
Bộ chấm trả về: 121
Bạn gọi: stare(3, 2)
Bộ chấm trả về: 121
Bạn trả về: {431, 431, 121}
Giải thích
Ví dụ gọi hàm này là một cách tương tác có thể xảy ra với đội tuyển được mô tả ở trên. Sức mạnh của Anna và Tony được xác định chính xác. Sức mạnh của Esther thì không thể xác định được.
