915  Stack of Cylinders
Moderator: Board moderators

 A great helper
 Posts: 281
 Joined: Tue Sep 10, 2002 5:14 am
 Location: Mountain View, CA, USA
 Contact:
915  Stack of Cylinders
The problem description is ambiguous. Why is the path not (2, 3, 6, 7)? It seems that if cylinder 7 were big enough, it would be part of the path. What is the precise definition of the "continous path" and the "path tail"?
If only I had as much free time as I did in college...
See the picture in the problem. Imagine that some circles are packed in a rectangle. Suppose you need length 'x' to pack all the circles. To be more precise suppose you have to place all the circles between two vertical lines. 'x' is the minimum required length between the vertical lines. Now the circles that cant be removed (otherwise the value of 'x' will decrease) are the elemets of the continuous path. Path Head means the first circle that should be taken, and Path Trail means the last circle that should be taken.
2, 3, 6, 7 is not the answer because if you remove 7, it has no effect to 'x'. But if you remove 2, 3 or 6; 'x' will decrease.
Hope you understand.
2, 3, 6, 7 is not the answer because if you remove 7, it has no effect to 'x'. But if you remove 2, 3 or 6; 'x' will decrease.
Hope you understand.
Ami ekhono shopno dekhi...
HomePage
HomePage
Right!yiuyuho wrote:It is ensured that each cylinder can touch no more than one cylinder at its left and no more than one cylinder at its right.
What cylinders is it refering to? 3 is touching 4 and 6 on the right, right?
May be they are talking about the cylinders which make the path.
Ami ekhono shopno dekhi...
HomePage
HomePage
Re: 915  Stack of Cylinders
Help me please.....
I don't know what i have to use to solve this kind of problem.
any help please?????
Thank u.
I don't know what i have to use to solve this kind of problem.
any help please?????
Thank u.

 Experienced poster
 Posts: 139
 Joined: Wed May 18, 2011 3:04 pm
Re: 915  Stack of Cylinders
Test data generator.
Code: Select all
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
const int MAX_CASES = 100;
int main(int argc, char *argv[])
{
srand(time(NULL));
for (int c = 1; c <= MAX_CASES; c++)
{
int circles = rand() % 90 + 10;
cout << circles << '\n';
for (int i = 1; i <= circles; i++)
{
int radius = rand() % 1000 + 3;
cout << radius << '\n';
}
}
return 0;
}
metaphysis: http://uhunt.onlinejudge.org/id/95895
My solutions for UVa problems: https://github.com/metaphysis/Code.
My solutions for UVa problems: https://github.com/metaphysis/Code.