303 - Pipe

lundril · Post by **lundril** » Fri Mar 22, 2002 2:22 am

Hi,

after changing the program so it doesn't
get TLEs (yes i should have thought
first

) 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 · Post by **Stefan Pochmann** » Fri Mar 22, 2002 2:37 am

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 · Post by **dt96hasv** » Wed Oct 27, 2004 1:06 pm

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 · Post by **wolfdigit** » Sun Mar 18, 2007 9:26 am

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 · Post by **LithiumDex** » Sun Jun 17, 2007 1:34 am

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

LithiumDex · Post by **LithiumDex** » Sun Jun 17, 2007 1:45 am

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

)

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

OJ Board

303 - Pipe

303 - Pipe

303 WA