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

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

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 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

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

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

Given an n×n matrix A,

                                                                                   ,

its determinant can be defined recursively as follows.

                                                                                   

where M­1,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 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 10⁶.

Output

For each case, output the LCM of a and b in a line.

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