Description

Given a,b, output a+b.

Input

a,b<=100000000.

Output

a+b

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a string S, output the reverse of S.

Input

The input consists of many lines. Each line is a string S with length <= 1000000.
The string S does not contain any spaces.

Output

Output the the reverse of S. One in each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Professor Robert A. J. Matthews of the Applied Mathematics and Computer Science Department at the University of Aston in Birmingham, England has recently described howthe positions of stars across the night skymay be used to deduce a surprisingly accurate value of π. This result followed from the application of certain theorems in number theory.

Here, we don'thave the night sky, but can use the same theoretical basis to form an estimate for π

Given any pair of whole numbers chosen from a large, random collection of numbers, the probability that the twonumbers have no common factor other than one (1) is 6/π²

For example, using the small collection of numbers: 2, 3, 4, 5, 6; there are 10 pairs that can be formed: (2,3), (2,4), etc. Six of the 10 pairs: (2,3), (2,5), (3,4), (3,5), (4,5) and (5,6) have no common factor other than one. Using the ratio of the counts as the probability we have:

6/π² ~ 6/10

π ~ 3.162

In this problem, you'll receive a series of data sets. Each data set contains a set of pseudo-random positive integers. For each data set, find the portion of the pairs which may be formed that have nocommon factor other than one (1), and use the method illustrated above to obtain an estimate for π. Report this estimate for each data set.

Input

The input consists of a series of data sets.

The first line of each data set contains a positive integer value, N, greater than one (1) and less than 50.

There is one positive integer per line for the next N lines that constitute the set for which the pairs are to be examined. These integers are each greater than 0 and less than 32768.

Each integer of the input stream has its first digit as the first character on the input line.

The set size designator, N, will be zero to indicate the end of data.

Output

A line with a single real value is to be emitted for each input data set encountered. This value is the estimate for π for the data set. An output format like the sample below should be used. Answers must be rounded to six digits after the decimal point.

For some data sets, it may be impossible to estimate a value for π. This occurs when there are no pairs without common factors. In these cases, emit the single-line message:

No estimate for this data set.

Exactly, starting with the first character, "N", as the first character on the line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

For any two integers x and k there exists two more integers p and q such that:

It’s a fairly easy task to prove this theorem, so we’d not ask you to do that. We’d ask for something even easier! Given the values of x and k, you’d only need to find integers p and q that satisfies the given equation. 

Input

The first line of the input contains an integer, T (1≤T≤1000) that gives you the number of test cases. In each of the following T lines you’d be given two positive integers x and k. You can safely assume that x and k will always be less than 10⁸.

Output

For each of the test cases print two integers: p and q in one line. These two integers are to be separated by a single space. If there are multiple pairs of p and q that satisfy the equation, any one would do. But to help us keep our task simple, please make sure that the values,  and fit in a 64 bit signed integer.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Have you ever played Minesweeper? It's a cute little game which comes within a certain Operating System which name we can't really remember. Well, the goal of the game is to find where are all the mines within a MxN field. To help you, the game shows a number in a square which tells you how many mines there are adjacent to that square. For instance, supose the following 4x4 field with 2 mines (which are represented by an * character):

*...
....
.*..
....

If we would represent the same field placing the hint numbers described above, we would end up with:

*100
2210
1*10
1110

As you may have already noticed, each square may have at most 8 adjacent squares.

Input

The input will consist of an arbitrary number of fields. The first line of each field contains two integers n and m (0 < n,m <= 100) which stands for the number of lines and columns of the field respectively. The next n lines contains exactly m characters and represent the field. Each safe square is represented by an "." character (without the quotes) and each mine square is represented by an "*" character (also without the quotes). The first field line where n = m = 0 represents the end of input and should not be processed.

Output

For each field, you must print the following message in a line alone:

Field #x:

Where x stands for the number of the field (starting from 1). The next n lines should contain the field with the "." characters replaced by the number of adjacent mines to that square. There must be an empty line between field outputs.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to find the shortest closed tour of knight moves that visits each square of a given set of n squares on a chessboard exactly once. He thinks that the most difficult part of the problem is determining the smallest number of knight moves between two given squares and that, once you have accomplished this, finding the tour would be easy.

Of course you know that it is vice versa. So you offer him to write a program that solves the "difficult" part.

Your job is to write a program that takes two squares a and b as input and then determines the number of knight moves on a shortest route from a to b.

Input

The input file will contain one or more test cases. Each test case consists of one line containing two squares separated by one space. A square is a string consisting of a letter (a-h) representing the column and a digit (1-8) representing the row on the chessboard.

Output

For each test case, print one line saying "To get from xx to yy takes n knight moves.".

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a range [a, b], you are to find the summation of all the odd integers in this range. For example, the summation of all the odd integers in the range [3, 9] is 3 + 5 + 7 + 9 = 24.

Input

There can be at multiple test cases. The first line of input gives you the number of test cases, T ( 1<=T<=100). Then T test cases follow. Each test case consists of 2 integers a and b ( 0<=a<=b<=100) in two separate lines.

Output

For each test case you are to print one line of output - the serial number of the test case followed by the summation of the odd integers in the range [a, b].

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Your job is, given a positive number N, determine if it is a multiple of eleven.

Input

The input is a file such that each line contains a positive number. A line containing the number 0 is the end of the input. The given numbers can contain up to 1000 digits.

Output

The output of the program shall indicate, for each input number, if it is a multiple of eleven or not.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You have devised a new encryption technique which encodes a message by inserting between its characters randomly generated strings in a clever way. Because of pending patent issues we will not discuss in detail how the strings are generated and inserted into the original message. To validate your method, however, it is necessary to write a program that checks if the message is really encoded in the final string.

Given two strings s and t, you have to decide whether s is a subsequence of t, i.e. if you can remove characters from t such that the concatenation of the remaining characters is s.

Input

The input contains several testcases. Each is specified by two strings s, t of alphanumeric ASCII characters separated by whitespace and the lengths of s, t are less than 100,000. Input is terminated by EOF.

Output

For each test case output, if s is a subsequence of t.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You will be given a decimal number. You will have to convert it to its ternary (Base 3) equivalent.

Input

The input file contains at most 100 lines of inputs. Each line contains a non-negative decimal integer N(N<1,000,000,001). Input is terminated by a line containing a negative value. This line should not be processed.

Output

For each line of input produce one line of output. This line contains the ternary equivalent of decimal value N.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In this problem you are to generate a triangular wave form according to a specified pair of Amplitude and Frequency.

Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

Each input set will contain two integers, each on a separate line. The first integer is the Amplitude; the second integer is the Frequency.

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

For the output of your program, you will be printing wave forms each separated by a blank line. The total number of wave forms equals the Frequency, and the horizontal ``height'' of each wave equals the Amplitude. The Amplitude will never be greater than nine.

The waveform itself should be filled with integers on each line which indicate the ``height'' of that line.

NOTE: There is a blank line after each separate waveform, excluding the last one.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

As Manuel wants to get rich fast and without too much work, he decided to make a career in gambling. Initially, he plans to study the gains and losses of players, so that, he can identify patterns of consecutive wins and elaborate a win-win strategy. But Manuel, as smart as he thinks he is, does not know how to program computers. So he hired you to write programs that will assist him in elaborating his strategy.

Your first task is to write a program that identifies the maximum possible gain out of a sequence of bets. A bet is an amount of money and is either winning (and this is recorded as a positive value), or losing (and this is recorded as a negative value).

Input

The input set consists of a positive number N ≤ 10000 , that gives the length of the sequence, followed by N integers. Each bet is an integer greater than 0 and less than 1000.

The input is terminated with N = 0.

Output

For each given input set, the output will echo a line with the corresponding solution. If the sequence shows no possibility to win money, then the output is the message "Losing streak."

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 Hashmat is a brave warrior who with his group of young soldiers moves from one place to another to fight against his opponents. Before fighting he just calculates one thing, the difference between his soldier number and the opponent's soldier number. From this difference he decides whether to fight or not. Hashmat's soldier number is never greater than his opponent.

Input

The input contains two integer numbers in every line. These two numbers in each line denotes the number of soldiers in Hashmat's army and his opponent's army or vice versa. The input numbers are not greater than 2³². Input is terminated by End of File.

Output

 For each line of input, print the difference of number of soldiers between Hashmat's army and his opponent's army. Each output should be in seperate line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a string of 0's and 1's up to 1000000 characters long and indices i and j, you are to answer a question whether all characters between position min(i,j) and position max(i,j) (inclusive) are the same.

Input

There are multiple cases on input. The first line of each case gives a string of 0's and 1's. The next line contains a positive integer n giving the number of queries for this case. The next n lines contain queries, one per line. Each query is given by two non-negative integers, i and j. For each query, you are to print Yes if all characters in the string between position min(i,j) and position max(i,j) are the same, and No otherwise.

Output

Each case on output should start with a heading as in the sample below. The input ends with an empty string that is a line containing only the new line character, this string should not be processed. The input may also with end of file. So keep check for both.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A problem that is simple to solve in one dimension is often much more difficult to solve in more than one dimension. Consider satisfying a boolean expression in conjunctive normal form in which each conjunct consists of exactly 3 disjuncts. This problem (3-SAT) is NP-complete. The problem 2-SAT is solved quite efficiently, however. In contrast, some problems belong to the same complexity class regardless of the dimensionality of the problem.

 Given a 2-dimensional array of positive and negative integers, find the sub-rectangle with the largest sum. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle. A sub-rectangle is any contiguous sub-array of size or greater located within the whole array. As an example, the maximal sub-rectangle of the array:

is in the lower-left-hand corner:

and has the sum of 15.

Input

The input consists of an array of integers. The input begins with a single positive integer N on a line by itself indicating the size of the square two dimensional array. This is followed by integers separated by white-space (newlines and spaces). These integers make up the array in row-major order (i.e., all numbers on the first row, left-to-right, then all numbers on the second row, left-to-right, etc.). N may be as large as 100. The numbers in the array will be in the range [-127, 127].

Output

The output is the sum of the maximal sub-rectangle.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

ATH is the TA of algorithm course. In the end of semester, Professor Wang send him a text file with homework and exam grades and some information of students(i.e. student id, name, gender, etc...). However, he just want to sum up the grades of homework and exam to evaluate the final score.

This work is a piece of cake for him, but he is too busy to finish this work. Thus, he decided to let you write this program for him.

Input

Each line represents the information of a student and each information will be seperated by one or more spaces. The information of first two columns are the grades of homework and exam, and there are at most 1000 characters in a line.

Output

For each line of inputs, print " Student #i: j" without quotes. Where i is the index (start from 1) of students, and j is the final score of such student.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Input

For each line in the test case represents the costs of items in a day and there are at most 5 items in a day.

Output

For each line, print the "Day i: j" for each day, where i is the number of day (start from 1) and j is the total cost of such day.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Calculating the average is an easy work, but how many digits after decimal point need to show is an annoying problem.

SSLin is another TA of algorithm course, and his professor might want to see the average of grades with 5 digits after decimal point, and before submit grades to online system, the average of grades need to round to integer for convenience. 

SSLin do not want to calculate the average again and again. Therefore, he asks Tiyano to write a program to calculate the average grade after given x digits after decimal. However, everyone knows that Tiyano is very very lazy, he also puts this problem into execrise and waiting for your answer.

Input

The first line has a number T which is the total number of testcase

For each testcase, there are 2 values n <= 1000 represents the number of scores and 0 <= x <= 12 is the digits after decimal point of average in output. 

And the following line contains n scores range from 0 to 100.

Output

For each testcase, print the average value rounding to x digits after decimal point in a line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Stud is a popular poker gamble and TPC get a Poker Online Game project from Gamanix Company.

In this game, each player have 5 cards, and they do the gambling by comparing the combination type of cards.

Your job is writing a program to determine what kind of combination types for someone's cards.

There are the rules of combination types

1.Straight Flush  (同花順)  五張的花色相同且五張的點數是連續的或AKOJT
2.Four of a Kind  (四條)    有四張點數相同
3.Full House       (葫蘆)    有三張點數相同且另兩張點數相同
4.Flush          (同花)    五張的花色相同
5.Straight      (順子)    五張的點數是連續的或AKOJT
6.Three of a Kind (三條)    有三張點數相同
7.Two Pairs      (兩對)    有兩對兩張點數相同
8.Pair          (一對)    有兩張點數相同
9 Zilch      (散牌)    沒有任何特殊牌型

Input

The first line of the input will contains an integer T (1<=T<=100) represent the number of testcase. The next T lines will contains five cards in each line. Cards are represented as a two character code. The the first character is the suit (C=Clubs, D=Diamonds, H=Hearts, S=Spades), and the second character is the face-value (A=Ace, 2-9, T=10, J=Jack, Q=Queen, K=King) .

Output

For each line of the five cards, please output the type of the cards.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You are to simulate the playing of games of ``Accordian'' patience, the rules for which are as follows:

Deal cards one by one in a row from left to right, not overlapping. Whenever the card matches its immediate neighbour on the left, or matches the third card to the left, it may be moved onto that card. Cards match if they are of the same suit or same rank. After making a move, look to see if it has made additional moves possible. Only the top card of each pile may be moved at any given time. Gaps between piles should be closed up as soon as they appear by moving all piles on the right of the gap one position to the left. Deal out the whole pack, combining cards towards the left whenever possible. The game is won if the pack is reduced to a single pile.

Situations can arise where more than one play is possible. Where two cards may be moved, you should adopt the strategy of always moving the leftmost card possible. Where a card may be moved either one position to the left or three positions to the left, move it three positions.

Input

Input data to the program specifies the order in which cards are dealt from the pack. The input contains pairs of lines, each line containing 26 cards separated by single space characters. The final line of the input file contains a # as its first character. Cards are represented as a two character code. The first character is the face-value (A=Ace, 2-9, T=10, J=Jack, Q=Queen, K=King) and the second character is the suit (C=Clubs, D=Diamonds, H=Hearts, S=Spades).

Output

One line of output must be produced for each pair of lines (that between them describe a pack of 52 cards) in the input. Each line of output shows the number of cards in each of the piles remaining after playing ``Accordian patience'' with the pack of cards as described by the corresponding pairs of input lines.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

There are many useful application of prime numbers. Determine whether a number is a prime number is an important job! Please write a program to check a positive interger N is a prime number or not.

Input

The input file contains several cases. Each case will be on a line by itself and will consist of a number N (2 <= N <= 2^31-1). The input ends with a 0 on a single line. Please do not do any output for this number.

Output

Please print "YES" (without quote) if N is a pirme number, otherwise print "NO" (without quote).

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Now, your task is to calculate the numbers of the prime numbers between 1 and an integer N.

Input

The input file contains several cases. The first line contains an integer T ( 1 <= T <= 1,000) represent the number of cases. The next T lines, there will be an integer N ( 1 <= N <= 1,000,000) on a single line.

Output

Please output the number of prime numbers between 1 and N.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A prime number is a number that has only two divisors: itself and the number one. Examples of prime numbers are: 1, 2, 3, 5, 17, 101 and 10007.

In this problem you should read a set of words, each word is composed only by letters in the range a-z and A-Z. Each letter has a specific value, the letter a is worth 1, letter b is worth 2 and so on until letter z that is worth 26. In the same way, letter A is worth 27, letter B is worth 28 and letter Z is worth 52.

You should write a program to determine if a word is a prime word or not. A word is a prime word if the sum of its letters is a prime number.

Input

The input consists of a set of words. Each word is in a line by itself and has L letters, where 1 ≤ L ≤ 20. The input is terminated by enf of file (EOF).

Output

For each word you should print: It is a prime word., if the sum of the letters of the word is a prime number, otherwise you should print: It is not a prime word..

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The branch of mathematics called number theory is about properties of numbers. One of the areas that has captured the interest of number theoreticians for thousands of years is the question of primality. A prime number is a number that is has no proper factors (it is only evenly divisible by 1 and itself). The first prime numbers are 2,3,5,7 but they quickly become less frequent. One of the interesting questions is how dense they are in various ranges. Adjacent primes are two numbers that are both primes, but there are no other prime numbers between the adjacent primes. For example, 2,3 are the only adjacent primes that are also adjacent numbers.

Your program is given 2 numbers: L and U (1<=L

Input

Each line of input will contain two positive integers, L and U, with L < U. The difference between L and U will not exceed 1,000,000.

Output

UFor each L and U, the output will either be the statement that there are no adjacent primes (because there are less than two primes between the two given numbers) or a line giving the two pairs of adjacent primes.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Webster defines prime as:

prime (prim) n.[ME, fr. MF, fem. of prin first, L primus; akin to L prior] 1 :first in time: original 2 a : having no factor except itself and one 3 is a   number b : having no common factor except one 12 and 25 are relatively   3 a : first in rank, authority or significance : principal b : having the highest quality or value   television time [from Webster's New Collegiate Dictionary]

The most relevant definition for this problem is 2a: An integer g>1 is said to be prime if and only if its only positive divisors are itself and one (otherwise it is said to be composite). For example, the number 21 is composite; the number 23 is prime. Note that the decompositon of a positive number g into its prime factors, i.e.,

is unique if we assert that f_i > 1 for all i and for i<j.

One interesting class of prime numbers are the so-called Mersenne primes which are of the form 2^p- 1. Euler proved that 2³¹ - 1 is prime in 1772 -- all without the aid of a computer.

Input

vaThe input will consist of a sequence of numbers. Each line of input will contain one number g in the range -2³¹ < g <2³¹, but different of -1 and 1. The end of input will be indicated by an input line having a value of zero.

Output

For each line of input, your program should print a line of output consisting of the input number and its prime factors. For an input number , where each f_i is a prime number greater than unity (with for i<j), the format of the output line should be

When g < 0, if , the format of the output line should be

Sample Input  Download

Sample Output  Download

Tags

Discuss