George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.
Input
The input contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.
Output
The output should contains the smallest possible length of original sticks, one per line.
An addition chain for n is an integer sequence with the following four properties: a_0 = 1 a_m = n a_0 < a_1 < a_2 < … < a_m-1 < a_m For each k (1<=k<=m) there exist two (not necessarily different) integers i and j (0<=i, j<=k-1) with a_k=a_i+a_j You are given an integer n. Your job is to construct an addition chain for n with minimal length. If there is more than one such sequence, any one is acceptable. For example, <1,2,3,5> and <1,2,4,5> are both valid solutions when you are asked for an addition chain for 5.
Input
The input will contain one or more test cases. Each test case consists of one line containing one integer n (1<=n<=100). Input is terminated by a value of zero (0) for n.
Output
For each test case, print one line containing the required integer sequence. Separate the numbers by one blank. Hint: The problem is a little time-critical, so use proper break conditions where necessary to reduce the search space.
Little Tom loves playing games. One day he downloads a little computer game called ‘Bloxorz’ which makes him excited. It’s a game about rolling a box to a specific position on a special plane. Precisely, the plane, which is composed of several unit cells, is a rectangle shaped area. And the box, consisting of two perfectly aligned unit cube, may either lies down and occupies two neighbouring cells or stands up and occupies one single cell. One may move the box by picking one of the four edges of the box on the ground and rolling the box 90 degrees around that edge, which is counted as one move. There are three kinds of cells, rigid cells, easily broken cells and empty cells. A rigid cell can support full weight of the box, so it can be either one of the two cells that the box lies on or the cell that the box fully stands on. A easily broken cells can only support half the weight of the box, so it cannot be the only cell that the box stands on. An empty cell cannot support anything, so there cannot be any part of the box on that cell. The target of the game is to roll the box standing onto the only target cell on the plane with minimum moves.
The box stands on a single cell ↑
The box lies on two neighbouring cells, horizontally ↑
The box lies on two neighbouring cells, vertically ↑
After Little Tom passes several stages of the game, he finds it much harder than he expected. So he turns to your help.
Input
Input contains multiple test cases. Each test case is one single stage of the game. It starts with two integers R and C(3 ≤ R, C ≤ 500) which stands for number of rows and columns of the plane. That follows the plane, which contains R lines and C characters for each line, with ‘O’ (Oh) for target cell, ‘X’ for initial position of the box, ‘.’ for a rigid cell, ‘#’ for a empty cell and ‘E’ for a easily broken cell. A test cases starts with two zeros ends the input.
It guarantees that
There’s only one ‘O’ in a plane.
There’s either one ‘X’ or neighbouring two ‘X’s in a plane.
The first(and last) row(and column) must be ‘#’(empty cell).
Cells covered by ‘O’ and ‘X’ are all rigid cells.
Output
For each test cases output one line with the minimum number of moves or “Impossible” (without quote) when there’s no way to achieve the target cell.
