University of Kentucky Students Programming Contest

UKSPC'99 - Upper Division

October 9, 1999

Individual work only. Use of tools other than program editors, compilers, calculators, and submit program are prohibited. Books and notes can be used but no materials in electronic format can be used, except for online software manuals.

Grading is based on the total time for the correctly solved problems plus the penalty for incorrect submissions of the problems that finally have been submitted and graded as correct. Because of penalties for incorrect solutions, verify your output comparing it to the sample inputs (spaces, lower/upper cases, sorting, etc.) Test your solutions on your a variety of data. The judges will use their own tests that will verify correctness of your solutions. Boundary conditions, various sizes, etc. will be tested.

The judges decision is final.

The style of the program is not graded. Comments are not required. In the first line of your program put your name and your assigned number.

 

Output of each program goes to the standard file (screen). Input for  programs is taken from files named prob1.dat, prob2.dat, prob3.dat, prob4.dat, prob5.dat, prob6.dat,  and prob7.dat respectively.

There are seven problems in this set.




1) Rivers are meeting

A digital river is a sequence of numbers where the number following n  is n plus the sum of its digits.
 For example, 12345 is followed by 12360, since 1+2+3+4+5 = 15. If the first number of a digital river 
is k , we will call it river k. The next number in this sequence is 12372 (= 12360 + 1 + 2 + 3 + 6 +0)
Normal streams and rivers can meet,and the same is true for digital rivers. This happens when two digital
rivers share some of the same values. For example: river 480 meets river 483 at 519, meets river 507 at 507, and never meets river 481.
It can be proven that every digital river will eventually meet river 1, river 3 or river 9. 
Write a program which inputs a single integer n (1<=n<=16384), and outputs the value where river n
first meets one of these three rivers.

Input Format

The first line of the input a single integer n (1<=n<=16384).

Example

Input:

86

Output:

River 86 first meets river 1 at 101

Input:

900

Output:

River 900 first meets river 9 at 909


2) Wetlands of Florida

A construction company owns a large piece of real estate within the state of Florida. Recently, the company decided to develop this property.
Upon inspection of the property, however, it was revealed that the land, at various locations, contained bodies of water. This came as a shock to the owners of the company, for they were from out of state and not familiar with wetlands of Florida. The situation was very grave and the owners not knowing that such bodies of water can be converted to beautiful lakes that will increase the value of the land around them, were about to abandon the construction project. Fortunately, this fact was brought to the owners' attention by a smart UK graduate who worked for the company and consequently the construction project started.

The engineers divided the construction site by a grid into uniform square cells such that each square cell entirely contained either water or land. (How they did it, of course, is anybody's guess.) Now, the question that the engineers are to answer is the following: ``Given the row and column number of a grid cell that contains water, what is the area of the lake containing that cell.'' (an area is measured by number of grid cells it contains.)

You are to write a program to answer this question!

The input consists of 0 < n <= 99 lines each containing 0 < m <= 99 character long sequence of ``L''s and ``W''s followed by k > 0 lines each containing a pair of integers i and j. The first n lines will represent the n by m grid covering the land where a ``W''/``L'' at the c. character of the r. line indicates water/land within the cell at row r and column c of the grid. The pairs of integers on the last k lines, each represent the row and column numbers of some grid cell that
contains water. The output for each pair of integers, i and j, on the last k lines of input, consists of an integer,on a separate line, indicating the area of the lake containing the grid cell, at row i and column j of the grid.

Sample input:
LLLLLLLLL
LLWWLLWLL
LWWLLLLLL
LWWWLWWLL
LLLWWWLLL
LLLLLLLLL
LLLWWLLWL
LLLLWLLLL
LLLLLLLLL

3 2
7 5
0 0

Sample output:
12
3


 

3) Arithmetic Progressions

An arithmetic progression is of the form a, a+b, a+2b....., a+nb where n=0,1,2,3...Assume that a and b are non-negative integers (0,1,2,3,....).

Write a program that finds all arithmetic progressions of length n in the set S of bisquares. The set of bisquares is defined as the set of all integers of the form p^2 + q^2 (where p and q are non-negative integers). As input, your program should accept the length of progressions N to search for and an upper bound M to limit the search to the bisquares in the range from 0 to M. Each line of the input file prob3.dat contains N M. Assume M <=10,000.

Input Format:
 8 200
10 100

Output Format
Arithmetic progressions of length 8
taken from bisquares within the range
from 0 to 200:

Difference of 12:
1  13 25 37 49 61 73  85
13 25 37 49 61 73 85  97
25 37 49 61 73 85 97  109
37 49 61 73 85 97 109 121

Difference of 24:
1  25 49 73 97  121 145 169
2  26 50 74 98  122 146 170
25 49 73 97 121 145 169 193
26 50 74 98 122 146 170 194

There are 8 progressions.


Arithmetic progressions of length 10
taken from bisquares within the range
from 0 to 1000:

Difference of 12:
1  13 25 37 49 61 73 85 97  109
13 25 37 49 61 73 85 97 109 121

Difference of 24:
2   26  50  74  98  122 146 170 194 218
26  50  74  98  122 146 170 194 218 242
101 125 149 173 197 221 245 269 293 317
761 785 809 833 857 881 905 929 953 977

Difference of 36:
421 457 493 529 565 601 637 673 709 745

Difference of 48:
4   52  100 148 196 244 292 340 388 436
52  100 148 196 244 292 340 388 436 484
202 250 298 346 394 442 490 538 586 634

Difference of 60:
5  65  125 185 245 305 365 425 485 545
65 125 185 245 305 365 425 485 545 605

Difference of 72:
29 101 173 245 317 389 461 533 605 677

Difference of 84:
29  113 197 281 365 449 533 617 701 785
37  121 205 289 373 457 541 625 709 793
73  157 241 325 409 493 577 661 745 829
121 205 289 373 457 541 625 709 793 877
205 289 373 457 541 625 709 793 877 961

Difference of 96:
8   104 200 296 392 488 584 680 776 872
104 200 296 392 488 584 680 776 872 968

Difference of 108:
9 117 225 333 441 549 657 765 873 981

There are 21 progressions.


4) Detecting Deadlock

In a computer system, a deadlock occurs when a group of two or more programs are all blocked waiting for resources (e.g. disks, tape drives) that another member of the group is using. When a group of programs deadlock, no program in the group can make forward progress. Write a program to detect when a system contains a deadlock. Note: just because a request made by a program can't immediately be satisfied, it does not mean the system is deadlocked (see Example 1).

Input Format

The input to the program consists of requests by programs to either acquire or release a resource. Each line will contain three values (each separated by a single space), an integer indicating the identity of the program making the request, a character indicating if the request is to acquire or release the resource (`a' or `r' respectively), and a string for the name of the resource.

Assumptions

  1. All program identifiers are less than 100, strings are less than 10 characters, and only an `a' or a `r' will be the request.
  2. There will be less than 100 resources.
  3. A program number -1 will indicate the end of the input file.
  4. Two requests for the same resource must be satisfied in the order received.
  5. there is only one instance of each resource.

 

Output Format

When a deadlock is detected, your program should print the programs that are deadlocked. The list of programs involved in the deadlock should be sorted in increasing order of program identifier. Your program should terminate when a deadlock is found (and not read any additional input). If the end of input is reached, and no deadlock has been detected, your program should print "No deadlocks found". If an error is found (such as a program trying to acquire a resource it already has), your program should print "Input Error" and terminate.

Example 1

Input:

1 a disk
2 a disk
1 r disk
2 r disk
-1 a empty

Output:

No deadlocks found

Example 2

Input:

3 a mouse
1 a disk
2 a tape
1 a tape
2 a disk
-1 r empty

Output:

Deadlock detected: 1 2

5) Finding Anagrams



An anagram is a word or phrase formed by rearranging the letters of another word or phrase. For example, "carthorse" is an anagram of "orchestra". Blanks within a phrase are ignores in forming anagrams. Thus, "orchestra" and "horse cart" are also anagrams.
Write a program that reads a list of phrases and prints all pairs of anagrams occurring in the list.


Input: Input will consist of from 1 to 100 lines. A completely empty or blank line signals the end of input. Each line constitutes one phrase.


Output: Some number of lines (including possibly 0 if there are no anagrams in the list), each line containing two anagrammatic phrases separated by ' = '.

(Each anagram pair should be printed exactly once, but the order of the two phrases within a printed pair is irrelevant.)


Sample input: (begins in the first line)

carthorse
horse
horse cart
i do not know u
ok i now donut
orchestra

the output could be:

carthorse = orchestra
carthorse = horse cart
horse cart = orchestra
i do not know u = ok i now donut


6) Alphametics (Cryptarithms)



An alphametic is an arithmetic expression where the numbers have been replaced by letters. Each number is  replaced by the same letter throughout the expression, and no letter 
is used to represent more than one number. Furthermore, the leftmost digit of any number is not allowed to be a zero. Given an alphametic,  the problem is to reconstruct the original. 

The classic puzzle is SEND + MORE = MONEY.  The only solution to this problem is 9567 + 1085 = 10652.  The restriction on the leftmost digit is important. It means, 
for example, that 8542 + 0915 = 09457 is not a valid solution.

Write a program which solves addition alphametics.  Your program should accept 3 lines. Each line contains a word of no more than 5 characters.  The alphametic to be solved is the sum of the first two words,  to total the final word. 

Sample Input:
SEND
MORE
MONEY

Output:
9567 + 1085 = 10652


Your output should consist of an example solution if you believe there to be one, or the word 'Impossible' if you do not. 


7) From Shakespeare

Romeo and Juliet are in love. However, their families forbid them  to meet each other and Juliet wants to see Romeo so much. Luckily, she is allowed to go to sing to a choir on Sunday afternoons.  She leaves her home exactly at four o'clock and she must use one 
of the shortest paths to the church. Similarly Romeo plays football at  a nearby football stadium every Sunday. He also leaves his home at four o'clock and must also follow a shortest path. 

Every Sunday Juliet hopes that going to church she will suddenly meet Romeo hurrying to the football. However, it has not happened so far  and Juliet does not know whether it is possible at all. 

Input specification:

The input file consists of several data blocks. Each data block describes one town. 

The first line of a data block contains two numbers N and M, where N  is the number of junctions and M is the number of streets in the town. Junctions are numbered by numbers from 1 to N. Every street connects exactly two junctions. On the second line there are four numbers JS,  JG, RS, RG. Juliet lives on the junction JS, the church is 
at the junction JG, Romeo's home is at the junction RS and  the football stadium is at the junction RG. 

Each of the next M lines contains three integers A, B and T  describing one street, where A and B are numbers of junctions  connected by this street and T is the time in minutes necessary  to walk from A to B or from B to A using this street. Suppose that  it is possible to go from each junction to any other junction using  the streets. 

After the last block there is a single line with the number -1. 

Output specification:

Your task is to determine for each data block whether there is a path for Romeo and a path for Juliet such that  they will meet at some junction. Note, that each of them can use only 
a shortest path but there may be several such paths for each of them. Both Romeo and Juliet start at the same time. They meet at a junction only if they arrive there at the same time. If they cannot meet,  output -1. If they can meet, output the time in minutes from 4  o'clock to the first possible meeting of Romeo and Juliet. 

Example
Input file: 

7 9 
1 4 7 6 
1 2 10
2 3 10
3 4 10
4 5 15
5 1 15
1 6 10
2 7 5
5 7 15
5 6 10
2 1
1 2 2 1
1 2 10
-1

Output file:
15
-1