TJU Programming Contest

     This is a compilation of TJU Programming problems that were given to us from Dr. Stansifer. The last question gave me the most trouble, as I forgot to make sure that the difference and sum could be equal.

---

Head or Tail

     John and Mary have been friends since nursery school. Since then, they have shared a playful routine: every time they meet, they play Head or Tail with a coin, and whoever wins has the priviledge of deciding what they are going to play during the day. Mary always choose Head, and John always choose Tail.

     Nowadays they are in college, but continue being truly good friends. Whenever they meet, they still play Head and Tail, and the winner decides which film to watch, or which restaurant to have dinner together, and so on.

     Yesterday Mary confided to John that she has being keeping a record of the results of every play since they started, in nursery school. It came as a surprise to John! But since John is studying Computer Science, he decided it was a good opportunity to show Mary his skills in programming, by writing a program to determine the number of times each of them won the game over the years.

Input

     The input contains several test cases. The first line of a test case contains a single integer N indicating the number of games played (1 ≤ N ≤ 10000). The following line contains N integers Ri, separated by space, describing the list of results. If Ri = 0 it means Mary won the ith game, if Ri = 1 it means John won theith game (1 ≤ i ≤ N). The end of input is indicated by N = 0.

Output

     For each test case in the input your program should output a line containing the sentence "Mary won X times and John won Y times", where X ≥ 0 and Y ≥ 0.

Sample Input

5

0 0 1 0 1

6 0 0 0 0 0 1

0

Output for the Sample Input

Mary won 3 times and John won 2 times 

Mary won 5 times and John won 1 times

---

Number Sequence

     Given a positive integer number, we want to generate a number sequence with the following rules:

     If the current number is 1, the process will be terminated. Otherwise, if the current number is even, the next number will be n/2. If the current number is odd (except 1), the next number will be 3*n+1. Then we turn to deal with the new number, until we get 1.

     For example, given the first number 22, we will get {22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1}. The length of this sequence is 16.

     Given the first number, your task is to find the length of the sequence generated with these rules. We assume that the length will not be more than 1000.

Input

There is only one number N (1 ≤ N ≤ 1000) for each test case, indicating the first number of the sequence.
The input is terminated by a zero.

Output

Output one number in a line for each test case, indicating the length of the sequence we generate.

Sample Input

22

1000

1

0

Sample Output

16

112

1

Author: RoBa

---

Bovine Latin

     The cows have heard that the pigs use a secret language called "Pig Latin" when they want to communicate with each other without Farmer John being able to understand what they are saying. Thinking this is an excellent idea, they have invented their own version, aptly called Bovine Latin.

     Converting an English word to a Bovine Latin word is quite simple. For words that start with a vowel ('a', 'e', 'i', 'o' or 'u'), "cow" is added to the end of the word; for example, "udder" becomes "uddercow". For words that do not begin with a vowel, the first letter is moved to the end of the word, and "ow" is added; e.g., "farmer" becomes "armerfow". So "the cows escape at dawn" becomes "hetow owscow escapecow atcow awndow." The cows fervently believe that FJ will not understand this subterfuge.

     Never known as enthusiastic linguists, the cows find this translation quite tedious and thus have asked you to write a program that will take single words and translate them into Bovine Latin. They will provide you with N (1 ≤ N ≤ 100) words to translate; word lengths range from 3 to 40 letters.

Input

* Line 1: A single integer: N
* Lines 2..N + 1: One word per line.

Output

* Lines 1..N: The Bovine Latin translations of the given words

Sample Input

5

udder

farmer

milk

aaa

zzz

Sample Output

uddercow 

armerfow 

ilkmow 

aaacow 

zzzow

---

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

Example input:	Example output:
3 20 2 30 6 10 7 2 60 1 30 5 4 15 1 25 2 30 3 10 5 -1	170 miles 180 miles 90 miles

---

Above Average

     It is said that 90% of frosh expect to be above average in their class. You are to provide a reality check.

     The first line of standard input contains an integer C, the number of test cases. C data sets follow. Each data set begins with an integer, N, the number of people in the class (1 ≤ N ≤ 1000). N integers follow, separated by spaces or newlines, each giving the final grade (an integer between 0 and 100) of a student in the class. For each case you are to output a line giving the percentage of students whose grade is above average, rounded to 3 decimal places.

Sample Input

5
5 50 50 70 80 100
7 100 95 90 80 70 60 50
3 70 90 80
3 70 90 81
9 100 99 98 97 96 95 94 93 91

Output for Sample Input

40.000%
57.143%
33.333%
66.667%
55.556%

---

Beat The Spread!

     Superbowl Sunday is nearly here. In order to pass the time waiting for the half-time commercials and wardrobe malfunctions, the local hackers have organized a betting pool on the game. Members place their bets on the sum of the two final scores, or on the absolute difference between the two scores.

     Given the winning numbers for each type of bet, can you deduce the final scores?

     The first line of input contains n, the number of test cases. n lines follow, each representing a test case. Each test case gives s and d, non-negative integers representing the sum and (absolute) difference between the two final scores. For each test case, output a line giving the two final scores, largest first. If there are no such scores, output a line containing "impossible". Recall that football scores are always non-negative integers.

Sample Input

2
40 20
20 40

Output for Sample Input

30 10
impossible

---