UNSW High Schools Programming Competition 1999

Preliminary Round

This page contains links to all of the material needed to complete the Preliminary Round of the UNSW High Schools Programming Competition.

The detailed rules of the competition are supplied in a separate page. Please read the rules carefully before commencing the competition.

Each programming task is described in a separate page, and there is a separate directory for each task containing data files.

Tasks may be completed in any order. You must stop working and submit your work so far after 2 hours. You can submit program listings, even if they're not working.

Good Luck!


Task 1 - UPI Validation

Description

The University of New South Wales is adopting an 8-digit Universal Personal Identifier (UPI) as a means of identifying staff and students. The digits of a valid UPI follow a rule that allows a single typing error to be detected. Your task is to write a program to validate UPIs.

Ths basic task is worth 10 points. The extension is worth up to 5 bonus points.

Validation Algorithm

Calculate the following quantity:

S = sum of digits in odd positions
+ 3 * (sum of digits in even positions except the last)
- digit in last position
where digit positions are counted from the left, beginning with 1. Thus the odd positions are the first, third, fifth and seventh digits. A UPI is valid if and only if S is a multiple of 10. Thus 53723516 is valid because 5+7+3+1+3*(3+2+5)-6=40, which is a multiple of 10.

The input format is one UPI per line. The program should display the UPI followed by the word "OK" or the word "REJECT".

Examples

Input Output 

53723516

00367857

12345678

28654322

19851688

99999999

00000000



53723516 OK

00367857 OK

12345678 REJECT

28654322 OK

19851688 OK

99999999 REJECT

Extension

As well as single-digit substitution errors, UPIs are also able to detect most transposition errors (exchanging adjacent digits). If you swap adjacent digits then 9 times out of 10 the result will be an invalid UPI. The tenth case is where the swapped digits differ by a fixed, critical amount.
  1. For 2 points, determine what that critical difference is. You can use reasoning (the algebra is not difficult), or you can write a short program incorporating your validation algorithm to try the 10 possibilities.

  2. For 3 additional points, modify your first solution to display after each valid UPI a risk factor, equal to the number of adjacent digits that differ by the critical amount just determined. The risk is an integer between 0 and 7 inclusive.
Input Output 

19851688

99999999

00000000



19851688 OK risk=1

99999999 REJECT

Constraints

Assume that every line contains exactly 8 digits. There is no limit on the number of input lines.

Task 2 - The nth Prime Number

Description

A prime number has only two factors, one and itself. For example, 13 is a prime number because it is divisible only by 1 and 13. However, 15 is not a prime number because is divisble by 1, 3, 5 and 15.

Write a program which when given a positive integer i returns the i-th prime number. Assume that 2 is the first prime number.

This task is worth 10 points.

Examples

Input Output 
1
 
2


2
 
3


3
 
5


4
 
7


5
 
11


42
 
181

Constraints

The input will be a single positive integer.

Task 3 - Letter Maths

Description

"Letter maths" are encoded arithmetic equations where each digit is substituted consistently by a particular letter. For example, the sum 256 + 512 = 728 might be expressed as ABC + BDA = EAF, where the encoding is A=2, B=5, C=6, D=1, E=7, F=8.

Your task is to write a program that reads in an arbitrary "letter maths" equation and determines an encoding that gives a valid arithmetic equality. The program should then print out the decoded equation. If no such encoding is possible, your program should indicate this with the output Invalid letter maths. If there are multiple encodings that produce a valid equality, then any of them is acceptable.

Input is a single line consisting of a "number", a single space, an operator (one of '+', '-', '*' or '/'), a single space, another "number", an '=' character with a single space on either side, and a final "number". In this context, "numbers" are sequences of upper-case alphabetic letters.

This task is worth 15 points.

Examples

Input Output 
ABC + BDA = EAF
 
256 + 512 = 728
 
ABCDDD * XYZ = JEDJZDDD
 
123000 * 765 = 94095000
 
EEL / A = XY
 
113 / 4 = 28
 
AAAA + B = CC
 
Invalid letter maths

Constraints

There will never be more than 10 distinct letters used in an input line.
Numbers in output should not contain leading zeroes.
Division will be performed as integer division (i.e. with truncation).

Task 4 - Game Show

Description

Consider a TV game show which is played as a sequence of rounds. Each round of the show is won by one (and only one) of the contestants and they score a certain number of points for that round. The other contestants score zero for the round. The winner of the game show is the contestant with the largest number of points when the game finishes.

The result of each game show round will be enter on single line. The line will contain the contestants name followed by their score for that round. A line containing only the word end indicates the finish of the game show. The number of rounds or contestants is not fixed.

Write a program which takes as input the results of each game show round and prints the winner of the game show.

The basic task is worth 10 points. The extension is worth up to 5 bonus points.

Examples

Input Output

john 1

fred 3

mary 7

fred 2

john 1

john 4

mary 1

fred 4

john 1

end



The winner is fred with a score of 9

Constraints

There will be no more than 16 contestants in any game show.

A game show will last no more than 100 rounds.

Contestants' names will always be a single word containing only lower-case alphabetic charcters. Names will always be spelt correctly.

There will always be one outright winner (no ties). In other words one contestant always has a score larger than any other.

The last line of input will always contain the word end. No contestant will have the name end.

Your program can assume input is correct.

No error checking is required.

Extension

Assume that, in the heat of the show, people will not have time to carefully type in contestant names. For 5 bonus marks, modify the program so that it will match names even if they differ in the case of characters (i.e. treat upper-case the same as lower-case), and they will match even if a single pair of characters is transposed (e.g. jhon will be treated the same as John, and NaNe will be treated the same as Anne).

Task 5 - Telephone Call Details

Description

The Car-Tel phone company produces an electronic list of call details for its larger customers. Call details include the phone number, the date a call started, and the starting and finishing times. The list is contained in a file with one call per line. All the calls for a line are grouped together and sorted by starting date and time.

Each line of the file contains 4 fields separated by commas: 


phonenumber,dd/mm/yyyy,hh:mm:ss,hh:mm:ss
where phonenumber is a 10-digit phone number (including area code, no spaces or hyphens); the date is presented as a 2-digit day (dd), 2-digit month (mm) and 4-digit year (yyyy), separated by / characters; and the times are in 24-hour format with 2 digits each for hour (hh), minute (mm) and second (ss).

The input is terminated by a line consisting of the dummy number 0000000000 and irrelevant other fields.

The basic task is worth 10 points. The extension is worth up to 5 bonus marks.

Basic Task

Write a program that calculates and prints the total length of all calls from each phone line, expressed in hours and minutes (hh:mm). Hint: produce your total as soon as a new phone number is encountered, don't try to store the entire input.

Examples

Input Output 

0291234567,02/02/1999,07:30:00,07:45:00

0293854329,02/02/1999,09:12:00,09:16:30

0293854329,02/02/1999,17:10:30,17:11:00

0296650000,02/02/1999,09:05:00,09:08:30

0296650000,02/02/1999,10:12:00,10:15:00

0296650000,02/02/1999,11:07:30,11:08:30

0296650000,02/02/1999,12:05:45,12:09:00

0000000000



0291234567 15:00

0293854329 05:00

0296650000 10:45

Extension

For an extra 5 points, modify your program to deal with overlapping calls, that is, to detect the situation where one call starts before the previous one has finished (such things are possible with some phones, but it might also indicate an error in Car-Tel's billing system).

Constraints

Assume that no call lasts more than 24 hours (so if the ending time is greater than the starting time the call must have ended on the same day the call started, otherwise on the following day.

There is no limit on the number of input lines.

You may may assume the input is of the correct format.

Task 6 - Ascii Spiral

Description

Write a program that draws a triangular spiral using only the ascii characters '/' (slash), '\' (backslash), '_' (underscore), '(' (left parenthesis), ')' (right parenthesis) and ' ' (space).

The program should read the length of the first side of the spiral and then draw sides until the spiral reaches "the middle" (a point where no further characters can be drawn that are not adjacent to or that cover some existing character).

This task is worth 15 points.

Examples

InputOutput 

1




/



3




  /\

 /  \

/ (__)



6




     /\

    /  \

   / /\ \

  / /  \ \

 / / (__) \

/ (________)



8




       /\

      /  \

     / /\ \

    / /  \ \

   / / /\ \ \

  / / / _) \ \

 / / (______) \

/ (____________)

Constraints

You may assume that the length of the first side will never be larger than 38 (so that the figure will always fit nicely on a 24x80 screen).