Simple puzzles

ID 33366. List of divisors - 02

Write a program that searches among the integers belonging to the numerical interval [289039; 311993] numbers,  which have exactly 8 different natural divisors, not counting 1 and the number itself. For each found number, print these 8 divisors from a new line in ascending order of the sum of these 8 divisors. Divisors must be in ascending order.

ID 33367. List of divisors - 03

Write a program that searches among the integers belonging to the numerical interval [108933; 132757] numbers which have exactly 2 different natural divisors, not counting 1 and the number itself. For each found number print these 2 divisors from a new line in ascending order of the product of these 2 divisors. Divisors must be in ascending order.

ID 33368. List of divisors - 04

Write a program that searches among the integers belonging to the numerical interval [102438; 124698] numbers that have exactly 7 different natural divisors, not counting 1 and the number itself. For each found number, print these 7 divisors from a new line in ascending order of the product of these 7 divisors. Divisors must be in ascending order.

ID 38234. Simple list - 01

Write a program that searches among the integers belonging to the numerical interval [2385177; 2385437] prime numbers. Print all found prime numbers in ascending order, to the left of each number print its number in order (print each number with a number on a new line). 

ID 38334. simple square

Petya has a playing field of 3x3 size, filled with numbers from 1 to 9. At the beginning of the game, he can place a chip in any cell of the field. At each step of the game, it is allowed to move a piece to any cell adjacent to the side, but it is not allowed to visit the same cell twice. Petya carefully keeps the protocol of the game, writing down the numbers in it in the order in which the chip visited the cells. Petya was wondering what is the maximum number he can get in the protocol. Help him answer this question.

Input
The input file contains the description of the — 3 lines of 3 integers separated by spaces. It is guaranteed that all nine numbers are different and lie in the range from 1 to 9.

Imprint
Print a single integer — the maximum number that could result in the protocol when playing on this field.

The answer can be displayed not as a number, but as a string or as a sequence of individual digits (but not separated by spaces).

Examples

ID 38435. Excavations

During recent excavations on Mars, sheets of paper with mysterious symbols on them were discovered. After much research, scientists came to the conclusion that the inscriptions on them could actually be ordinary numerical equalities. If this conclusion turned out to be correct, it would prove not only that there were intelligent beings on Mars many years ago, but also that they already knew how to count…
Scientists were able to understand what the found symbols mean in this case, and translated these equalities into ordinary language — the language of numbers, brackets, arithmetic and equal signs. In addition, strong evidence was obtained from other sources that the Martians knew only three operations — addition, multiplication and subtraction (the Martians never used "unary minus": instead of "5" they wrote "0" 5). Scientists also proved that the Martians did not give operations different priorities, but simply calculated expressions (if there were no brackets in them) from left to right: for example, 3 + 3 * 5 was 30, not 18.
Unfortunately, for some reason, the Martians applied the symbols of arithmetic operations with special ink, which, as it turned out, was not very resistant, and therefore there were spaces between the numbers instead of the action signs in the sheets found. If all of the above theory is correct, then instead of these spaces, signs of addition, subtraction and multiplication can be put so that the equalities become true. For example, if a sheet of paper with the inscription “18=7 (5 3) 2” was found, then the following arrangement of characters is possible: “18=7+(5–3)*2” (remember the order in which Martians evaluate expressions!). At the same time, if a sheet with the inscription “5=3 3” came across, then the Martians clearly did not mean numerical equality when they wrote it…
You must write a program that finds the required character set or reports that it doesn't exist.

Input data format
The first line of the input file consists of a natural (positive integer) number not exceeding 2³⁰, an equal sign, and a sequence of natural numbers (not more than ten), the product of which also does not exceed 2<sup>30. Some groups of numbers (one or more) may be surrounded by brackets. The length of the input string will not exceed 80 characters, and there are no other restrictions on the number and nesting of parentheses. There will always be at least one space between two adjacent numbers not separated by brackets, in all other places there can be any number of spaces (including 0) (of course, there are no spaces inside the number).

Output data format
It is necessary to output one line containing the obtained equality (ie, the original equality with inserted arithmetic operation signs) into the output file. If the required character arrangement is not possible, output a string consisting of the single number “–1”. The output string must not contain spaces.</sup>
 

Examples

ID 38587. Diamond Turtles

Funny Wu likes to give diamond turtles as gifts. He has turtles in his bag in either three colors: pink, white and green, or four colors: pink, white, green and yellow. He gave the turtles one by one from the bag, the color of the ith turtle was Si. The colors are presented as follows: P -pink, W- white, G -green, < code>Y - yellow. If there were three colors of turtles in the bag, print Three; if there were four colors, print Four. 

Input
The first line contains the number N (\(1<=N<=100\)) - the number of Turtles that Veselchak U. Vo took out the second line contains N characters Si - the colors of the turtles taken out. Each character Si is equal to P, W, G  or Y. There are always i, j and k such that Si = &# 39;P', Sj = 'W' and Sk = 'G'.

Imprint
If there were three colors of turtles in the bag, print Three; if there were four colors, print Four. 

Examples

ID 38618. Lagrange's theorem

Lagrange's theorem states that any natural number can be represented as the sum of four perfect squares. For the given number n find the following representation: print from 1 to 4 natural numbers whose squares add up to the given number.

Input
The program receives as input one natural number n < 10000.

Imprint
The program should print from 1 to 4 natural numbers, the squares of which add up to the given number.

Examples

ID 38620. The sum of two cubes

Express the given number n as the sum of two cubes.

Input
The program receives as input one natural number n (n <= 1028).

Imprint
The program should output 2 non-negative integers (in descending order) whose sum of cubes is equal to n. If it's impossible, print the string impossible.
 

Examples

ID 38632. Mockery

Stirlitz was driving a car, saw Bormann voting, and drove past. After a while, he again saw Bormann voting, and again drove past. Soon he saw Bormann voting again.
 - scoffs! thought Bormann.
 - Ring! - Stirlitz guessed.

There are N squares in the city. Any two squares are connected to each other by exactly one two-way road. Stirlitz lives in this city. Stirlitz has a hobby - he likes to leave the house on Sunday mornings, get into the car, choose some ring route that passes exactly three squares (that is, first he goes from some square to some other, then to the third , then returns to the initial one, and again travels along this route). He imagines that Bormann is somewhere along the way. And so Stirlitz drives all Sunday, until his head is spinning, and rejoices...

Naturally, Stirlitz wants to drive past the point where, as he imagines, Bormann is standing, as often as possible. To do this, of course, the route chosen by Stirlitz should be as short as possible. Write a program that will choose the optimal route for Stirlitz.

Input
The first line specifies  number N (3 <= N <= 100). The following lines contain a matrix of NxN distances between squares (the number in position i,j denotes the length of the road connecting the i-th and j-th squares). All numbers in the matrix (except for those on the main diagonal) are natural numbers, not exceeding 1000. The matrix is ​​symmetrical with respect to the main diagonal, there are 0 on the main diagonal.

Imprint
It is required to print three numbers — numbers of areas in the optimal route. If there are several routes, print any of them.

Examples

ID 38653. Lots of formulas

You are given a string S consisting of numbers from 1 to 9 inclusive. You can insert the character + at some positions (perhaps none) between two digits in this string. Here, the + character must not appear consecutively after insertion (i.e., there must not be two or more +  characters in a row). All rows that can be obtained in this way can be evaluated as formulas. Evaluate all possible formulas and print the sum of the results from all possible formulas.

Input
The input is a non-empty string S, consisting of numbers from 1 to 9 inclusive. The string is limited to 10 characters.

Imprint
Print the sum of the results obtained by evaluating all possible formulas.
 

Examples

ID 38795. Ascending Equation

Given a function \(z(x) = ax^3 + bx^2 + cx + d\). For the given numbers a, b, c and d, print all x integer values code> from the range from 0 to 1000, in which the function z(x) takes the value zero.

Input
The program receives 4 numbers as input: a, b, c and d. Each number is written on a separate line.

Imprint
Print all the x values ​​that satisfy the task condition in ascending order. 
 

Examples

ID 18728. Trolleybuses

ID 38919. Coloring book in three colors

Petya drew n circles on paper and connected some pairs of circles with lines. After that, he colored each circle in one of the three colors – red, blue or green.

Now Petya wants to change their coloring. Namely – he wants to recolor each circle with some other color so that no two circles of the same color are connected by a line. At the same time, he wants to necessarily recolor each circle, and repainting the circle in the same color as it was originally painted is not allowed.

Help Petya decide what colors the mugs should be repainted in order to fulfill the specified condition.

Input
The first line contains two integers n and m – the number of circles and the number of lines drawn by Petya, respectively (1 ≤ n ≤ 1000, 0 ≤ m ≤ 20000).
The next line contains n characters from the set {'R', 'G', 'B'} – The i-th of these symbols means the color of the i-th circle ('R' – red, 'G' – green, 'B' &ndash ; blue).
Then m lines contain two integers – pairs of circles connected by segments.

Imprint
Print  one line consisting of n characters from the set {'R', 'G', 'B'} – the colors of the circles after repainting. If there are several solutions, print any one.
If there is no solution, print  the word "Impossible''.
 

Examples

ID 39387. royal journey

His Majesty King Bubei II wished to travel around his domain. At the same time, the route has the following wishes:

1) the route should take the least possible time (royal time – is a very valuable thing and should be protected);

2) the route must include all the settlements exactly once (if the king misses a settlement, then its inhabitants will be outraged by the royal inattention and stop paying taxes; if the king visits a settlement more than once, then the inhabitants of the remaining settlements items will also be indignant)

3) the route must begin and end in the capital of the state (having traveled around his possessions, the king must immediately get down to business). The capital is included in the route exactly 2 times: as a point of departure and as a destination, it cannot be an intermediate settlement of the route.

Write a program that uses the road map of the kingdom to find such a route or determines that it is impossible to fulfill all the requirements.

Input
first enter the number N (natural, does not exceed 10) – the number of settlements in the kingdom. Then follows N lines of N numbers in each – travel time between settlements (time – is a non-negative integer, does not exceed 500; if time = 0, then this means that there is no way between some settlements). Settlement No. 1 is the capital of the state.

Imprint
print the least total time that His Majesty will spend on a detour around his domains, or the number -1 if it is impossible to build a route with the given properties.

Examples

ID 39390. Social distancing I

A terrible disease afflicts the cows. Farmer John wants to protect them.
The FD Barn is a narrow long building containing N stalls in a row (2≤N≤105). Some of these stalls are already occupied by cows, some are free. After reading about the need for social distancing, the FD wants to maximize D, where D is the distance between the two closest occupied stalls. For example, if stalls 3 and 8 are the closest that are occupied, then D=5.

Two new cows have been added to FD's herd, and he must decide which unoccupied stall to place each of them in. Determine how k he should place these cows so that the result D, becomes the maximum possible. The FD cannot move any existing cows, he can only assign stalls to new cows.

Input
The first line of input contains N. The next line contains a string of length N, consisting of 0 and 1, describing the sequence of stalls in the barn. 0 means an empty stall, 1 means an occupied stall. There are at least two zeros in the string, which is enough to accommodate two cows.
Imprint
Output the largest value of D (the smallest distance between two occupied stalls) that the FD can obtain by adding two new cows in an optimal way.

Examples

ID 43474. Gromozeka and valerian

Gromozeka loves valerian very much. On his home planet Chumaroza you can buy for k chumriks (local currency) the first package of valerian, for 2·k chumriks -  the second and so on (in other words, ith packing you have to pay i·k chumrikov). Gromozek wants to buy  w packages of valerian.  He has n chumriks. How many chumriks will he have to take on credit from the chumaroz bank in order to buy w packages of valerian?

The first line contains three positive integers k, n, w (1  <=  k, w< /code>  <=  1000, 0 <= n <= 109) , the cost of the first package, Gromozeka's initial number of chumaroziki and the number of packages of valerian he wants to buy.

ID 43718. Misha's Cubes

Little Misha has cubes, each of which has one English lowercase letter written on it. Yesterday he laid out the cubes in two rows. In the first row Misha has n cubes with letters, in the second - m cubes with letters. It so happened that in these two rows there are no matching letters. In other words, no letter is contained in both rows at the same time.
Today little Misha decided to continue playing with blocks. But now he takes any one cube from any row and makes a third row of them, always adding a cube to the end. Little Misha never takes more than k dice in a row from the same row. Misha stopped playing when he ran out of cubes in one row (in the first or in the second).
Dad, who was watching the game, noticed that playing in this way, Misha got the lexicographically smallest line. Using the known two strings, which are formed by reading the letters of the first and second rows and the number k determine the string that little Misha received.

The string x is lexicographically less than the string y only and only if one of the following conditions is true:
- x is a prefix of y, but x != y;
- in the first position, where x and y differ, in the string x there is a letter that is in the alphabet earlier than the corresponding letter y.


Input
The program receives several lines as input. The first line contains three numbers: n - the number of cubes in the first row, m - the number of cubes in the second row, k > is an integer(1 <= n, m, k <= 100). The second line contains a string a of length n - a string formed by reading the letters written on the cubes of the first row. In the third line - string b of length m - a string formed by reading the letters written on the cubes of the second row.

Imprint
Print the answer to the problem.
 
 

Examples

ID 44034. Get to the toys

Santa Claus decided to check the toy factory to see if all the gifts for children are ready. To get to the toy storage area, he needs to go through a narrow secret corridor. In the corridor, for each meter of the path, the number of meters from the door is indicated. At the door, near which Santa Claus is standing, the number 0 is written. You can move along the corridor both to the left and to the right. When moving to the left, the numbers are negative, when moving to the right, they are positive.

Because the location is classified, the factory is constantly changing the entrance to the toy store. 

Santa Claus knows that today the entrance to the factory is located at the door with the number X. It is also known that in the corridor, next to the number Y there is a door blocking the passage along the corridor. To open it, you need to take the key, which is located on the wall on the shelf in the corridor next to the number Z.

Determine if Santa Claus himself can get to the door to the toys. If possible, determine the minimum distance that Santa Claus will need to walk. If it fails, then print -1.

Examples