## 4094 - WonderTeam

Do you want to discuss about these problems? Go now!
Users are shared (no need to re-register).

Moderator: Board moderators

armansuleimenov
New poster
Posts: 15
Joined: Tue Sep 25, 2007 3:07 am
Location: Astana, Kazakhstan
Contact:

### 4094 - WonderTeam

I have been trying to solve this problem
http://acmicpc-live-archive.uva.es/nuev ... php?p=4094
from "Asia - Tehran - 2007/2008" since early morning.

I think greedy should work. According to my observations, the wonderteam should have 0 draws not to increase its points count. Hence, we need to find the number of its victories that maximizes the number of teams with more points than wonderteam. I will demonstrate my approach on the following example: let's say n = 4. Then each team plays 6 matches. If wonderteam is represented by this triple (3,0,3) [3 victories, 0 draws, 3 losses], then the team with the higher rank should have at least 10 points. It should be represented by (2,4,0). Now I need to assign these triples to as much teams as possible. But I don't see when to stop assigning, what is the stopping condition that shows the impossibility of the current configuration.

int mpt = 2*(n-1); // matches per team
int res=0; // the maximum number of teams with higher rank than wonderteam
for(int win=0;win<=mpt;++win) // search for all possible values of victories
{
int p = 3 * win + 1; // the points count of the team T with higher rank than the wonderteam
int won = win – 1; // win count of T
int draw = p-3*won; // draw count of T
int loss=mpt-won-draw; // loss count of T

if( (won<0) || (draw<0) || (loss<0)) continue;
if( (won>mpt) || (draw>mpt) || (loss>mpt)) continue;
if((won+draw+loss)!=mpt)continue;

int cur = 0; // the current number of teams with higher rank than wonderteam
// I TRIED ALL SORTS OF THINGS HERE, NO LUCK, ANY SUGGESTIONS
// HOW TO COUNT CUR?
res = max(res,cur);
}

Is my approach right? If yes, how to count cur? If not, what are the alternative approaches? It seems that so many coders got AC in <=20 minutes.