Send your solutions on or before January 7th 1998.
The revolution started in the country whose name we will not mention here. The old bad chief Bubutu Sese Kosa was removed and young Tekila was apointed into his function. The new chief promised to replace all old (and bad) laws with new (and better) ones. Tekila kept declaring new laws and removing old ones until no old laws remained. However, did Tekila really remove all of Bubutu's bad laws? Tekila took the code and started to check all laws to see whether his sign appears under each of them. However, the code is too large. What luck that the code was recently released on CD.
Problem: One page of the code scanned in high resolution (rectangle m x n of zeroes and ones) as well as Tekila's sign (rectangle a x b, a <=m; b <= n) are given. Your task is to write a program which will determine whether the sign is located on the page or not (i.e. whether it can be shifted so that it will match exactly some region of the page).
Example:
Input:
m = 5; n = 4; a= 3; b = 3
Sign:
111 010 010
Page of the code:
11001 00111 10010 00010
Output:
Yes, the sign is located on the page (top left corner is located on
coordinates 3,1).
Santo and Banto decided to use their gold mining experience in a surprising way. In their old age they decided to become guides in mines which were excavated by many gold miners on Vysna Klondika. A gold mine consists of chambers (where gold was mined before) which are connected by corridors. No two corridors cross (if two corridors did cross then there would be collisions of cars loaded with gold on the crossing).
Some chambers (so called outer chambers) connected by corridors form the outer circle. Each of the outer chambers is connected exactly with two other outer chambers by a corridor. All other chambers are called inner chambers. They are located inside the outer circle. There is only one entrance to the mine located in one of the outer chambers. From each chamber there are exactly three corridors to three other different chambers (i.e. from each outer chamber there is exactly one corridor to an inner chamber). Between any two chambers in the mine there is exactly one path connecting them if we do not use corridors of the outer circle and passing each chamber at most once.
Santo and Banto want to prepare a tour for visitors of the mine. During the tour visitors will pass each chamber exactly once. Because one tour will become boring for visitors in a short time they want to have prepared several of them. For this reason they want to know how many such tours exist.
Problem: Write program which reads n (number of chambers in the mine), k (number of outer chambers 3<= k<n <= 1000) and list of 3n/2 corridors connecting chambers and determine number of tours through the mine. Chambers are numbered 1...n, chambers 1...j are outer chambers and chamber number one is the entrance to the mine. Each tour starts and ends in the chamber number one. Two tours which differ only with respect to direction are also different.
Example:
For the mine shown in the picture there are 6 tours:
1, 5, 4, 6, 8, 7, 2, 3 (and back to 1),
1, 8, 6, 5, 4, 2, 7, 3,
1, 5, 6, 4, 2, 3, 7, 8
plus each of them in oposite direction.
As usual Brutus and Frutus were bored at the lecture also today. Since they had no good magazine or book and they did not want to play tic-tac-toe again they started to play a new game. The cars game is played on paper with a grid of squares on which a race track is drawn. Each of the players has one car placed in the starting point at the beginning. A goal of the game is to reach the finish point with the car in as few moves as you can. In each move the car changes its position by its velocity vector which the player can change beforehand by -1, 0 or 1 in both directions (x and y). Cars cannot cross the border of the race track, i.e. the velocity vector cannot pass through any point outside the track. At the beginning the car is stationary, at the end the car can have any velocity. After Frutus won for the third time, Brutus decided to ask for your help (so that he need not knock out any more of Frutus' teeth).
Problem: Write a program which for a given race track outputs the minimum number of moves in which the car can reach the finish point from the starting point. The race track is given as follows: M, N - size of the grid, N rows with M characters on each represent the track itself ('O' means place inside the track, 'X' place outside the track) and coordinates of the starting and the finish point.
Example:
Input: M=14, N=14
XXXXXXXXXXXXXX XOOOOOXXXXXXXX XOOOOOOXXXXXXX XOOOOOOOOXXXXX XOOOXOOOOOOXXX XOOOXXOOOOOOOO XOOOOXXOOOOOOO XXOOOXXXXXXXXX XXOOOXXXXXXXXX XXOOOXXXXXXXXX XXOOOXXXXXXXXX XXOOOXXXXXXXXX XXOOOXXXXXXXXX XXXXXXXXXXXXXX
Starting point: (3,13) Finish point: (14,6)
Output:
It is possible to reach the finish point in 9 moves.
Oil was discovered on the Legoland plateau. The greedy Lewings sank several holes immediately. As soon as they found out that they need no more holes to pump the oil field dry they decided to fence the plot in. The Legoland plateau is divided into squares of the same size. Each of the squares have one special point - its centre. In Legoland the price of the plot is determined by number of special points inside the plot. Lewings would like to pay as less as possible - only for squares with holes. Pillars between which the fence is stretched are also located in special points.
Problem: Write a program which reads number n and coordinates of n grid points and determine whether there is such a polygon with vertices in grid points that all of given points and no other grid points are located inside this polygon. If so, output the list of vertex coordinates of any such polygon ordered around the perimeter of the polygon. The perimeter cannot cross any point more than once. If such polygon does not exist output corresponding message.
Note: Grid points are points with integer coordinates.
Example:
Input:
n=6
Grig points:
(1,2),(1,3),(2,4),(2,1),(3,2),(3,3)
Output:
(1,0),(4,2),(3,5),(0,3),(1,1),(2,3),(3,4)
Predefined functions. In addition to the functions + and - the
language cotains also the function p: N x N -> N with following
characteristics:
Using the function p it is possible to encode unambiguously any pair o f non-negative integers into one non-negative integer and for each non-negative integer x>0 there is exactly one pair of non-negative integers which is encoded by p into x. No pair is encoded into the number 0.
Notation: for simplicity we will write expression P(x,y) as x,y. Expression u,v,w means u,(v,w). Operator , has lower priority than + a -. It means that u,v+w is the same as u,(v+w).
Note:Functions with three characteristics mentioned above are called pairing functions. There is an infinite number of such functions. One of them is the Cantor pairing function c(x,y) = (x+y)(x+y+1)/2 + x+1 . Order all pairs of non-negative integers (x,y) by sum x+y and pairs with the same sum order by x. We have the sequence (0,0), (0,1), (1,0), (0,2), (1,1), (2,0), (0,3)... Let c(x,y) be the order of the pair (x,y) in this sequence. It is easy to see that the function c has all the characteristics mentioned.
Lists. The list of number a(1), a(2), ... a(n) is encoded as a(1),a(2),...,a(n),0=p(a(1),p(a(2),p(... p(a(n),0)...))). Each non-negative integer is a code of exactly one list, 0 is a code of the empty list and number x=u,v is a code of the list whose first element is u and v is a code of the list of remaining elements.
Auxiliary variables. In addition to input variables it is also possible to use auxiliary variables in clauses. Values are assigned to auxiliary variables at the time of clause evaluation. Auxiliary variables with value already assigned we call valuated variables. It is possible to use valuated variables in any expression of any clause in the same way as input variables.
Evaluation of clauses. The clause is evaluated as follows: At first values are assigned to input variables. Then the condition of the clause is evaluated from left to right. The condition is of the following form: A1 and A2 and ... and An where Ai can have one of the following forms:
If it was not possible to valuate variables of the clause or some part of the condition was not true then the evaluation is stopped and another clause is used. If the whole condition is true then the expression on the left side of the arrow is evaluated and its value is assigned to the function.
Example: Function Length returns for a given list its length.
Length(x) = 0 & <- & x=0
Length(x) = 1 + Length(v) & <- & x=u,v
Let us explain how the value of the function is determined for the input x = 7,0,0:
Length(7,0,0) = 1+Length(0,0) = 1+(1+Length(0)) = 1+(1+0) = 2
The function was called with the parameter x=7,0,0 so in definition the second clause is satisfied (u=7 and v=0,0 because of the first equation). The evaluation in the second equation is similar (only difference is that u=v=0). In the third equation x=0 is the parameter of the function so the first clause was used. Now all arguments of + function are know so final value can be determined. Therefore the length of the list 7,0,0 is 2.
Task: Write following functions in functional language
Note: Do not forget to include a precise description and proof of your program.
Note 2: If it is possible write your programs using tail recursion. Try to make your solution as efficient (with respect to number of function calls) as you can. However, the most important thing is the correctness of your program.