Page 2 of 6

Posted: Mon Jan 27, 2003 6:02 pm
by Larry
has this been corrected? if not, how do people get AC..?

Posted: Tue Jan 28, 2003 4:38 am
by LittleJohn
Yes, it has been rejudged.

Posted: Tue Jan 28, 2003 10:19 am
by 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..

Posted: Mon Feb 10, 2003 6:50 am
by 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?

Posted: Mon Feb 10, 2003 7:07 am
by hank
I also got WA many times!
Can you tell me how can I get AC?

Posted: Mon Feb 10, 2003 8:38 am
by Larry
it was a problem at Waterloo. I have corrected a slight mistake and got AC btw...

Posted: Mon Feb 10, 2003 8:53 am
by hank
how can you get AC?
can you tell me what's wrong?

Posted: Mon Feb 10, 2003 8:58 am
by 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.

Posted: Mon Feb 10, 2003 11:07 am
by 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~!

Posted: Wed Feb 12, 2003 4:23 pm
by 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?

Re: What's going on with 10037?

Posted: Fri Feb 14, 2003 8:37 pm
by Moni
Revenger wrote: But I have judge solution! What's wrong?
Hai! what do you mean by this? How did you get judge solution ??? :o

Posted: Fri Feb 14, 2003 9:51 pm
by ..
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.....

10037 Bridges

Posted: Wed Mar 26, 2003 7:47 am
by hank
I programmed this problem and got wrong answer.
But I can't find any bug in my program!!
Is there any trick?

Posted: Thu Mar 27, 2003 10:14 am
by cyfra
Hi!

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

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

Posted: Tue Sep 16, 2003 7:59 am
by Observer
hmmm... this qq (Q10037) looks interesting :P

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