Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
WA5 and tests | Mortus | 1267. Екатеринбургское метро | 13 июл 2024 20:05 | 1 |
wa5 - check how you calculate time when change direction at the station Test: 12 1 2 45 64 31 23 128 61 2 2 7 8 7 3 5 ans: 805 Test: 4 7 6 3 3 12 3 4 ans : 60 Good luck! |
I think this problem really needs a clearer statement and an explanation of the sample | 337446ZX | 1267. Екатеринбургское метро | 24 янв 2024 09:01 | 3 |
I will post one if I solve it. There are n subway stations on a subway line, numbered from 1 to n. The distance between the ith station and the i+1th station is s_i, which means the train need s_i minutes to drive from the ith station to the i+1th. There are trains driving from 1 to n and trains driving from station n to station 1. The trains driving from station 1 to station n departs every d minutes at station 1 and the first one of that departs at d1 minutes. Similarly, The trains driving from station n to station 1 departs every d minutes too at station n and the first one of that departs at dn minutes. However, in this problem the trains are considered not to stay at any station, just drive past A vistor is going to visit every station. He starts from station t. To visit a station, he has to take a train and get off at that station. It takes him 1 minutes to visit a staion, so that he cannot take the train he get off just now. The station t is considered visited. After all visits he need to return to station t. You are going to make a plan for him so that the time cost is minimized. The time cost is calculated as (the time he has visited all stations and gets off a train to station t - the time he departs--getting on a train at station t (can be any train)). Output such time in minutes. Input n s_1 s_2 ... s_(n-1) t d d1 dn Edited by author 24.01.2024 09:02 Explanation of the sample: One possible solution. Take the train to n at 5 and get of to station 3 at 12. Then take the train to 1 at 13 and get of to station 1 at 25. Then take the train to n at 28 and get of to station 2 at 33. It costs 33-5=28 Edited by author 24.01.2024 09:05 |
Why I got Wrong answer at Test 2? Can anybody give me a test about it? | Dryad | 1267. Екатеринбургское метро | 17 фев 2017 14:24 | 13 |
This is my program: #include <stdio.h> int len[16]; int ldist[16]; int rdist[16]; int depart; int gor,gol,iv; int N; void prelr() { int i; ldist[0]=0; for (i=1;i<N;i++) ldist[i]=ldist[i-1]+len[i-1]; for (i=N-2;i>=0;i--) rdist[i]=rdist[i+1]+len[i]; } void read() { scanf("%d",&N); int i; for (i=0;i<N-1;i++) scanf("%d",&len[i]); scanf("%d",&depart); depart--; scanf("%d%d%d",&iv,&gor,&gol); } int best; bool first; int deptime; void nexttimepoint(int&time,int&posi,int&dir) { //Test nearest shuttle int tmp; if (dir==1) { tmp=((time-ldist[posi]-gor)%iv+iv)%iv; if (tmp!=0) tmp=iv-tmp; time+=tmp; } else { tmp=((time-rdist[posi]-gol)%iv+iv)%iv; if (tmp!=0) tmp=iv-tmp; time+=tmp; } //Record if it's first if (first) { first=false; deptime=time; } //Make path if (dir==1) { time+=len[posi]; posi++; } else { time+=len[posi-1]; posi--; } //Test if reverse needed if (posi==0) dir=1; if (posi==N-1) dir=-1;
} void testdepart(int direct) { int i,time,p,delayi,dir; int last; for (i=1<<(N-2);i-->0;) { delayi=i; last=(1<<N)-1; if (direct==1) time=ldist[depart]; else time=rdist[depart]; p=i; dir=direct; p=depart; first=true; nexttimepoint(time,p,dir); while (p!=depart||dir!=direct) { if (p==0||p==N-1) time++; else if (last&(1<<p)&&p!=depart) { if (delayi&(1<<(p-1))) delayi^=1<<(p-1); else { last^=1<<p; time++; } } nexttimepoint(time,p,dir); } if (best>time-deptime) best=time-deptime; } } void process() { prelr(); if (depart!=N-1) testdepart(1); if (depart!=0) testdepart(-1); } int main() { read(); best=2147483647; if (N==1) printf("0\n"); else process(); printf("%d\n",best); return 0; } Thanks. These two absolutely random test based on my AC prog 6 7 6 3 2 8 3 12 56 34 res:96 12 1 2 45 64 31 23 128 61 2 2 7 8 11 1001 31 res:825 Edited by author 07.09.2010 23:23 Edited by author 07.09.2010 23:24 These two absolutely random test based on my AC prog 6 7 6 3 2 8 3 12 56 34 res:96 12 1 2 45 64 31 23 128 61 2 2 7 8 11 1001 31 res:825 I think it`s wrong answer, because this need at least 1 train starting in 1, and it takes 1001 minutes, but your answer less than it. Let then another AC authors apply their programs to these tests The interval between the trains is nonzero and doesn’t exceed 10^5, and the departure time from the terminal stations doesn’t exceed the interval. In your tests it is not true. Edited by author 01.04.2011 17:46 Edited by author 01.04.2011 17:46 Yes, I solved problem with more wide conditions. In my test 11 1001 31, and 1001,31>11. But my algo (DP) allow such expansion. So tests are useful. Solve problem in broader conditions and get AC in narrow case. These two absolutely random test based on my AC prog 6 7 6 3 2 8 3 12 56 34 res:96 12 1 2 45 64 31 23 128 61 2 2 7 8 11 1001 31 res:825 My AC program gives 156 and 1837 respectively. So... weak tests? Edited by author 13.10.2014 19:33 These tests are wrong as "departure time from the terminal stations doesn’t exceed the interval." not trusted. try test 1 1 100 100 100 answer is 0 :) can anyone tell me why the sample's answer is 28? |
2 ADMINS: very unclear problem statement => so few authors for such simple problem | Vedernikoff 'Goryinyich' Sergey (HSE: АОП) | 1267. Екатеринбургское метро | 29 июн 2014 22:06 | 1 |
1. Problem model is not clear: whether train from station 1, after reaching station N, continues then moving in the opposite direction (station N -> station 1), or "disappears" after? 2. Another bug in statement: "You may assume that train stops at each station are instant." and "it takes one second to board a train". How these two statements relate to each other? If train stop is instant, how tourist can board it the whole 1 second??? Answers: 1. No, it "disappears" (which is very different from the real world) 2. This stupid statement is just to show that the tourist should stay on the station during 1 minute, i.e. he cannot leave on the same train he reached the station with Edited by author 01.07.2014 00:38 |
why the sample's answer is 28? i think it's 26 | Edric Mao | 1267. Екатеринбургское метро | 27 окт 2011 20:43 | 1 |
|
How is it possible?(+) | Sergey Lazarev (MSU Tashkent) | 1267. Екатеринбургское метро | 27 окт 2011 20:33 | 2 |
"train stops at each station are instant" and "it takes one second to board a train". So, the man spend one second to board a train, but the train do not stop for a second at the station. That's the point really confuse me. Edited by author 27.10.2011 20:34 |
Can anyone explain the prob? I don't understand! | Maigo Akisame (maigoakisame@yahoo.com.cn) | 1267. Екатеринбургское метро | 27 окт 2011 20:27 | 2 |
|
some hint | Oracle[Lviv NU] | 1267. Екатеринбургское метро | 13 мар 2011 01:54 | 1 |
Tourist can not get into train at time 0 - he must wait for another one. (I got WA 4, when missed this). |
So easy | Mukhametianov Den [USU] | 1267. Екатеринбургское метро | 23 авг 2010 22:34 | 1 |
So easy Mukhametianov Den [USU] 23 авг 2010 22:34 Why so few authors? Classic dp gets AC fast enough... |
DP | svr | 1267. Екатеринбургское метро | 30 дек 2007 10:22 | 1 |
Excellent problem. Very realistic and DP works. Small advice: We should consider moments after stationary condition established: first trains went to last stations. Without this we must include 10^5 moments in Dp and will be MLE and TLE. Edited by author 30.12.2007 10:32 |