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 1267. Yekaterinburg Subway

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?
Posted by Zayakin Andrey[PermSU] 7 Sep 2010 23:22


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?
Posted by Zayakin Andrey[PermSU] 7 Sep 2010 23:23


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?
Posted by Zayakin Andrey[PermSU] 7 Sep 2010 23:24
svr wrote 30 December 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
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?
Posted by Zayakin Andrey[PermSU] 8 Sep 2010 21:02
I understand, thanks
Re: Why I got Wrong answer at Test 2? Can anybody give me a test about it?
Posted by olpetOdessaONU [1 2/3] 1 Apr 2011 17:45
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?
Posted by Edric Mao 27 Oct 2011 20:47
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?
Posted by bsu.mmf.team 13 Oct 2014 19:33
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?
Posted by Tolstobrov Anatoliy[Ivanovo SPU] 17 Feb 2017 14:24
These tests are wrong as "departure time from the terminal stations doesn’t exceed the interval." not trusted.