JOI 2014 - Vote
Xem PDFMột đại hội thể thao mang tầm thế giới sẽ được tổ chức tại Tokyo vào năm 20XX. Thi lập trình được yêu thích như một môn thể thao trên toàn thế giới và có khả năng được đưa vào đại hội. Sau khi tìm hiểu về hội đồng xét chọn các môn thi, ta biết được những thông tin sau.
Một danh sách gồm \(N\) môn thi ứng viên đã được lập cho hội đồng, sắp xếp theo thứ tự từ thú vị nhất đến ít thú vị nhất. Môn ở vị trí thứ \(i\) từ trên xuống là môn thú vị thứ \(i\) và được gọi là môn thi \(i\). Danh sách còn ghi chi phí \(A_i\) cần thiết để tổ chức môn thi \(i\).
Hội đồng gồm \(M\) thành viên, được đánh số từ \(1\) đến \(M\). Thành viên \(j\) có ngưỡng chi phí riêng là \(B_j\) và bỏ một phiếu cho môn thú vị nhất trong số các môn có chi phí tổ chức không vượt quá \(B_j\).
Với ngưỡng chi phí của mỗi thành viên, luôn có ít nhất một môn thi có chi phí tổ chức không vượt quá ngưỡng đó. Vì vậy, tất cả thành viên đều bỏ đúng một phiếu. Có duy nhất một môn thi nhận được nhiều phiếu nhất.
Cho danh sách các môn thi và thông tin về các thành viên hội đồng, hãy viết chương trình tìm số hiệu của môn thi nhận được nhiều phiếu nhất.
Dữ liệu vào
Dữ liệu vào gồm \(1 + N + M\) dòng:
- Dòng đầu tiên chứa hai số nguyên \(N, M\), lần lượt là số môn thi và số thành viên hội đồng.
- Dòng thứ \(i\) trong \(N\) dòng tiếp theo (\(1 \le i \le N\)) chứa số nguyên \(A_i\), là chi phí cần thiết để tổ chức môn thi \(i\).
- Dòng thứ \(j\) trong \(M\) dòng tiếp theo (\(1 \le j \le M\)) chứa số nguyên \(B_j\), là ngưỡng chi phí của thành viên \(j\).
Dữ liệu ra
In ra một dòng chứa số hiệu của môn thi nhận được nhiều phiếu nhất.
Ràng buộc
- \(1 \le N \le 1000\).
- \(1 \le M \le 1000\).
- \(1 \le A_i \le 1000\) với mọi \(1 \le i \le N\).
- \(1 \le B_j \le 1000\) với mọi \(1 \le j \le M\).
- Mỗi thành viên đều có thể bỏ đúng một phiếu theo quy tắc đã nêu.
- Có duy nhất một môn thi nhận được nhiều phiếu nhất.
Ví dụ
Ví dụ 1
Input
4 3
5
3
1
4
4
3
2
Output
2
Giải thích
Có \(4\) môn thi và \(3\) thành viên hội đồng. Chi phí của các môn thi trong danh sách lần lượt là \(5, 3, 1, 4\).
- Thành viên \(1\) có ngưỡng chi phí là \(4\). Trong các môn có chi phí không vượt quá \(4\), môn thú vị nhất là môn \(2\).
- Thành viên \(2\) có ngưỡng chi phí là \(3\). Trong các môn có chi phí không vượt quá \(3\), môn thú vị nhất là môn \(2\).
- Thành viên \(3\) có ngưỡng chi phí là \(2\). Trong các môn có chi phí không vượt quá \(2\), môn thú vị nhất là môn \(3\).
Do đó, môn \(2\) nhận được \(2\) phiếu và môn \(3\) nhận được \(1\) phiếu. Môn \(2\) nhận được nhiều phiếu nhất, nên in ra \(2\).
Ví dụ 2
Input
6 6
3
1
4
1
5
9
2
6
5
3
5
9
Output
1
Giải thích
Môn \(1\) nhận được \(5\) phiếu và môn \(2\) nhận được \(1\) phiếu. Môn \(1\) nhận được nhiều phiếu nhất, nên in ra \(1\).
Kỳ thi:
- JOI 2013/2014 - Vòng sơ khảo (1 Tháng 1., 2014)
Bình luận