Description

Your chief judge is getting long in the tooth and it is getting increasingly difficult for him to read through the densely-written messages of complaints about the problems and scores. The chief judge prefers to have more and uniform spacing between the words, and you have been drafted to write a program to format lines of text accordingly.

Your task is to write a program to read a number of lines of text and format each line independently such that:

1. successive words on a formatted line are separated by exactly two blank spaces, and
2. words are NOT split between lines, and
3. width of the formatted text does not exceed a specified value.

Leading and trailing blank spaces on each given line should be ignored.

As an example:

The first input line is formatted into three (3) lines of width bounded by 20 places, and words separated by two blank spaces in each line. The second input line is formatted independently on the fourth output line.

Input

Input to this problem starts with an integer K , K > 0 , that represents the number of messages. The number K is given on a separate line followed by a description of the K messages. The description of each message starts with a line that contains two integers. The first integer W , W ≥ 20 , represents the desired width of the formatted text, and the second integer N , N > 0 , represents the number of lines in the message. A single blank space separates the two integers. The message, which consists of N lines, follows with each line consisting of a sequence of one or more words separated by blank spaces. The length of each word is less than or equal to W . That is, a word like ``supercalifragilistic-expialidocious" is only to be expected as part of the input if W ≥ 35 .

Output

For each message the output consists of one line. The line starts with the message number (the first message being ``Message 1"), followed by a ``: " (colon followed by space), as shown in the Sample Output below. This is followed by the number of lines that the formatted text would occupy.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

An integer number is said to be self-divisible if each digit divides the number formed by all digits up to and including that digit evenly. If you find yourself puzzled by the previous sentence, you should not worry. You are not alone. I needed to scribble few examples to understand it myself.

Here are few of them:

1)
        213 is a self-divisible number because

        2 divides 2, 1 divides 21, and 3 divides 213.

2)
        201 is not a self-divisible number because

        2 divides 2, but 0 does not divide any number.

3)
        2534 is not a self-divisible number because

2 divides 2, 5 divides 25, but 3 does not divide 253.

Your task is to write a program to count the number of self-divisible numbers in a selected range. As an example, for the range of integers between 7 and 15, where

• 7, 8, 9, 11, 12, and 15 are self-divisible
• 10 is not self-divisible because it contains a zero, which cannot divide any number, and
• 13 and 14 are not self-divisible because the 2nd digit in each number does not divide it.

your program must calculate a count of 6.

Input

Input to this problem starts with an integer N that represents the number of cases, N > 0 , on a separate line followed by a description of the N cases. Each case is described on a separate line by two positive integers S and F , where S is less than or equal to F , that represent the start and finish values of a range of integers. The two numbers are separated by a single blank space as shown in the Sample Input below. Each of the integers S and F consists of K digits, 0 < K < 400 , and the number of self-divisible numbers in the range between each pair is less than 1000000.

Output

For each case, the output consists of one line. The line starts with the case number starting with the value of one (1), followed by a ``:", as shown in the Sample Output below, and then followed by the number of self-divisible numbers in the range.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Darts (Some historical records suggest that the first standard dartboards were the bottoms of wine casks, hence the game's original name of ``butts".) is a very popular game in which darts are thrown at a circular target (dart board) hung on a wall. Dart boards are usually made of sisal fibers or boar bristles, low quality boards are sometimes made of paper. A regulation board is 45.72 cm in diameter, and is divided into sectors. Each sector is lined with metal wire. The numbers indicating the various scores of sectors on the dart board are normally made of wire, especially on tournament-quality boards, but may be printed on the board instead. In the standard game, the dart board is hung so that the bulls-eye is 1.73 m from the floor, eye-level for a six foot person. The oche, the line behind which the player must stand, is 2.37 m from the face of the board. When playing darts players often aim at the high scoring sectors, but for ordinary players it is hard to land a dart on the desired sector. The risk of aiming at a sector can thus be measured by the difference between the scores of adjacent sectors, where two sectors are said to be adjacent if they share an edge or an arc. A large such difference increases the risk and makes the game more challenging. The total risk of a dart board is the sum over the risks between all adjacent sectors. We have been asked by the sponsor of a programming competition to design a new, and challenging, dart board to occupy the touchy coaches during the contest.

The new dart board design consists of a circle that is divided into N sectors, N ≥ 3 , by lines running from the centre of the circle to its perimeter and a smaller concentric circle that subdivides each sector into two areas: as shown in the sketch for N equal to three (3).

Your task is to write a program to read ``2N " positive integer values and assign them to the ``2N " areas of the new dart board design such that the total risk is maximized. An example of such an assignment is:

The total risk of this dart board design with ``6" areas is 59.

Input

The first line of the input contains a single integer between 1 and 1000, inclusive, which is the number of dart boards that follow. The description of each dart board consists of two lines:

1. The first line consists of an integer N , 300 ≥ N ≥ 3 , which identifies the number of sectors on the board.
2. The second line consists of ``2N " positive integers, separated by single spaces, which represent the scores. Each integer is less than or equal to 10000.

Output

For each dart board the output is an integer, on a separate line, which represents the maximum risk of the board.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A skyline is the outline formed by a group of buildings against the sky. The ACM city in Second Life, which has been built with a beautiful skyline that's visible to anyone that approaches it, sold the rights to place advertisement at the approaches to the city to a company as long as it does so while preserving the shape of the city's skyline. The company wants to accept all requests for advertising that are of rectangular shape and can be fully placed, with sides parallel to edges of the skyline as shown shaded in the example below, within the interior of the skyline.

Each skyline of the ACM city is formed by N buildings, all with a width of one (1) but with different heights. The height of each building is between 0 and 1000, inclusive and the number of buildings N is between 1 and 400, inclusive. The example below shows a skyline with six (6) buildings, and an advertisement of size 3 by 5 (shown in gray) placed parallel to the sides of the skyline. Note that an advertisement may be rotated by 90o so that it can fit into the skyline. That is, advertisement of size 5 by 3 can be placed within the skyline by rotating it first. It is ``Second Life" after all.

Your task is to write a program to read the descriptions of a number of skylines and advertising requests, and decide for each request whether it should be accepted or rejected. Each request is to be checked independently as only one advertisement will be displayed at any time.

Input

The first line of the input contains a single integer C between 1 and 1000, inclusive, which is the number of cases that follow. Each case starts with a description of the skyline of the city from one approach that consists of two lines:

1. The first line contains an integer N , 1 ≤ N ≤ 400 , that is the number of buildings in the skyline
2. The second line contains the heights of the buildings

followed by a sequence of advertising requests. Each request consists of two integers on a single line, separated by a single space, which describe the length of the two sides of the rectangle that contains the advertisement. Both lengths are between 1 and 1000, inclusive. A request of two zeros separated by a single space (0 0) terminates the case.

Output

For each skyline the output starts with a line that contains the case number starting with the value of one (1), followed by a ``:", as shown in the Sample Output below, and then followed by a sequence of decisions of ``Accept" or ``Reject", on a separate line, for each request.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Jeremy is not known for his organizational skills, but he is now determined to change. Jeremy's plan is to place notes around the house to remind him of tasks to be done and of the proper ways to do them. Jeremy's plan also includes encrypting the messages so that his parents (who don't understand anything!) do not nag him, but in a simple way so that he can recover the original message easily.

Jeremy's encryption scheme consists of two steps:

1. Enter the message, of M characters, which includes the spaces between words, into a spiral that curls inwards in a clockwise direction, starting at the top-left corner of a square. The width and height of the square enclosing the spiral are chosen to be equal to the square root of P , where P is the smallest perfect square larger than or equal to M . If M is strictly less than P , then the remaining locations in the square are filled with the character `$'.
2. Write the encrypted note by writing the characters one row at a time starting with the top row.

As an example, for the following message of 33 characters

abcd fgh jklmn pqrstu wxyz1 34567

Jeremy writes the following note:

abcd ftu wxgs67$yhr5$$z q43 1jp nmlk

based on entering his original message in a square of 6 rows and 6 columns as follows:

Your task is to write a program to encrypt Jeremy's messages with the hope that he will acquire some organizational skills, in peace. In case you have forgotten, let me remind you that a number X is a perfect square if there exists a positive integer K , such that K² equals X . For example, 16 is a perfect square but 18 is not a perfect square.

Input

Input to this problem starts with an integer N that represents the number of messages, N > 0 , on a separate line followed by a sequence of N messages. Each message consists of M characters, 1000 ≥ M > 0 , on a single line with no blank spaces at the end.

Output

For each message, the output consists of one line that contains the note with an encrypted message.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

As the sole employee in a pharmaceutical company with programming exposure, you have been asked to oversee the process of cutting DNA strands into smaller pieces, which has been outsourced to a company by the name of Chopper!, and check for any attempt of over charging.

DNA (Deoxyribonucleic acid) strand is a long polymer of simple units called nucleotides, with a backbone made of sugars and phosphate atoms joined by ester bonds. Attached to each sugar is one of four types of molecules called bases. It is the sequence of these four bases along the backbone that encodes information needed to construct other components such as proteins and RNA molecules. The cost of cutting a DNA strand, with today's technology, is equal to the length of the strand, where a ``cut" refers to splitting a strand into two pieces. The cost of a single cut does not depend on the location where the cut is made. Chopper! claims to have developed the world-best-practice in sequencing the cuts of a DNA strand and to deliver the most savings to its customers.

Your task is to write a program to process the next batch of DNA strands and calculate the best price for slicing each of them into smaller strands of integer lengths. For each DNA strand you are given its length as an integer N , N ≤ 10000 , and a list of M , 2 ≤ M ≤ 15 , strands' lengths to be produced. The sum of the M integers equals the original strand length N .

The total cost of slicing a given strand depends on the choice of locations and the order of the M - 1 required cuts. As an example, for a given list of M (=4) lengths 2, 2, 5 and 5 and a DNA strand of length 14, we can:

• first cut the strand in half then twice split a 2 and 5 from the remaining 7s for a cost of 28 (=14 + 7 + 7), or
• first cut off a 5 from the end of the strand, then another 5, then split the remaining 4 in half for a cost of 27 (= 14 + 9 + 4).

Input

The input contains information about a number of DNA strands to be processed. The information for each strand consists of two lines:

1. The first line consists of the two integers M and N ( 2 ≤ M ≤ 15 and 0 ≤ N ≤ 10000 ) that identify the number of required smaller strands and the length of DNA strand, respectively.
2. The second consists of M positive integers (separated by blank spaces) that sum to N .

The input is terminated by a line of two zeros (0 0) for which no output is to be produced.

Output

For each input DNA strand the output is an integer, on a separate line, which represents the minimum cost for slicing the strand into the given list.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

You must be familiar with binary trees and all their operations, but this problem deals with a less popular structure, which I shall call myTree. There are three possible organizations of a myTree:

1. an empty tree. That is, a tree with no nodes.
2. a tree whose root node has a single data item, say K, and two children. Each of its two children is a myTree. Any values in the left subtree are less than or equal to K, and any values in the right subtree are larger than K.
3. a tree whose root node has two data items, say K₁ and K₂ , and three children. K₁ < K₂ . Each of its three children is a myTree. Any values in the left subtree are less than or equal to K₁ , any values in the middle subtree are larger than K₁ and smaller than or equal to K₂ , and any values in the right subtree are larger than K₂ .

All internal (non-terminal) nodes have two or three children, although some may be empty. One way to represent such a tree is to use level-order traversal, starting at the root node, with the content of each node enclosed in parentheses. An empty tree is represented by a pair of parentheses that encloses nothing. The following figure demonstrates an example of such a tree, along with its representation, with values in the nodes being uppercase characters chosen in the range of ``A" to ``Z", inclusive.

A lecturer of ``Data Structures 101" likes to test her students understanding of the myTree structure by asking them to identify all possible ways to assign a missing value in a given myTree.

Examples of such a question would be:

1. a tree ``(M R) (C) (N P) (? U) () () () () () () () ()", for which the answer should be the letters ``S" and ``T".
2. a tree ``(M R) (X) (N O) (? U) () () () () () () () ()", for which the answer should be ``This is not a myTree". The reason is that X > M .
3. a tree ``(M R) (N O) (? U)", for which the answer should be ``This is not a myTree". The reason is that nodes with two values should have three children in a myTree structure, which is violated in this question.

Your task is to write a program to answer such a question.

Input

The input contains descriptions of a number of myTree structures to be processed. The information for each tree is given in a single line as a series of properly matched parentheses. Each pair of matched parentheses encloses zero, one, or two characters selected from uppercase letters in the range of ``A" to ``Z" and ``?". Each line contains exactly one ``?". The selected characters and parentheses are separated by single spaces.

The input is terminated by a line of a set of matched parentheses, which encloses a zero, for which no output is to be produced.

Output

For each input tree the output is a single line with:

1. a listing of possible uppercase letters sorted in increasing order that can replace the ``?" in the given tree, or
2. the string ``This is not a myTree", if the given data does not conform to the given specifications.

Sample Input  Download

Sample Output  Download

Tags

Discuss