Description
Give two signed numbers, output their sum. Those two numbers may be too large to be represented by long long data type. Need a data structure to store their data.
Input
The input consists of many lines. Each line has two numbers, which are between -6*10100 to 6*10100.
Output
For each case, output their sum.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Calculate N! = 1×2×...×(N-1)×N. Note the number may exceed the range of integer or long long data type. Need to define a data structure to store the computed results.
Input
There are multiple test cases. Each test case is in a line, containing a number N (1<= N <= 114). The input terminates when N=0.
Output
For each case, output N!
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Compute ab for the given integers a and b.
Input
The first line of input contains a positive integer t (t <= 100), which indicates the number of test cases. For each case, there are two positive number a, b in a line (0 < a, b <= 250).
Output
For each test case, output 
in a single line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Output the sum of A+B in radix N.
Input
For each line, there are three positive integers, N, A and B. (2 <= N <= 16, A, B is at most 100-digits) A and B are represented in radix N.
Output
For each line a case, output the sum of A+B in radix N.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
We can encrypt a string into other string. One method is to put a string into an n×n array first, where n is the smallest number such that n2 is equal to or larger than the length of the string. Each character is put into a cell of the array, from the top left cell of the array and along neighboring cells in the counterclockwise order. The encrypted string is the output of the row major order. For example, the input string "Greed is good", whose length is 13, are put into a 4×4 array, as shown in the following figure.
The output string is "Googrd e sed i".
If the end of the encrypted string are spaces, don't output them. For example, the output of "Bass GG" is "B Ga Gss".
Input
The input consists of multiple lines. Each line is a test case, a string S with length <= 1000. The number of test case is less than 100.
Output
For each test case, output the encrypted string of S.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given n integers and q queries, in which each query defines a range, find the sum of the n given integers within this range.
Input
The first line contains an integer t(1<=t<=20), which indicates the number of test cases. In each test case, the first line contains an integer n (n<=105), specifying how many integers will be given. The next line contains n integers, in which the ith integer represents ai (-50000 <= ai <= 50000). The followed line contains a positive integer q (q <= 104), denoting the number of queries. Next q lines define q queries, one per line. Each query is specified by two integers a and b(1<=a<=b<=n), meaning a range, in which the partial sum of the given integers are queried.
Output
For each query, output a line with the partial sum of the given integers within the queried range.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given two polynomials please calculate the result of adding these two polynomials.
A = Cnxn + Cn-1xn-1 + ... + C0
B = C'mxm + C'm-1xm-1 + ... + C'0
Input
The first line contains an integer t (1 <= t <= 20), which indicates the number of test cases in the input. For each case, the first line contains two integers n, m(n, m <= 1000). Integer n means the highest power of the first polynomial. Integer m means the highest power of the second polynomial. In the next 2 lines, the first line contains n+1 integers, which means the coefficients of the polynomial A from high to low. The second line contains m+1 integers, which means the coefficients of the polynomial B from high to low. All coefficients are less or equal than 105.
Output
For each case, output a line with the coefficients of the polynomial A+B. There is a space between two consecutive numbers.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
The problem is about minesweeper. Given an N*N matrix A whose elements are either 0 or 1. Output the another N*N matrix B. Every element in B is the sum of the adjacency “8” elements in the same location in A. If an element is on the boundary, the adjacency elements may not be “8”.
Input
The input includes multiple test cases. In each test case, the first line contains one integer N. The next N lines follow. Every line contains N elements which are either 1 or 0.
1 <= N <=100
Output
Output N lines. Every line contains N integers. Every two numbers are separated by single space.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given an article, find the number of appearance for queried strings.
Input
The input includes multiple test cases. In each test case, the first line contains two integers, N and M (0 < N < 10, 0 < M < 100). N indicates the number of lines in the article, and M indicates the number of strings needs to search. The next N lines are for the article, and the length of each line < 200. The followed M lines contains M queried, one per line. The alphabet of strings is (a-z, A-Z) and digit (0-9).
Output
For each string, output the string and the number of appearance in the article, separate by ‘:’. Uppercase and lowercase are treated as the same alphabet.
Print a blank line after the output of each test case.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given two strings, find the length of the longest common substring.
Input
The first line of input contains a positive integer t (t <= 100), which indicates the number of test cases. For each case, there are two strings in a line (length of the string < 1000).
Output
Output the length of the longest common substring.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Palindrome is a string that is identical to its reverse, like "level" or "aba". Given a string, find the longest palindrome in the string.
Input
The input consists of multiple lines. Each line contains a string. The length of each string is less than 1000. The number of test case is less than or equal to 700.
Output
In each test case, output the longest palindrome in the string. If there are many palindromes of the same length, output the first one in the string.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Palindrome is a string that is identical to its reverse, like "level" or "aba". Check whether a given string is a palindrome or not.
Input
The input consists of multiple lines. Each line contains a string. The length of each string is less than 100000. The number of test case is less than 1000.
Output
For each test case, output "Yes" if it's a palindrome or "No" if it's not a palindrome in a line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given two strings, output them in alphabetical order.
Note: the order is AaBbCcDd ... YyZz.
Input
For each case a line, there are two strings separated by a single space. The lengths of the strings are no more than 30.
Output
For each case a line, output the two strings in alphabetical order, separated by a single space.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given the relationship of the nodes in a tree, construct the tree and output it in the pre-order. Each node has unique integer identification (ID), but all IDs may not be consecutive.
Input
There are multiple test cases. Each test case begins with an integer N (1 <= N <=1000), denoting the number of relations in the tree. In the following N lines, each line contains two integers a and b (1 <= a,b <= 1000), which means node a is node b’s parent. After that, the next line contains an integer R, which represents the root of the tree. You can assume that all the nodes will be on the same tree. The input is terminated by N = 0.
Output
For each test case, print the pre-order of the tree. In each level, traverse the node with smaller ID first.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
There are many countries in a map. Each of them has a unique ID, which is a positive integer. All of them want to expand their territories. A country can expand its territory if its neighboring land (up, down, left, and right) has not been occupied by any other countries. The speeds of expanding territories of all countries are the same. If two or more countries want to occupy the same land, the country with the smaller ID can occupy the land. The expansion stops if no changes of the map can be made.
Input
The input file begins with an integer T (1 < T < 1000), indicating the number of test cases. Each test case begins with two integers N and M (0 < N < 300, 0 < M < 300), indicating the height and the width of the map. Next N lines specify the occupancy of the map. The number 0 means the land has not been occupied, and the number > 0 denotes the country ID, which is smaller than 10.
Output
For each case, output the final occupancy map. Print a blank after each case.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a graph, output "Yes" if it's a forest, otherwise "No".
Hint: You can use disjoint set or a DFS with adjacency list to solve this problem.
Input
For each case, The first line contains two positive integers N and M (2 <= N <= 1000000), and N denotes the number of node. In the next M lines, there will be two integers A and B, denoting the two end points of an edge (A, B).
Each case is separated by a blank line. The input is terminated by two zeros in place of N and M.
Output
For each case a line, output "Yes" if it's a forest, otherwise "No".
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Output the lowest common ancestor.
Input
The first line contains a positive integer t, which indicates how many cases in the input. For each case, the first line contains a positive integer N (1 <= N <= 100000), denoting the amount of node in the tree (labeled from 1 to N). The second line contains exactly N numbers. The first number denotes the parent of node 1, and the second number denotes the parent of node 2 ..., etc. The parent of the root will be labeled as -1.
Then multiple queries (query < 100) follow. Each line contains two positive integers A and B. The query is terminated by two zeros.
Each case is separated by a blank line.
Output
For each case a line, print the case number first, then output the node number of the least common ancestor for each query. Each answer should be separated by a single space.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Calculate the distance between two nodes.
Input
For each case, the first line contains a positive integer N (1 <= N <= 1000), denoting the number of node in the tree (labeled from 1 to N). The second line contains exactly N numbers. The first number denotes the parent of node 1, and the second number denotes the parent of node 2 ..., etc. The parent of the root will be labeled as -1.
Then follows multiple lines of query (query < 10000). Each line contains two positive integers A and B. The query is terminated by two zeros.
Do not assume it is a binary tree.
Output
For each case a line, print the case number first, then output the distance between A and B for each query. Each answer should be separated by a single space.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a tree, count the number of leaves in this tree. Each node has unique integer identification (ID), but all IDs may not be consecutive.
Input
There are multiple test cases. Each test case begins with an integer N (1 <= N <=1000). In the following N lines, each line has two integer a and b (1 <= a,b <= 1000), indicating node a is node b’s parent. The next line contains an integer R, which represents the root of the Tree. You can assume that all the nodes will be on the same tree. The input is terminated by N = 0.
Output
Print the number of the leaves for each test case.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a binary tree, in which each node has an integer, determine whether there exists a tree path whose sum equal to the queried number. A tree path is a path from the root to a leaf node. The sum of a tree path is the summation of numbers in each node on a tree path. For example, in the tree shown below there are exactly three root-to-leaf paths. The sums of each path are 19, 8 and -6.
The binary tree above is represented by the expression (5(3(11()())(0()()))(1()(-12()()))). With this form, every tree node has an expression (integer()()). The range of the integer in the expression is between -100000 and 100000. And the length of the whole tree expression is at most 100 characters.
Input
The input consists of a sequence of test cases. Each test case occupies a newline. First, there is an integer indicating the query. Second, there is a space. Next, there is a binary tree representation and there are no spaces in the representation.
Output
For each test case, output “yes” or “no” in a new line to check whether the target does exist or not.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given two strings which represent the pre-order traversal and the in-order traversal of a binary tree, generate the post-order traversal of the binary tree.
Input
The input consists of several test cases. Each test case has two strings in a line separated by a space. The first string is the pre-order traversal of the binary tree; the second string is the in-order traversal of the binary tree. Each string will contain only capital characters and the characters will be unique.
Output
For each test case, output a string to represent the post-order traversal of the binary tree.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a tree G(V, E) and its root, print its level-order traversal, where we visit all of the nodes at the same level before going to the lower ones. Each node is labeled by a unique integer number, and in case that the node has more than one child, the one who is labeled by smaller number should be visited first. The figure below illustrates the structure of two sample cases.
Figure. The illustration of two sample cases.
Input
The first line of input is a single integer T (T ≤ 100), denoting the number of test cases. Each test case started with an integer pair N (N ≤ 1000) and R, indicating the number of nodes and the root number respectively. The following N - 1 lines contain pairs of integers ui and vi (1 ≤ ui, vi ≤ N), each in a line, which means ui and vi are adjacent.
Output
For each test case, output “Case i:” denoting the traversal of i-th test case on a line. Then, for each visited node, started from the root, print the labeled number. Every two successive numbers are separated by a space characters. Print a blank line between test cases.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a string, output all different possible set of K characters in the string. And sort them in the dictionary order. For example, if K=2 and the given string is ‘CDBABBD’, output
AB
AC
AD
BB
BC
BD
CD
DD
Input
The first line of input contains a positive integer t (t <= 30), which indicates the number of test cases. For each case, there are one strings and a positive integer K in a line. The length of the string is less than 100 and strings contain only 'A'-'K'; The number K, less than or equal to 10, indicates the length of substrings.
Output
For each test case, output all different possible set of K characters in the string. And sort them in the dictionary order, one substring per line. Print a blank line after each test case.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
There are three jugs of volume a, b and c liters. The number a, b, and c are positive integers. The first and the second jug are empty initially, and the third one is completely filled with water. It is allowed to pour water from one jug into another until either the pouring jug is empty or the poured jug is full. This operation can be performed zero, one, or more times.
Compute the minimum number of water pouring operations to be performed so that one of the jugs contains d’ liters of water. The number d’ is a nonnegative integer, which is closest to but less than or equal to a given positive integer d.
Input
The first line of input contains the number of test cases. In the next T lines, T test cases follow. Each test case is given in one line, containing four positive integers: a, b, c and d, 1 <= a, b, c, d <= 200.
Output
The output consists of two integers separated by a single space. The first integer equals the least total amount (the sum of all waters you pour from one jug to another) of poured water. The second integer equals d, if d liters of water could be produced by such transformations, or equals the closest smaller value d' that your program has found.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given N different digits. You have to choose M digits from them to create all possible numbers in ascending order. For example, given 3 digits "4", "5", "6", and M = 2, the possible answers are "45", "46", "54", "56", "64", "65".
Input
The first line contains a positive integer T (T <= 20), which indicates how many cases in the input. Each case starts with two positive integers N and M (1 <= M <= N <= 10), which denote the amount of the digits and the amount of digits of desired numbers. The next line contains exactly n different digits (0~9) separated by blanks.
Output
For each case, first line outputs the case number. Then, output all the possible numbers in ascending order. (See the Sample Output)
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given N 1×1×1 cubes, arrange them to form a rectangular solid such that the surface area is minimized.
Input
The first line of the input contains an integer T, which is the number of test cases. Each of the next T lines contains an integer N (N ≤ 10000) denoting the number of cubes.
Output
For each case, output a line containing an integer which is the minimized surface area.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given N numbers. You need to separate them A and B such that is 
minimum.
Input
Each case starts with a positive integer N (1 <= N <= 20), then the next line contains exactly N integers (range from -100000 to 100000).
A test case of N = 0 indicates the end of input, and should not be processed.
Output
Output one line per case that contains an integer denoting the minimum value of .
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a map, find the shortest time from S (Start) to G (Goal). The size of the map is specified by two integers: N and M. Each integer grid cell of the map has a mark, whose meanings are explained as follows.
1.'.' denotes an empty space,
2.'@' denotes a swamp,
3.'#' denotes a wall,
4.'S' denotes the start point, and
5.'G' denotes the goal.
There are only one S and only one G in the map. You can pass an empty space in 1 second, and pass a swamp in 2 seconds. But you cannot pass a wall cell. You are only allowed to move up, down, left, or right.
Here is an example: A map is of size 3×5, whose marks are specified as follows
S@..#
..#..
@@@@G
The shortest time from S to G is 7 seconds
Input
The input file begins with an integer T (1 < T < 5000), indicating the number of test cases. Each test case begins with two integers N and M (0 < N < 100, 0 < M < 100), indicating the height and width of the map. In the following N lines, each line contains M characters describing the marks of the map.
Output
For each case, output the shortest time you need from the start point to the goal. If there is no valid path from the start to the goal, output -1.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
The map is a 2-dimensional grid of squares, each square is filled with one color. You will be given a sequence of colors. You can move between adjacent squares vertically or horizontally in the given color order. '*' is where you start, and '#' is the goal.
For example, given the map as follow, and the color order "RGB":
BGRG#
RGBGR
*GRGB
There are two different ways to reach the goal:
xx456
123xx
0xxxx
and
xxxx8
123x7
0x456
So we know that the shortest path from '*' to '#' needs 6 steps.
Implement a BFS to find the smallest number of steps to reach the goal.
Input
The input consists of several maps. Each map begins with a line containing two integers N and M (1 <= N, M <= 10^3) specifying the map height and width. The next N lines will be M upper case letters, '*', or '#'. Each letter denotes one color.
The next line is a string that specifies the color order. One color won’t appear twice in the given order.
Each case is separated by a blank line. The input is terminated by two zeros.
Output
For each map, print one line containing the smallest possible number of step to reach the goal. If there's no way to reach the goal, output the string "No solution." instead. One step is defined as a movement between two adjacent cells.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a map, how fast can you get the key and then escape?
The map is a 2-dimensional grid of squares, each square is either free or filled with a wall. You can move between adjacent free squares vertically or horizontally, diagonal movement is not allowed. You may not go across walls. You have to get the key first and then you can go to the door.
Input
The input consists of several maps. Each map begins with a line containing two integer numbers R and C (1 <= R, C <= 1000) specifying the map size. Then there are R lines each containing C characters. Each character is one of the following:
s : Your start position.
. : A free square that you can move.
k : The position of the key.
w : The wall.
d : The door.
There are exactly one key and exactly one door.
There is one blank line after each map. The input is terminated by two zeros in place of the map size.
Output
For each map, print one line containing the sentence "Escape in S steps.", where S is the smallest possible number of step to reach the door. If no way to reach the door, output the string "No solution." instead. One step is defined as a movement between two adjacent squares. Grabbing a key or unlocking a door does not count as a step.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A plot '#' represents a land. If two plots are adjacent horizontally, vertically, or diagonally, then they are part of the same island. An island can be quite large and may contain numerous plots. Your job is to determine how many different island are there.
Input
The input file contains one or more maps. Each map begins with a line containing M and N, the number of rows and columns in the map, separated by a single space. If M = N = 0 it signals the end of the input; otherwise 1 <= M <= 100 and 1 <= N <= 100. Following this are M lines of N characters each (not counting the end-of-line characters). Each character corresponds to one plot, and is either '*', representing the sea, or '#', representing the land.
Output
For each map, output the number of distinct islands. Two different lands are part of the same island if they are adjacent horizontally, vertically, or diagonally.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
In the Go game, there is a 9×9 board, and the stones are of two colors: black and white. Determine the territory of the black stones and the territory of the white stones. The position of the chess also has its own territory. If there is a territory surrounded by both black stones and white stones, the territory does not belong to either side. For example, in the game shown in the figure below, “a” does not belong to any side; “c” belongs to the black side; “b” belongs to the white side, because it is only surrounded by the black stones and the boundary of the board; “d” belongs to the white side; and “e” belongs to the black side.
Input
The first line of the input has an integer, specifying the number of test cases. In each test case, the first line is a blank line. Next, there will be 9 lines, and each line has 9 characters, representing the status on a Go board. The character “O” means the white chess; the character “X” means the black chess; and the character “.” means the territory no one occupied yet.
Output
For each test case, output “Black
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A knight can move in eight directions on a 8x8 chess board as shown in fig. 1. Your job is to write a program that takes two coordinates a and b as input and then count the number of knight moves on a shortest route from a to b, on a 10x10 chess board.
Input
The input consists of several test cases. In each test case, there are four integers x1, y1, x2 and y2., where x1 and y1 represents the start point, and x2 and y2 represents the end point. ( 1 <= x1, y1, x2, y2 <= 10)
Output
For each test case, print one line saying “To get from (x1,y1) to (x2,y2) takes n knight moves”.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Each chessboard has numbers in the range 1 to 99 written on each square and is supplied with 8 chess queens. The task is to place the 8 queens on the chess board in such a way that no queen threatens another one, and so that the sum of the numbers on the squares selected is the maximum . (For those unfamiliar with the rules of chess, this implies that each row and column of the board contains exactly one queen, and each diagonal contains no more than one queen.)
Write a program that will read in the number and details of the chessboards and determine the highest scores possible for each board under these conditions.
Input
Input will consist of K (the number of boards), on a line by itself, followed by K sets of 64 numbers, each set consisting of eight lines of eight numbers. Each number will be a non-negative integer less than 100. Each case is separated by a blank line. There will never be more than 20 boards.
Output
The outputs of all test cases should be printed in order. For each test case a line, print the highest score right justified in field 5 characters wide.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Output the given strings according to the defined format.
Input
The first line of input contains a positive integer t (t <= 20), which indicates the number test cases. For each case, the first line contains one positive integer n (n <= 100) indicating the number of strings. In the next n lines, one string is appeared per line. The length of each string is between 1 and 20.
Output
The output format is as follows. First, each line has 4 strings. Second, each string occupies 20 spaces and right aligned.Print a blank line after each case.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
MSpaint is a program that allows users to draw pictures. The canvas is defined by two integers, N and M, specifying the height and the width of the canvas. The coordinate system of the canvas is described as follows. The left-bottom corner is the origin, (0,0). The x-axis is the horizontal line; and the y-axis is the vertical line. You may assume all given coordinate (x, y) are positive integers and within the range of canvas, 0 <= y < N, and 0 <= x < M. The picture is represented by a bitmap. Each pixel of the picture is either empty or filled.
MSpaint accepts four kinds of commands:
1.R x1 y1 x2 y2: Draw a rectangle from(x1, y1) to (x2, y2)
2.F x y: If the point (x, y) is filled, then do nothing.
Otherwise, fill the smallest closed region which contains the point(x, y).
3.L x1 y1 x2 y2: Draw a vertical or horizontal line from (x1, y1) to (x2, y2), which means either x1=x2 or y1=y2.
4.E: The end of the case.
The fill operation in the ‘F x y’ command works as follows. It first fills the current pixel, which must be empty. Next it finds the four neighbors (left, right, top, and bottom of the current pixel. If one of them is empty, it moves to the empty neighbor pixel and fills it recursively, until all neighbors are filled or out of the range of the canvas.
Input
The input file begins with an integer T (1 < T < 500), indicating the number of test cases. Each test case begins with two integers N and M , 1 < N < 100, 1 < M < 100. Next N lines describe the bitmap of the picture (0 is empty and 1 is filled). There are commands followed by the bitmap. And all the commands of a test case end with command ‘E’. The number of commands of a test case is less than 20.
Output
For each case please output the bitmap of the picture. Print a blank line after each case.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Problem description
The problem is to parse a series of commands that instruct a robot arm in how to manipulate blocks lying on a flat table. Initially there are n blocks on the table (numbered from 0 to n-1) with block bi adjacent to block bi+1 for all 0 <= i < n-1 as shown in the figure below:
Figure 1. Initial Blocks World
The valid commands for the robot arm that manipulates blocks are:
move a onto b
where a and b are block numbers, put block a onto block b after returning any blocks that are stacked on top of blocks a and b to their initial positions.
move a over b
where a and b are block numbers, put block a onto the top of the stack containing block b, if there are other blocks, stacked on top of block a or block b . return them to their initial position, after returning any blocks that are stacked on top of block a to their initial positions.
pile a onto b
where a and b are block numbers, moves the pile of blocks consisting of block a, and any blocks that are stacked above block a, onto block b. All blocks on top of block b are moved to their initial positions prior to the pile taking place. The blocks stacked above block a retain their order when moved.
pile a over b
where a and b are block numbers, puts the pile of blocks consisting of block a, and any blocks that are stacked above block a, onto the top of the stack containing block b. The blocks stacked above block a retain their original order when moved.
quit
terminates manipulations in the block world.
Any command in which a = b or in which a and b are in the same stack of blocks is an illegal command. All illegal commands should be ignored and should have no affect on the configuration of blocks.
Input
The input begins with an integer n on a line by itself representing the number of blocks in the block world. You may assume that 0 < n < 25.
The number of blocks is followed by a sequence of block commands, one command per line. Your program should process all commands until the quit command is encountered.
You may assume that all commands will be of the form specified above. There will be no syntactically incorrect commands.
Output
The output should consist of the final state of the blocks world. Each original block position numbered i ( 0 <= i < n where n is the number of blocks) should appear followed immediately by a colon. If there is at least a block on it, the colon must be followed by one space, followed by a list of blocks that appear stacked in that position with each block number separated from other block numbers by a space. Don't put any trailing spaces on a line.
There should be one line of output for each block position (i.e., n lines of output where n is the integer on the first line of input).
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Implement a system to do the encoding and decoding for a text message. The encoding method has two steps, described as follows:
(1) Reverse the message. For example, ABCD → DCBA
(2) Shift each character by a constant k. To do that, we first map character ‘A’~’Z’ to number 0~25, and then add a number k to each mapped number, and then map the shifted number back to characters. If the shifted number exceeds 25, then mod it by 26. For example, if k = 3, ‘Z’+3 = ‘C’.
Input
The input includes multiple test cases. The number of test cases T, T <= 1000, is given in the first line of the input. The next T lines are for test data. Each line contains two integers and a character string. The first integer specifies the operation mode: 1 for encryption, and 2 for decryption. The second integer is the shift k, k <= 100. The character string, consists of capital English letters only, is the message to be encoded or to be decoded. The length of the string is less than or equal to 106.
Output
For each case, output the encoded or decoded text in a single line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Consider the following algorithm:
- Input n
- Set Count to be 0
- If n is equal to 1, then STOP
Else Set
- Count = Count +1
- GOTO Step 3.
Given one integer n. Please output the count after processing the algorithm.
Input
The input includes multiple test cases. In each test case, the first line contains one integer n. Guarantee the algorithm won’t go into infinite steps when n is between 1 and 106.
1<= n <= 106
Output
The one line contains one integer which indicates the count.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given integers M and N, calculate the combination result for C(M, N) = M!/((M-N)!*N!), and output it in the prime factor decomposition form.
Input
The input contains several test cases. Each test case starts in a newline with two integers M and N whose range are from 0 to 10000 and M is greater than or equal to N.
Output
For each test case, print the result combination answer in the form of the prime factor decomposition per line shown as in the Sample Output.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a decimal integer n and a base k, translate n to the corresponding k-based number.
Input
The first line contains an integer t (1 <= t <= 20), which indicates the number of test cases in the input. Each test case is given in a line, containing two integers n and k (n <= 10000000, k<=9).
Output
Output the number in base k.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Calculate R = (BP) mod M for large B, P, and M. Integer B and P are in the range 0 to 2147483647 (=231 – 1) inclusive. Integer M is in the range 1 to 46340 inclusive. Note you cannot calculate R directly because M is too large.
Input
There are multiple test cases. Each test case is given in three lines, containing B, P, and M in each line.
Output
For each test case, output the answer R in a single line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given an n×n matrix A,
,
its determinant can be defined recursively as follows.
where M1,j is an (n–1)×(n–1) matrix, defined by removing the first row and the jth column of A,
For example,
.
Input
The first line contains an integer t (1 <= t <= 20), which indicates the number of test cases in the input. Each case starts with an integer n (2 <= n <= 8), specifying the size of the square matrix A. Then following next n lines, each line containing n integers, define the entries of the matrix A. The range of values in the entries is from -5 to 5.
Output
For each case, output one line with the determinant of matrix A.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given two positive integers a and b, compute the greatest common divisor (GCD) of a and b. The GCD of a and b is the biggest integer that can divide a and b with no reminder.
Input
First line contains a positive integer t (t<=1000), which indicates the number of test cases in the input. In the next t lines, each line contains two positive integers a, b, which are smaller than or equal to 106.
Output
For each case, output the GCD of a and b in a line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given two positive integers a and b, compute their least common multiple (LCM). The LCM of a and b is the smallest positive integer that can be divided by a and b with no reminder.
Input
First line contains a positive integer t (t<=1000), which indicates the number of test cases in the input. In the next t line, each line contains two positive integers a, b, which are smaller or equal to 106.
Output
For each case, output the LCM of a and b in a line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Compute C=AB, where A is a matrix of size m×n, B is a matrix of size n×p, and C is a matrix of size m×p.
Input
First line contains a positive integer t (t<=50), which indicates the numbers of test cases in the input. The first line of each test case contains three positive integers m, n, p (m, n, p <=100) for the dimension of matrices. In the next m lines, each line contains n integers, representing the elements of matrix A. Followed by n lines, each line containing p integers, represent the elements of matrix B. All elements of A and B are integers in the range [-5, 5].
Output
For each case, output an m*p matrix in m lines and each line contains p integers.
Use one space between two consecutive integers. Output a blank line after each case.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
The Pascal sequence of order n generates n integers, in which the kth element is defined as
For example: if n = 3, the sequence is 1 3 3 1.
Input
There will be multiple test cases. No number of test cases is given. Each case is given in a single lines, containing an integer n (1 <= n <= 1000).
Output
For each case, output the Pascal sequence. Two consecutive numbers are separated by a space. All numbers should be mod by 1000007.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
測資有誤暫時請不要嘗試!!!!
There are many ways to calculate a value of a polynomial. One of them is Horner’s rule:
Given a polynomial and some parameters x, compute P(x) by Horner’s rule.
Input
First line contains a positive integer t(t<=1000), which indicates the number of test cases in the input. In each case, the first line gives an integer n(1 <= n <= 1000). The second line contains n+1 integers, which are the coefficients of P(x) arranged from the highest power term to the constant term. The third line gives an integer m (1 <= m <= 105), which is the number of parameters. In next m lines, each line contains an integer, which indicate the parameter x (-300000 <= x <= 300000).
Output
For each case, output the case number like “Case 1:” in a line, each value of m parameters is output in a line and mod 10000007. Please refer to sample output.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Output the number of primes between two given integer a and b.
Input
The first line of input contains a positive integer t (t<=1000), which indicates the numbers of test cases in the input. In the next t line, each line contains two positive integers a, b(1 <= a <= b <= 10000), indicating the range between a and b.
Output
Output the number of primes in the range between a and b (including a and b).
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a fraction, find its simplest fraction representation.
Input
The first line contains an integer t (1 <= t <= 20), which indicates the number of test cases in the input. In each case, each line contains two integers a and b (a, b <= 100000), which represent the numerator and the denominator of a fraction.
Output
For each case, output a line with the simplest fraction.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given two positive integers a and b. Please output the result of a / b. If it exists the repeating cycle, please output the minimum length of it. If it doesn’t exist, please output “(0)” after the result. For example, the answer of “1/3” is “0.(3)” and the answer of “1/4” is “0.25(0)”.
Input
The input includes multiple test cases. In each test case, the one line contains two integers, a and b.
1<= a,b <= 3000
If the length of the repeating cyle is more than 50, only output the first 50 digits. Then output "..." after.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A string is called a number if every digit is a number.
A string is called a palindrome if it’s the same when read backward and forward.
A palindrome number has the properties of a palindrome and a number.
To simplify the problem, every palindrome number cant’s start from 0, ex: 010 is not a palindrome number. But “0” is the smallest palindrome number. Please output the kth smallest palindrome number.
Input
The input includes multiple test cases. In each test case, the one line contains one integer K.
1 <= K <= 2*109
Output
The one line contains the output the kth smallest palindrome number.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
The number 151 is a prime palindrome because it’s a prime number and a palindrome. (A palindrome means it’s the same number when read backward.) Write a program to find all prime palindromes in the range of two supplied numbers a and b. Both a and b are considered to be within the range.
Input
The input includes multiple test cases. In each test case, the one line contains two integers a and b.
5 <= a <= b <=108
Output
One line contains all prime palindromes in numerical order. If it doesn't exist any prime palindrome, please output "Impossible".
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a triangle, find the circumcircle center of the given triangle. A circumcircle center of a triangle is a point whose distances to three point are the same. The coordinates of all points are integers. The coordinates of the circumcircle center must be integers too. It is possible that no such circumcircle center exists.
Input
The input contains several test cases. In each test case, there are six integers representing the three coordinates of a triangle on a 2D plane. All the input integers are ranged from -1000 to 1000. You can assumed that no three coordinates will be collinear.
Output
For each test case, print the coordinate of the circumcircle center. If the coordinates of the circumcirle center are not integers, print -1.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
There are N straight lines in a 3D coordinate. Your job is to find the maximum number of intersections for N straight lines.
Input
The input contains multiple cases. In each test case, there is an integer N which indicates the number of straight lines. ( 0 < N < 1000000 ) When N is equal to 0, it is the end of the input file.
Output
Print the result mod 10000 in a newline.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
There are some 2D coordinates on the Cartesian plane. Please count all the possible acute triangles whose inner angles are all smaller than 90 degrees on the plane. For example, if there are five dots on the plane whose coordinate are p1 (1, 1), p2 (3, 1), p3 (2, 3), p4 (2, 4) and p5 (4, 4), there are three acute triangles on the plane which are p1-p2-p3, p1-p2-p4, and p2-p4-p5.
Input
The input consists of several test cases. In each test case, the first line is an integer indicating N points on the Cartesian plane. ( 0 < N < 300 ) In the next N lines, there are two integers in each line. And all the integers are ranged from -10000 to 10000. You can assume that no three points will be collinear. When N equals to 0, the input file ends.
Output
Print the total number of the acute triangles in a newline.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given an integer N, do the prime factor decomposition of N. If there are k prime numbers, print the format as N = p1^x1*p2^x2*p3^x3....pk^xk.
Input
There are several test cases. In each test case, there is an integer N ( 2 <= N < 1000000 ) occupied a newline.
Output
Print the given integer's prime factor decomposition in the format, which is N = p1^x1*p2^x2...pk^xk if N has k primes.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given five coefficients of an integer equation
determine the number of integer solutions (x1, x2, x3, x4, x5) for the above equation where xi are non-zero integers in the range [-50, 50].
Input
Input consists of lines of test cases. Each test case contains 5 coefficients (-50 ≤ ai ≤ 50) separated by spaces, and they occupy a single line. The input is terminated by end-of-file (EOF).
Output
For each test case, output the number of solutions on a single line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a sequence of digits, there may be many ways to add “+” and “-” between them to form an expression whose evaluated result is 0. For example, there are 3 solutions to the sequence “1 2 1 2”, which are “1 + 2 - 1 - 2”, “1 - 2 - 1 + 2” and “12 - 12”. Note that the sign must be put between two digits (which means “- 1 + 2 + 1 - 2” is not a valid solution), but it is not necessary to add signs between every pairs of digits (“12 - 12” is valid, for instance). Moreover, the order of digits in the sequence may not be changed. Find the number of valid solutions to a given sequence.
Input
Each test case consists of two lines. The first line is an integer N (2 ≤ N ≤ 12) denoting the number of digits in the sequence, and the second line contains N digits in the range [1, 9]. The input is terminated by a zero after the last test case, and the number of test cases will be no more than 1500.
Output
For each case, output “Case i:” and then the number of solutions, seperated by a space character, i is the number of test case starting from 1.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given an undirected weighted graph G = (V, E, W), output the weight of its minimum spanning tree.
Input
The input includes multiple test cases. The first of the input is an integer T (T <= 1000) specifying the number of test cases. For each case, the first line contains two integers: the number of the node n (2 <= n <= 1000) and the number of the edges m(1<=m<=100000). In the following m lines, each line contains three integers (si, ei, ci), 1<=si, ei<=n, 1<= ci<=100, representing the indices of end vertices of an edge and the weight of the edge.
Output
For each case, output a line that indicates the weight of the minimum spanning tree of the graph.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given an undirected graph, determine whether it is bi-colorable or not. A graph is called bi-colorable if only two colors are used and each node is assigned a color such that all adjacent nodes have different assigned colors. Note that all nodes are connected.
Input
The input consists of several test cases. Each test case starts with a line containing a number N which represents N nodes indexed from 1 to N.( 0 < N < 1000) The second line contains a number K. After this, there are K lines, each containing two numbers that indicate two end nodes of an edge. When N is equal to 0, the input ends.
Output
If the graph is bi-colorable, print “BICOLORABLE”. Otherwise, print “NOT BICOLORABLE”.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a graph, try to find an optimal coloring. Available colors are black and white only. The coloring of the graph is called optimal if a maximum of nodes is black. The coloring is restricted by the rule that no two connected nodes are black.
Input
The input file contains M graphs. The number M is given on the first line. The first line of each graph contains N and K, the number of nodes and the number of edges, respectively.( 1 <= N <= 30 ). The following K lines contain the edges given by a pair of node numbers, which are separated by a space. The nodes are indexd from 1 to N.
Output
The output should consist of 2M lines, two lines for each graph found in the input file. The first line of should contain the maximum number of nodes that can be colored black in the graph. The second line should contain one possible optimal coloring. It is given by the sorted list of black nodes, separated by spaces.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given an undirected graph with several connected components, find the one with the largest number of nodes. A connected component is a subset of nodes in which any two nodes are connected to each other by paths, and which is connected to no additional nodes.
Input
There will be several test cases. In each test case, the first line will be an integer N ( 0 < N <= 100000 ) representing the number of nodes. The second line contains an integer K which is the number of edges. In the next K lines, each line contains two integers, A and B ( 0 <= A, B < N ), which are two end nodes of an undirected edge. If N = 0, the input ends.
Output
For each graph, print the number of nodes for the largest connected component.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
There are N jobs (labeled from 1 to N) that you have to schedule, and some jobs are related to other jobs. For example, if job No.3 is related to job No.2, then job No.3 can only be done after job No.2 is done.
Output the number of all possible scheduling.
Input
The first line contains a positive integer T (T <= 20), which indicates how many cases in the input.
Each case starts with two positive integers N and M (1 <= N <= 10), and N denotes the amount of the job. The next M lines contain the relationship among jobs. Each line contains two positive integers A and B, separated by a single space, denoting A is related to B.
Each case is separated by a blank line.
Output
The output contains one line for each test case. Each line contains an integer, which is the number of all possible ways.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A directed graph is called “DAG” if it has no cycles. Given a DAG, find the longest path from a starting point to a target point.
Input
The input consists of several test cases. Each test case begins with two integers A, B in a line, indicating the number of the starting point and the number of the target point. ( 0 <= A, B < 100000 ) In the second line, there is an integer N representing N edges. ( 0 < N < 1000 ) In the next N lines, there are two integers R, T in each line which means there is a directed edge from node R to node T and R is not equal to T. ( 0 <= R, T < 100000 ) When A and B both equal to 0, input ends.
Output
In each test case, print “Case”, a space, the case number, a colon and a space orderly shown in the sample output. And then print the length of the longest path. If the longest path does not exist, please print “INVALID”.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A directed graph is called “DAG” if it has no cycles. Given a DAG, find the shortest path from a starting point to a target point.
Input
The input consists of several test cases. Each test case, begins with three integers N, A, B indicating the number of nodes in the graph (indexing from 0 to N-1), the number of the starting point and the number of the target point. ( 0 < N <= 1000, 0 <= A, B < N ) In the second line, there is an integer K representing K edges. In the next K lines, there are two integers R, T in each line which means there is a directed edge from node R to node T and R is be equal to T. ( 0 <= R, T < n ) When N, A and B all equal to 0, the input ends.
Output
In each test case, please print “Case”, a space, the case number, a colon and a space orderly shown in the sample output. And then print the shortest path. In the shortest path, print a dash between each node. If there are two or more shortest paths, print the one with minimum number order. And If the shortest path does not exist, please print “INVALID”.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a directed acyclic graph of N nodes, two players take turn to pick a valid node to visit, starting from node number 1. A valid node v is a node which is connected by the current one u (there is an edge from u to v). If a player reaches the ending point, node number N, then he or she wins the game. Determine whether the player who moves first can win or not, assuming both taking the best strategies.
For example, consider the following graph, the best way to win if you move first is to move to node number 2 from the starting point. Your opponent have no choice but to move to node number 3, and you win the game by moving to the end point after that.
.png)
Figure. An example of the game
Input
There are serveral test cases in the input. Each case starts with two integers N (2 ≤ N ≤ 5000) and M (M ≤ 60000), denoting the number of nodes and the number of edges in the graph. Each of the next M lines contains two integers u and v (u ≠ v), indicating a directed edge from u to v. It is guaranteed that there is at most one edge from u to v. Moreover, there will be no edge ending at the starting point and starting from the ending point (i.e. (u, 1) and (N, v) does not exist). The number of test cases will be no more than 100, and the input is terminated by N = M = 0.
Hint: Using adjacency lists to store the graph is recommended.
Output
For each test case, output a line contains “Case i:” and then “Yes” or “No” to indicate whether it is possible or not to win the game if you move first. i is the number of test case starting from 1.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Sudoku is a number-placement puzzle. The goal is to fill a 9×9 grid so that each row, each column and each of the nine 3×3 blocks (the sub-squares that compose the grid, indicated by the bold lines in the figure below) contains all of the digits from 1 to 9. Please solve the given puzzles.
.png)
Figure. A Sudoku puzzle
Input
The first line of the input consists of an integer T, which is the number of puzzles. Each puzzle occupies 9 lines, and there are 9 digits in each line. The empty cell is filled with 0. The first line is followed by an empty line, and there is also an empty line between two successive puzzles.
Output
For each test case, output the sequence number of the test case, followed by the solved puzzle (all of the empty cells are filled according to the rule) in the same format as the input. Print an empty line between two successive puzzles.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
You are given the ages (in years) of all people of a country with at least 1 year of age. You know that no individual in that country lives for 100 or more years. Now, you are given a very simple task of sorting all the ages in ascending order.
Input
There are multiple test cases in the input file. Each case starts with an integer n (0<n<=2000000), the total number of people. In the next line, there are n integers indicating the ages. Input is terminated with a case where n = 0. This case should not be processed.
Output
For each case, print a line with n space separated integers. These integers are the ages of that country sorted in ascending order.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given two sets of numbers, output their intersection set.
Input
There are multiple test cases. Each case contains four lines. The first line begins with an integer N (1 <= N <= 106). The second line contains N integers, representing the numbers in the first set. The third line has one integer M (1 <= M <= 106), and the fourth line contains M integers, represent the numbers in the second set. All the numbers in one set will be unique. The input is terminated if N = 0.
Output
For each test case, print the intersection of the two sets. Output them in ascending order. If the intersection of the two sets is an empty set, print “empty” (without quotes).
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given two increasing sorted lists S1 and S2. Each has N integers. There are N*N sums composed of one element in S1 and the other element in S2. Please output the smallest N sums.
Input
The input includes multiple test cases. In each test case, the first line contains one integers N. The second line contains N integers and the third line also contains N integers.
Guarantee every element or every sum must be an integer.
1 <= N <= 105
Output
The one line contains the smallest N sums. They are separated by single space.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given an original point O and N points in 2D plane, please sort N points by the angles.
Input
The input includes multiple test cases.
In each test case, the first line contains one integer N, which indicates the number of points. Next line contains two floating point numbers, which indicate the position of O. The following N lines are same as above.
Guarantee every two points must be at the different positions.
Guarantee every angle exists at most one point.
1 <= N <= 104
-10001 <= x, y <= 10001, for every x, y
Output
The one line contains N numbers representing the indices of the points. Every two numbers are separated by single space. The indices are between 1 and N. (1 <= Pi <= N)
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given N positive numbers. Find the biggest number composed of these numbers.
Input
The input includes multiple test cases. In each test case, the first line contains one integer N. The following line contains N positive integers.
1 <= N <= 50
0 <= X <= 50000
Output
Output the biggest number composed of these numbers.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a sequence S = {X1, X2, X3,..., Xn | Xi is an integer}. For all Xi, you should count a number Ci such that Ci = min1<=j{ |Xi - Xj| }. Let C1 = 0.
Input
The input includes multiple test cases. In each test case, the first line contains one integer N. The following line contains N integers.
1 <= N <= 105
Output
The one line contains C1, C2,..., Cn. They are separated by single space.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given N integers X1, X2, ..., Xn. Please output the sorted result. (Increasing order)
Input
The input includes multiple test cases. In each test case, the first line contains one integers N. The next line contains N integers.
Hint:
The sorting algorithms in O(n lg n) don’t work.
To avoid Time Limit Exceeded in Input/Output process, try to use scanf / printf to replace cin / cout.
1 <= N <= 2*106
0 <= Xi <= 104
Output
The one line conatins many pairs. Every pair (pi,qi) means there are pi numbers whose value are qi.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Here we consider the strings composed of only characters ‘A’, ‘C’, ‘G’ and ‘T’. In the alphabetical order, ‘A’ is in front of ‘C’, ‘C’ is in front of ‘G’, and ‘G’ is in front of ‘T’. The “unsortedness” of a string is the number of pairs of characters that are out of alphabetical order with respect to each other. For example, the “unsortedness” of “ACACA” is 3, because the first ‘C’ is in front of two ‘A’s, and the second ‘C’ is in front of one ‘A’.
Given N strings, sort them in the ascending order of strings’ “unsortedness”. For example, given “AACATGAAGG” and “CCCGGGGGGA”, output
CCCGGGGGGA
AACATGAAGG
because the unsortedness of “AACATGAAGG” is 3+5+2=10, and the unsortedness of “CCCGGGGGGA” is 9.
Input
The input includes multiple test cases. In each test case, the first line contains two integers, N and L, which indicate the number of strings, and the length of every string. (1 <= N <= 105, 1 <= L <= 10.) The next N lines follow. Every line contains one string composed of the characters ‘A’, ‘C’, ‘G’ and ‘T’.
Output
For each test case, output the sorted results in N lines, one string per line. If the unsortedness of two strings are the same, sort them in lexicographically order.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given the grades of N people. Please output the sorted result. (Increasing order)
Input
The input includes multiple test cases.
In each test case, the first line contains one integer N. The following N lines specify the name Si and the grade Gi.
1 <= N <= 105
1 <= |Si| <= 10
0 <= Gi <= 100 (Gi is an integer.)
Output
For every test case, output the result in N lines. Every line contains the name and the grade. If more people’s grades are same, output by input order. (That means it uses stable sort.)
Sample Input Download
Sample Output Download
Tags
Discuss
Description
There are many boxes. In each box; there are treasures of different values. Make a list of these boxes, in which they are sorted by the total value of treasures in them from large to small. If two boxes have the same total value, the one appearing earlier in the input data should be output first. And in each box, list the treasures values from small to large.
Input
There are multiple test cases. Each case begins with an integer N (1 <= N <= 104) which represents the number of boxes. In the next N lines, each line contains a sequence of positive integers, representing the value of the treasures. There are at most 103 treasures in one box. Each line is terminated by 0. The input is terminated by N = 0 in a single line.
Output
For each test case, output the sorted boxes in N lines. In each line, output a sequence of sorted integers, representing the values of treasures. Use a blank line to separate two test cases.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given an article, calculate the value of each character and output them in the descending order of their values. The price of characters is calculated as follows: one dollar for a letter ‘a’, two dollars for a letter ‘b’ … and 26 dollars for a letter ‘z’. 'A' and 'a' are not the same in this problem, just count the lowercase letters.
Input
The input contains an article, which is terminated by EOF.
Output
Output the total value of each character in the descending order. Do not print the character not in the article. If two characters have the same value, output the one with smaller ASCII code first.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
In a number sequence S = {S1, S2, S3, …, Sn}, we called (i,j) an “inversion pair” when Si > Sj and i < j. Given S, calculate the number of inversion pair in this sequence.
Input
There are several numbers of test cases. Each case begins with an integer N (1 <= N <= 106) in a line, and then N integers follow, each in a single line. The input is terminated by the number zero.
Output
For each test case, print a number of inversion pairs in the given sequence. All the answer can be fit in 64-bits integers.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
There is a list of English words. Output them in lexicographic order. We compare the first character of two strings S1 and S2. If the ASCII code of the first character of S1 is smaller than the first character of S2, we said that S1 is smaller than S2. Otherwise, if their first characters are the same, we compare their second characters, so on so forth until we can determine their order. If S1 is S2’s prefix, S1 is smaller than S2 and vice versa.
Input
There are multiple test cases. Each case begins with an integer N (1 <= N <= 1000) in a line, and then N words follow, each word in a line. The maximum length of words is 50. The alphabets are 26 small English letters ‘a’ to ‘z’. The input is terminated if N = 0.
Output
For each test case, print the words in lexicographic order. Print a blank line after each case.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
There are some line segments in 1 dimensional space. If two segments overlap or one segment’s start is another segment’s end, we consider them as one segment. Please output the length of the longest segment.
Input
There are multiple of test cases. Each case begins with an integer N (1 <= N <= 106) which represents the number of line segments. In the next N lines, each line contains two integers a and b (1 <= a <= b <= 109) representing a line segment. The input is terminated by N = 0.
Output
For each test case, output the length of the longest segment.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
The median of an integer sequence can be found by arranging all the integers from the smallest to the largest and picking the middle one. If the number of integers is even, the median is defined to be the mean of the two middle integers. Given an integer sequence, output the median of the sequence.
Input
There are multiple test cases. Each case begins with an integer N (1 <= N <= 106) in a line. The next line has N integers are in the next line, separated by spaces. The input is terminated if N = 0.
Output
For each test case, print a number represent the median of the sequence.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Mode means the most frequent value in a data set. Given a sequence of integers, find out their mode.
Input
There are several numbers of test cases. Each case begins with an integer N (1 <= N <= 107). The next line contains N integers separated by a blank space. Each number is less than 1000 and greater than 0. The input is terminated if N = 0.
Output
For each test case, print the mode of the sequence. If the mode is not unique, print the smallest one.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
It is a common feature that the web browsers support moving backward and forward among the pages recently visited. Please simulate this function, which uses two stacks, backward stack and forward stack, and is commanded by following keywords.
(1) VISIT <url> - Push the current page on the top of the backward stack, and make the page specified by URL become the new current page. The entries in forward stack are then discarded.
(2) BACK - Push the current page on the top of the forward stack and pop the page from the top of the backward stack, which becomes the new current page. If the backward stack is empty, this command should be ignored.
(3) FORWARD - Push the current page on the top of the backward stack and pop the page from the top of the forward stack, which becomes the new current page. If the forward stack is empty, this command should be ignored.
Assume that the browser initially loads the web page at the URL “http://www.acm.org/”.
Input
There is only one set of commands in the input. Each command occupies a line, and the length of URLs will be no more than 100 and they contain no space character. The number of commands will be no more than 100000, and the input is terminated by end-of-file (EOF). You may assume that the entries in the stack will be no more than 10000 at any time.
Output
For each command, output the URL of the current page after the command is executed, in a line. In case that the command is ignored, print “Ignored” instead.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
There are N numbers in a queue. The origin sequence is from 1 to N. (1 is the head). The operation “Move a b” means to move all the numbers in front of a (including a) and then insert them in front of b without changing order. Given several such operations and output the final status of the sequence.
Input
There will be only one test case. The test case begins with an integer N (1 <= N <= 106) indicating the number of people. There are several operations followed. The format is “Move a b” (without quote) you can assume that the position of a is in front of the position of b. The test case is terminated by “Exit” (without quote).
Output
Output the numbers from the first one to the last one, and separate two consecutive numbers by a space.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Maintain a doubly linked list, which supports the following operations:
(1) IH i : Insert a new integer i to the head of the list.
(2) IT i : Insert a new integer i to the tail of the list.
(3) RH : Print and remove the element in the head of the list.
(4) RT : Print and remove the element in the tail of the list.
(5) S : Swap the first floor(k/2) elements and the last k - floor(k/2) elements, where k is the total number of elements in the list. For example, if k = 5, the result of swapping a1, a2, a3, a4, a5 will be a3, a4, a5, a1, a2.
To improve the performance, it is suggested that three pointers be maintained: head, tail and middle, where middle points to the floor(k/2) + 1-th element. With the help of these pointers, all of the operations can be done in constant time.
Input
There is only a single set of input and each operation will occupy a line. There will be a space between “IH” and “i”, and “IT” and “i”. The input contains no more than 500000 operations, and it is terminated by end-of-file (EOF). You may assume that i will fit in a 32-bit signed integer. The list is initially empty.
Output
For each “RH” or “RT” operation, print a line containing the removed integer as commanded by the operation.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
The Mid-Square hash function works as follows.
(1) The number of hash values is 65536, which are numbered from 0 to 65535.
(2) To obtain the hash value for an integer, the hash function squares the key and return 16 bits from the middle of the square; key is considered as a 32-bit unsigned integer.
Input will contain these commands:
(1) INSERT i – Insert the integer i into the hash.
(2) DELETE i – Delete the integer i from the hash.
(3) PRINT i – Print the elements that have the same address as integer i in the hash table.
Input
There is only one data set in the input. Each line contains a single command. The range of the given integer is considered as a 32-bit unsigned integer, and the number of commands will be no more than 200000. The input is terminated by end-of-file (EOF), and the hash table is initially empty.
Output
For each “PRINT” command, output a line which contains integers of the same address as the given integer i in ascending order, including i. Each distinct integer should appear exactly once, and a single space character should be printed to separate two successive integers. In case that i is not found in the hash, print “Null” instead, even there are other integers in the same address of the hash table.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given f1, f2… fn denoting the frequencies of n different symbols to be encoded into variable length binary representation using Huffman encoding. Let d1, d2… dn denote the encoded length of the symbols. Please find the optimal encoding, which means that the average length of the encoded message
is minimized.
Input
The first line of the input consists of an integer T (T ≤ 1000) denoting the number of test cases. Each test case starts with an integer N (N ≤ 10000) representing the number of symbols to be encoded, and the following are N integers corresponding to the frequencies of the symbols.
Output
For each test case, output “Case i:”, where i is the sequence number starting from 1, and then the minimized average length of the encoded message, rounded to two decimal places.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Please maintain a max-heap, which stores integers and is able to support following operations:
(1) PUSH k – Insert an integer k into the heap. k will fit in a 32-bit signed integer.
(2) POP – Delete the maximum element from the heap.
(3) TOP – Print the maximum element in the heap.
Input
There is only one set of commands. Each command occupies a line, and the total number of commands is less than or equal to 500000. You may assume that the number of elements stored in the heap will be no more than 1024 at any time.
Output
For each “TOP” command, output a line containing the value of the element on the top of the heap. In case that the heap is empty, print ”Null” instead.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
You need to write a program to simulate a queue of names. Each name is a string consisting of English letters only. There are three operations:
1. “Push [name]”, which means to enque name in the queue.
2. “Pop”, which means to deque. If the queue is empty, this operation takes no effect.
3. “Front”, which means to print out the name in the front of queue. If the queue is empty, print "empty" (without quotes).
Input
There will be at most 106 operations. Each line contains one of the following operations. “Push [name]” (without quotes), “Pop” (without quotes), “Front”(without quotes). The length of each name is at most 10.
Output
For each “Front” operation, print out the name in the front of the queue.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A team queue works almost the same as the ordinary queue, with a little difference: When an element enters a queue, it first searches the queue to check if some of its teammates (elements of the same team) are already in the queue. If yes, it enters the queue right behind its teammates. If not, it enters the queue at the tail and becomes the new last element. Dequeuing is the same as the ordinary one: The elements are popped in the order they appear in the team queue. Given the team descriptions and a sequence of commands, simulate such a queue.
Input
The first line contains a single integer T (T ≤ 10) which represents the number of test cases. Each test case starts with two integers n, m (n ≤ 500, m ≤ 50000) denoting the number of teams and operations in this test case. The next n lines describe the teams, one team per line. The first integer k (k ≤ 500) in each line is the number of teammates in the team, and the following integers are the IDs of the team members. After that, next m lines describe m operations, one operation per line. You may assume that the ID will fit in a 32-bit signed integer.
Output
For each test case, first print a line containing “Case i:”, where i is the number of the test case, starting from 1. For each POP operation, print the popped number on a single line. Print a blank line between test cases.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A string is said to be valid if it matches one of the following rules:
(1) The string is an empty string.
(2) If a string S is valid, then {S}, [S], (S) and <S> are valid.
(3) If strings S1 and S2 are both valid, then S1S2 is valid.
Given a string consisting of parentheses, determine if it is a valid string.
Input
The first line of the input contains an integer N (N ≤ 1000) denoting the number of test cases followed by. Each of the next N lines corresponds to a test case, which contains a string consisting of parentheses, and the maximum string length will be no more than 1000. Note that an empty string (a line which contains the newline character only) may be contained in the input and it should be considered as a valid string according to rule (1).
Output
For each test case, print “Case i:” and then “Yes” or “No” to indicate that the string is valid or not, separated by a space character. i is the test case number starting from 1.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Evaluate the result of a given numerical expression written in postfix notation.
Input
The first line of the input contains an integer N (N ≤ 100) which denotes the number of test cases. Each test case begins with an integer M (M ≤ 10000) representing the number of tokens in the expression, followed by M tokens in the next line. Tokens are separated by spaces and the operators contain only “+”, “-”, “*” and “/”; the operands are integers in the range [0, 100]. The division operator “/” here is considered as integral divsion. You may assume that all of the expressions are valid (divide-by-zero would never occur) and the evaluated results (in each stage of the evaluation) will fit in 32-bit signed integers.
Output
The output of each test case occupies a line. Each line begins with the test case number “Case i:”, and then a space character followed by the evaluated answer.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a positive integer sequence a1, a2... an, whose elements are initially put in a queue Q in the given order. Determine that if it is possible, using a stack S and two operations:
(1) pop the first element in Q and push it into S, and
(2) pop the top element in S,
to obtain the other given sequence b1, b2… bn, where bi represents the i-th element popped from S. Note that “pop the first element in Q and push it into S” is considered as a single operation.
Input
The first line of the input contains an integer indicating the total number of test cases to follow. Each test case is composed of three lines. The first line contains a single integer n (n ≤ 1000), and each of the next two lines contains n integers, which respectively represents a1, a2… an, and b1, b2… bn. The numbers in the sequence are distinct integers from 1 to n.
Output
For each test case, print the sequence number “Case i:” and then “Yes” or “No” following a single space character to indicate if it is possible or not, in a line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given a sorted integer sequence in the ascending order and some queries, determine whether each queried number is in the sequence or not.
Input
There are multiple test cases. Each case begins with an integer N (1 <= N <= 106) in a line. The second line contains N integers, separated by a space. The third line contains an integer Q (1 <= Q <= 106) representing the number of the queries. In the next Q lines, each line contains an integer, representing a query. The input is terminated if N = 0.
Output
For each query, print “Yes” (without quotes) if the queried integer is in the given sequence and print “No” (without quotes) otherwise. Print a blank line between every two test cases.