Sane's Monthly Algorithms Challenge: November 2008
You are a computer scientist for a popular online game which hosts one-on-one chess games between players across the world. After each game, the username of both players is recorded in the website's database, along with the username of the player who won.
The website has statistics for the Wins and Losses of each player. However, these statistics are poor representations since the most active members can increase their win count by 'picking' on bad players with low win-loss ratios. Some also cheat by playing against their own alternate accounts.
To help reduce this problem, they want to add an intelligent stat to each user, which indicates how many players the user "can" beat, given the playing history of all players and the following logical rule:
Player
- Player
has beat Player or - Player
has beat Player and Player can beat Player .
This statistic will hopefully provide an incentive for users to compete against better players, and to not repeatedly pick on the same person.
Your job is, given the database of playing history, generate the database containing this new statistical attribute for each player.
Input Specification
The first line contains an integer
The next
Output Specification
On the first line, output an integer
For each of the next
Sample Input
7
Jim Denise
Noobie111 AwesumChessPlyr1337
Gerald AwesumChessPlyr1337
AwesumChessPlyr1337 Denise
Denise 2GudAtChessLOL
2GudAtChessLOL AwesumChessPlyr1337
Jim Gerald
Sample Output
6
Jim 4
Gerald 3
Noobie111 3
Denise 2
2GudAtChessLOL 2
AwesumChessPlyr1337 2
Comments