Page 1 of 1
10997 - Medals
Posted: Sat Mar 25, 2006 3:34 pm
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?
Posted: Sat Mar 25, 2006 6:03 pm
Only very few values of j,k,l have to be checked.
Posted: Mon Mar 27, 2006 7:37 am
"Only very few values of j,k,l have to be checked."
how to do this problem
could you please describe your method in detail
thanks a lot
Posted: Mon Mar 27, 2006 11:02 am
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.
10997 - Medals
Posted: Sat Apr 01, 2006 8:50 am
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?
Posted: Sat Apr 01, 2006 1:21 pm
What do you mean? Problem statement clearly says that you should only consider vectors of that form.
Posted: Sat Apr 01, 2006 6:59 pm
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?
Posted: Sat Apr 01, 2006 8:17 pm
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?
Posted: Thu Apr 27, 2006 4:31 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.
Posted: Thu Apr 27, 2006 4:40 pm
Posted: Fri Apr 28, 2006 6:40 pm
Thanks mf! I found my mistake. My algorithm is wrong...