首页 > 试题广场 >

Spring Outing

[编程题]Spring Outing
  • 热度指数:3397 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
You class are planning for a spring outing. N people are voting for a destination out of K candidate places.
The voting progress is below:
First the class vote for the first candidate place. If more than half of the class agreed on the place, the place is selected. The voting ends.
Otherwise they vote for the second candidate place. If more than half of the class agreed on the place, the place is selected. The voting ends.
Otherwise they vote for the third candidate place in the same way and go on.
If no place is selected at last there will be no spring outing and everybody stays at home.
Before the voting, the Chief Entertainment Officer did a survey, found out every one's preference which can be represented as a permutation of 0, 1, ... K. (0 is for staying at home.) For example, when K=3, preference "1, 0, 2, 3" means that the first place is his first choice, staying at home is the second choice, the second place is the third choice and the third place is the last choice.
The Chief Entertainment Officer sends the survey results to the class. So everybody knows the others' preferences. Everybody wants his more prefered place to be selected. And they are very smart, they always choose the optimal strategy in the voting progress to achieve his goal.
Can you predict which place will be selected?

输入描述:
The first line contains two integers, N and K, the number of people in your class and the number of candidate places.
The next N lines each contain a permutation of 0~K, representing someone's preference.
For 40% of the data, 1 <= N, K <= 10
For 100% of the data, 1 <= N, K <= 1000


输出描述:
Output the selected place. Or "otaku" without quotes if no place is selected.

In the sample case, if the second peoson vote against the first place, no place would be selected finally because the first person must vote against the second place for his own interest. Considering staying at home is a worse choice than the first place, the second person's optimal strategy is voting for the first place. So the first place will be selected
示例1

输入

2 2
1 0 2
2 1 0

输出

1
头像 觞乄默
发表于 2022-10-12 20:45:45
这个博弈题很类似于“海盗分金”问题,从前往后考虑是行不通的,应该自底而上求解每轮的结果。如果我们从第1轮入手,并不知道,后面将会出现什么样的结果,从而无法确定每个voter的策略。但是,我们先假设投票能够进入最后一轮(cantidate K)。如果这轮赞成不过半,那么最终投票结果一定为0。所以在这轮 展开全文

问题信息

难度:
21条回答 8985浏览

热门推荐

通过挑战的用户

查看代码