Write a program for computing the area of the union of a given sequence of rectangles A_1,A_2,...,A_N.

*Example:*

A_1 is given by [1;1],[4;3] A_2 is given by [0;1],[6;2] A_3 is given by [2;1],[3;3] A_4 is given by [7;7],[9;9] The area of the union is 13.

Two neighbour elements are those having a common "side" (e.g. P[2,3] and P[2,4], but not P[2,2], P[3,3]).

Write a program for creating such a permutation of the set M that for no two elements of the permutation their arithmetic mean is situated "inbetween" them.

*Example:*

M={1,2,3,4,5,6} One possible output: {1,5,6,3,2,4}

*Remark:* The element "inbetween" two elements needn't be a neighbour
of any of them.

Write a program that will first read then number N of vertices, some pairs of vertices (i,j), being connected by an edge. Then it will write a sequence of vertices determining how to draw a given picture by a single draw. If the given picture cannot be drawn by a single closed draw then the program has to find it out and announce it. (Be careful, it is case if the picture is not contiguous, as well).

- Find the integer part of the ratio M/N, the shortest periodical part (and its length) and the initial pre-periodical part (and its length) of the fraction part of M/N.
- Solve the problem of 1) if the following limitation is required: The program can use 10 simple integer variables only, no arrays or structured data can be used.

*Example:*

In: M=7, N=12 Out: integer part (0), period (3) of length 1, pre-period (58) of length 2 In: M=125, N=198 Out: integer part (0), period (31) of length 2, pre-period (6) of length 1

Write a program which will determine, for a given element of the sequence, the number of steps necessary for the element to became the leading element the sequence.

*Example:*

1st step 3 4 5 6 7 8 9 10 ... 2nd step 4 5 6 3 7 8 9 10 ... 3rd step 5 6 3 7 4 8 9 10 ... 4th step 6 3 7 4 8 5 9 10 ... Input: 6 Output: the element 6 becomes leading in the 4th step.

Write a program for cutting the remaining part of the chessboard to L-shaped triminoes (pieces consisting of three chessboard fields each, having the shape of the letter "L").

Think about all the values m and [x,y] such that the problem yields a solution, prove your assumption.

*Example:*

Input: n=8 (m=3) [x,y]=[1,4] Output: the solution (drawing)

Write a program modelling for a given N this action until all the soldiers stop turning. Can you find out (and give your reasons) what is the longest possible duration of this action for a given N ?

*Remark:* The result is not specified precisely, it's based on your
imagination and fantasy. The main point in this exercise is to design a solution
being as close as possible to the intuitive idea of a labyrinth.

- For each symbol in some simple message text its frequency in the text is determined (i.e. the ratio of the number of the occurrences of the text to the total number of symbols).
- The symbols used are coded by finite sequences of 0's and 1's, then more frequented symbols having shorter codes.
- The coded messages have to be decodable, hence the authors have decided that a code of a symbol mustn't be a prefix (initial part) of a code of any other symbol.
- Any messages have to be encoded and decoded using the created code table.

*Remark:* For the sample text with 8 different symbols
BACADAEAFABBAAAGAH the frequencies are as follows:

A - 9/18 B - 3/18 C - 1/18 D - 1/18 E - 1/18 F - 1/18 G - 1/18 H - 1/18If a fixed-length code for symbols is used (at least 3 bits in this case) the satisfying 1)--3) of the project is:

A -> 0 B -> 100 C -> 1010 D -> 1011 E -> 1100 F -> 1101 G -> 1110 H 0> 1111Using the above code we get 42 bits (symbols 0 or 1)

100010100101101100011010100100000111001111Supposing the transmitted messages here similar frequencies of occurrences of symbols, about 20% of bits (and consequently of transmission time) can be saved.

Observe that the code

A -> 0 B -> 100 C -> 1001 D -> 1011 E -> 1100 F -> 1101 G -> 1110 H 0> 1111doesn't fulfil the requirements of the project as the codes for 1) and 2) don't fulfil 3).

*Task:* Create a program which for a given sample message builds a
frequency table of the symbols used, assigns to them codes fulfilling 2),3),4)
and then encodes or decodes some further text.

The first i elements are left in the sequence, the next i elements are deleted, the next i elements are left, the next i elements deleted, etc.

The result of the operation is again an infinite sequence (not containing the deleted elements). Now we can define a sequence Q of natural numbers being the results of the following process on infinite sequences:

- Q_0 is the ascending sequence of all natural numbers
- Q_1 is the result of Delete(1,Q_0)
- Q_2 is the result of Delete(2,Q_1)

- Q_i is the result of Delete(i,Q_{i-1})

This process is an infinite one. Nevertheless, one can determine the first K elements of Q for an arbitrary K after a finite number of steps.

Write a program, for generating the first K elements of the sequence Q, for a given K.

*Remark:* The result for K=5 is 1,3,9,25,57. A program will be
considered to be very good if it is able to generate in reasonable time the
first 15 elements of Q.

The workers in the Centre here one task only: to obtain from the received (disturbed) text the most probable message. A message is most probable, if when written cyclically bellow the received text, the number of differences in vertical pairs of symbols is minimal.

- Help the Centre and write down a program which for a given text and a number K>0 will write all the most probable messages of length K (The length of the text needn't be a multiple of K.)
- Find out which interesting thing was discovered by sonde of the planet if
the following text was received:
BLABOLQIALVBPTPVGYWXRKBTAWZXNTCZIAWQFLGBDNPZYKIAWEFHIONIIEYHNSAXH EKSEHVWQDEQDYZDYMABFDYIBCVKCNGTRNBDKZPZCSBHICIZIUNFIUGCKMCFKFQIGUNAEP IRUKYVSEIIFUBCXFMIUHCBTSBVNGBMDNYDVCORXMDNIGHZPRREGCEQRILDMPBPOBOIXFU TEHQNDTDNMNLKEYLSHYZKAFADIAYTAUNVVZEGYQMQXJXVVUTODVKNQCQXCPACAJYVUINK ASNGKTDOVJUDTTISPMYAZXIBBHLLWLEJPGNGXDDXEGOXQOENKHKCAAUJRQYXONFPAPRFJ QNVLCHRIMOVGGZANYUMDAFXEHQLNXVNNGBVBENICHZQGQNBNKQRNNDNERRCGBSHXZLTGM CIHAXFEJXUGFADNGUXVWPYLROEVTFKCWPWGCAVVCPDSOUOKMSMDFHDOHTMYKSPIKDOUNI YZTLECVANUHLCNIERUVNQIRGIOHFRLCLUORICNICGHYJAMNMMUXCJCENUVARWOMRNDYNW PDNAZECWINYXCMMFKGRTSTBTFHISXANBRYOSYNMQHGYBNJZVEKDEUOVDBWZSGOILRPKWD PNQCNIRQUSNIRSKQIOKGTWLAUKHKCMFYYYVIALKALBAYEZAJZUJBWFESQQRACEUEGPWAB BEMXPPHNFGKMZHRHKCWFTQNAONUMNTINLRRSLUIVURCQZFEPVHNKNRTUBRHCNWZWNHMAI GVRNJZWUNRBIWCZENOGWDOQUFIINPSGDLPAMPETWTSEHICQASRPLMUEPWUDKEBMIAMZPZ ZNDHQIMFYPJIFZSBYEMFSMCBEMHNYCSQCMTLRPWVHKHCQEBQMCMOHWWYJBAAIRZTRSEBQ NHHKGFCRHCVBWKJBJFVEECETFIEWGIBYNUYROXRDHDRNESIIBVTSDJKLWRCITCLWMISVQ KCCWJFQZPUTREVKIFSDRDENCNSJAHQCRXWBIINRIFUTNASWBMNVAMGBUCMNDPNCYWBRPE DLCCTABRIPAAKYXDKIQNTJKXZRZDMKBZCYMXXRMVXFIXRSTTVTQQNZBONFKVCLTANHGGC KQOLTSHWSJIWLSNUWISYRJJNAMGWVICZIXBIRNLARBIMDYJWUYYCMGJHMMZQKHHDZCGOO QRDPOEAIRAWGFKCVHONZHNTITOXBWNYFDYJXHZISDWPEDCHIBGSKLFAUIELPHNJKYDINP XYDAIVARCPAAJBEHHWIZOROJTAICMICNDHYXLJDXATEQFCENFRWONHLKUDRTVP

*Linguistic remark:* The word "NIC" means "NOTHING" in Slovak, but
"SEMINAR" is the shortened name of this competition.

You obtain a new number, with which you will repeat the same procedure. After the finite repetition of this procedure we will obtain the numbers 1 or 4.

E.g.: If we start with the number 324

- a_1 = 324
- a_2 = 3.3+2.2+4.4 = 29
- a_3 = 2.2+9.9 = 85
- a_4 = 8.8+5.5 = 89
- a_5 = 8.8+9.9 = 145
- a_6 = 1.1+4.4+5.5 = 42
- a_7 = 4.4+2.2 = 20
- a_8 = 2.2+0.0 = 4 ... end of procedure.

*Task:* Find out the numbers from the interval [1,1000] which, after
the application of the presented procedure, will give the result 1.

More precisely:

- () is a correctly parenthesized expression.
- If the expression X is correctly parenthesized then (X) is a correctly parenthesized expression, too.
- If X,Y are the correctly parenthesized expressions then XY is the correctly parenthesized expression.

*Task:* You dispose of N pairs of the parentheses '(' and ')'. Compose
and write out all correctly parenthesized expressions (length 2.N parentheses).
E.g.: if N=2 then write up (()), ()().

*Remark:* Mind the effectiveness of your algorithm.

Write a program that finds and reports all the numbers that occur in each row. The program should also report if there is no such number.

*Example:* for M=4, N=5 and following matrix P:

2 3 5 7 9 4 6 9 11 13 1 3 7 8 10 3 3 4 8 9Correct answer is "9" because this number occurs in each of the rows.

Print out input values X,E and results, i.e. A and B, respectively.

*Example:*

X = 2.718 E=0.01 (* INPUT *) A = 19 B = 7 (* OUTPUT *)

Test your program using input values X=3.1415926 and E=0.001, E=0.0001 respectively.

Write a program that extracts a subsequence (of length <=N ) of consecutive elements with the maximum possible sum.

*Note:* Try your best to find the fastest algorithm. The problem is
more difficult than one might think at first glance.

Write a program that reads positive integer number N , real number P and a sequence of N real numbers. Program should print the first and last indexes of the required subsequence. The program should also report if there is no such subsequence.

*Note:* "Average of the sequence" equals the sum of the sequence's
elements divided by the number of the elements.

*Example:* Let's take four weights of 1kg, 3kgs, 9kgs and 27kgs
respectively and an object of 5kgs. Obviously, the only solution is the
following:

Place weights of 1kg and 3kg on the side of the scales with the object and place weight of 9kg on the other side.

Design the output of the program in the way shown above. Input for your program are two integer numbers: N (N>0) , the number of weights, and H (0<=H<=3^{N-1}) , the weight of the object.

*Note:* For given N and H (within required range), there is only one
correct solution.

A fraction is reduced if its numerator and denominator are relative primes.

*Example:* For N=7 the output is:

1/7 , 1/6 , 1/5 , 1/4 , 2/7 , 1/3
, 2/5 , 3/7 , 1/2 , 4/7 , 3/5 , 2/3 , 5/7 , 3/4 , 4/5 , 5/6 , 6/7 , 1/1

Write a program which first reads the value N>0 , N pairs of coordinates [x_i,y_i] of the sharp-eyed points and coordinates of the final points [a_x,a_y] , [b_x,b_y] of the fatty line, then it will output the number of pairs of points that cannot see each other because of the fatty line (there is a crossly point of the line connecting the two points with the fatty line).

Don't use any goniometric functions as sin, cos, tan, arctan...

*Example:* If N=8 , K=3 and the original array was [ 1 2 3 4 5 6 7 8 ]
then the new values after the rotation will be [ 6 7 8 1 2 3 4 5 ]

For K=0 all the values will remain in their positions.

For a negative value of K the values will be shifted cyclically in the opposite direction.

Write a program which reads the description of the room floor, and outputs the covering of the floor by bricks or -- a special message, if it is not possible.

The following description of the room floor is recommended: Find a rectangle fully containing the room floor, give the size of the rectangle and then a corresponding matrix containing for each square 0 or 1 depending on whether the square belongs to the room floor or not.

The output has to be a matrix containing in each position a natural number: 0 -- of the square doesn't belong to the room, i (i >= 2) , -- if the square is covered by the brick No (i -1).

*Example 1:* The binary notation of 93 (=1011101_2) is Symmetric, the
notation of 67 (=1000011_2) is not.

*Example 2:* For k=4 the output is '3,5,7,9,15'

*Remark:* Try to make your program as fast as possible.

*Task:* The army unit consist of N soldiers numbered by numbers
1,2,... N . There are given K pairs [commander_i, subordinees_i] (i=1,2,...,K) .
Write a program for ordering the soldiers to a queue such that the above rule is
fulfilled. If it is not possible the program has to find it out and report it.

*Example*

N=6, K=5, commander: 1 4 2 1 2 subordinee: 5 5 3 3 4 Output: 1 2 4 6 3 5 or 6 2 1 4 5 3.

*Remark:* One solution is sufficient.

*Remark:* Convex hull of a set A is the least convex set containing A.

Contact me at perivamsi@yahoo.com

Last Updated: September 20, 2002 .