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 1645. Ski Race

TO ADMIN: TEST 14
Posted by Hikmat Ahmedov 16 Mar 2012 16:50
I think you have a wrong check in test 14.
In test 14, two or more sportsmen are passing the track in equal amount of time so that one of them is doing his best or worst rank.
For example, in this test

31
2 24 14 23 21 18 4 26 30 25 13 11 17 9 29 22 15 7 3 19 5 8 12 10 28 27 6 31 16 20 1

--------We want to find the best rank for 1.------------

1 achieves his best rank only if all previous sportsmen cross the finish line with 1 second difference.  In this case 1 and 2 passes the track in equal amount of time.

 If 2 reaches the finish at time 1000 and
24 reaches the finish at time 999 and
14 reaches the finish at time 998 and so on

1 reaches the finish at time 970
To find who the winner was we should subtract start time from finish time.
 So,
2 passed the tack in 970 seconds
24 passed the track in 309 seconds

1 passed the track in 970 seconds

As you can see, 1 and 2 are both passed the track in 970 seconds.
The best rank of 1 is 30( or 31, 1 and 2 passed the track in equal time)
And worst rank of 1 is 31(or 30,   1 and 2 passed the track in equal time)
Here rank is ambiguous.

My program gives this output for the test given above.
30 31
1 31
18 30
6 29
18 30
23 30
16 27
17 29
12 25
17 29
10 23
15 28
9 21
2 19
11 23
15 30
8 20
4 16
9 24
12 30
3 13
7 19
2 11
1 9
3 14
1 13
4 27
3 26
2 16
1 10
1 28

Calculations are summarized below:

Finish    Start    Reached    Passed
order    time    finish    track in
2        30        1000        970
24        690        999        309
14        390        998        608
23        660        997        337
21        600        996        396
18        510        995        485
4        90        994        904
26        750        993        243
30        870        992        122
25        720        991        271
13        360        990        630
11        300        989        689
17        480        988        508
9        240        987        747
29        840        986        146
22        630        985        355
15        420        984        564
7        180        983        803
3        60        982        922
19        540        981        441
5        120        980        860
8        210        979        769
12        330        978        648
10        270        977        707
28        810        976        166
27        780        975        195
6        150        974        824
31        900        973        73
16        450        972        522
20        570        971        401
1        0        970        970

Please, let me know, if I'm wrong

Thanks,



Edited by author 16.03.2012 16:54

Edited by author 16.03.2012 16:55
Re: TO ADMIN: TEST 14
Posted by Sandro (USU) 16 Mar 2012 18:10
1) The permutation of numbers is the order in which the skiers finished.
In your test the skier number 2 crossed the finish line earlier than the skier number 1. So it is impossible that number 1 finished in time 970 and number 2 finished in time 1000.

2) Skiers don't necessary pass the track in integer time.
Re: TO ADMIN: TEST 14
Posted by Hikmat Ahmedov 18 Mar 2012 15:52
Thank you very much Sandro

Now I have AC!

For other people:

Correct answer for test:
31
2 24 14 23 21 18 4 26 30 25 13 11 17 9 29 22 15 7 3 19 5 8 12 10 28 27 6 31 16 20 1

is:

31 31
1 30
18 30
6 29
18 30
23 30
16 27
17 29
12 25
17 29
10 23
15 28
9 21
2 19
11 23
15 30
8 20
4 16
9 24
12 30
3 13
7 19
2 11
1 9
3 14
1 13
4 27
3 26
2 16
1 10
1 28