|
Department of Computer Science, CTU FEE
& Czech ACM Chapter
CTU FEE Local Programming Contest 1998
PSOS Political Party
Several new political parties have appered in our country due to the
next election to come. PSOS (Programmers for Stable Operating
Systems) are one of that parties. They are going to attract people
not only with their promises. The main point of Election Programme can be
easily found from the name of the Party. But it would be very incorrect, if
someone should say it is the only point.
PSOS want to get as many votes as possible, of course. Because of that
they decided to use computers during the campaign. They have bought the
very fast computer which has been optimized for computations during the
election campaign. The main problem is with the software. Because of strict
security requirements, none of the large (and known) companies could be
contacted. That is the main reason that you are to write all the required
software. Your goal is to create a set of programs that help PSOS to win the
election.
We wish you good luck with your mission.
Metric Time (Metricky cas)
(file name: cas.c, cas.p, cas.C)
The Metric Time is one of the most important points of PSOS Election
Programme. The Time can be much easier calculated in operating systems.
These systems are then more stable, which meets the main goal of the Party.
The length of one day is the same as with the "classic" time. The day is
divided into 10 metric hours, each of them into 100 metric minutes,
and each minute into 100 metric seconds. 10 metric days form one metric
week, 10 metric weeks give one metric month, 10 metric months are called
metric year. It is obvious this Metric Time is much better than the classic
one.
Some opponent parties often complain that the Metric Time has also some
drawbacks. First of all, it would be very difficult to change to the new
time. PSOS Chairman decided to solve these problems all at once. He plans to
publish a freeware utility which will be able to convert between the time
formats. Your goal is to write one half of this utility, the program which
converts classic time to Metric Time. Metric hours, metric minutes, and
metric seconds are counted starting with zero, as usual. Metric days and
metric months start with one. There exist metric year zero. The metric
seconds should be rounded to the nearest smaller integer value. Assume that
0:0:0 1.1.2000 classic time is equal to 0:0:0 1.1.0 Metric Time.
Note that the classic year is leap, if it is an integer multiple of 4.
The only exception are years divisible by 100 - they are leap only if they
are an integer multiple of 400. For example, leap years are 1996, 2400, and
2000; leap years are not 1900, 2300, 2002.
Input Specification
At the first line there is a positive integer N stating the
number of assignments to follow. Each assignment consists of exactly one
line in the form "hour:minute:second
day.month.year" which is the date in
the classic form (usual in most of European countries). The date is always
valid, 2000 <= year <= 50000.
Output Specification
The program must print exactly one line for each assignment. The line
should have the form "mhour:mmin:msec
mday.mmonth.myear" which is the Metric
Time equal to the specified classic time.
Sample Input
7
0:0:0 1.1.2000
10:10:10 1.3.2001
0:12:13 1.3.2400
23:59:59 31.12.2001
0:0:1 20.7.7478
0:20:20 21.7.7478
15:54:44 2.10.20749
Output for Sample Input
0:0:0 1.1.0
4:23:72 26.5.0
0:8:48 58.2.146
9:99:98 31.8.0
0:0:1 100.10.2000
0:14:12 1.1.2001
6:63:0 7.3.6848
Photograph (Foto)
(file name: foto.c, foto.p, foto.C)
The election campaign just started, so PSOS decided to make some
propagation. One of the representatives came with a great idea - he proposes
to make an photography of their Parliament Club. Unfortunatelly, even after
many briefings, the representatives are still not able to agree upon an
ordering of people in the photography. Moreover, there are a lot of
representatives and it is not possible to have all of them in a single
picture. The situation became critical. In the end, the representatives
decided they will make one photo of every possible combination of people
and their ordering. Different photographs will be used for a large number of
billboards PSOS plan to use. To make things more clear, every person gets
a Unique Identification Number (UIN). Every picture can be then
described as the succession of several UINs x1,
x2, ... xk, in whichxi is
UIN of the i-th person in the picture x. Now we can
sort all the possible photographs (combinations) to a single succession.
The ordering of combinations of the same length (photographs with the
same number of people in it) is defined as follows: the combination
p is greater than the combination q if there exists
any i such as that pj = qj for
every j < i, and pi > qi.
Your goal is to find the right place for a given picture among all possible
photographs.
Input Specification
At the first line there is a positive integer N stating the
number of assignments to follow. Each assignment consists of exactly two
lines. At the first line of each assignment, there are two integers
n and k, 1 <= k <= n <= 12 stating
the total number of representatives (n) and the number of them
which can fit into a single picture (k). At the second line of
the assignment, there is exactly k positive numbers
x1, x2, ... xk, each of them
1 <= xi <= n. No number can appear more than
once on this line.
Output Specification
For each assignment, output the text "Variace cislo I ma
poradove cislo J." (Combination #I is
J-th in sequence). Fill the number of assignment instead of
I (starting with one), and the number of the given photograph
among all possible combinations after ordering, instead of J
(also starting with one).
Sample Input
4
1 1
1
5 1
4
3 3
1 2 3
5 3
5 3 1
Output for Sample Input
Variace cislo 1 ma poradove cislo 1.
Variace cislo 2 ma poradove cislo 4.
Variace cislo 3 ma poradove cislo 1.
Variace cislo 4 ma poradove cislo 55.
Cavern (Jeskyne)
(file name: jeskyne.c, jeskyne.p,
jeskyne.C)
A large system of caverns was discovered some time ago. PSOS know about
it and they promised to make these caverns accessible for tourists. PSOS
think it could add some more votes for the Party.
Unfortunatelly, there is a big problem. The members did not notice that
the caverns are completely flooded by water. Because PSOS want to be modest
and they do not want to break their promises, they started to think about
the solution in case they really would win the election. One of the most
interesting proposals involved even little submarines. But it seems as the
best solution, to exhaust the water out of the cavern. The caverns are very
well examined, that means it is exactly known where the water is. PSOS would
like to know how much water they have to pump out, so they need a computer
program that will be able to determine this.
All the cavern space consists of equal cubes, their size is 1 meter.
Obviously, it is possible to exhaust water from a continous space only, e.g.
the space consisting of neighbouring cubes. Moreover, only the space running
to the top layer of cubes may be exhausted. Two cubes are considered
neighbouring if they have one common side, not only the edge.
Input Specification
At the first line there is a positive integer N stating the
number of assignments to follow. Each assignment begins with three integer
numbers X, Y, Z on a single line,
separated by spaces. 1 <= X,Y,Z <= 100. All the flooded
cubes are inside a box with the size
X, Y, and Z meters. All cubes outside
this box are filled with rock. After the first
line, the description of Z layers follows, starting from the top
one. Each layer begins with a line with a single integer number
P that denotes the number of flooded cubes in that layer. Then
P lines follow, each of them consisting of two integer numbers
R and S, 1 <= R <= X,
1 <= S <= Y. These number are coordinates of one flooded
cube, given in meters.
Output Specification
Output a single line for each assignment. The line must contain the
sentence "Je nutne vycerpat X litru vody."
(X litres of water must be exhausted). Fill the right
ammount of litres of water, instead of X. It should include all
the water that is accessible from the top layer of the cavern.
Sample Input
2
4 4 5
1
3 3
2
1 2
3 3
4
1 2
2 2
2 3
3 3
2
3 3
1 1
0
3 7 2
1
2 4
5
1 4
2 3
2 4
2 5
3 4
Output for Sample Input
Je nutne vycerpat 8000 litru vody.
Je nutne vycerpat 6000 litru vody.
Code (Kod)
(file name: kod.c, kod.p, kod.C)
The important thing is also the fact, where the representatives sit in
the Parliament. Some of them prefer front rows because of more light, some
prefer back rows because of less light and more silence. The others want to
sit by the window. Moreover, the sitting order must be kept absolutely
secret, because the neighbouring representatives may influence each other.
Since we do not want to have corruption in the Parliament, it was decided to
use Hyper-secret Code to encrypt the numbers of seats. The Hyper-secret Code
of length n is designated SK(n) and consists of all
possible binary strings of length n. That means it always has
2n elements. The Code is generated using the following
recursive algorithm:
- SK(1) = [0, 1]
- SK(n) = 0.SK(n-1) + 1.REV{SK(n-1)}
in which
- [0, 1] is succession of two binary strings of length one.
The first of them is "0" and the second is "1".
- b.SK(x) is the code created from SK(x) such
that the binary digit b is prepended to the beginning of each
string in succession SK(x).
- REV{SK(x)} is the reverse succession to SK(x),
it means the first string becomes the last one.
Note that the ordering of whole strings is reversed, not the ordering
of digits inside the string.
- X + Y is the concatenation of successions X and
Y.
Every seat in the Parliament has its own number. The numbers make a
continuos succession beginning with one. The Hyper-secret Code
SK(n) is generated (using the above algorithm) for greater and
greater n, until the length of the Code (the number of binary
strings that form the succession) is greater or equal to the highest number
of seat. Every seat s is then given the binary string that
appears at the s-th possition in the succession SK(n).
Every representative then gets the Code of his seat and nobody can determine
who is going to be his neighbour.
But the problem appears when the representative enters the Parliament,
takes the paper with his Code and finds his seat. To solve this, the
Chairman of the Parliament wants the computer program that will be able to
convert any Hyper-secret Code to the appropriate number of a seat. You
propably guess that you are to write this program.
Input Specification
At the first line there is a positive integer N stating the
number of assignments to follow. Each assignment consists of two lines. The
first line contains an integer number k,
1 <= k <= 30. At the second line, there is the Hyper-secret
Code consisting of exactly k characters. Each of the characters
is either 0 or 1.
Output Specification
The program should print the line for each assignment. The line must
contain the sentence "Poslanec P se posadi na sedadlo cislo
S." (The representative #P sits down at the
seat S). Fill the number of the assignment (starting with
one) instead of P, and the right number of a seat instead of
S - it means the possition of the given string in the Code
SK(k).
Sample Input
5
1
0
4
0000
4
1000
4
1111
8
10101010
Output for Sample Input
Poslanec 1 se posadi na sedadlo cislo 1.
Poslanec 2 se posadi na sedadlo cislo 1.
Poslanec 3 se posadi na sedadlo cislo 16.
Poslanec 4 se posadi na sedadlo cislo 11.
Poslanec 5 se posadi na sedadlo cislo 205.
Regions (Okrsky)
(file name: okrsky.c, okrsky.p, okrsky.C)
The new election system was introduced in our republic. The system is
based on a majority of votes in regions. The republic is divided into
M regions, each of them means exactly one seat in the Parliament.
The Chairman of PSOS would like to know how many voters makes the
certainty that PSOS win the election. To win the election means to get more
than one half of Parliament seats. We do not know the exact number of
political Parties participating in election but we can determine the number
of voters in every region. We can assume that all voters will participate in
election and each of them will give his/her vote to one of the candidates.
PSOS have their candidates in all regions. At least one another party has
its candidate in each of the regions. You are to determine the minimum
number of votes which ensures the landslide of PSOS, even in the worst
possible case.
Input Specification
At the first line there is a positive integer N stating the
number of assignments to follow. Each assignment consists of two lines. The
first line contains an integer number M stating the number of
regions. At the second line, there are exactly M numbers
separated by spaces. These numbers state the number of voters in each of
the regions. All the number are possitive and less or equal to 100000.
Output Specification
Print a single line for each assignment. The line must contain the
sentence "H hlasu zajisti strane vitezstvi."
(H votes ensures the win of Party). Instead of
H, fill the minimum number of votes which ensures the win.
Sample Input
3
10
340 260 180 15 1 20 40 90 78 34
2
12 1
6
1 2 3 4 5 6
Output for Sample Input
1003 hlasu zajisti strane vitezstvi.
13 hlasu zajisti strane vitezstvi.
18 hlasu zajisti strane vitezstvi.
Parliament (Parlament)
(file name: parlament.c, parlament.p,
parlament.C)
The representatives have to spend a lot of time in the Parliament. That
is why PSOS want to choose their seats to have the best ones. The special
committee was formed to check all the seats and give a score to each of
them. The more attractive the seat is, the higher is its score. The score
involves the upholstering of chairs, the position of cameras that could take
picture of sleeping representative, e.t.c. It was not easy, but finally,
after many months, the committee put a score to each seat. Unfortunatelly,
it is not possible to take all the best seats. There is also a Security
Committee that decided the representatives must sit all together, in
a rectangular shape. Moreover, the election is still not over and PSOS do
not know how many seats they are going to get. The Party needs a program
that will read the score of each seat and then it will be able to determine
the total score of any rectangular area.
Input Specification
At the first line there is a positive integer N stating the
number of assignments to follow. Each assignment begins with a line
consisting of two integers R and S, separated by
space. R is the number of rows in the Parliament, S is
the number of seats in every row (all rows are of the same size). It is
known that no Parliament can have more than 1000 rows, nor more than 1000
seats in a row. Then R lines follow. Each of them describes one
row of the Parliament, in sequence starting with the first one. Each line
contains exactly S numbers separated by spaces. These numbers are
score values of each seat in the given row, in sequence starting with the
first one. The total score of all seats in the Parliament will always fit
into the standard int or integer type.
Then the line containing the single integer number D follows.
It is the number of queries. Then D lines follow, each
specifying a single query. The query consists of four coordinates separated
by spaces, R1, S1,
R2, S2 (in that order),
1 <= R1 <= R2 <= R <= 1000,
1 <= S1 <= S2 <= S <= 1000.
The coordinates designate that representatives are sitting at the seats
forming a rectangle. The seats are in rows from R1
to R2 (including them) and in each of these row the
seats from S1 to S2 (including
them) are occupied.
Output Specification
Output a single line for each query. The line must contain the sentence
"Absolutni hodnota pohodlnosti je X bodu." (The total
score is X points). Fill the total score instead of
X. The total score is a sum of score values of each seat occupied
by PSOS Party. Print one empty line after each assignment (including the
last one).
Sample Input
2
10 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
5
1 1 1 1
2 2 2 2
1 1 10 10
9 9 10 10
2 2 9 9
1 1
1
1
1 1 1 1
Output for Sample Input
Absolutni hodnota pohodlnosti je 1 bodu.
Absolutni hodnota pohodlnosti je 2 bodu.
Absolutni hodnota pohodlnosti je 550 bodu.
Absolutni hodnota pohodlnosti je 38 bodu.
Absolutni hodnota pohodlnosti je 352 bodu.
Absolutni hodnota pohodlnosti je 1 bodu.
Roulette (Ruleta)
(file name: ruleta.c, ruleta.p, ruleta.C)
The political Party needs some money to lead its campaign. PSOS have
insufficient funds in this time, so they want to earn some money. One of the
new members have designed a completely Electronic Roulette in Monte Carlo
some time ago. During the obligatory Learn-How-to-Say-the-Truth
Course, the member said that the random number generator follows the
equation:
xk+1 =
(A . xk) mod 47
in which xk+1 is the random number following the
previous number xk, and A is the
Constant of the Day that is determined by the director Karl Monte
each morning. PSOS sent several members to Monte Carlo immediately, to get
some money. The problem is that the author of the algorithm suddenly died
during the Course. PSOS now need somebody who is able to break the
algorithm and predict pseudo-random numbers. Given the succession
xt-n, xt-n+1, ...,
xt-1, xt
the program should be able to decide, what the next number
xt+1 will be. The Constant A is always
integer, non-negative, and less then 1000000. All the numbers
xi are integer and non-negative.
Input Specification
At the first line there is a positive integer N stating the
number of assignments to follow. Each assignment consists of exactly two
lines. There is an integer non-negative number M at the first
line of each assignment. The next line contains the succession of exactly
M numbers (x1, x2, ...
xM) separated by spaces.
Output Specification
Output a single line for each assignment. If it is possible to determine
the next number in the succession, the line must contain the sentence
"Vsad na X." (Bet on X). Replace
X with the number which will follow in the succession. If it is
not possible to determine the following number, output the sentence
"Dalsi cislo nelze urcit." (It is not possible to determine the
next number). If the given succession does not follow the above
equation, output the sentence "Algoritmus byl zmenen." (The
algorithm was changed).
Sample Input
3
1
5
3
7 33 28
3
25 26 25
Output for Sample Input
Dalsi cislo nelze urcit.
Vsad na 38.
Algoritmus byl zmenen.
Secretary (Sekretarka)
(file name: sekretarka.c, sekretarka.p,
sekretarka.C)
The basic condition of success of a political party, it is the good
Election Programme. PSOS know about it, so they entrust the top secretary
Juliet with this task. Because she wanted to make her work easier, she used
her charm to talk round her friend Romeo to help her. Romeo is assistent of
another political party and he was writing the programme some time ago.
While writing the Programme for Juliet, he used some parts of his previous
programme. When he gave the finished Programme to Juliet, they recognized
that both programmes are too similar and that someone could notice it. They
need to determine the longest part of text which is common to both
programmes.
Input specification
At the first line there is a positive integer N stating the
number of assignments to follow. Each assignment consists of exactly two
lines of text, each of them contains at most 10000 characters. The
end-of-line character is not considered to be a part of the text.
Output Specification
Print a single line of text for each assignment. The line should contain
the sentence "Nejdelsi spolecny retezec ma delku
X." (The longest common part of text has X
characters). Replace X with the length of the longest common
substring of both texts.
Sample Input
2
Tady nejsou zadni mimozemstani.
Lide tady take nejsou.
Ja do lesa nepojedu.
V sobotu pojedeme na vylet.
Output for Sample Input
Nejdelsi spolecny retezec ma delku 7.
Nejdelsi spolecny retezec ma delku 5.
| 
