2016-17 Woburn Challenge Finals Round - Junior Division
Problem 1: Fencing
Bo Vine, beloved leader of the peace-loving cows of Scarberia, has gotten wind that his land may be in danger. It seems that his long-time nemesis, the Head Monkey, may be planning to end their year-long armistice and lead her troops to invade Scarberia! To confirm this intelligence, Bo Vine will need to send in a spy to infiltrate the monkeys' ranks.
There are N (2 ≤ N ≤ 100) trained cow spies, numbered from 1 to N, any of whom would surely be able to complete the mission successfully. As such, Bo Vine will have them engage in a round robin fencing tournament, with the victor earning the honour of being sent on the mission. As it turns out, the cows are quite lazy, and none of them actually want to be chosen. As such, they'll all try their best to lose (without being too obvious about it), but at the end of the day, one of them is sure to win the largest number of fencing matches and be forced to go on the mission.
Over the course of the tournament, each of the N cows will partake in one match against each of the remaining N − 1 cows. During the match between each pair of distinct cows i and j, cow i will score Si, j points, while cow j will score Sj, i points (0 ≤ Si, j, Sj, i ≤ 10, Si, j ≠ Sj, i). Whichever of them scores more points than the other will be declared the winner of that match. Note that there are no ties. Also note that cows don't play against themselves, so Si, i is given to be 0 for each i.
At the conclusion of the tournament, the cow who has won the largest number of their N − 1 matches will be crowned the champion. It's guaranteed that there will be a unique cow with strictly the largest number of wins. Given the results of all of the matches, can you help Bo Vine determine the winner?
The first line of input consists of a single integer N.
N lines follow, the i-th of which consists of N space-separated integers Si, 1, …, Si, N (for i = 1..N).
Output one line consisting of a single integer – the number of the cow who will be sent on the spy mission.
5 0 4 0 9 2 5 0 9 2 2 9 0 0 0 0 1 4 9 0 2 1 6 9 1 0
The 5 cows won 2, 2, 1, 3, and 2 matches, respectively. As such, cow 4 won the largest number of matches.
Point Value: 5 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: May 07, 2017
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3