33OJ
登录 注册

#P4520. [COCI 2017/2018 #4] Izbori

    ID: 5286 远端评测题 3000ms 64MiB 尝试: 0 已通过: 0 显示难度普及 上传者: 标签>2017Special JudgeCOCI(克罗地亚)

[COCI 2017/2018 #4] Izbori

题目描述

在一个遥远的民主发达的土地上,正在进行足球协会的总统选举。这个土地由 NN 个县组成,每个县都有自己的足球协会。有 MM 名总统候选人,编号为 1,2,…M1, 2,\dots M。每个足球协会将选择一个候选人投票。选举的获胜者是获得最多选票的候选人。如果有多个候选人获得最多选票,获胜者是编号最小的候选人。

在竞选期间,候选人访问了各个县,试图赢得他们的支持。在会见了所有候选人后,每个县的足球协会确定了他们为每个候选人投票的顺序。

例如,假设选举中有四名候选人,一个县的投票顺序是 2,1,4,32, 1, 4, 3。这意味着,除非 22 撤回候选资格,编号为 22 的候选人将获得该县的选票。如果候选人 22 撤回候选资格,而候选人 11 仍在竞选中,那么他们将获得选票,依此类推。

Zdravko 是一个热情的足球迷,也是编号为 KK 的候选人的密友。他想知道如果没有候选人撤回候选资格,哪位候选人将获胜。

他还想知道他必须说服多少名候选人撤回候选资格,才能让他的朋友,候选人 KK,成为足球协会的主席。

Zdravko 目前正在处理其他问题,所以他希望你能回答这些问题。

输入格式

输入的第一行包含任务中的数字 N(1≤N≤100)N (1 \le N \le 100), M(1≤M≤15)M (1 \le M \le 15) 和 K(1≤K≤M)K (1 \le K \le M)。

接下来的 NN 行中的每一行包含各县足球协会给出的投票顺序,即前 MM 个自然数的一个排列。

输出格式

你必须输出任务中问题的答案,每个答案占一行。

3 4 1
3 4 1 2
4 2 3 1
3 4 2 1
3
3
4 1 1
1
1
1
1
1
0
4 4 4
2 3 1 4
2 3 1 4
1 3 2 4
4 3 2 1
2
3

提示

输出必须由两个非空行组成,每行包含一个整数。每个问题的正确答案在该测试用例中占 50%50\% 的分数。(不会做 spj 没用)

第一个测试用例的说明:

选举所在的土地由 33 个县组成,有 44 名候选人竞选协会主席。如果没有候选人撤回候选资格,候选人 33 将以两票赢得选举。候选人 11 只有在所有其他候选人撤回候选资格时才会获胜。

第二个测试用例的说明:

只有一个候选人,即 Zdravko 的朋友,所以他们肯定会赢。

题面翻译由 ChatGPT-4o 提供。