IOI '08 - Cairo, Egypt

Pyramid

The Grand Egyptian Museum is under construction two kilometers away from Giza pyramids and it is planned to have the opening in 2010. Some of the Egyptian antiquities were already moved there like the Statue of Ramses II which was moved there in 2006. In Egypt there are more than 100 pyramids and for the purpose of this problem we are planning to move one of those near the entrance of the new museum.

The pyramid is of course incredibly heavy, and cannot be moved as a single block. Instead, it will be carefully sliced into horizontal sections (slices). An enormous crane will be used to move one slice at a time to the new location. Of course, the crane can only hold one slice at a time, and the slices must be reassembled in the proper order, so some temporary space is needed for keeping slices out of the way. Unfortunately, there is very limited space, so in total there can be at most three stacks of slices at any time: one at the original location, one at the new location, and one at the temporary space. The crane can only pick up the slice at the top of one stack and place it on the top of a different stack.

The engineers have measured each slice and determined both its weight and its strength. The strength of a slice is the maximum combined weight of slices that may be placed on top of it. Of course, every slice is strong enough to hold the slices that were originally on top of it, otherwise the pyramid would have collapsed long time ago.

Your task is to plan how to move the slices from the original location to the new location, in an appropriate order. Your goal is to complete the job using as few moves as possible (a move consists of picking up a slice from the top of one stack and placing it on the top of a different stack).

Input

The first line of input contains 1 integer N (2 ≤ N ≤ 20), the number of horizontal slices. The next N lines describe the N horizontal slices in order from the top to the bottom of the pyramid. Each slice description consists of 2 integers that are the weight then the strength of this slice. The weight will range from 1 to 100,000,000 inclusive and the strength will range from 0 to 100,000,000 inclusive.

Output

The output must list the moves, one per line. Each line contains two integers, the source then the destination stack, separated by single space. Note that stack 1 is the original location, stack 2 is the temporary space and stack 3 is the new location. The maximum allowed number of moves in any of your output files is 3,000,000 moves.

Grading

There are 10 test cases total, each worth 10% of points. For each test case, your score (out of 10 points) will be:

• 0 points if the output violates the rules specified above.
• 10 points if your number of moves is the fewest for that case among the contestants.
• 2 + (6×A)/B points where A is a very good answer for the smallest number of moves in that test case, and B is your number of moves. The value will be rounded to the nearest integer. In the smaller test cases, A will be the optimal number of moves. In the larger test cases, A will be a very good answer that has been predetermined.

Example

4
3 4
2 3
3 6
2 10

1 3
1 3
1 2
3 2
3 2
1 3
2 1
2 1
2 3
1 3
1 3

1 2
1 2
1 3
1 2
3 1
2 3
1 3
2 3
2 3

For the sample input, output 1 solves it in 11 moves while output 2 solves it in 9 moves. Assuming that 9 moves is the best solution for that case, then output 2 will receive 10 points and output 1 will receive 2 + (6×9)/11 rounded to the nearest integer which is 7 points.

Note from admin: This problem was originally an output-only task that was intended to be solved over the course of the real contest. No optimal solution in polynomial time is known to the authors. Competitors' during the real contest were scored out of the best score among all the contestants. Ergo, it is even more difficult (if not, impossible?) to solve it by an actual program under the current time and memory limits here on the judge.

All Submissions
Best Solutions

Point Value: 50 (partial)
Time Limit: 30.00s
Memory Limit: 256M
Added: Apr 15, 2014

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

i realize this problem was up since like 2014 and nobody has solved it