1014. Product of Digits

Your task is to find the minimal positive integer number Q so that the product of digits of Q is exactly equal to N.

Input
The input contains the single integer number N (0 ≤ N ≤ 109). 

Output
Your program should print to the output the only number Q. If such a number does not exist print −1.

Sample
Input
10

Ouput 
25 

http://acm.timus.ru/problem.aspx?space=1&num=1014 

1009. K-based Numbers

Let’s consider K-based numbers, containing exactly N digits. We define a number to be valid if its K-based notation doesn’t contain two successive zeros. For example: 

1010230 is a valid 7-digit number;
1000198 is not a valid number;
0001235 is not a 7-digit number, it is a 4-digit number. 

Given two numbers N and K, you are to calculate an amount of valid K based numbers, containing N digits.
You may assume that 2 ≤ K ≤ 10; N ≥ 2; N + K ≤ 18.

Input
The numbers N and K in decimal notation separated by the line break.

Output
The result in decimal notation.

Sample
Input
2
10


Output
90

http://acm.timus.ru/problem.aspx?space=1&num=1009

1005. Stone Pile

You have a number of stones with known weights W1, …, Wn. Write a program that will rearrange the stones into two piles such that weight difference between the piles is minimal.

Input

Input contains the number of stones N (1 = N = 20) and weights of the stones W1, …, Wn (integers, 1 = Wi = 100000) delimited by white spaces.

Output

Your program should output a number representing the minimal possible weight difference between stone piles.

Sample

Input

5

5 8 13 27 14

Output

3

http://acm.timus.ru/problem.aspx?space=1&num=1005

1025. Democracy in Danger

Background
In one of the countries of Caribbean basin all decisions were accepted by the simple majority of votes at the general meeting of citizens (fortunately, there were no lots of them). One of the local parties, aspiring to come to power as lawfully as possible, got its way in putting into effect some reform of the election system. The main argument was that the population of the island recently had increased and it was to longer easy to hold general meetings.
The essence of the reform is as follows. From the moment of its coming into effect all the citizens were divided into K (may be not equal) groups. Votes on every question were to be held then in each group, moreover, the group was said to vote “for” if more than half of the group had voted “for”, otherwise it was said to vote “against”. After the voting in each group a number of group that had voted “for” and “against” was calculated. The answer to the question was positive if the number of groups that had voted “for” was greater than the half of the general number of groups.
At first the inhabitants of the island accepted this system with pleasure. But when the first delights dispersed, some negative properties became obvious. It appeared that supporters of the party, that had introduced this system, could influence upon formation of groups of voters. Due to this they had an opportunity to put into effect some decisions without a majority of voters “for” it.
Let’s consider three groups of voters, containing 5, 5 and 7 persons, respectively. Then it is enough for the party to have only three supporters in each of the first two groups. So it would be able to put into effect a decision with the help of only six votes “for” instead of nine, that would be necessary in the case of general votes.
Problem
You are to write a program, which would determine according to the given partition of the electors the minimal number of supporters of the party, sufficient for putting into effect of any decision, with some distribution of those supporters among the groups.

Input
In the first line an only odd integer K — a quantity of groups — is written (1 ≤ K ≤ 101). In the second line there are written K odd integers, separated with a space. Those numbers define a number of voters in each group. The population of the island does not exceeds 9999 persons.

Output
You should write a minimal quantity of supporters of the party, that can put into effect any decision.

Sample
Input:
3
5 7 5


Output
6

http://acm.timus.ru/problem.aspx?space=1&num=1025

1068. Sum

Your task is to find the sum of all integer numbers lying between 1 and N inclusive.


Input
The input consists of a single integer N that is not greater than 10000 by it's absolute value.

Output
Write a single integer number that is the sum of all integer numbers lying between 1 and N inclusive.


Sample
Input:
-3

Output
-5

http://acm.timus.ru/problem.aspx?space=1&num=1068

The Moronic Cowmpouter

 Inexperienced in the digital arts, the cows tried to build a calculating engine (yes, it's a cowmpouter) using binary numbers (base 2) but instead built one based on base negative 2! They were quite pleased since numbers expressed in base -2 do not have a sign bit.

You know number bases have place values that start at 1 (base to the 0 power) and proceed right-to-left to base^1, base^2, and so on. In base -2, the place values are 1, -2, 4, -8, 16, -32, ... (reading from right to left). Thus, counting from 1 goes like this: 1, 110, 111, 100, 101, 11010, 11011, 11000, 11001, and so on.

Eerily, negative numbers are also represented with 1's and 0's but no sign. Consider counting from -1 downward: 11, 10, 1101, 1100, 1111, and so on.

Please help the cows convert ordinary decimal integers (range -2,000,000,000 .. 2,000,000,000) to their counterpart representation in base -2.
Input

A single integer to be converted to base -2
Output

A single integer with no leading zeroes that is the input integer converted to base -2. The value 0 is expressed as 0, with exactly one 0. 

Example
Input:
-13

Output:
110111

https://www.spoj.pl/problems/NEG2/

Longest path in a tree

 You are given an unweighted, undirected tree. Write a program to output the length of the longest path (from one node to another) in that tree. The length of a path in this case is number of edges we traverse from source to destination.
Input

The first line of the input file contains one integer N --- number of nodes in the tree (0 < N <= 10000). Next N-1 lines contain N-1 edges of that tree --- Each line contains a pair (u, v) means there is an edge between node u and node v (1 <= u,v <= N).
Output

Print the length of the longest path on one line. 

Example
Input:
3
1 2
2 3

Output:
2

https://www.spoj.pl/problems/PT07Z/

Two squares or not two squares

Given integer n decide if it is possible to represent it as a sum of two squares of integers.
Input

First line of input contains one integer c<=100 - number of test cases. Then c lines follow, each of them consisting of exactly one integer 0<=n<=10^12.
Output

For each test case output Yes if it is possible to represent given number as a sum of two squares and No if it is not possible. 

Example
Input:
10
1
2
7
14
49
9
17
76
2888
27

Output:
Yes
Yes
No
No
Yes
Yes
Yes
No
Yes
No

https://www.spoj.pl/problems/TWOSQRS/

Relax! It is just a game

 You: What's the score? Did I miss much?

Me: It's 2-1 for elAhli and the second half just started. The first half was quite boring.

You: Who scored first? elAhli or ezZamalek?

Me: What difference does it make?

You: Big difference! I can predict the outcome of the match if I knew the order of which goals were scored in the first half.

Me: What do you mean?

You: It's 2-1 for elAhli, right? One of three things could have happened: elAhli scored two goals then ezZamalek scored; Or, elAhli scored its first goal, then ezZamalek, then elAhli again; Or, ezZamalek scored first, then elAhli scored its two goals.

Me: So?!! I still don't understand what difference does that make? It's still 2-1 for elAhli! Why don't you just relax and let us continue watching the game in peace.

You: You don't understand!! I believe the probability of who'll win depends on the order of how goals were scored. Now I have to predict the outcome for 3 possibilities.

Me: And what if the score was 3-2? What would you have done then?

You: I would have to work for 5 different possibilities. No?

Me: Of course not! The number of possibilities isn't always equal to the sum.

You: Can you tell me when will it be equal to the sum?

Me: You're a programmer, why don't you write a program that counts the number of possibilities and compare it to the sum?

You: I don't have the time, I want to watch the match. Besides, I have nine other problems to worry about.

Me: I'll give you a hint. The possibilities will be equal to the sum only if one of the teams scored a certain number of goals.
Input

Your program will be tested on one or more test cases. Each test case specifies two natural numbers (A and B ) (separated by one or more spaces) representing the score of the first half. No team will be able to score more than 10 goals. The last line of the input file contains two -1's (which is not part of the test cases.)
Output

Format For each test case where the number of possibilities is equal to the sum, print:

A+B=C

Where A and B are as above and C is their sum. If the number of possibilities is not equal to the sum, replace the '=' sign with '!=' (without the quotes.) 

Example
Input:
2 1
1 0
-1 -1

Output:
2+1=3
1+0=1

https://www.spoj.pl/problems/ANARC08E/

A Game with Numbers

Nikifor and Trofim play the following game: they write some integer smaller then 2000000000 and take turns one after another. Nikifor is the first to make a move. The turn is made by the following rule: from the written integer any non-zero digit is subtracted, and the new integer replaces the old one on the desk. For example for integer 40534, the next move can be: 40530, 40531 or 40529. The winner is the player who writes zero on the desk.

Write a program to decide who will win if both players do their best.
Input

The input contains the integer from which the game is started.
Output

In the first line you must write 1 if Nikifor wins and 2 otherwise. If Nikifor wins then in the second line you must output the move in the first turn which guarantees victory for him. If there are many such moves then output any of them. 

Example
Input:
14

Output:
1
4

https://www.spoj.pl/problems/NGM/

Bitmap

There is given a rectangular bitmap of size n*m. Each pixel of the bitmap is either white or black, but at least one is white. The pixel in i-th line and j-th column is called the pixel (i,j). The distance between two pixels p1=(i1,j1) and p2=(i2,j2) is defined as:


d(p1,p2)=|i1-i2|+|j1-j2|.


Task


Write a program which:
reads the description of the bitmap from the standard input,
for each pixel, computes the distance to the nearest white pixel,
writes the results to the standard output.
Input


The number of test cases t is in the first line of input, then t test cases follow separated by an empty line. In the first line of each test case there is a pair of integer numbers n, m separated by a single space, 1<=n <=182, 1<=m<=182. In each of the following n lines of the test case exactly one zero-one word of length m, the description of one line of the bitmap, is written. On the j-th position in the line (i+1), 1 <= i <= n, 1 <= j <= m, is '1' if, and only if the pixel (i,j) is white.
Output


In the i-th line for each test case, 1<=i<=n, there should be written m integers f(i,1),...,f(i,m) separated by single spaces, where f(i,j) is the distance from the pixel (i,j) to the nearest white pixel.


Example
Sample input:
1
3 4
0001
0011
0110


Sample output:
3 2 1 0
2 1 0 0
1 0 0 1

https://www.spoj.pl/problems/BITMAP/ 

Bytelandian gold coins

 In Byteland they have a very strange monetary system.

Each Bytelandian gold coin has an integer number written on it. A coin n can be exchanged in a bank into three coins: n/2, n/3 and n/4. But these numbers are all rounded down (the banks have to make a profit).

You can also sell Bytelandian coins for American dollars. The exchange rate is 1:1. But you can not buy Bytelandian coins.

You have one gold coin. What is the maximum amount of American dollars you can get for it?
Input

The input will contain several test cases (not more than 10). Each testcase is a single line with a number n, 0 <= n <= 1 000 000 000. It is the number written on your coin.
Output

For each test case output a single line, containing the maximum amount of American dollars you can make. 

Example
Input:
12
2

Output:
13
2

You can change 12 into 6, 4 and 3, and then change these into $6+$4+$3 = $13. If you try changing the coin 2 into 3 smaller coins, you will get 1, 0 and 0, and later you can get no more than $1 out of them. It is better just to change the 2 coin directly into $2.


https://www.spoj.pl/problems/COINS/

Ambiguous Permutations

 Some programming contest problems are really tricky: not only do they require a different output format from what you might have expected, but also the sample output does not show the difference. For an example, let us look at permutations.
A permutation of the integers 1 to n is an ordering of these integers. So the natural way to represent a permutation is to list the integers in this order. With n = 5, a permutation might look like 2, 3, 4, 5, 1.
However, there is another possibility of representing a permutation: You create a list of numbers where the i-th number is the position of the integer i in the permutation. Let us call this second possibility an inverse permutation. The inverse permutation for the sequence above is 5, 1, 2, 3, 4.
An ambiguous permutation is a permutation which cannot be distinguished from its inverse permutation. The permutation 1, 4, 3, 2 for example is ambiguous, because its inverse permutation is the same. To get rid of such annoying sample test cases, you have to write a program which detects if a given permutation is ambiguous or not.
Input Specification

The input contains several test cases.
The first line of each test case contains an integer n (1 ≤ n ≤ 100000). Then a permutation of the integers 1 to n follows in the next line. There is exactly one space character between consecutive integers. You can assume that every integer between 1 and n appears exactly once in the permutation.
The last test case is followed by a zero.
Output Specification

For each test case output whether the permutation is ambiguous or not. Adhere to the format shown in the sample output. 

Sample Input
4
1 4 3 2
5
2 3 4 5 1
1
1
0
Sample Output
ambiguous
not ambiguous
ambiguous


https://www.spoj.pl/problems/PERMUT2/

Candy I

Jennifer is a teacher in the first year of a primary school. She has gone for a trip with her class today. She has taken a packet of candies for each child. Unfortunatelly, the sizes of the packets are not the same.

Jennifer is afraid that each child will want to have the biggest packet of candies and this will lead to quarrels or even fights among children. She wants to avoid this. Therefore, she has decided to open all the packets, count the candies in each packet and move some candies from bigger packets to smaller ones so that each packet will contain the same number of candies. The question is how many candies she has to move.
Input specification

The input file consists of several blocks of data. Each block starts with the number of candy packets N(1<= N <=10000) followed by N integers (each less than 1000) in separate lines, giving the number of candies in each packet. After the last block of data there is the number -1.
Output specification

The output file should contain one line with the smallest number of moves for each block of data. One move consists of taking one candy from a packet and putting it into another one. If it is not possible to have the same number of candies in each packet, output the number -1. 
 
Example
Input file:
5
1
1
1
1
6
2
3
4
-1

Output file:
4
-1
  

https://www.spoj.pl/problems/CANDY/

Fashion Shows

A fashion show rates participants according to their level of hotness. Two different fashion shows were organized, one for men and the other for women. A date for the third is yet to be decided ;) .

Now the results of both fashion shows are out. The participants of both the fashion shows have decided to date each other, but as usual they have difficuly in choosing their partners. The Maximum Match dating serive (MMDS) comes to their rescue and matches them in such a way that that maximizes the hotness bonds for all couples.

If a man has been rated at hotness level x and a women at hotness level y, the value of their hotness bond is x*y.

Both fashion shows contain N participants each. MMDS has done its job and your job is to find the sum of hotness bonds for all the couples that MMDS has proposed.
Input

The first line of the input contains an integer t, the number of test cases. t test cases follow.

Each test case consists of 3 lines:
The first line contains a single integer N (1 <= N <= 1000).
The second line contains N integers separated by single spaces denoting the hotness levels of the men.
The third line contains N integers separated by single spaces denoting the hotness levels of the women.

All hotness ratings are on a scale of 0 to 10.
Output

For each test case output a single line containing a single integer denoting the sum of the hotness bonds for all pairs that MMDS has proposed.

Example
Input:
2
2
1 1
3 2
3
2 3 2
1 3 2

Output:
5
15

https://www.spoj.pl/problems/FASHION/

Count on Cantor

 One of the famous proofs of modern mathematics is Georg Cantor's demonstration that the set of rational numbers is enumerable. The proof works by using an explicit enumeration of rational numbers as shown in the diagram below.
1/1 1/2 1/3 1/4 1/5 ...
2/1 2/2 2/3 2/4
3/1 3/2 3/3
4/1 4/2
5/1

In the above diagram, the first term is 1/1, the second term is 1/2, the third term is 2/1, the fourth term is 3/1, the fifth term is 2/2, and so on.
Input

The input starts with a line containing a single integer t <= 20, the number of test cases. t test cases follow.

Then, it contains a single number per line.
Output

You are to write a program that will read a list of numbers in the range from 1 to 10^7 and will print for each number the corresponding term in Cantor's enumeration as given below.
 
Example
Input:
3
3
14
7

Output:
TERM 3 IS 2/1
TERM 14 IS 2/4
TERM 7 IS 1/4


https://www.spoj.pl/problems/CANTON/

To and Fro

Mo and Larry have devised a way of encrypting messages. They first decide secretly on the number of columns and write the message (letters only) down the columns, padding with extra random letters so as to make a rectangular array of letters. For example, if the message is “There’s no place like home on a snowy night” and there are five columns, Mo would write down 

t o i o y
h p k n n
e l e a i
r a h s g
e c o n h
s e m o t
n l e w x


Note that Mo includes only letters and writes them all in lower case. In this example, Mo used the character ‘x’ to pad the message out to make a rectangle, although he could have used any letter. Mo then sends the message to Larry by writing the letters in each row, alternating left-to-right and right-to-left. So, the above would be encrypted as

toioynnkpheleaigshareconhtomesnlewx

Your job is to recover for Larry the original message (along with any extra padding letters) from the encrypted one.
Input

There will be multiple input sets. Input for each set will consist of two lines. The first line will contain an integer in the range 2...20 indicating the number of columns used. The next line is a string of up to 200 lower case letters. The last input set is followed by a line containing a single 0, indicating end of input.
Output

Each input set should generate one line of output, giving the original plaintext message, with no spaces.

Example
Input:

5
toioynnkpheleaigshareconhtomesnlewx
3
ttyohhieneesiaabss
0

Output:

theresnoplacelikehomeonasnowynightx
thisistheeasyoneab

https://www.spoj.pl/problems/TOANDFRO/

Mispelling

Misspelling is an art form that students seem to excel at. Write a program that removes the nth character from an input string.
Input

The first line of input contains a single integer N, (1 ≤ N ≤ 1000) which is the number of datasets that follow.

Each dataset consists of a single line of input containing M, a space, and a single word made up of uppercase letters only. M will be less than or equal to the length of the word. The length of the word is guaranteed to be less than or equal to 80.
Output

For each dataset, you should generate one line of output with the following values: The dataset number as a decimal integer (start counting at one), a space, and the misspelled word. The misspelled word is the input word with the indicated character deleted. 

Example
Input:
4
4 MISSPELL
1 PROGRAMMING
7 CONTEST
3 BALLOON

Output:
1 MISPELL
2 ROGRAMMING
3 CONTES
4 BALOON



https://www.spoj.pl/problems/GNY07A/

Feynman

Richard Phillips Feynman was a well known American physicist and a recipient of the Nobel Prize in Physics. He worked in theoretical physics and also pioneered the field of quantum computing. He visited South America for ten months, giving lectures and enjoying life in the tropics. He is also known for his books "Surely You're Joking, Mr. Feynman!" and "What Do You Care What Other People Think?", which include some of his adventures below the equator.

His life-long addiction was solving and making puzzles, locks, and cyphers. Recently, an old farmer in South America, who was a host to the young physicist in 1949, found some papers and notes that is believed to have belonged to Feynman. Among notes about mesons and electromagnetism, there was a napkin where he wrote a simple puzzle: "how many different squares are there in a grid of N ×N squares?".

In the same napkin there was a drawing which is reproduced below, showing that, for N=2, the answer is 5.
    
Input

The input contains several test cases. Each test case is composed of a single line, containing only one integer N, representing the number of squares in each side of the grid (1 ≤ N ≤ 100).

The end of input is indicated by a line containing only one zero.
Output

For each test case in the input, your program must print a single line, containing the number of different squares for the corresponding input.
 
Example
Input:
2
1
8
0


Output:
5
1
204

https://www.spoj.pl/problems/SAMER08F/

Divisor Summation

 Given a natural number n (1 <= n <= 500000), please output the summation of all its proper divisors.

Definition: A proper divisor of a natural number is the divisor that is strictly less than the number.

e.g. number 20 has 5 proper divisors: 1, 2, 4, 5, 10, and the divisor summation is: 1 + 2 + 4 + 5 + 10 = 22.

Input

An integer stating the number of test cases (equal to about 200000), and that many lines follow, each containing one integer between 1 and 500000 inclusive.
Output

One integer each line: the divisor summation of the integer given respectively. 

Example
Sample Input:
3
2
10
20

Sample Output:
1
8
22

https://www.spoj.pl/problems/DIVSUM/