Etapa 4 adm

SPOJ Problem Set (classical): 3406. Bases. Problem code: SAMER08B

http://www.spoj.pl/problems/SAMER08B/

What do you get if you multiply 6 by 9? The answer, of course, is 42, but only if you do the calculations in base 13.

Given an integer B ≥ 2, the base B numbering system is a manner of writing integers using only digits between 0 and B -1, inclusive. In a number written in base B, the rightmost digit has its value multiplied by 1, the second rightmost digit has its value multiplied by B, the third rightmost digit has its value multiplied by B2, and so on.

Some equations are true or false depending on the base they are considered in. The equation 2+2=4, for instance, is true for any B ≥ 5 - it does not hold in base 4, for instance, since there is no digit '4' in base 4. On the other hand, an equation like 2+2=5 is never true.

Write a program that given an equation determines for which bases it holds.

Input

Each line of the input contains a test case; each test case is an equation of the form "EXPR=EXPR", where both "EXPR" are arithmetic expressions with at most 17 characters.

All expressions are valid, and contain only the characters '+', '*' and the digits from '0' to '9'. No expressions contain leading plus signs, and no numbers in it have leading zeros.

The end of input is indicated by a line containing only "=".

Output

For each test case in the input your program should produce a single line in the output, indicating for which bases the given equation holds.

If the expression is true for infinitely many bases, print "B+", where B is the first base for which the equation holds.

If the expression is valid only for a finite set of bases, print them in ascending order, separated by single spaces.

If the expression is not true in any base, print the character '*'.

Example

Added by: Diego Satoba

Date: 2008-11-23

Time limit: 1s

Source limit: 50000B

Languages: C C++ 4.3.2 C++ 4.0.0-8 JAVA PAS fpc PAS gpc

Resource: South American Regional Contests 2008 

SPOJ Problem Set (classical): 3407. Candy.Problem code: SAMER08C.

http://www.spoj.pl/problems/SAMER08C/

Little Charlie is a nice boy addicted to candies. He is even a subscriber to All Candies Magazine and was selected to participate in the International Candy Picking Contest.

In this contest a random number of boxes containing candies are disposed in M rows with N columns each (so, there are a total of M ×N boxes). Each box has a number indicating how many candies it contains.

The contestant can pick a box (any one) and get all the candies it contains. But there is a catch (there is always a catch): when choosing a box, all the boxes from the rows immediately above and immediately below are emptied, as well as the box to the left and the box to the right of the chosen box. The contestant continues to pick a box until there are no candies left.

The figure bellow illustrates this, step by step. Each cell represents one box and the number of candies it contains. At each step, the chosen box is circled and the shaded cells represent the boxes that will be emptied. After eight steps the game is over and Charlie picked 10+9+8+3+7+6+10+1 = 54 candies.

[pic 1]

For small values of M and N, Charlie can easily find the maximum number of candies he can pick, but when the numbers are really large he gets completely lost. Can you help Charlie maximize the number of candies he can pick?

Input

The input contains several test cases. The first line of a test case contains two positive integers M and N (1 ≤ M ×N ≤ 105), separated by a single space, indicating the number of rows and columns respectively. Each of the following M lines contains N integers separated by single spaces, each representing the initial number of candies in the corresponding box. Each box will have initially at least 1 and at most 103 candies.

The end of input is indicated by a line containing two zeroes separated by a single space.

Output

For each test case in the input, your program must print a single line, containing a single value, the integer indicating the maximum number of candies that Charlie can pick.

Example

Added by: Diego Satoba

Date: 2008-11-23

Time limit: 2s  

Source limit: 50000B

Languages: C C++ 4.3.2 C++ 4.0.0-8 JAVA PAS fpc PAS gpc

Resource: South American Regional Contests 2008

SPOJ Problem Set (classical): 3409. Electricity. Problem code: SAMER08E.

http://www.spoj.pl/problems/SAMER08E/

Martin and Isa stopped playing crazy games and finally got married. It's good news! They're pursuing a new life of happiness for both and, moreover, they're moving to a new house in a remote place, bought with most of their savings.

Life is different in this new place. In particular, electricity is very expensive, and they want to keep everything under control. That's why Martin proposed to keep a daily record of how much electricity has been consumed in the house. They have an electricity meter, which displays a number with the amount of KWh (kilowatt-hour) that has been consumed since their arrival.

...