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/