시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 1024 MB | 13 | 5 | 5 | 100.000% |
Ranked choice voting, a way of determining the winner of an election, proceeds as follows:
A
, B
, C
, etc.) is placed on the ballot.B
first, then A
, then C
last) and submits that ranking as their vote.C
is eliminated before B
.)Spoiling refers to an additional candidate Z
entering a race, thereby causing the winner to switch from one existing candidate to another candidate (who is not Z
). Proponents of ranked choice voting claim that this type of election is less vulnerable to spoiling than the more common plurality voting (the candidate with the most votes wins).
You are candidate A
in an election against one or two other candidates, and you wish to prove them wrong by engineering a candidate Z
to enter the election and spoil it in your favor. Suppose you knew every voter's rankings for the existing candidates, and you were capable of engineering a candidate Z
such that you had full control over where each voter inserts Z
into their rankings. For a given set of such rankings, is it possible to engineer a candidate Z
to spoil the election in your favor?
The first line contains two integers $n$ ($1 \leq n \leq 1\,000$) and $k$ ($2 \leq k \leq 3$), where $n$ is the number of voters and $k$ is the number of existing candidates.
Each of the next $n$ lines contains $k$ space-separated capital letters (A
, B
, or C
) indicating the rankings of each voter from first to last place. Each line will list each candidate exactly once (when $k = 2$, C
is not present).
Output a single integer, $1$ if it is possible to create a candidate Z
who spoils the election in favor of candidate A
(or if A
would already win the election), 0 otherwise.
5 2 B A A B A B B A B A
1
1 3 A B C
1
8 3 A B C B C A B C A B C A C B A C B A C B A C B A
0
ICPC > Regionals > North America > North America Championship > North America Championship 2022 H번
Camp > Petrozavodsk Programming Camp > Summer 2022 > Day 1: Welcome Contest H번