121 - Pipe Fitters

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

Moderator: Board moderators

skylander
New poster
Posts: 13
Joined: Mon Jun 10, 2002 3:24 pm
Contact:

problem 121 - pipe fitters

Post by skylander »

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

thank you :D

ithamar
Learning poster
Posts: 56
Joined: Mon May 13, 2002 11:58 pm
Location: Venezuela

Post by ithamar »

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

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 »

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

skylander
New poster
Posts: 13
Joined: Mon Jun 10, 2002 3:24 pm
Contact:

Post by 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
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by 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
New poster
Posts: 1
Joined: Thu Dec 26, 2002 6:02 pm
Location: Easton, PA, US
Contact:

121 - pipe Fitters

Post by 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]

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. »

do you handle the case that, when a (or b) < 2, there is no skew pattern?
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

Post by 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)
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

Post by 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...
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

Post by 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
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

Post by epsilon0 »

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

input "1.95 1.95" gives best fit " 2 skew"
...____.................
./..........\...............
|............|.._____..
.\.____./../..........\.
..............|............|
...............\_____/.
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

zsepi
Learning poster
Posts: 51
Joined: Thu Sep 26, 2002 7:43 pm
Location: Easton, PA, USA

dear epsilon0

Post by 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]
Last edited by zsepi on Fri Jan 03, 2003 1:22 pm, edited 1 time in total.

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

Post by 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
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

zsepi
Learning poster
Posts: 51
Joined: Thu Sep 26, 2002 7:43 pm
Location: Easton, PA, USA

Post by zsepi »

epsilon0 wrote: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
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

Post by 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.
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

Post Reply

Return to “Volume 1 (100-199)”