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 » Mon Jan 27, 2003 6:02 pm

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 » Tue Jan 28, 2003 4:38 am

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

=( 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..

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

Post by hank » Mon Feb 10, 2003 6:50 am

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?

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

Post by hank » Mon Feb 10, 2003 7:07 am

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 » Mon Feb 10, 2003 8:38 am

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

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

Post by hank » Mon Feb 10, 2003 8:53 am

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

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.

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

Post by hank » Mon Feb 10, 2003 11:07 am

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

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

Post by hank » Wed Feb 12, 2003 4:23 pm

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?

User avatar
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 » Fri Feb 14, 2003 8:37 pm

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

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.

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

10037 Bridges

Post by hank » Wed Mar 26, 2003 7:47 am

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 » Thu Mar 27, 2003 10:14 am

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 » Tue Sep 16, 2003 7:59 am

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)”