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).
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.
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/18
If 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> 1111
Using the above code we get 42 bits (symbols 0 or 1)
100010100101101100011010100100000111001111
Supposing 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> 1111
doesn'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:
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.
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
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:
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.