WC '16 Finals J1 - Fencing

View as PDF

Submit solution


Points: 5 (partial)
Time limit: 1.0s
Memory limit: 16M

Author:
Problem type
2016-17 Woburn Challenge Finals Round - Junior Division

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 \le N \le 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 S_{i,j} points, while cow j will score S_{j,i} points (0 \le S_{i,j}, S_{j,i} \le 10, S_{i,j} \ne S_{j,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 S_{i,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?

Input Specification

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 S_{i,1}, \dots, S_{i,N} (for i = 1 \dots N).

Output Specification

Output one line consisting of a single integer – the number of the cow who will be sent on the spy mission.

Sample Input

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

Sample Output

4

Sample Explanation

The 5 cows won 2, 2, 1, 3, and 2 matches, respectively. As such, cow 4 won the largest number of matches.


Comments

There are no comments at the moment.