[USACO Mar]参加考试

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file teststr.in Output file teststr.out

【题目描述】


Farmer John要参加一年一度的农民资格考试。考试很简单,只有N个 (1≤N≤1,000,000)true/false的判断题。然而FJ去年考试却“杯具”了,Bessie:希望今年能帮帮他。

Bessie得到可靠的内部消息,有可能有T_1,T_2,T_3,...,或T_K(0≤T_i≤N;0≤K≤10,000)

道题的答案为ture:,但具体哪道题的答案是什么却不知道。Bessie希望知道在认真研究了这些内部消息后(虽然不能确定任何一道题的具体答案),一定保证FJ考试时能获得的最高分数是多少?

为了说明Bessie的想法,考虑N=6的一次考试,Bessie知道答案为true的题的数量是0或者3。FJ可以按这样的做题策略来答对至少3题:如果FJ全部答'false',那么当有0道题的正确答案是'true',则FJ答对6题;而当有3道题的正确答案是'true',则FJ答对3题。因此,只要FJ部答'false',那么至少一定能答对3题,尽管FJ并不知道每道题的确切答案。

另一方面,考虑如果FJ选择了另一种非最优的做题策略:他猜测某3道题为'true'而另3道题为'false'。当所有题目的正确答案是'false'时,那么FJ能答对3道题。而当有3道题的正确答案是'true'时,那么FJ有可能一道题都答不对。这是因为FJ有可能把3道正确答案为'true'的题全猜成'false'!这说明这种做题策略不如前一种优秀。

给出Bessie获得的内部消息,计算出FJ采用最优做题策略保证能得到的最高分数是多少?


【输入格式】


第1行:2个整数N,K

第2…K+1行:第i+1行包含一个整数t_i


【输出格式】

第1行:一个整数,表示FJ一定能获得的最高分数

【样例输入】

6 2
0
3

【样例输出】

3

【提示】

在此键入。

【来源】

在此键入。