10037 - Bridge

[Larry]

has this been corrected? if not, how do people get AC..?

[LittleJohn]

Yes, it has been rejudged.

[Larry]

=( I passed all waterloo's tests, but it still get WA for this. Anyone have any additional insights? I have checked case for 1, 2, 3 ppl..

[hank]

I also got WA many times,but I still can't find any bug in my program!
any idea?
by the way,
How did you know the judge's testdata is wrong?

[hank]

I also got WA many times!
Can you tell me how can I get AC?

[Larry]

it was a problem at Waterloo. I have corrected a slight mistake and got AC btw...

[hank]

how can you get AC?
can you tell me what's wrong?

[Larry]

basically, there are two strategies of choosing who to go across... and when to use which one ... without giving too much away.. if you need more explanation, tell me or something.

[hank]

[c]#include "stdio.h"
#include "string.h"
#include "stdlib.h"
#define MAX 1000
int n;
int src[MAX+1],dest[MAX+1];
int totalcost,process[(MAX+1)*100][2],list;
void output()
{
int i,p,q;
printf("%d\n",totalcost);
for(i=0;i<=list;i++){
p=process[0];
q=process[1];
if( p > q && q!=-1) p^=q^=p^=q;
if(p!=-1) printf("%d",p);
if(q!=-1) printf(" %d",q);
printf("\n");
}
}
void solve()
{
int i,j,k;
int cost;
int finish=0;
totalcost=0;
list=-1;
memset(process,-1,sizeof(process));
list++;
for( i=1,j=0,cost=0 ; i<=n && j<2 ; i++ )
if( src!=-1 ) {
j++;
dest=src;
src=-1;
finish++;
if( cost<dest ) cost=dest;
process

• [j-1]=dest;
  }
  totalcost+=cost;
  if(finish==n) return;
  ++list;
  for( i=1 ; i<=n ; i++ )
  if( dest!=-1 ) {
  src[i]=dest[i];
  dest[i]=-1;
  finish--;
  totalcost+=src[i];
  process
  • [0]=src[i];
    break;
    }
    while( finish<n ){
    /*go to dest*/
    if( ( n-finish ) == 3 && n%2 ){
    cost=0;
    list++;
    for( i=1 ; i<=n ; i++ )
    if( src[i]!= -1 ){
    dest[i]=src[i];
    src[i]=-1;
    if( cost<dest[i] ) cost=dest[i];
    finish++;
    process
    • [0]=dest[i];
      break;
      }
      for( i=n ; i>=1 ; i--)
      if( src[i]!= -1 ){
      dest[i]=src[i];
      src[i]=-1;
      if( cost<dest[i] ) cost=dest[i];
      finish++;
      process
      • [1]=dest[i];
        break;
        }
        totalcost+=cost;
        }else{
        ++list;
        for( i=n,j=0,cost=0 ; i>=1 && j<2 ; i-- )
        if( src[i]!= -1 ){
        dest[i]=src[i];
        src[i]=-1;
        finish++;
        j++;
        if(cost<dest[i]) cost=dest[i];
        process
        • [j-1]=dest[i];
          }/*if*/
          totalcost+=cost;
          }/*else*/
          if(finish==n) break;
          list++;
          for(i=1;i<=n;i++)
          if(dest[i]!=-1){
          src[i]=dest[i];
          dest[i]=-1;
          totalcost+=src[i];
          finish--;
          process
          • [0]=src[i];
            break;
            }
            }/*while*/
            }
            int cmp(const void *a,const void *b)
            {
            return *(int *)a-*(int *)b;
            }
            void main()
            {
            int N,i,temp,kk=0;
            scanf("%d",&N);
            for(;N;N--){
            if(kk==0) printf("\n");
            kk++;
            scanf("%d",&n);
            for(i=1;i<=n;i++){
            scanf("%d",&temp);
            src[i]=temp;
            }
            src[0]=-1;
            memset(dest,-1,sizeof(dest));
            qsort(src,n+1,sizeof(src[0]),cmp);
            solve();
            output();
            }
            }[/c]
            I think my program is right
            but why I always got WA?
            please help me~!

[hank]

The judge's testdata is wrong.
But there still were some people got AC last month.
It's very strange!
How can they got AC?

[Moni]

But I have judge solution! What's wrong?

Hai! what do you mean by this? How did you get judge solution ???

[..]

To Revenger:
I am not sure what's going on. But I guessed that the judge may modify the input by adding some tricky case..... It is usually that I can solve the "judge input", but still got WA.....

To Moni:
"judge solution" means the input/output files used during the regional/online contest. It is easy to check if such files exist on the network: copy a sentence from the problem specification to google and search, then you will know.....

[hank]

I programmed this problem and got wrong answer.
But I can't find any bug in my program!!
Is there any trick?

[cyfra]

Hi!

Maybe you will write what's is your algorithm..

In this task I had many algorithms, most of which were wrong

[Observer]

hmmm... this qq (Q10037) looks interesting

Could anyone plz suggest some test cases for which different strategies should be applied (with output, plz )? Thx in adv.