Why I got Wrong answer at Test 2? Can anybody give me a test about it?
Posted by
Dryad 24 Mar 2006 19:09
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.
Re: Why I got Wrong answer at Test 2? Can anybody give me a test about it?
Posted by
svr 30 Dec 2007 10:11
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
Re: Why I got Wrong answer at Test 2? Can anybody give me a test about it?
Posted by
107th 18 Jul 2008 10:50
try test
1
1
100 100 100
answer is 0 :)
Re: Why I got Wrong answer at Test 2? Can anybody give me a test about it?
Edited by author 07.09.2010 23:23
Re: Why I got Wrong answer at Test 2? Can anybody give me a test about it?
Edited by author 07.09.2010 23:24
Re: Why I got Wrong answer at Test 2? Can anybody give me a test about it?
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.
Re: Why I got Wrong answer at Test 2? Can anybody give me a test about it?
Posted by
svr 8 Sep 2010 09:41
Let then another AC authors apply their programs to
these tests
Re: Why I got Wrong answer at Test 2? Can anybody give me a test about it?
I understand, thanks
Re: Why I got Wrong answer at Test 2? Can anybody give me a test about it?
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
Re: Why I got Wrong answer at Test 2? Can anybody give me a test about it?
Posted by
svr 1 Apr 2011 18:41
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.
Re: Why I got Wrong answer at Test 2? Can anybody give me a test about it?
can anyone tell me why the sample's answer is 28?
Re: Why I got Wrong answer at Test 2? Can anybody give me a test about it?
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
Re: Why I got Wrong answer at Test 2? Can anybody give me a test about it?
These tests are wrong as "departure time from the terminal stations doesn’t exceed the interval." not trusted.