121 - Pipe Fitters

[minskcity]

What can be wrong with this code? It solves all samples correctly...
Every guess welcome...
[cpp]#include <iostream.h>
#include <math.h>
long double n,m;
long max;
char pattern;

long get_max(long double x, long double y){
long out;
long nx,ny;
nx = int(x * 2) - 1;
ny = int(((y - 1)/sqrt(0.75))) + 1;
if(ny % 2){
out = ((ny + 1)*nx)/2;
out -= nx/2;
} else out = (nx*ny)/2;
return out;
}

int main(){
while(cin >> n >> m){
pattern = 0;
max = int(n)*int(m);
if(get_max(n,m) > max){
max = get_max(n,m);
pattern = 1;
}
if(get_max(m,n) > max){
max = get_max(m,n);
pattern = 1;
}
cout << max;
if(!pattern) cout << " grid\n";
if(pattern) cout << " skew\n";
}
return 0;
}[/cpp]

[epsilon0]

who said skew patterns had different number of pipes on each row?
ie:
OO
.O.
OO

i think

.OO
OO.
.OO

is a perfectly cool skew pattern.

try it with a box 2.9 x 2.9 i think it should give you
6 skew
and not
5 skew, like your program seems to do... (i didn't check)

hope this helps

[minskcity]

"2.9 2.9"
Results in
"6 skew"
with my program...
Just before posting this topic, I tried all the samples, including those you give at forum (http://acm.uva.es/board/viewtopic.php?t=1990) and got all correct answers. Then I found one tricky input that results in error - "1.5 X 1+sqrt(0.75)". I changed all doubles to long doubles to fix this bug, but still got WA....

[minskcity]

After running this code
(get_max - yours, get_max1 - mine)

Code: Select all

	while(1){
		a = float(rand())/float(rand());
		b = float(rand())/float(rand());
      if(get_max(a,b)!=get_max1(a,b)){
			cout << a << " " << b << endl;
         cout << get_max(a,b) << " " << get_max1(a,b) << endl;
      	getch();
      }

I finnaly found the mistake - my program printed "1 skew" for "1 0.8", my get_max, was only supposed to get numbers equal or higher than 1....
Most of these mistakes are so simple...
Thx for your help.

[wonderboy]

Hello everyone,
I am getting WA for this problem. I have checked my prog with all kinds of inputs. It runs fine. I even checked it with the inputs given in two other threads related to this problem in this forum. One thing I am confused about is what should be the output if the max number of pipes is 0. My program gives "0 grid" as o/p in that case which looks quite stupid So please, can anyone help me here? Thanx in advance. Cheers!!!

[xbeanx]

You know, some people say that seeing the solution detracts from the problem. I agree with this, to some extent.

But a lot of problems I've dealt with I have spent hours upon hours trying to figure out the math. I find that with problems like this, after I see a solution I can work backwards and figure out why it works.

That's what I did with this one. My logic was a bit off for my solution, so when I saw yours I saw exactly why mine didn't work. Otherwise, I probably would never have figured out why my math was bad.

[40366]

I got the following code with all test cases i got my hands on to
it seems to work fine but WA
can anyone please help
BTW i dont know how to add my code to this page[/cpp]

[junbin]

This question depends a lot on floating point numbers.. which is simply put, not an exact science.

If you find one method does not work, try reordering your formula or using another forumla altogether.. I had to try 3 different formulas before I found one which the judge will not reject.

[dpitts]

One question, I'm a little tired so thats probably why it doesn't make sense...

Why 1 + floor((b-1)/(sqrt(3)/2)) instead of just floor(b/(sqrt(3)/2))?

That was the only difference between WA/AC for me.

Hmm, well, at least my original was close.

[faltooreza]

/*Here's my code someone plz help me to find out the problem*/

#include <stdio.h>
#include <math.h>

long grid(double x, double y){
return floor(x)*floor(y);
}

long skew(double x, double y){
long pipes;
double remain_row,row1,row2,nrow1,nrow2;

pipes=floor(x);
remain_row=floor((y-1)/0.866);

row1=floor(x-0.5);
row2=floor(x);

nrow1=ceil(remain_row/2.0);
nrow2=floor(remain_row/2.0);

pipes += (row1*nrow1+row2*nrow2);

return pipes;
}

int main(void){

double a,b;
long val1,val2,val3;

while(scanf("%lf %lf",&a,&b)!=EOF){
val1=grid(a,b);
val2=skew(a,b);
val3=skew(b,a);

if(val1>=val2){
if(val1>=val3) printf("%ld grid\n",val1);
else printf("%ld skew\n",val3);
}
else{
if(val2>=val3) printf("%ld skew\n",val2);
else printf("%ld skew\n",val3);
}
}

return 0;
}

[murtaza]

Thnx for the posts ... my code had the same bug as the one u posted.

[AndyGee]

[pascal]program uva121;
AC
[/pascal]

[Ankur Kumar Nayak]

Even my code had the same bug....Thanks for the help..........

[lazenca]

hm...Is there some critical test case for this prob...
I still got WA...@_@

This prob seems easy, but confused for floating computation...

[GVahe]

try this

input
10 0.9
output
0 grid