303 - Pipe

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

Moderator: Board moderators

Post Reply
lundril
New poster
Posts: 6
Joined: Tue Mar 19, 2002 2:00 am
Contact:

Post by lundril »

Hi,

after changing the program so it doesn't
get TLEs (yes i should have thought
first :smile:) I get Wrong Answer.

Problem: I checked now with various
inputs, and I don't get a Wrong Answer
in my own tests.

So I'm asking myself (again) if
there is something special about the
input:
What is "EOL" is that a new line (I use fgets so I depend on new lines...)?

Why doesn't the encryption of
'Hello Bob ' (10 Chars!) result in
'BolHeol b' (2 spaces between 'l' and 'b') in the given example.

Other Hints what might go wrong ?
(As I said my own test cases seem to work...)

so long
lundril

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann »

Maybe you submit it with the wrong problem number? You seem to talk about problem 306, not 303. Yes, "eol" should be a newline character. And yes, the sample test data is wrong. But I didn't find anything strange with the secret test data.

dt96hasv
New poster
Posts: 5
Joined: Wed Oct 20, 2004 9:27 am
Location: Gothenburg
Contact:

303 - Pipe

Post by dt96hasv »

Hi, I have been fiddling around with those pipes for quite some time, and has been able to produce a program which behaves correctly in all the testcases I can think of.

Since the reply from judge is WA, it is obviously the case that I have missed some interesting case(s). It would be nice to see some more testcases!

/Hans

wolfdigit
New poster
Posts: 1
Joined: Sun Mar 18, 2007 9:20 am

303 WA

Post by wolfdigit »

i have got WA several times
could anyone please give some tricky inputs or help me find bugs in my code?

Code: Select all

#include <stdio.h>
#include <math.h>
#define MAXN 20
#define EPS 1E-10

int n ;
double x[MAXN], y[MAXN] ;

double findx(double y0) {
       int i ;
       int uid, did ;
       double ori_dm, new_dm ;
       double ori_um, new_um ;
       double t, b, m ;
       double ny, ly ;

       uid = 1 ;
       did = 1 ;
       for (i=2; i<n; i++) {
           //(x[uid]-x[0]) * (x[did]-x[0]) * (x[i]-x[0])
           ori_um = (y[uid]-y0)*(x[did]-x[0])*(x[i]-x[0]) ;
           ori_dm = (y[did]-1-y0)*(x[uid]-x[0])*(x[i]-x[0]) ;
           new_um = (y[i]-y0)*(x[uid]-x[0])*(x[did]-x[0]) ;
           if (new_um<ori_um) {
              uid = i ;
              if (new_um<ori_dm) {
                 t = x[i] ;
                 b = x[i-1] ;
                 while (t-b>0.001) {
                       m = (t+b) / 2 ;
                       //(x[did]-x[0]) * (x[i]-x[i-1])
                       ny = y0*(x[did]-x[0])*(x[i]-x[i-1]) + (y[did]-1-y0)*(m-x[0])*(x[i]-x[i-1]) ;
                       ly = y[i-1]*(x[did]-x[0])*(x[i]-x[i-1]) + (y[i]-y[i-1])*(m-x[i-1])*(x[did]-x[0]) ;
                       if (ny>ly) {
                          t = m ;
                       }
                       else {
                            b = m ;
                       }
                 }
                 return m ;
              }
           }
           new_dm = (y[i]-1-y0)*(x[uid]-x[0])*(x[did]-x[0]) ;
           if (new_dm>ori_dm) {
              did = i ;
              if (new_dm>ori_um) {
                 t = x[i] ;
                 b = x[i-1] ;
                 while (t-b>0.001) {
                       m = (t+b) / 2 ;
                       //(x[uid]-x[0]) * (x[i]-x[i-1])
                       ny = y0*(x[uid]-x[0])*(x[i]-x[i-1]) + (y[uid]-y0)*(m-x[0])*(x[i]-x[i-1]) ;
                       ly = (y[i-1]-1)*(x[uid]-x[0])*(x[i]-x[i-1]) + (y[i]-y[i-1])*(m-x[i-1])*(x[uid]-x[0]) ;
                       if (ny>ly) {
                          b = m ;
                       }
                       else {
                            t = m ;
                       }
                 }
                 return m ;
              }
           }
       }

       return x[n-1] ;
}

int main() {
    int i ;
    double tans, maxx ;
    double y0 ;
    
    while (scanf("%d", &n)!=EOF&&n!=0) {
          for (i=0; i<n; i++) {
              scanf("%lf%lf", &x[i], &y[i]) ;
          }
          if (n==1||n==2) {
             printf("Through all the pipe.\n") ;
             continue ;
          }
          maxx = 0.0 ;
          for (y0=y[0]; y0>=y[0]-1; y0-=0.0005) {
              tans = findx(y0) ;
              if (tans>maxx) {
                 maxx = tans ;
              }
              if (maxx==x[n-1]) {
                 break ;
              }
          }
          if (fabs(maxx-x[n-1])<EPS) {
             printf("Through all the pipe.\n") ;
          }
          else {
               printf("%.2f\n", maxx) ;
          }
    }

    return 0 ;
}

LithiumDex
New poster
Posts: 44
Joined: Tue Jun 06, 2006 6:44 pm
Location: Nova Scotia, Canada
Contact:

Post by LithiumDex »

I'm also getting WA... However in my tests, our programs produce the same result, with the exception of this test case:

Code: Select all

20
0 .5
10 -.5
20 .5
30 -.5
40 .5
50 -.5
60 .5
70 -.5
80 .5
90 -.5
100 .5
110 -.5
120 .5
130 -.5
140 .5
150 -.5
160 .5
170 -.5
180 .5
190 -.5
The only solution too this, is a horizontal line that brushes past all the bent points.
Assume that the light is not bent at the pipe bent points and the bent points do not stop the light beam.
You program produces:

Code: Select all

19.99
And mine:

Code: Select all

Through all the pipe.
Could someone with an AC solution verify this? (Or perhaps provide some tricky input?)

At the moment, I think both our problems are due to precision errors... I'm using an error of 0.01, which is the only EPS value that I can get from the problem description...
- Chris Adams

LithiumDex
New poster
Posts: 44
Joined: Tue Jun 06, 2006 6:44 pm
Location: Nova Scotia, Canada
Contact:

Post by LithiumDex »

You know... I always find it ironic that almost every time I post for help, I then solve in a few minutes later.

(This is one of those times)..

I used a value of EPS around 0.0000001, and doubles... and that gave me the AC (giving away too much? I think EPS should have been stated in the problem statement :P)

anyway, the outputs I gave before are still the same... hope that helps you.
- Chris Adams

Post Reply

Return to “Volume 3 (300-399)”