2001 Canadian Computing Competition, Stage 2

Day 2, Problem 3: Election Night

The nation of Cicoci elects its president using a winner-take-all electoral vote system. Each of the N states has one electoral vote, and that vote is awarded to the candidate receiving the highest popular vote in that state. The candidate with the most electoral votes is elected president. If there is a tie, no president will be elected, a constitutional crisis will ensue and the country will be plunged into civil war.

As election returns are tabulated it becomes possible to determine the outcome of the vote in a number of states. But many remain too close to call. You have been retained by Cicoci Press (CP) to compute the possible winners and losers.

Input

The input may contain several test cases. The first line of each test case contains two positive integers: the number of states, followed by the number of candidates. Neither exceeds 100. For each state there is a line stating the number of candidates who might yet win the state, and a list of the identifiers of the candidates who might yet win the state. Candidates are identified by consecutive integers starting from 1.

Output

For each candidate numbered X, in ascending order, print one of the following messages, as appropriate. 
Candidate X will become president.
Candidate X may become president.
Candidate X will not become president.
Output a blank line after each test case. The input ends with a line indicating 0 states and 0 candidates.

Sample Input

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

Sample Output

Candidate 1 will not become president.
Candidate 2 may become president.
Candidate 3 will not become president.
Candidate 4 will not become president.
Candidate 5 will not become president.

All Submissions
Best Solutions


Point Value: 30
Time Limit: 2.00s
Memory Limit: 16M
Added: Apr 18, 2009

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Daniel on Apr 27, 2009 - 9:14:32 pm UTC help?
  • (0/0)
I can't seem to find and/or correct a problem in my code...
Could anyone help?

hansonw1 on Apr 27, 2009 - 10:35:03 pm UTC Re: help
  • (1/0)
This problem is more difficult than it seems: it requires use of network flow.

When considering if someone can win, the situation can be very complicated. Consider this:
  • 2 states that can vote for candidates 1 and 2
  • 1 state that can vote for just candidate 3.
No matter what, candidate 3 cannot win: although neither 1 nor 2 is guaranteed even a single vote, at least one of them will have a vote.