Farmer John phải thi giấy phép nông nghiệp hằng năm, gồm $N$ câu đúng/sai ($1 \le N \le 1,000,000$). Sau kết quả tệ năm ngoái, Bessie muốn giúp.
Bessie biết thông tin nội bộ rằng số câu đáp án đúng là một trong $t_{1}$, $t_{2}$, $t_{3}$, ..., $t_{K}$ ($0 \le t_i \le N; 0 \le K \le 10,000$), nhưng không biết đáp án câu cụ thể nào. Cô muốn điểm cao nhất bảo đảm bằng cách dùng thông tin cẩn thận, dù FJ không biết đáp án thực.
Xét $N=6$ câu với0 hoặc3 đáp án đúng. FJ bảo đảm ít nhất3 câu chính xác: đánh sai hết, nếu0 đáp án đúng thì chính xác6, nếu3 thì chính xác3. Vậy đánh sai hết bảo đảm ít nhất3 mà không biết đáp án.
Chiến lược tệ hơn là đoán3 đúng,3 sai. Nếu không đáp án nào đúng, chính xác3 câu đánh sai. Nếu3 đáp án đúng, có thể chính xác0: cả3 câu đánh đúng đều sai, còn3 câu kia đúng. Dù đánh sai hết có thể chính xác3, đoán3 đúng không bảo đảm nổi1 câu, nên không bảo đảm câu nào. FJ nên dùng chiến lược đoạn trước.
Theo thông tin Bessie, xác định số câu luôn bảo đảm chính xác khi sử dụng tối ưu.
Dữ liệu vào
- Dòng1: hai số nguyên cách nhau dấu cách $N$ và $K$.
- Các dòng $2..K+1$: dòng $i+1$ chứa một số nguyên $t_{i}$.
Dữ liệu ra
- Dòng1: một số nguyên, điểm tốt nhất bảo đảm cho FJ.
Ví dụ
Dữ liệu vào 1
6 2 0 3
Dữ liệu ra 1
3
Tác giả bài toán: Tom Conerly, 2010