Description

A number of K balls are dropped one by one from the root of a fully binary tree structure FBT. Each time the ball being dropped first visits a non-terminal node. It then keeps moving down, either follows the path of the left subtree, or follows the path of the right subtree, until it stops at one of the leaf nodes of FBT. To determine a ball's moving direction a flag is set up in every non-terminal node with two values, either false or true. Initially, all of the flags are false. When visiting a non-terminal node if the flag's current value at this node is false, then the ball will first switch this flag's value, i.e., from the false to the true, and then follow the left subtree of this node to keep moving down. Otherwise, it will also switch this flag's value, i.e., from the true to the false, but will follow the right subtree of this node to keep moving down. Furthermore, all nodes of FBT are sequentially numbered, starting at 1 with nodes on depth 1, and then those on depth 2, and so on. Nodes on any depth are numbered from left to right.

For example, Fig. 1 represents a fully binary tree of maximum depth 4 with the node numbers 1, 2, 3, ..., 15. Since all of the flags are initially set to be false, the first ball being dropped will switch flag's values at node 1, node 2, and node 4 before it finally stops at position 8. The second ball being dropped will switch flag's values at node 1, node 3, and node 6, and stop at position 12. Obviously, the third ball being dropped will switch flag's values at node 1, node 2, and node 5 before it stops at position 10.



Fig. 1: An example of FBT with the maximum depth 4 and sequential node numbers.


Now consider a number of test cases where two values will be given for each test. The first value is D, the maximum depth of FBT, and the second one is I, the Ith ball being dropped. You may assume the value of I will not exceed the total number of leaf nodes for the given FBT.

Please write a program to determine the stop position P for each test case.


For each test cases the range of two parameters D and I is as below:

Input

Contains l+2 lines.

Line 1 I the number of test cases
Line 2 D₁ I₁
test case #1, two decimal numbers that are separatedby one blank
...
Line k+1 D_k I_k
test case #k
Line l+1 D_l I_l
test case #l
Line l+2 -1 a constant -1 representing the end of the input file

Output

Contains l lines.

Line 1 the stop position P for the test case #1
...
Line k the stop position P for the test case #k
...
Line l the stop position P for the test case #l

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A single positive integer i is given. Write a program to find the digit located in the position i in the sequence of number groups S1S2…Sk. Each group Sk consists of a sequence of positive integer numbers ranging from 1 to k, written one after another. For example, the first 80 digits of the sequence are as follows:
11212312341234512345612345671234567812345678912345678910123456789101112345678910

Input

The first line of the input file contains a single integer t (1 <=t <=25), the number of test cases, followed by one line for each test case. The line for a test case contains the single integer i (1 <=i <=2147483647)

Output

There should be one output line per test case containing the digit located in the position i.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A positive integer may be expressed as a sum of different prime numbers (primes), in one way or another. Given two positive integers n and k, you should count the number of ways to express n as a sum of k different primes. Here, two ways are considered to be the same if they sum up the same set of the primes. For example, 8 can be expressed as 3 + 5 and 5 + 3 but they are not distinguished.

When n and k are 24 and 3 respectively, the answer is two because there are two sets {2, 3, 19} and {2, 5, 17} whose sums are equal to 24. There are no other sets of three primes that sum up to 24. For n = 24 and k = 2, the answer is three, because there are three sets {5, 19}, {7, 17} and {11, 13}. For n = 2 and k = 1, the answer is one, because there is only one set {2} whose sum is 2. For n = 1 and k = 1, the answer is zero. As 1 is not a prime, you shouldn't count {1}. For n = 4 and k = 2, the answer is zero, because there are no sets of two different primes whose sums are 4.

Your job is to write a program that reports the number of such ways for the given n and k.

Input

The input is a sequence of datasets followed by a line containing two zeros separated by a space. A dataset is a line containing two positive integers n and k separated by a space. You may assume that n<=1120 and k<=14.

Output

The output should be composed of lines, each corresponding to an input dataset. An output line should contain one non-negative integer indicating the number of ways for n and k specified in the corresponding dataset. You may assume that it is less than 2³¹.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Wavio is a sequence of integers. It has some interesting properties.
· Wavio is of odd length i.e. L = 2*n + 1.
· The first (n+1) integers of Wavio sequence makes a strictly increasing sequence.
· The last (n+1) integers of Wavio sequence makes a strictly decreasing sequence.
· No two adjacent integers are same in a Wavio sequence.
For example 1, 2, 3, 4, 5, 4, 3, 2, 0 is an Wavio sequence of length 9. But 1, 2, 3, 4, 5, 4, 3, 2, 2 is not a valid wavio sequence. In this problem, you will be given a sequence of integers. You have to find out the length of the longest Wavio sequence which is a subsequence of the given sequence. Consider, the given sequence as :

1 2 3 2 1 2 3 4 3 2 1 5 4 1 2 3 2 2 1.

Here the longest Wavio sequence is : 1 2 3 4 5 4 3 2 1. So, the output will be 9.

Input

The input file contains less than 75 test cases. The description of each test case is given below: Input is terminated by end of file.

Each set starts with a postive integer, N(1<=N<=10000). In next few lines there will be N integers.

Output

For each set of input print the length of longest wavio sequence in a line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

One of our best friends is getting married and we all are nervous because he is the first of us who is doing something similar. In fact, we have never assisted to a wedding, so we have no clothes or accessories, and to solve the problem we are going to a famous department store of our city to buy all we need: a shirt, a belt, some shoes, a tie, etcetera.

We are offered different models for each class of garment (for example, three shirts, two belts, four shoes, ..). We have to buy one model of each class of garment, and just one.

As our budget is limited, we cannot spend more money than it, but we want to spend the maximum possible. It's possible that we cannot buy one model of each class of garment due to the short amount of money we have.

Input

The first line of the input contains an integer, N, indicating the number of test cases. For each test case, some lines appear, the first one contains two integers, M and C, separated by blanks (1<=M<=200, and 1<=C<=20), where M is the available amount of money and C is the number of garments you have to buy. Following this line, there are C lines, each one with some integers separated by blanks; in each of these lines the first integer, K (1<=K<=20), indicates the number of different models for each garment and it is followed by K integers indicating the price of each model of that garment.

Output

For each test case, the output should consist of one integer indicating the maximum amount of money necessary to buy one element of each garment without exceeding the initial amount of money. If there is no solution, you must print "no solution".

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You have to cut a wood stick into pieces. The most affordable company, The Analog Cutting Machinery, Inc. (ACM), charges money according to the length of the stick being cut. Their procedure of work requires that they only make one cut at a time.
It is easy to notice that different selections in the order of cutting can led to different prices. For example, consider a stick of length 10 meters that has to be cut at 2, 4 and 7 meters from one end. There are several choices. One can be cutting first at 2, then at 4, then at 7. This leads to a price of 10 + 8 + 6 = 24 because the first stick was of 10 meters, the resulting of 8 and the last one of 6. Another choice could be cutting at 4, then at 2, then at 7. This would lead to a price of 10 + 4 + 6 = 20, which is a better price.

Your boss trusts your computer abilities to find out the minimum cost for cutting a given stick.

Input

The input will consist of several input cases. The first line of each test case will contain a positive number l that represents the length of the stick to be cut. You can assume l < 1000. The next line will contain the number n (n < 50) of cuts to be made.
The next line consists of n positive numbers ci ( 0 < ci < l) representing the places where the cuts have to be done, given in strictly increasing order.

An input case with l = 0 will represent the end of the input.

Output

You have to print the cost of the optimal solution of the cutting problem, that is the minimum cost of cutting the given stick. Format the output as shown below.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a set S = (e1, e2, ..., en) of n distinct elements such that e1 < e2 < ... < en and considering a binary search tree (see the previous problem) of the elements of S, it is desired that higher the query frequency of an element, closer will it be to the root.

The cost of accessing an element ei of S in a tree (cost(ei)) is equal to the number of edges in the path that connects the root with the node that contains the element. Given the query frequencies of the elements of S, (f(e1), f(e2, ..., f(en)), we say that the total cost of a tree is the following summation:

f(e1)*cost(e1) + f(e2)*cost(e2) + ... + f(en)*cost(en)

In this manner, the tree with the lowest total cost is the one with the best representation for searching elements of S. Because of this, it is called the Optimal Binary Search Tree.

Input

The input will contain several instances, one per line.

Each line will start with a number 1 <= n <= 250, indicating the size of S. Following n, in the same line, there will be n non-negative integers representing the query frequencies of the elements of S: f(e1), f(e2), ..., f(en). 0 <= f(ei) <= 100. Input is terminated by end of file.

Output

For each instance of the input, you must print a line in the output with the total cost of the Optimal Binary Search Tree.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The island nation of Flatopia is perfectly flat. Unfortunately, Flatopia has a very poor system of public highways. The Flatopian government is aware of this problem and has already constructed a number of highways connecting some of the most important towns. However, there are still some towns that you can't reach via a highway. It is necessary to build more highways so that it will be possible to drive between any pair of towns without leaving the highway system.

Flatopian towns are numbered from 1 to N and town i has a position given by the Cartesian coordinates (xi, yi). Each highway connects exaclty two towns. All highways (both the original ones and the ones that are to be built) follow straight lines, and thus their length is equal to Cartesian distance between towns. All highways can be used in both directions. Highways can freely cross each other, but a driver can only switch between highways at a town that is located at the end of both highways.

The Flatopian government wants to minimize the cost of building new highways. However, they want to guarantee that every town is highway-reachable from every other town. Since Flatopia is so flat, the cost of a highway is always proportional to its length. Thus, the least expensive highway system will be the one that minimizes the total highways length.

Input

The first line of the input consists of an integer indicating the number of test cases in the input. Then there's a blank line and the datasets separated by a blank line.

Each test case consists of two parts. The first part describes all towns in the country, and the second part describes all of the highways that have already been built.

The first line of the test case contains a single integer N (1 ≤ N ≤ 750), representing the number of towns. The next N lines each contain two integers, xi and yi separated by a space. These values give the coordinates of ith town (for i from 1 to N). Coordinates will have an absolute value no greater than 10000. Every town has a unique location.

The next line contains a single integer M (0 ≤ M ≤ 1000), representing the number of existing highways. The next M lines each contain a pair of integers separated by a space. These two integers give a pair of town numbers which are already connected by a highway. Each pair of towns is connected by at most one highway.

Output

Write to the output file a single line for each new highway that should be built in order to connect all towns with minimal possible total length of new highways. Each highway should be presented by printing town numbers that this highway connects, separated by a space.

If no new highways need to be built (all towns are already connected), then the output file should contain a line with the sentence "No new highways need".

Print a blank line between test cases.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A chest of drawers means a wardrobe which has many drawers aligned vertically as shown in the figure on the left. Although this is useful furniture, some problems arise when all the drawers need have provisions of locking - that is sometimes a drawer is not secured even if it is locked. For example assume that the third drawer from the top is locked but the drawer immediately above it is not locked. Then the drawer that is locked is also not secured because one can access it by pulling out the drawer immediately above it.

In a chest of n drawers, there are a number of ways to ensure that exactly s drawers are secure. For example for the chest of drawers shown on the left, exactly four drawers can be secured in six ways. These six ways are shown in Figure 2.

Given the value of n and s, your job is to find out in how many ways they can be secured.

Input

The input file contains at most 5000 lines of inputs.

Each line contains two integers n and s (1 ≤ n ≤ 65 and 0 ≤ s ≤ 65). Here n is the total number of drawers and s is the number of drawers that needs to be secured.

Input is terminated by a line containing two negative numbers. This input should not be processed.

Output

For each line of input produce one line of output. This line contains an integer which denotes in how many, s drawers out of the n drawers can be secured.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The sum of p (p>0) consecutive integers can often be equal to the sum of next q consecutive positive integers. For example:

9+10+11+12 = 13+14+15, Here p = 4 and q = 3

4+5+6+7+8 = 9+10+11, Here p = 5 and q = 3.

Given the value of q, how many possible values of p are there?

Input

The input file contains at most 1500 lines of inputs. Each line contains a positive integer less than 10¹⁴, which denotes the value of q. Input is terminated by a line containing a single zero. This line should not be processed.

Output

For each line of input produce one line of output. This line contains an integer, which denotes the total number of possible values of p.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Telephone poles are part of an outdated technology. Cell phones nowadays allow us to call whoever we want, wherever we want, independent of any wire. There is one problem - without a service tower nearby a cell phone is useless.


In the absence of hills and mountains, a service tower will provide coverage for a circular area. Instead of planning where to place the wires, a wireless telephone company has to plan where to build its service towers. Building the towers too far apart causes holes in the coverage and increases complaints. Building the towers too close to each other results in large areas covered by more than one service tower, which is redundant and inefficient.


International Cell Phone Company is developing a network strategy to determine the optimal placement of service towers. Since most customers have replaced their old wired home phones by cell phones, the strategy for planning service towers is therefore to cover as many homes of customers as possible.


The figure below shows the service areas for the five towers ICPC's strategic department planned to build this year. Tower 5 will serve 24 customers, 6 of which are also served by tower 4. Towers 1, 2 and 3 have a common service area containing 3 customers.

Shortly after the plans for these five towers had been published, higher management issued a stop on all tower building. Protesting customers forced them to weaken this decree, and allow the building of three towers out of the five planned. These three towers should serve as many customers as possible, of course. Finding the best possible choice for the towers to build is not trivial (the best choice in this case is towers 2, 4 and 5, serving 68 customers).


You must write a program to help ICPC choose which towers to build in cases like these. If several choices of towers serve the same number of customers, choices including tower 1 are preferable. If this rule still leaves room for more than one solution, solutions including tower 2 are preferable, and so on.

Input

The input file contains several test cases. The first line of each test case contains two positive integers: the number n (n<=20) of towers planned, and the number of towers to be actually built. The next line contains n numbers, each giving the number of customers served by a planned tower. (The first number refers to the first tower, and so on.) No tower serves more than a million people. The next line contains the number m (m<=10) of common service areas. Each of the next m lines contains the description of a common service area. Such a line starts with the number t (t > 1) of towers for which this is a common service area, followed by the t numbers of the towers. The last number on the line is the number of customers in the common service area. The last line of the input file consists of the two integers `0 0'.

Output

For each test case, display the number of customers served and the best choice for the location of the towers. Follow the format of the sample output. All numbers are left-justified and there are no blank spaces at the end of any line. Print a blank line after each test case.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The personnel department of Association of Cookie Monsters (ACM) has noticed that the productivity of various work groups in the company is not as good as it could be. They have interviewed the employees in the affected groups and they have detected the root of the problem: trust (or, rather, the lack thereof). Some employees do not trust the rest of the group, and this is decreasing their motivation and happiness. The personnel department wants to solve this problem, and has decided to reorganize the groups so that they are stable, i.e., they are formed by people who trust each other. They have asked the employees, and they know the people each employee trusts directly. Moreover, if employee A trusts employee B and employee B trusts employee C, then employee A will trust employee C. And obviously, each employee trusts himself. They want to create as few groups as possible to reduce administration overhead (they also do not want to work too hard).

With this information they have contacted you, and asked you to write a program that finds the minimum number of stable groups that can be created.

Input

The input consists of several test cases. Each test case begins with a line containing two positive integers P and T ( 1<=P<=1000, 0<=T<=999000) separated by a single space. P lines come next, each containing the name of one person. The names will have the following format: surname, a comma, a space and first name (for example McBride, John or Smith, Peter). Both the surname and the first name will be strings of uppercase or lowercase characters (with no blanks or punctuation marks), with a maximum length of 10 characters. There will not be repetitions in the complete names of the people. After the names there will appear T blocks of 2 lines representing the trust relations between people. Each line of the block will contain the name of a person in the same format as before, and the block will mean that the person in the first line trusts the person in the second line. All people appearing in the confidence relations will have appeared in the previous list of P people.
The input will end with the ``phantom'' test case `0 0', which must not be processed.

Output

For each test case, the output will be a line containing a positive integer representing the minimum number of stable groups of people that can be formed.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 A bar-code symbol consists of alternating dark and light bars, starting with a dark bar on the left. Each bar is a number of units wide. Figure 1 shows a bar-code symbol consisting of 4 bars that extend over 1+2+3+1=7 units.

Figure 1: Bar-code over 7 units with 4 bars

In general, the bar code BC(n,k,m) is the set of all symbols with k bars that together extend over exactly n units, each bar being at most m units wide. For instance, the symbol in Figure 1 belongs to BC(7,4,3) but not to BC(7,4,2). Figure 2 shows all 16 symbols in BC(7,4,3). Each `1' represents a dark unit, each `0' a light unit.

0: 1000100 | 4: 1001110 | 8:  1100100 | 12: 1101110
1: 1000110 | 5: 1011000 | 9:  1100110 | 13: 1110010
2: 1001000 | 6: 1011100 | 10: 1101000 | 14: 1110100
3: 1001100 | 7: 1100010 | 11: 1101100 | 15: 1110110

Figure 2: All symbols of BC(7,4,3)

Input

Each input will contain three positive integers n, k, and m (1 ≤ n, k, m ≤ 50).

Output

 For each input print the total number of symbols in BC(n,k,m). Output will fit in 64-bit signed integer.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A computing center has ten different computers (numbered 0 to 9) on which applications can run. The computers are not multi-tasking, so each machine can run only one application at any time. There are 26 applications, named A to Z. Whether an application can run on a particular computer can be found in a job description (see below).

Every morning, the users bring in their applications for that day. It is possible that two users bring in the same application; in that case two different, independent computers will be allocated for that application.

A clerk collects the applications, and for each different application he makes a list of computers on which the application could run. Then, he assigns each application to a computer. Remember: the computers are not multi-tasking, so each computer must handle at most one application in total. (An application takes a day to complete, so that sequencing i.e. one application after another on the same machine is not possible.)

A job description consists of

one upper case letter A...Z, indicating the application.
one digit 1...9, indicating the number of users who brought in the application.
a blank (space character.)
one or more different digits 0...9, indicating the computers on which the application can run.
a terminating semicolon `;'.
an end-of-line.

Input

The input for your program is a textfile. For each day it contains one or more job descriptions, separated by a line containing only the end-of-line marker. The input file ends with the standard end-of-file marker. For each day your program determines whether an allocation of applications to computers can be done, and if so, generates a possible allocation.

Output

The output is also a textfile. For each day it consists of one of the following:

ten characters from the set {`A'...`Z' , `_'}, indicating the applications allocated to computers 0 to 9 respectively if an allocation was possible. An underscore `_' means that no application is allocated to the corresponding computer.
a single character `!', if no allocation was possible.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

 With the advent of high speed graphics workstations, CAD (computer-aided design) and other areas (CAM, VLSI design) have made increasingly effective use of computers. One of the problems with drawing images is the elimination of hidden lines -- lines obscured by other parts of a drawing.

You are to design a program to assist an architect in drawing the skyline of a city given the locations of the buildings in the city. To make the problem tractable, all buildings are rectangular in shape and they share a common bottom (the city they are built in is very flat). The city is also viewed as two-dimensional. A building is specified by an ordered triple  where  and  are left and right coordinates, respectively, of building i and  is the height of the building. In the diagram below buildings are shown on the left with triples (1,11,5), (2,6,7), (3,13,9), (12,7,16), (14,3,25), (19,18,22), (23,13,29), (24,4,28)

the skyline, shown on the right, is represented by the sequence: (1, 11, 3, 13, 9, 0, 12, 7, 16, 3, 19, 18, 22, 3, 23, 13, 29, 0)

Input

 The input is a sequence of building triples. All coordinates of buildings are positive integers less than 10,000 and there will be at least one and at most 5,000 buildings in the input file. Each building triple is on a line by itself in the input file. All integers in a triple are separated by one or more spaces. The triples will be sorted by  , the left x-coordinate of the building, so the building with the smallest left x-coordinate is first in the input file.

Output

 The output should consist of the vector that describes the skyline as shown in the example above. In the skyline vector  , the  such that i is an even number represent a horizontal line (height). The such that i is an odd number represent a vertical line (x-coordinate). The skyline vector should represent the ``path'' taken, for example, by a bug starting at the minimum x-coordinate and traveling horizontally and vertically over all the lines that define the skyline. Thus the last entry in the skyline vector will be a 0. The coordinates must be separated by a blank space.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

http://uva.onlinejudge.org/external/102/10245.html 

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss