Farmer John doit passer l’examen annuel de licence agricole, avec $N$ questions vrai/faux ($1 \le N \le 1,000,000$). Après son mauvais résultat l’an dernier, Bessie veut l’aider.
Bessie sait de source interne que le nombre de réponses vraies vaut l’un de $t_{1}$, $t_{2}$, $t_{3}$, ..., $t_{K}$ ($0 \le t_i \le N; 0 \le K \le 10,000$), sans connaître aucune réponse précise. Elle cherche le meilleur score garanti à FJ s’il exploite soigneusement ces informations, même sans connaître les réponses réelles.
Prenons $N=6$ questions, avec0 ou3 réponses vraies. FJ garantit au moins3 bonnes réponses : s’il répond faux partout,0 vraies donne6 bonnes réponses,3 vraies donne3. Ainsi, sans connaître de réponse, tout cocher faux garantit au moins3.
Considérons une stratégie inférieure : deviner3 vraies et3 fausses. Si aucune n’est vraie, les3 cochées fausses sont correctes. Si3 sont vraies, il peut obtenir0 : les3 cochées vraies sont fausses et les3 autres sont vraies. Tout cocher faux aurait donné3, mais choisir3 vraies ne garantit même pas1 bonne réponse. Cette stratégie n’en garantit aucune. FJ doit utiliser celle du paragraphe précédent.
Avec les informations de Bessie, déterminez le nombre de bonnes réponses toujours garanti en les exploitant au mieux.
Entrée
- Ligne1 : deux entiers séparés par un espace $N$ et $K$.
- Lignes $2..K+1$ : ligne $i+1$ contient un entier $t_{i}$.
Sortie
- Ligne1 : un entier, le meilleur score garanti à FJ.
Exemples
Entrée 1
6 2 0 3
Sortie 1
3
Auteur du problème : Tom Conerly, 2010