## 121 - Pipe Fitters

**Moderator:** Board moderators

### problem 121 - pipe fitters

can anybody tell me the formulas i need to know for this problem?

thank you

thank you

using that method, i found that i could fit 128 circles instead of 126 circles in the box 11 by 11, but i am not very sure about those dimensions with decimals...they are quite confusing.

### 121 - pipe Fitters

hi,

I was just wondering if anyone could help me out with some more input - output data.... I think I got the problem right, it runs fine with all the data I could think about, but obviously there must be something I didn't think about... all help would be appreciated![/quote]

I was just wondering if anyone could help me out with some more input - output data.... I think I got the problem right, it runs fine with all the data I could think about, but obviously there must be something I didn't think about... all help would be appreciated![/quote]

pipe fitters is an interesting problem.

first off, there are 2 ways of arranging pipes. one is obvious, the other one requires basic trigonometry to figure out the difference in height between two row of pipes.

1:

O O O

O O O

2:

O O

O O O

in case 2, the height is less than case 1!!!!

second, consider ALL cases.... in square mode, it's useless to rotate the bin... ie 2x5 holds as much as 5x2.

BUT in skew mode, try and rotate it... it might not hold the sam number of pipes if you chose 2x5 or 5x2 bin.

one case i forgot the first time i submitted looks like:

O O O

O O O

you need to consider this case... what's the breadth os this structure??? if you can compute the height, it should not be much more difficult...

third.. compute the number of pipes given the bin size and structure.. this part is easy.

if you have:

O O O

O O

O O O

O O

O O O

it would depend wether the number of rows N is even or odd..... but it would be close to (N/2) * (2B-1) (if B is the max number of pipes pe1 row)

first off, there are 2 ways of arranging pipes. one is obvious, the other one requires basic trigonometry to figure out the difference in height between two row of pipes.

1:

O O O

O O O

2:

O O

O O O

in case 2, the height is less than case 1!!!!

second, consider ALL cases.... in square mode, it's useless to rotate the bin... ie 2x5 holds as much as 5x2.

BUT in skew mode, try and rotate it... it might not hold the sam number of pipes if you chose 2x5 or 5x2 bin.

one case i forgot the first time i submitted looks like:

O O O

O O O

you need to consider this case... what's the breadth os this structure??? if you can compute the height, it should not be much more difficult...

third.. compute the number of pipes given the bin size and structure.. this part is easy.

if you have:

O O O

O O

O O O

O O

O O O

it would depend wether the number of rows N is even or odd..... but it would be close to (N/2) * (2B-1) (if B is the max number of pipes pe1 row)

We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

sorry, the formatting went bad...

case 2 should look like

_O_O

O_O_O

and the special case to consider:

_O_O_O

O_O_O

where O denotes a pipe and _ a mere separator...

my explanations are very unclear i'm sorry

anyway like i said the first step in this problem is work out trigonometry in the SKEW case.

then write 2 functions max_grid(a,b) and max_skew(a,b) that returns the max number of pipes for GRID nd SKEW patterns given a bin of size a*b

then for each input m,n compute max_grid(m,n) max_skew(m,n) and max_skew(n,m)

(max_grid(n,m) is equal to max_grid(m,n) thus useless to compute)

then return the MAX of these 3 values.

max_grid(a,b) is very simple to write.... use the math function floor for example:

return floor(a) * floor(b);

max_skew(a,b) is the "hard" part...

case 2 should look like

_O_O

O_O_O

and the special case to consider:

_O_O_O

O_O_O

where O denotes a pipe and _ a mere separator...

my explanations are very unclear i'm sorry

anyway like i said the first step in this problem is work out trigonometry in the SKEW case.

then write 2 functions max_grid(a,b) and max_skew(a,b) that returns the max number of pipes for GRID nd SKEW patterns given a bin of size a*b

then for each input m,n compute max_grid(m,n) max_skew(m,n) and max_skew(n,m)

(max_grid(n,m) is equal to max_grid(m,n) thus useless to compute)

then return the MAX of these 3 values.

max_grid(a,b) is very simple to write.... use the math function floor for example:

return floor(a) * floor(b);

max_skew(a,b) is the "hard" part...

We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

since my explanations were very poor i'd like to post my code, hope this helps you:

[c]#include <stdio.h>

#include <math.h>

#define GRID 0

#define SKEW 1

char *method[] = {"grid", "skew"};

int comp_grid(float a, float b)

{

return (int)(floor(a) * floor(b));

}

int comp_skew(float a, float b)

{

int x = (int)floor(a);

int y = (int)( 1 + floor((b-1)/(sqrt(3)/2)));

int x2;

if (a-(float)x >= 0.5)

x2 = x;

else

x2 = x-1;

if (y%2 == 0)

return (y/2) * (x+x2);

else

return (y/2) * (x+x2) + x;

}

int main()

{

float a,b;

int max, res, best_method;

while (scanf("%f %f",&a,&b) == 2)

{

max = comp_grid(a,b);

best_method = GRID;

if ((res = comp_skew(a,b)) > max)

{

max = res;

best_method = SKEW;

}

if ((res = comp_skew(b,a)) > max)

{

max = res;

best_method = SKEW;

}

printf("%d %s\n",max,method[best_method]);

}

return 0;

}

[/c]

i'll try to give you input data as well:

INPUT

65 23

23.2 15.8

22 13

2.9 10.5

15 15

7 7

1.95 10

10.5 10.5

OUTPUT

1677 skew

405 skew

313 skew

30 skew

247 skew

49 grid

19 skew

110 skew

[c]#include <stdio.h>

#include <math.h>

#define GRID 0

#define SKEW 1

char *method[] = {"grid", "skew"};

int comp_grid(float a, float b)

{

return (int)(floor(a) * floor(b));

}

int comp_skew(float a, float b)

{

int x = (int)floor(a);

int y = (int)( 1 + floor((b-1)/(sqrt(3)/2)));

int x2;

if (a-(float)x >= 0.5)

x2 = x;

else

x2 = x-1;

if (y%2 == 0)

return (y/2) * (x+x2);

else

return (y/2) * (x+x2) + x;

}

int main()

{

float a,b;

int max, res, best_method;

while (scanf("%f %f",&a,&b) == 2)

{

max = comp_grid(a,b);

best_method = GRID;

if ((res = comp_skew(a,b)) > max)

{

max = res;

best_method = SKEW;

}

if ((res = comp_skew(b,a)) > max)

{

max = res;

best_method = SKEW;

}

printf("%d %s\n",max,method[best_method]);

}

return 0;

}

[/c]

i'll try to give you input data as well:

INPUT

65 23

23.2 15.8

22 13

2.9 10.5

15 15

7 7

1.95 10

10.5 10.5

OUTPUT

1677 skew

405 skew

313 skew

30 skew

247 skew

49 grid

19 skew

110 skew

We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

.. there are skew patterns if a, or b or both are < 2

input "1.95 1.95" gives best fit " 2 skew"

...____.................

./..........\...............

|............|.._____..

.\.____./../..........\.

..............|............|

...............\_____/.

input "1.95 1.95" gives best fit " 2 skew"

...____.................

./..........\...............

|............|.._____..

.\.____./../..........\.

..............|............|

...............\_____/.

### dear epsilon0

dear epsilon0,

that's the thing which gets on my nerves - yes, I did get right the idea about rotating, about the height, etc. More than that, for each input you gave me, I get exactly the same output you have.... and this is not the only problem I have like this - it works completely fine for me, both under DOS/LINUX (g++), but not for the OJ... i'll just post the code here, see if anyone can find any bugs...

[cpp]

/* decided to cut my code out, but I am still stuck on the problem */

[/cpp]

that's the thing which gets on my nerves - yes, I did get right the idea about rotating, about the height, etc. More than that, for each input you gave me, I get exactly the same output you have.... and this is not the only problem I have like this - it works completely fine for me, both under DOS/LINUX (g++), but not for the OJ... i'll just post the code here, see if anyone can find any bugs...

[cpp]

/* decided to cut my code out, but I am still stuck on the problem */

[/cpp]

Last edited by zsepi on Fri Jan 03, 2003 1:22 pm, edited 1 time in total.

what error do you get? TL or WA?

if it's TL it might be a problem with the cin.feof() test... or the cin >> a >> b that blocks (i don't know C++ so i'm not sure)

if it's WA it's really weird since you tested your program a lot... unless it's a formatting problem but your code looks correct

if it's TL it might be a problem with the cin.feof() test... or the cin >> a >> b that blocks (i don't know C++ so i'm not sure)

if it's WA it's really weird since you tested your program a lot... unless it's a formatting problem but your code looks correct

thanks a lot for helping. as for the OJ, guess what: it is WA. would you do me a favor? would u compile my code and see if it works on your machine? today the OJ doesn't compile my messages, so I just put it aside a bit. But I have some problems like this, where I really think that I have the right answer, but the OJ throws'em back...epsilon0 wrote:what error do you get? TL or WA?

dear zsepi,

your c++ code compiles and run just fine on my box.

although i only tested it with a same input as i gave you.

if you have more input test, please give them to me and i'll test it with your code and mine to compare the output.

your c++ code compiles and run just fine on my box.

although i only tested it with a same input as i gave you.

if you have more input test, please give them to me and i'll test it with your code and mine to compare the output.