Problem A       Logical Line Counting

A software development company develops programs using a little known programming language with the following features:

Write a program that reads a series of programs and, for each program, counts the number of logical lines and the number of physical lines and issues warning messages for unterminated strings and unterminated block comments.

For each line containing an unterminated string, output a line of the form:

Unterminated string in line #.

where # is the physical line number within the current program. Subsequent text must be handled as though the string had been terminated at the end of the line.

If the program contains an unterminated block comment, output a line of the form:

Unterminated block comment at end of program.

After error messages, if any, output a line of the form:

Program # contains # logical lines and # physical lines.

The input will be a series of programs each terminated by a # at the start of a line. The entire input will be terminated by a second # i.e. a line starting ##. There will be no other # characters in the input.

Output will be as specified above. It must have exactly the form shown, with no extra spaces around numeric output, and with a full stop at the end of each line and with no blank lines.

Sample Input

(( Block comment; ))
"string"; ('another string;') @ line comment;
#
(((;(( A program typed by many monkeys; ));)))
yo mama! ;;@ ; '
' @ ;" ; ;'; "
)) ; (( ; )) '@"'; (";");
##

Sample Output
Program 1 contains 1 logical lines and 2 physical lines.
Unterminated string in line 3.
Program 2 contains 7 logical lines and 4 physical lines.
 

Problem B       Australian Voting

The Australian electoral system elects Members of Parliament by holding local elections in a number of electoral divisions, with only one representative elected per division. Under this system each voter not only indicates his or her candidate of first preference by placing a number 1 on a box besides the name, but goes on to indicate who is their second choice, third choice and so on until all their preferences have been indicated. In order to be elected, a candidate must receive an absolute majority of the first preference votes cast in the electoral division, that is, more than 50% of the votes.

Counting consists of one or more rounds. If at any round any candidate receives strictly more than 50% of the first preference votes, then that candidate is duly elected; otherwise the candidates (one or more) with the fewest first preference votes are excluded, and each vote currently assigned to them is re-assigned as a first preference to that voter’s next most preferred candidate still remaining. This process continues until one candidate has more than half of the first preference votes cast and is duly elected or all the remain ing candidates have the same number of first preference votes, in which case the election is tied and a new ballot is called.

Consider 4 candidates labelled A, B, C and D and 11 voters (labelled for convenience) who vote as follows:

Second round: 4 4 3 X - still no majority -- eliminate C. Take votes for C and reallocate v9 and vA to B, and vB to A.

Third round: 5 6 X X. Declare B the winner.

Write a program to determine the outcome of elections under this system.

Input will consist of a series of elections. The first round of line of each election will contain two integers C and V, where C is the number of candidates (2 ? C ? 26) and V is the number of voters (1 ? V ? 1000). Candidates are deemed to be labelled with an uppercase letter , starting with ‘A’, then ‘B’ and so on. (This is to preserve anonymity — this is a secret election after all). This will be followed by V lines with each line containing a voting preference in alphabetical order. These will be permutations of the numbers 1 to C. The file will be terminated with an election for which both C and V are zero.

Output will consist of one line for each election. If there is a clear winner output a line of the form:

Candidate X wins with n1 votes out of V.

otherwise output a line of the form:

Election is a tie.

Sample Input

4 11
1 2 3 4
1 4 2 3
1 3 4 2
1 2 4 3
4 1 2 3
3 1 4 2
2 1 3 4
3 4 1 2
4 2 1 3
4 3 1 2
4 2 3 1
4 6
1 4 3 2
1 2 3 4
3 1 2 4
4 1 2 3
4 2 1 3
2 3 4 1
0 0

Sample Output

Candidate B wins with 6 votes out of 11.
Election is a tie.
 

Problem C         Resistance is Facile

An electronic workshop is going to have several boxes of resistors, each containing at least 2,500 resistors of a particular value, different for each box. They may have as few as four boxes or as many as twenty.. One box will hold "1 thousand ohm" resistors. They haven't decided what values to use for the other boxes.

If you combine resistors in series, their values add up. For example, if you combine (in any order) three 500 thousand ohm resistors, two 200 thousand ohm resistors, a 50 thousand ohm resistor, two 20 thousand ohm resistors, a 5 thousand ohm resistor, and two 2 thousand ohm resistors, you get the equivalent of a 1999 thousand ohm resistor. Similarly you could replace the 5 thousand ohm resistor with two 2 thousand ohm resistors and one 1 thousand ohm resistor or one 2 thousand ohm resistor and three 1 thousand ohm resistors or five 1 thousand ohm resistors without changing the total resistance. In order to decide how many boxes to use and what to put in them, the workshop want to find out how easy it will be to make up various values, given a set of boxes. That is, given a number of boxes b, and resistor values 1 = v1 < v2 < … < vb in thousands of ohms, they want to know how many different ways there are to make up an n thousand ohm resistance using those values in the boxes, for several values of n.

Input

Input consists of scenarios. Each scenario starts with an integer, b, (4 ? b < 20). Input ends when b = 0. The next line in each scenario contains an ascending sequence of b numbers, starting with 1, representing v1 to vb, in that order. This line is followed by a series of lines each conmtaining a single integer representing the values of the resistances we wish to make, in the range 1 to 1999. The list is term inated by the integer 0, which should not be processed.

Output

For each value of n in the input output the number of ways to make up an n thousand ohm resistance, left justified on a line by itself.
 
 

Sample Input	Sample Output
9	1
1 2 5 10 20 50 100 200 500	4
1	11
5	271
10	451
42	15154
50	6295435
137	27888185754
500	1
1999	2
0	3
4	23
1 2 3 4
1
2
3
10
0
0

 

Problem D        Derivative Arithmetic

In mathematical modelling, it is often convenient to have the derivative df/dx of a function as well as the function f itself. Numerical differentiation evaluates f twice, to compute (f(x+v)-f(x))/v for some small value of v.Programdifferentiation computes the derivative symbolically. Derivative arithmetic, on the other hand, works simply and efficiently without the problems involved in symbolic differentiation. For this we augment an expression with its derivative, i.e. we represent it by the ordered pair (e, de/dx). Thus we have:

Input

IInput will be a series of characters representing instructions chosen from the following set, where n repre sents a digit in the range 0 to 9, and a and b are numbers that may contain a decimal point and may start with a sign. Blanks and line breaks may be inserted arbitrarily to enhance readability, except within a and b.

Sample Input

(2,1)(2,1)*(2,1)/W(3,2)P6G6
(1,0)+P6G6^3 W (2,1)SP7G7W
G7ELWG7LEW G7DLDWEWLLDWEEWQ
 
 

Sample Output	Alternative Sample Output
(2,1)	( 2.00000, 1.00000)
(64.0,96.0)	( 64.00000, 96.00000)
(1.41421,0.353553)	( 1.41421, 0.35355)
(1.41421,0.353553)	( 1.41421, 0.35355)
(1.41421,0.353553)	( 1.41421, 0.35355)
(0.34657,0.25)	( 0.34657, 0.25000)
(1.41421,0.353553)	( 1.41421, 0.35355)
(-1.05966,0.721348)	( -1.05966, 0.72135)
(1.41421,0.353553)	( 1.41421, 0.35355)

 

Problem E        Juggling Trams

After many years of .aut.ful service, the good city of Melbourne has decided to upgrade all of its aged green and gold trams to newer, more fashionable models. But alas, the pursuit of fashion has not been without its costs. The newer trams, whilst looking stunning, can only travel in straight lines. However this has not deterred the Melbourne City Council. In order to deal with this problem, they have laid more tracks and built more trams, so that there is now a vast grid of tram tracks criss-crossing throughout the city.

For simplification, consider the city to be a large grid of roads running north-south and east-west. Each road has a tram line running along it. You, the humble traveller, wish to travel south and west through this grid using the new tram system.

Trams run along each road at t-minute intervals, where t is a fixed time that has been determined by the Melbourne City Council. Thus, if you stand at any street intersection, you will see a tram travelling south every t minutes, and a tram travelling west every t minutes (although the trams will not necessarily pass by at the same times). We will assume that trams run at a constant speed, and take no time to pick up or drop off passengers.

Based on your training in city traversal optimisation theory, you wish to write a computer program that will find the fastest route from your starting point to your finishing point through the grid. You can hop on or off a tram at any intersection, and you may need to .aut. at some intersections for a tram to come along. You may assume that hopping on or off a tram takes no time at all, so, for instance, if a southward tram and a westward tram pass through an intersection at the same time, you may hop off one and immediately hop onto the other.

Input will consist of a number of data sets. The first line of each data set will contain two integers t and m, where t represents the number of minutes between each tram travelling down a street, as described earlier, with 1 ? t ? 60 inclusive and m represents the number of minutes it takes a tram to move from one intersection to the next, with m > 0. Input will finish with t = 0 and m = 0.

The second line of the data set will contain two integers n and e, where n is the number of north-south streets and e is the number of east-west streets. Both n and e will be between 1 and 100 inclusive. North-south streets will be numbered from 1 to n, where 1 is the eastmost street and n is the westmost street. East-west streets will be numbered from 1 to e, where 1 is the northmost street and e is the southmost street.

The third line will contain four integers sx sy fx fy. Your journey must begin at the intersection of north-south street sx and east-west street sy, and must end at the intersection of north-south street fx and east-west street fy. You can assume that both intersections exist and that sx ? fx and sy ? fy.

The fourth line will contain a single integer representing the number of minutes after midnight when your journey begins.

Following this will be n lines each containing two integers, first and k, where first is the number of minutes after midnight when the first tram leaves the northmost intersection along that street, and k is the total num ber of southward trams that will travel down that street throughout the day (k > 0). Note that these k trams will be spaced by intervals of t minutes. These lines are then followed by e lines containing the same information for the east-west streets.

Output consists of one line for each input data set. If it is possible to travel from the start point to the finish point, you must output a line of the form:

You arrive at hh:mm.

where hh:mm is the earliest time of day (using a 24-hour clock) at which you can arrive at your destination. Both hours and minutes must be two digits; use a leading 0 if necessary. You may assume that if a solution exists, the time of arrival will be before the next midnight.

If it is impossible to reach the destination, output the line:

Impossible.

Sample Input

30 3
5 4
2 2 5 4
93
30 5
100 6
115 4
100 7
30 8
10 10
0 11
20 9
10 10
30 3
5 4
2 2 5 4
300
30 5
100 6
115 4
100 7
30 8
10 10
0 11
20 9
10 10
0 0

Sample Output

You arrive at 01:52.
Impossible.
 

Problem F        Type Inference

Compile time type-checking catches some errors, but the declarations can be a heavy notational burden. To obviate this, some programming languages, such as Lisp and Smalltalk, allow variables to take on values of any type. Others, such as SML and Haskell, enforce strict compile time types, but infer the type of a var iable from the way it is used. This is done by initially assigning a general (unspecific) type to each variable and then constraining it to increasingly specific types as information about its usage is gathered.

Consider a simple programming language in which the types (from least to most specific) are:

         E

________/ \ ________

|   |   |   |   |   |

B   D   N   S   P   F

|___|___|__/ \ / \ /

     |        T   I

     C        |   |

     |_______|___|

         |

         U

As the program is parsed, the compiler accumulates constraints on the types of variables. For example, after seeing x < y the compiler concludes that:

Input

Input will consist of a series of lines representing constraints, all applying to the same program, and terminating with a line containing the letter Q. The possible formats are:

Output

Output will be one line for each distinct variable in the input, in the form shown below. The lines are to ap pear in ascending order of variable number i. The output represents the most general solution of the input constraints.

Sample Input

V0>=U
V1>=U
V0>=V1
V1>=V0
V0>=C
V1>=C
V1>=T
Q

Sample Output

V0=S
V1=S
 

Problem G        Isotope Composition

An element is characterised chemically by its atomic number (the number of protons in the nucleus), however most elements occur in two or more isotopes— atoms with the same number of protons but differing numbers of neutrons. Isotopes are indistinguishable chemically, but become important in mass spectrometry. A mass spectrometer is a device which bombards a compound to produce a series of charged fragments and then sorts them according to their mass. Because of the presence of isotopes, fragments with diff erent compositions may have the same mass and fragments with the same composition may have different masses. The proportions of the various naturally occurring isotopes of the common elements is known very accurately and this allows us to cal culate the range and relative proportions of masses that a given fragment may exhibit.

The composition of a fragment is written as a chemical formula — a list of symbols representing entities followed by the number of times each entity occurs if it occurs more than once. Entities are typically elements in which case their symbols are either a single upper case letter (e.g. N for Nitrogen) or an upper case letter followed by a lower case letter (e.g. Na for Sodium)Pseudo-elements (frequently occurring groups of entities) will also be given symbols, thus the ethyl grouping (C2H5) could be referred to as Et. Parentheses are used to delimit recurring groups of entities; a number ? 2 must follow every closing parenthesis to specify the number of times the group occurs. Thus valid formulae include H2O (water), H2SO4 (sulphuric acid), EtOH (ethanol, the ‘alcohol’ in drinks), (C2H5)2O (diethyl ether, the ‘ether’ used as an anaesthetic).

Write a program that will determine the range of weights and their percentage occurrence for a given formula.

Input

The input file will consist of two parts. The first part will define a list of symbols and either their isotopic composition (for elements) or their formula (for pseudo-elements). These formulae may be in terms of elements, other pseudo-elements or both. All symbols mentioned will be defined before use and there will not be any circularities. The symbol will occur in the first two character positions (the first character will be an upper case letter, the second will be a blank or a lower case letter) followed by a blank and either an ‘=’ (for a pseudo-element) followed by a chemical formula or a ‘:’ followed by the number of isotopes (in the range 1..5) followed in turn by that number of (atomic weight, abundance) pairs in order of increasing weight. Atomic weights are given as integers and abundances as percentages, i.e. as real numbers in the range (0.000, 100.000]. This part of the file is terminated by a line containing only ##.

The second part of the file contains a series of lines containing chemical formulae (one per line) according to the above rules. Lines will consist of no more than 60 characters, and no formula will consist of more than 60 atoms. This part of the file will also be terminated by a line consisting only of ##. This line should not be processed.

Output

For each formula (line) in the input, echo it to the output, followed by a list of the masses of all fragments that occur with an abundance greater than or equal to 0.001% together with their abundances, in order of increasing mass. The masses should be right justified in a field of width 5 and the abundances right justified in a field of total width 8 with 3 digits after the decimal point. Leave one blank line after each block of output corresponding to one formula. Follow the example shown below.
 

Sample Input

C : 2 12 98.93 13 1.07
H : 2 1 99.99 2 0.01
S : 4 32 94.93 33 0.76 34 4.29 36 0.01
Me = CH3
Et = MeCH2
##
H2
C2H4
C6H14
Et
C2H5
C(CMe3)4
S
##

Sample Output

H2

 2 99.980
 3 0.020

 28 97.832
 29 2.155
 30 0.012

 86 93.618
 87 6.206
 88 0.173
 89 0.003

 29 97.823
 30 2.165
 31 0.013

 29 97.823
 30 2.165
 31 0.013

 240 82.987
 241 15.557
 242 1.376
 243 0.076
 244 0.003

 32 94.930
 33 0.760
 34 4.290
 36 0.010

Problem H       The Game of Tarot

Playing cards, used for trick-taking games, came to Europe from the Islamic world in the late 14th century. Islamic card packs had four suits: Cups (C), Coins (N), Swords (S), and Polo-Sticks. At that time Europeans hadn't the faintest idea what a polo stick was, so they called that suit Batons (B). Each suit consisted of ten numeral cards (A, 2-10), and three court cards: King, Knight, and Knave. European card players experimented with doubling the court cards, so that there was a King (K), Queen (Q), Knight (N), Dame (D), Page (P), and Maid (M). It was this form, with 16 cards per suit, for a total of 64 suit cards, which was used in the oldest known Tarot decks. Modern cartomantic packs drop the Maid and Dame, so cartomancers are quite literally not playing with a full deck. For ordinary card games, Europeans reverted to a 52 card pack, dropping the Knight, Dame, and Maid.

The trump Tarot cards were invented sometime in the first half of the 15th century. The order of the trumps has never quite stabilised, but the pictures were fairly stable for a while. The following table lists the names of the trumps, from the oldest sources, together with single letters chosen to represent them.

Ranking and Score.

Each card has a rank and a value. Rank determines which cards win, value determines how much they win. In Swords and Batons, the cards are ranked (in descending order): King, Queen, Knight, Dame, Page, Maid, 10, 9, 8, 7, 6, 5, 4, 3, 2, Ace. In Cups and Coins, the cards are ranked (in descending order): King, Queen, Knight, Dame, Page, Maid, Ace, 2, 3, 4, 5, 6, 7, 8, 9, 10. The reversed order of the num eral cards in these suits looks rather odd, but all Italian trick-taking games of that time used this convent ion.

The Game

Assume there are N players. At the start of a game the cards are shuffled and dealt from left to right (clockwise) until all players have the same number of cards and there are fewer than N cards left — these excess cards play no further part in the game. The dealer then leads a card (places it face up on the table), and each player in turn plays a card face up on the preceding one. These N cards constitute a trick. The winner of a trick leads to the next trick. When playing to a trick one must follow suit (play a card of the same suit as the card that was led) if possible. If not, then one may trump the trick (play a trump card) or discard (play any card from one's hand). Also, if one holds the Idiot, one may play it (even if one could follow suit). There may be an advantage in doing this — see later. At the end of a game the cards are shuffled and the person to the left of the previous dealer deals the next hand and leads to the first trick.

For deciding who won a trick, the Idiot does not count as a trump; IT never wins a trick. If a trick does not contain any trump (except perhaps the Idiot) the highest ranking card of the suit led wins the trick, otherwise the highest ranking trump wins it. The player who won a trick takes all the cards that were played (except that the player who played the Idiot may swap it for another card), and gains the sum of the values of the cards captured (the value of the Idiot is used, not that of the card swapped for it).

Write a program that will read in a listing of cards in the order they were played and determine the scores of each player.

Input

The input consists of a description of a game setup, followed by the description of several games. The first line of the input consists of 22 letters giving the order of the trumps from highest to lowest. The Idiot (I) will always be the last letter. This will be followed by 86 integers on 5 lines giving the values of all the cards, firstly 22 integers on one line giving the value of the trumps in alphabetic order followed by 4 lines of 16 integers giving the values of the other cards in the order Cups, Coins, Swords and Batons. Within a suit the order is from King down to Ace. The next line contains only the number of players (N) in the range 2 to 8.

This will be followed by at least one but no more than nine games. Each game will consist of a sequence of card desig nators represent ing the cards in the order in which they are played, starting on a new line and terminating with ##. This sequence will be broken into lines of convenient length and not necessarily at the end of each trick. There will be zero or more spaces between card designators but there will not be any spaces at the end of a line. If the Idiot is played to any trick then the card designator following the N’th card of that trick repre sents the card that is swapped for the Idiot. This may be the Idiot, in which case there has not been a swap. Each deal will be terminated by ## and the en tire set of games will be terminated by a line consisting of ##.

Output

For each game write a line containing the string ‘Game ’, followed by the number of the game, followed by ‘:’ and the scores for each person in order in fields of width 7, assuming that the dealer for the first game is player 1. When all games have been played, write a summary line giving the total scores. Follow the format shown below.

Sample Input

XWVUTSRPONMLJHGFEDCBAI

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116

201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216

301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316

401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416

7

UT XT GT FT PT RT VT TT WT CT QS ET MT JT OT ST TS 2S DT LT IT 9C

AT NT DS TC NS 7S BT QN HT 9S KC 8S 6S PS PN MS NN IT TN 4S 5S 5B

KN KS 4N 5C 5N MN DN 7N AS 3N PB NC 8N AN 6N 4C PC DB QB QC 9N

2N 3C DC IT NB AC 6C IT MC 2C 8C 4B 8B MB 9B 7C TB 6B 2B 7B AB 3B ##

FT VT UT TT WT PT XT ET ST MS MT RT OT HT NS LT 2S JT NT CT BT

9S TS PN DT IT PS AT IT3S 7S KN 8S GT DS KS 8N 5S 9N QC QS DN AS

4N TN 5N PC 6S 7N 4S TC AN NC AC 3N 6N QN KC 2N MC 2C 9C QB MN

7C 6C DC PB 8C KB TB AB 4C NB 5B 5C 7B DB 8B MB 9B 3B 3C 4B 6B##

##

Sample Output

Game 1: 3004 105 371 677 1040 1544 8839

Game 2: 1517 2270 5799 0 4825 0 1768

Final : 4521 2375 6170 677 5865 1544 10607