ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1062. Triathlon

I THINK THE EXAMPLE IS WRONG !!! plz take a look
Posted by Manastireanu 20 Feb 2005 18:48
I think the correct output for the example should be:
YES
YES
YES
NO
NO
NO
NO       //not YES
NO
YES

if  I am wrong plz tell me why


this is the way i thought of solving the problem

STEP 1:
--sort the contestants in descending order:
  after v     |        after W    |     after u
10 2 6        |        1 8 7      |      5 6 7
10 7 3        |        10 7 3     |     3 2 7
10 4 2        |        5 6 7      |     3 5 7
8 4 6         |        3 5 7      |     1 8 7
6 2 6         |        8 4 6      |     10 2 6
5 6 7         |        10 4 2     |     6 2 6
3 2 7         |        10 2 6     |     8 4 6
3 5 7         |        3 2 7      |     10 7 3
1 8 7         |        6 2 6      |     10 4 2

STEP 2:
--only the first of each sort might be winners
=>
after v  |   after w    |   after u
10 2 6   |   1 8 7      |  5 6 7
10 7 3   |              |  3 2 7
10 4 2   |              |  3 5 7
         |              |  1 8 7

STEP 3:
--I sort the three columns after the other 2 speeds
column 1 --after w and than u
         --after u and than w
column 2 ...

STEP 4:
-- the first of  every sort is surely a winner

in conclusion i sort the competitors after:
vwu
vuw
wvu
wuv
uvw
uwv
and the first of every sort is a winner


hope you cold understand me :)

PS:
-if you have a nother idea post it plz
-if the example is ok than plz tell me why


Edited by author 20.02.2005 18:51
Re: I THINK THE EXAMPLE IS WRONG !!! plz take a look
Posted by Kit 30 Mar 2005 19:29
STEP 2 is wrong. Try this:

4
100 100 1
100 1 100
1 100 100
50 50 50

The answer should be:
YES
YES
YES
YES!!!

A my idea.
We should find answer for the first contestant.
a[i] b[i] c[i] - is the speeds.
x y z - the lengths.
Write inequation describing that first contestant will win over i-th:
(1/a[1] - 1/a[i])x + (1/b[1] - 1/b[i])y + (1/c[1] - 1/c[i])z < 0
Then, we should answer: are exist such x, y and z, that satisfy this inequations for each i > 1?

Edited by author 30.03.2005 19:31
Re: I THINK THE EXAMPLE IS WRONG !!! plz take a look
Posted by CF# {Anoshin,Sotov,Khuramshin} 24 Nov 2007 18:00
Ok, and which algo can answer on this question?
Kit wrote 30 March 2005 19:29
A my idea.
We should find answer for the first contestant.
a[i] b[i] c[i] - is the speeds.
x y z - the lengths.
Write inequation describing that first contestant will win over i-th:
(1/a[1] - 1/a[i])x + (1/b[1] - 1/b[i])y + (1/c[1] - 1/c[i])z < 0
Then, we should answer: are exist such x, y and z, that satisfy this inequations for each i > 1?