Block TowerProblem code: BLOCKS |
All submissions for this problem are available.
Dave has several rectangular blocks with which he wishes to build a tower. He may only place a block on another if its base fits within the other's base with the edges parallel. So he could place a block with a base of 1x9 on top of a block with a base of 2x9, but not on top of a block with a base of 8x8. Help Dave make the tower as tall as possible. Blocks may be rotated by any multiple of 90 degrees about any axis. Each block may only be used once, and you must use at least 3 blocks.
Input:
Input begins with an integer T (about 500), the number of test cases. Each test case begins with an integer N (chosen uniformly between 10 and 200, inclusive), the number of blocks. N lines follow, each containing 3 integers that give the dimensions of a block. All dimensions are chosen uniformly between 1 and 100, inclusive. A blank line separates each case.
Output:
For each case, first ouput an integer P>=3, indicating the number of blocks you wish to use. Follow with P lines, each containing the dimensions of a block, with the height of the block listed first (the order of the other 2 dimensions does not matter). Output the blocks in order from the top of the tower to bottom of the tower.
Scoring
Your score for each test case is the height of your tower divided by N. Your total score is the average of your scores on the individual test cases.Sample input:
1 10 7 2 10 8 8 8 7 1 1 2 7 9 6 8 1 6 6 5 3 2 5 10 3 9 10 10 8 4 4 1
Sample output:
5 4 1 4 1 1 7 10 2 7 2 7 9 8 10 10
Score: (4+1+10+2+8)/10 = 2.5
| Author: | pieguy |
| Date Added: | 9-06-2010 |
| Time Limit: | 7 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
can any one plz tell mr how
can any one plz tell mr how they chooses the blocks from the given blocks to built a building.....
i m not able to understand the question....
why not the ans is...
7
10 10 8
10 9 3
10 7 2
9 7 2
8 6 1
4 4 1
7 1 1....
avg =(10+10+10+9+8+4+7)/10=5.6
............. plz someone elaborate the question.....
@Mayur: this is the
@Mayur: this is the tiebreaker problem, which means there is no single correct answer. Any answer that conforms to the output specification and represents a valid tower will be considered correct. Please refrain from discussing answers to specific test cases during an active contest.
Can a block with base a*b be
Can a block with base a*b be placed above other one with same dimensions of base.
@Vipul: yes
@Vipul: yes
is given sample output is the
is given sample output is the tower of maximum
hieght ? if it is then what is it
8 1 6
10 2 7
10 3 9
2 7 9
8 10 10
score=3.8
anyone please help
thanks
The sample output is just
The sample output is just that; a sample. It is not necessarily the optimal answer.
does wrong answer can be
does wrong answer can be segmentation fault?
No.
No.
@atul wrong answer and
@atul
wrong answer and segmentation fault are two different things.
For segmentation fault you will be shown a runtime error icon.
does input is always >=3 or
does input is always >=3
or we have to consider the case?
sorry for previous one it is
sorry for previous one it is clear in problem.
is it ok if i give the output
is it ok if i give the output immeadiately after each test case is entered rather than after all of them have been entered?
It's not only OK, but it is
It's not only OK, but it is what you should be doing. See the FAQ.
This was a nice problem to
This was a nice problem to solve.... I thought that I had found out an optimal solution(and still think so) , but apparently I have been wrong....considering the scores. Any pointers as to y it is not possible to find the perfect solution?
I also think there is a
I also think there is a perfect algorithm before.
But some details made it tough to use one block just once.
And when the height of each blocks is determined , it is easy to find a perfect algorithm.
Of course choosing one block
Of course choosing one block at most once was tricky, but I thought I had passed that hurdle by keeping some indicator(a true/false value).... Is thr nething else I mite hav missed ? my score was .992 , so i am sure it must be some small case.
Post The Tutorials for this
Post The Tutorials for this month contest,,,(JULY10)