10037 - Bridge

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

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

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

Post by LittleJohn »

Yes, it has been rejudged.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post 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..

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post 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?

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank »

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

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

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

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank »

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

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post 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.

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post 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~!

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post 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?

Moni
Experienced poster
Posts: 202
Joined: Fri Mar 22, 2002 2:00 am
Location: Chittagong. CSE - CUET
Contact:

Re: What's going on with 10037?

Post 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
ImageWe are all in a circular way, no advances, only moving and moving!

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post 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.....
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

10037 Bridges

Post by hank »

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

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Post by cyfra »

Hi!

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

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

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post 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.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Post Reply

Return to “Volume 100 (10000-10099)”