## 10997 - Medals

Moderator: Board moderators

DongJoo Kim
New poster
Posts: 20
Joined: Tue Sep 20, 2005 9:20 am
Location: Daejeon, Korea

### 10997 - Medals

What I can think for 10997 is putting all the possible values.

It gives AC. However, I am thinking that there should be faster way to solve this kind of problem. Any idea?

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
Only very few values of j,k,l have to be checked.

lonelyone
Learning poster
Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm
"Only very few values of j,k,l have to be checked."

how to do this problem

thanks a lot

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
There's not much to describe.

Keep in mind that n is big. If j > k > l, then if you sort triples (g,s,b) by the value of g/n^j + s/n^k + b/n^l, the order you get doesn't depend on the actual values of j,k,l.

bluebird
New poster
Posts: 12
Joined: Mon Oct 17, 2005 2:35 am

### 10997 - Medals

Hi,

I can't think of the real/intended way to solve this problem. I managed to make an AC solution by trying the vectors

(n,1,1) (n,2,1) .... (n,n,1).....(n,n,n)

so basically, I try to change each component from 1 to n. This means I try a total of n^3 different vectors.

Clearly, this wasn't the intended solution, since some of the vectors may not be in the form (1/n^j, 1/n^k, 1/n^l). Can someone please point me in the right direction?

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
What do you mean? Problem statement clearly says that you should only consider vectors of that form.

bluebird
New poster
Posts: 12
Joined: Mon Oct 17, 2005 2:35 am
Yes, but I guess the test data wasn't that comprehensive--even though my solution was wrong, it somehow got AC.

Regardless, I still get this problem. In your earlier posts, you said that if

j > k > l

and n is large enough, then the actual values of j k and l don't matter. Why is that?

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
Take two countries with (g1,s1,b1) and (g2,s2,b2) medals. If j > k > l and g1 > g2 (regardless the actual values), can the second coutry be ranked above the first one? Now let g1 = g2 and s1 > s2. Again, can the second coutry be ranked above the first one?

C
New poster
Posts: 35
Joined: Mon Apr 17, 2006 1:04 pm
I got WA. But I don't know why.
I generally sorted the g,s,b in all possible order(3!=6), if there is a way so that Canada rank frist,exists also i,j,k. Or else Canada cannot win.

Can someone give me some I/O data. PLZ ! Thanks in advance.

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

C
New poster
Posts: 35
Joined: Mon Apr 17, 2006 1:04 pm
Thanks mf! I found my mistake. My algorithm is wrong...