KöMaL Problems in Informatics, March 2005
Please read the rules of the competition.
Show/hide problems of signs:
Problems with sign 'I'Deadline expired on April 15, 2005. |
I. 100. We are given a square lattice of size mxn (with positive integers m and n). Unit square based columns are put onto each square. The front and side views of this bar chart-like solid are represented by the vectors u=(u_{1}, u_{2}, ..., u_{m}) and v=(v_{1}, v_{2}, ..., v_{n}), where the numbers u_{i} and v_{j} are the heights of the rectangles being shadows of the columns.
Prepare a sheet into which coordinates of vectors u and v can be entered, then it computes the matrix describing heights of the columns of the (or, a possible) solid of maximal volume. Your program should recognize with writing ``Error!'' (see the diagram,), if no such solid exists.
v_{1} | v_{2} | v_{3} | v_{4} | v_{5} | ... | ... | ... | v_{n} | |||||
Error! | * | * | |||||||||||
u_{1} | |||||||||||||
u_{2} | * | ||||||||||||
... | |||||||||||||
u_{m} |
Notice that this is a converse of problem I. 98., where a matrix describing the heights of the individual columns was given and we had to display the front and side views of the solid. Now we have to reconstruct the solid of maximal volume from the front and side views.
A text file (i100.txt) is to be submitted containing the precise description of the applied algorithm, further, the detailed justification of the fact that your algorithm gives the correct answer in all cases (that is, whether or not the solid exists, and, if it does, the algorithm produces the one with the required property. Finally, the sheet itself (i100.xls, ...) is also to be submitted.
(15 pont)
I. 101. Determine the number of ways of writing a positive integer n as a sum of positive integers without regard to order. (For example, there are 7 possibilities to decompose ``five'': 5=4+1=3+2=3+1+1=2+2+1=2+1+1+1=1+1+1+1+1, where ``5'' itself is also allowed as a sum with one term.)
Write your program (i101.pas, ...) whose input is a positive integer n, then it displays the different decompositions of n as well as the number of these decompositions.
The program should be submitted. Notice that there are similarities but also differences between the current problem and problem I. 87.
(10 pont)
I. 102. Write a program (i102.pas, ...) to decide whether a matrix with integer entries has at least one prime number in each of its rows.
The first line of the input will contain two positive integers, m and n, the dimensions of the first matrix, separated by a space, then the entries of the matrix will follow in m lines, each line containing n positive integers separated by spaces. Then either an end of input mark will be entered (two 0's separated by a space), or the description of another matrix in a similar format.
Your program should be submitted.
(10 pont)
Problems with sign 'S'Deadline expired on April 15, 2005. |
S. 7. Given a set of words, each of length between 5 and 30 letters. Write a program to sort them such that the last 5 letters of each word matches the first 5 letters of the next one. The number of words is at most 10,000 and only the 26 lower case letters of the English alphabet are used.
The first line of the input contains the number of words; then each subsequent line contains one word. If there exists a proper sorting, write one to the output such that each line contains one word. If there is no solution, just display NO SOLUTION.
(10 pont)
$Var(Body)
Upload your solutions above