917 - Euro 2004

All about problems in Volume 9. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

917 - Euro 2004

Post by Leonid » Tue Nov 07, 2006 1:18 am

I think that problem statement of this problem doesn't agree with input and output data but somehow one person have solved it.
Here is how the classification is made:

1. For a win 3 points will be awarded; for a tie, 1 point; for a defeat, 0 points
2. For establishing the final places, the following criteria will be applied, in descending order of priority:
* Number of points
* Goal-Average (difference between goals scored and given)
* Number of wins (victories)
* Number of goals scored

So after the games are taken in account, this parameters are all calculated. Things get interesting when there is more than one team with the same number of points. In that case, a sub-league is considered. You must now imagine that only the games between the tied teams count, and see the new sub-classification. If that does not break the tie (in points) for all the teams, you must do a sub-sub-league for all the teams that are still tied, and so on. There is only one case when a sub-league should not be partitioned. That is when all the teams in that sub-league have the same number of points and obviously, the partition would give the exact same group of teams and parameters. In that cases, teams should be ranked according to the four parameters calculated for that sub-league. If the parameters are not sufficient, then the teams should be considered to be in the same place, and they should appear in alphabetical order.
Sample input provided in the problem descriprion
6
portugal grecia 4 1
espanha russia 3 1
portugal russia 3 0
espanha grecia 1 2
portugal espanha 1 3
grecia russia 7 0
Corresponding sample output
1 portugal
2 espanha
3 grecia
4 russia
Explanation of sample input / output according to the problem description
Looking at the games, we see that "portugal", "espanha" and "grecia" made 6 points, and "russia" made 0 points (which automatically gives them the 4th place). A tie between the first three teams is achieved. A sub-league with only that three teams is then considered but in this sub-league all the three teams have 3 points. This tied group cannot be partitioned further and then the other parameters are considered. Since in that sub-league, "portugal" has the best goal-average, it achieves 1st place. Then comes "spain" (2nd goal-average) and finally "grecia". If necessary, the other parameters would have been taken in account.
Consider ranking of teams having 3 points:
portugal grecia 4 1
espanha grecia 1 2
portugal espanha 1 3
=> total scored / missed
portugal 5 - 4 (+1)
espanha 4 - 3 (+1)
grecia 3 - 5 (-2)
=> grecia takes 3rd place
ans we reconsider ranking again
portugal espanha 1 3
In that cases, teams should be ranked according to the four parameters calculated for that sub-league.
Then, we start again from the first parameter again.
espanha 3 pts
portugal 0 pts
=> final ranking is the following according to the problem description:
1. espanha
2. portugal
3. grecia
4. russia
=> but according to the sample output it is:
1 portugal
2 espanha
3 grecia
4 russia
Did I miss something or the problem description is wrong?

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Tue Nov 07, 2006 3:08 am

I've got accepted with the following interpretation of the problem statement:

If all teams in a sub-league have the same number of points, then they're sorted lexicographically by their parameters and names. Division into further sub-leagues is not performed.

Otherwise, if some teams got different number of points, teams are split into sub-leagues by their points, and then each of these sub-leagues is sorted as said above.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Fri Nov 24, 2006 11:33 am

There is one more thing to note:
The correct output for:

Code: Select all

2
brasil franca 0 0
grecia russia 7 0
should be

Code: Select all

1 grecia
2 brasil
2 franca
4 russia
and NOT

Code: Select all

1 grecia
2 brasil
2 franca
3 russia
That is, we have to skip some ranks if necessary.
BTW, these scores are just nonsense. :lol:

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am

Post by hamedv » Wed Aug 15, 2007 5:47 pm

I think it's an easy problem
can any one tell me why 8 people got AC on this problem

Post Reply

Return to “Volume 9 (900-999)”