网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[USACO Mar]参加考试
成绩 | 开启时间 | 2014年09月19日 星期五 10:07 | |
折扣 | 0.8 | 折扣时间 | 2014年09月26日 星期五 10:07 |
允许迟交 | 是 | 关闭时间 | 2014年09月26日 星期五 10:07 |
输入文件 | teststr.in | 输出文件 | 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
【提示】
在此键入。
【来源】
在此键入。