121 - Pipe Fitters

[skylander]

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

thank you

[ithamar]

Try to resolve the problem for yourself. Its much better that way . But in case u dont find the answer ask for hints or advices, not the answer

[C8H10N4O2]

There is no clever 'formula'. This is a simple intuition problem.

[skylander]

after some long thinking, i manage to come up with equilateral triangles linking 3 circles together, and stuck there...

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.

[C8H10N4O2]

That's certain a part of it. Think about how many layers you can have and then how many pipes in each layer.

[zhepi]

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]

[..]

do you handle the case that, when a (or b) < 2, there is no skew pattern?

[epsilon0]

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)

[epsilon0]

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

[epsilon0]

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

[epsilon0]

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

input "1.95 1.95" gives best fit " 2 skew"
...____.................
./..........\...............
|............|.._____..
.\.____./../..........\.
..............|............|
...............\_____/.

[zsepi]

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]

[epsilon0]

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

[zsepi]

what error do you get? TL or WA?

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]

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.