The following are problems from several recent ACM Programming Contests. While the contest allows teams to use C, C++, or Java, you must solve the problem in Java. Also, the teams have three contestants who work together, you should work alone. On the other hand, the teams have 5 hours to solve as many problems as they can out of the nine problems given. You will have over two weeks to solve up to three problems, and these are the easy problems. You should design your solution and create a test data set that will test your program as much as you can. When you think that you have a correct solution, email your source code to me. I will compile and run your program using my own test data. There will be no hardcopy turned in to me.

Gnome Sequencing

In the book All Creatures of Mythology, gnomes are kind, bearded creatures, while goblins tend to be bossy and simple-minded. The goblins like to harass the gnomes by making them line up in groups of three, ordered by the length of their beards. The gnomes, being of different physical heights, vary their arrangements to confuse the goblins. Therefore, the goblins must actually measure the beards in centimeters to see if everyone is lined up in order.

Your task is to write a program to assist the goblins in determining whether or not the gnomes are lined up properly, either from shortest to longest beard or from longest to shortest.

Input: The input starts with line containing a single integer N, 0 < N < 30, which is the number of groups to process. Following this are N lines, each containing three distinct positive integers less than 100.

Output: There is a title line, then one line per set of beard lengths. See the sample output for capitalization and punctuation.

Duplicate Removal

The company Al's Chocolate Mangos has a web site where visitors can guess how many chocolate covered mangos are in a virtual jar. Visitors type in a guess between 1 and 99 and then click on a "Submit" button. Unfortunately, the response time from the server is often long, and visitors get impatient and click "Submit" several times in a row. This generates many duplicate requests.

Your task is to write a program to assist the staff at ACM in filtering out these duplicate requests.

Input: The input consists of a series of lines, one for each web session. The first integer on a line is N, 0 < N ≤ 25, which is the number of guesses on this line. These guesses are all between 1 and 99, inclusive. The value N = 0 indicates the end of all the input.

Output: For each input data set, output a single line with the guesses in the original order, but with consecutive duplicates removed. Conclude each output line with the dollar sign character '$'. Note that there is a single space between the last integer and the dollar sign.

Speed Limit

Bill and Ted are taking a road trip. But the odometer in their car is broken, so they don't know how many miles they have driven. Fortunately, Bill has a working stopwatch, so they can record their speed and the total time they have driven. Unfortunately, their record keeping strategy is a little odd, so they need help computing the total distance driven. You are to write a program to do this computation.

For example, if their log shows

Speed in miles per hour	Total elapsed time in hours
20	2
30	6
10	7

this means they drove 2 hours at 20 miles per hour, then 6-2=4 hours at 30 miles per hour, then 7-6=1 hour at 10 miles per hour. The distance driven is then (2)(20) + (4)(30) + (1)(10) = 40 + 120 + 10 = 170 miles. Note that the total elapsed time is always since the beginning of the trip, not since the previous entry in their log.

Input: The input consists of one or more data sets. Each set starts with a line containing an integer n, 1 ≤ n ≤ 10,  followed by n pairs of values, one pair per line. The first value in a pair, s, is the speed in miles per hour and the second value, t, is the total elapsed time. Both s and t are integers, 1 ≤ s ≤ 90 and 1 ≤ t ≤ 12.  The values for t are always in strictly increasing order. A value of -1 for n signals the end of the input.

Output: For each input set, print the distance driven, followed by a space, followed by the word "miles". 

Rock, Paper, Scissors

Rock, Paper, Scissors is a classic hand game for two people. Each participant holds out either a fist (rock), open hand (paper), or two-finger V (scissors). If both players show the same gesture, they try again. They continue until there are two different gestures. The winner is then determined according to the table below:

Your task is to take a list of symbols representing the gestures of two players and determine how many games each player wins.

In the following example:

Turn     :   1 2 3 4 5
Player 1 : R R S R S
Player 2 : S R S P S

Player 1 wins at Turn 1 (Rock beats Scissors), Player 2 wins at Turn 4 (Paper beats Rock), and all the other turns are ties.

Input: The input contains between 1 and 20 pairs of lines, the first for Player 1 and the second for Player 2. Both player lines contain the same number of symbols from the set {'R', 'P', 'S'}.  The number of symbols per line is between 1 and 75, inclusive.  A pair of lines each containing the single character 'E' signifies the end of the input.

Output: For each pair of input lines, output a pair of output lines as shown in the sample output, indicating the number of games won by each player.

The Seven Percent Solution

Uniform Resource Identifiers (or URIs) are strings like http://icpc.baylor.edu/icpc/, mailto:foo@bar.org, ftp://127.0.0.1/pub/linux, or even just readme.txt that are used to identify a resource, usually on the Internet or a local computer. Certain characters are reserved within URIs, and if a reserved character is part of an identifier then it must be percent-encoded by replacing it with a percent sign followed by two hexadecimal digits representing the ASCII code of the character. A table of seven reserved characters and their encodings is shown below. Your job is to write a program that can percent-encode a string of characters.

Input: The input consists of one or more strings, each 1–79 characters long and on a line by itself, followed by a line containing only "#" that signals the end of the input. The character "#" is used only as an end-of-input marker and will not appear anywhere else in the input. A string may contain spaces, but not at the beginning or end of the string, and there will never be two or more consecutive spaces.

Output: For each input string, replace every occurrence of a reserved character in the table above by its percent-encoding, exactly as shown, and output the resulting string on a line by itself. Note that the percent-encoding for an asterisk is %2a (with a lowercase "a") rather than %2A (with an uppercase "A").

Voting

A committee clerk is good at recording votes, but not so good at counting and figuring the outcome correctly. As a roll call vote proceeds, the clerk records votes as a sequence of letters, with one letter for every member of the committee:

Y means a yes vote
N means a no vote
P means present, but choosing not to vote
A indicates a member who was absent from the meeting

Your job is to take this recorded list of votes and determine the outcome.

Rules:
There must be a quorum. If at least half of the members were absent, respond "need quorum". Otherwise votes are counted. If there are more yes than no votes, respond "yes". If there are more no than yes votes, respond "no". If there are the same number of yes and no votes, respond "tie".

Input: The input contains of a series of votes, one per line, followed by a single line with the # character. Each vote consists entirely of the uppercase letters discussed above.  Each vote will contain at least two letters and no more than 70 letters.

Output: For each vote, the output is one line with the correct choice "need quorum", "yes", "no" or "tie".

Pizza Pricing

Pizza has always been a staple on college campuses. After the downturn in the economy, it is more important than ever to get the best deal, namely the lowest cost per square inch. Consider, for example, the following menu for a store selling circular pizzas of varying diameter and price:

One could actually compute the costs per square inch, which would be approximately 10.2¢, 7.6¢, and 7.1¢ respectively, so the 12-inch pizza is the best value. However, if the 10-inch had been sold for $5, it would have been the best value, at approximately 6.4¢ per square inch.

Your task is to analyze a menu and to report the diameter of the pizza that is the best value. Note that no two pizzas on a menu will have the same diameter or the same inherent cost per square inch.

Input: The input contains a series of one or more menus. Each menu starts with the number of options N, 1 ≤ N ≤ 10, followed by N lines, each containing two integers respectively designating a pizza's diameter D (in inches) and price P (in dollars), with 1 ≤ D ≤ 36 and 1 ≤ P ≤ 100. The end of the input will be designated with a line containing the number 0.

Output: For each menu, print a line identifying the menu number and the diameter D of the pizza with the best value, using the format shown below.

Refrigerator Magnets

Like many families with small children, my family’s refrigerator is adorned with a set of alphabet magnets:  26 separate magnets, each containing one letter of the alphabet. These magnets can be rearranged to create words and phrases. I feel it is my parental duty to use these magnets to create messages that are witty and insightful, yet at the same time caring and supportive. Unfortunately, I am somewhat hindered in this task by the fact that I can only make phrases that use each letter once.

For example, a nice inspiring message to leave for the children might be, “I LOVE YOU.” Unfortunately, I cannot make this message using my magnets because it requires two letter "O"s. I can, however, make the message, “I LOVE MUSTARD.” Admittedly this message isn't as meaningful, but it does manage to not use any letters more than once.

You are to write a program that will look at a list of possible phrases and report which phrases can be written using refrigerator magnets.

Input:  The input will consist of one or more lines, ending with a line that contains only the word “END”.

Each line will be 60 characters or less, and will consist of one or more words separated by a single space each, with words using only uppercase letters (A–Z). There will not be any leading or trailing whitespace, and there will not be any blank lines.

Output:  Output only the lines which can be written in refrigerator magnets—that is, the lines which have no duplicate letters. Output them exactly the same as they were in the input—white spaces and all. Do not output the final “END” string.