Задачи
|
Задачи
|
Задача A (автор - Залецкий П.В.)
Задача B (автор - Фролов Е.С.)
Задача C (автор - Штыков Е.А.)
Задача D (автор - Залецкий П.В.)
Задача E (автор - Филимоненков Д.О.)
Задача F (автор - Пинаев В.Н. (г. Рыбинск))
Задача G (автор - Филимоненков Д.О.)
Задача H (автор - Залецкий П.В.)
Задача X - пробный тур (автор - Васильев С.Н.)
Problem A. Stars.
Time limit: 6 sec per test.
Astronomers often examine star maps where stars are represented by points on a plane and each star has Cartesian coordinates. Let the level of a star be an amount of the stars that are not higher and not to the right of the given star. Astronomers want to know the distribution of the levels of the stars.
For example, look at the map shown on the figure above. Level of the star number 5 is equal to 3 (it's formed by three stars with a numbers 1, 2 and 4). And the levels of the stars numbered by 2 and 4 are 1. At this map there are only one star of the level 0, two stars of the level 1, one star of the level 2, and one star of the level 3.
You are to write a program that will count the amounts of the stars of each level on a given map.
The first line of the input file contains a number of stars N (1<=N<=15000). The following N lines describe coordinates of stars (two integers X and Y per line separated by a space, 0<=X,Y<=32000). There can be only one star at one point of the plane. Stars are listed in ascending order of Y coordinate. Stars with equal Y coordinates are listed in ascending order of X coordinate.
The output should contain N lines, one number per line. The first line contains amount of stars of the level 0, the second does amount of stars of the level 1 and so on, the last line contains amount of stars of the level N-1.
Input sample.
5
1 1
5 1
7 1
3 3
5 5
Output sample.
1
2
1
1
0
Problem B. Ministry.
Time limit: 5 sec per test.
Mr. F. wants to get a document be signed by a minister. A minister signs a document only if it is approved by his ministry. The ministry is an M-floor building with floors numbered from 1 to M, 1<=M<=100. Each floor has N rooms (1<=N<=500) also numbered from 1 to N. In each room there is one (and only one) official.
A document is approved by the ministry only if it is signed by at least one official from the M-th floor. An official signs a document only if at least one of the following conditions is satisfied:
a. the official works on the 1st floor;
b. the document is signed by the official working in the room with the same number but situated one floor below;
c. the document is signed by an official working in a neighbouring room (rooms are neighbouring if they are situated on the same floor and their numbers differ by one).
Each official collects a fee for signing a document. The fee is a positive integer not exceeding 10^9.
You should find the cheapest way to approve the document.
The first line of an input file contains two integers, separated by space. The first integer M represents the number of floors in the building, and the second integer N represents the number of rooms per floor. Each of the next M lines contains N integers separated with spaces that describe fees (the k-th integer at l-th line is the fee required by the official working in the k-th room at the l-th floor).
You should print the numbers of rooms (one per line) in the order they should be visited to approve the document in the cheapest way. If there are more than one way leading to the cheapest cost you may print an any of them.
Note: You can assume that for each official there always exists a way to get the approval of a document (from the 1st floor to this official inclusively) paying no more than 10^9.
Input sample
3 4
10 10 1 10
2 2 2 10
1 10 10 10
Output sample
3
3
2
1
1
Problem C. Titanic.
Time limit: 5 sec per test.
It is a historical fact that during the legendary voyage of "Titanic" the wireless telegraph machine had delivered 6 warnings about the danger of icebergs. Each of the telegraph messages described the point where an iceberg had been noticed. The first five warnings were transferred to the captain of the ship. The sixth one came late at night and a telegraph operator did not notice that the coordinates mentioned were very close to the current ship's position.
Write a program that will warn the operator about the danger of icebergs!
The input messages are of the following format:
Message #<n>.
===
Received at <HH>:<MM>:<SS>.
Current ship's coordinates are
<X1>^<X2>'<X3>" <NL/SL>
and <Y1>^<Y2>'<Y3>" <EL/WL>.
An iceberg was noticed at
<A1>^<A2>'<A3>" <NL/SL>
and <B1>^<B2>'<B3>" <EL/WL>.
Here
The distance to the iceberg: <s> miles.
Where <s> should be the distance between the ship
and the iceberg, (that is the length of the shortest path on the
sphere between the ship and the iceberg). This distance should
be printed up to (and correct to) two decimal digits.
If this distance is less than (but not equal to!) 100 miles the
program should print one more line with the text:
DANGER! For simplicity of calculations assume that the
Earth is an ideal sphere with the diameter of 6875 miles completely
covered with water. Also you can be sure that lines in the input file
break exactly as it is shown in the input samples. The ranges of the
ship and the iceberg coordinates are the same as the usual range for
geographical coordinates, i.e. from 0 to 90 degrees inclusively
for NL/SL and from 0 to 180 degrees inclusively for EL/WL.
Input sample.
Message #513.
Output sample.
The distance to the iceberg: 52.04 miles.
Problem D. Railway tickets. Time limit: 5 sec per test.
The railway line УEkaterinburg-SverdlovskФ with several stations has been built. This railway line can be represented as a line segment, railway stations being points on it. The railway line starts at the station УEkaterinburgФ and finishes at the station УSverdlovskФ, so stations are numbered starting from УEkaterinburgФ (it has number 1) and УSverdlovskФ is the last station.
Cost of the ticket between any two stations depends only on a distance between them. The prices for the tickets are specified in the following table.
distance between stations - X price for the ticket 0<X<=L1 C1 L1<X<=L2 C2 L2<X<=L3 C3 Direct tickets from one station to another can be booked if and only if the distance between these station does not exceed L3. So sometimes it is necessary to book several tickets to pay for the parts of the whole way between stations.
For example, on the railway line shown at the figure above there are seven stations. The direct ticket from the second station to the sixth one can not be booked. There are several ways to pay for the travel between these stations. One of them is to book two tickets: one ticket at price C2 to travel between the second and the third stations, and other at price C3 to travel between the third and the sixth stations. Note, that though the distance between the second and the sixth stations is equal to 2*L2, the whole travel can not be paid by booking two tickets at price C2, because each ticket is valid for only one travel and each travel should start and end only at stations.
Your task is to write a program, that will find the minimal cost of the travel between two given stations.
The first line of the input file contains 6 integers L1, L2, L3, C1, C2, C3 (1 <= L1 < L2 < L3 <= 10^9, Program should print to the output file the only number, which is the minimal travel cost between two given stations.
Input sample.
3 6 8 20 30 40 Output sample.
70
Problem E. Find a multiple. Time limit: 5 sec per test.
The input file contains N natural (i.e. positive integer)
numbers ( N <= 10^6 ). Each of that numbers in not greater than 15000. This numbers are not
necessarily different (so it may happen that two or more of them will be
equal). Your task is to choose a few of given
numbers ( 1 <= few <= N ) so that the sum of chosen
numbers is multiple for N (i.e. N = k*(sum of chosen numbers)
for some natural number k). The input file contains N natural (i.e. positive integer) numbers ( N <= 10^6 ). Each of that numbers in not greater than 15000. This numbers are not necessarily different (so it may happen that two or more of them will be equal). Your task is to choose a few of given numbers ( 1 <= few <= N ) so that the sum of chosen numbers is multiple for N (i.e. N * k = (sum of chosen numbers) for some natural number k).
The first line of the input file contains the single number N. Each of
next N lines contains one number from the given set.
In case your program decides that the target set of numbers can not
be found it should print
to the output file the single number 0. Otherwise it should print the number
of the chosen numbers in the first line followed by the chosen numbers
themselves (on a separate line each) in arbitrary order.
If there are more than one set of numbers with required properties you
should print to the output file only one (preferably your favorite) of them.
Input sample.
5 Output sample.
2 Problem F. Labyrinth. Time limit: 5 sec per test.
Administration of the labyrinth has decided to start a new season with new
wallpapers. For this purpose they need a program to calculate the square of
the walls inside the labyrinth. This job is just for you!
The labyrinth is represented by a matrix
N*N (3 <= N <= 33, you see, ‘3’ is a magic digit!).
Some matrix cells contain a dot character (‘.’) that denotes an empty square.
Other cells contain a diesis character (‘#’) that denotes a square filled by
monolith block of stone wall. All squares are of the same size 3*3 meters.
The walls are constructed around the labyrinth (except for the upper left
and lower right corners, which are used as entrances) and on the cells with a
diesis character. No other walls are constructed. There always will be a dot
character at the upper left and lower right corner cells of the input matrix.
Figure 1. The labyrinth from the input sample. Your task is to calculate the square of visible part of the walls inside
the labyrinth. In other words, the square of the walls' surface visible to
a visitor of the labyrinth. Note that there's no holes to look or to move
through between any two adjacent blocks of the wall. The blocks are
considered to be adjacent if they touch each other in any corner. See picture
for an example: visible walls inside the labyrinth are drawn with bold
lines. The height of all the walls is 3 meters.
The first line of the input file contains the single number N.
The next N lines contain N characters each. Each line describes
one row of the labyrinth matrix. In each line only dot and diesis
characters will be used and each line will be finished with a new line
character. There will be no spaces in the input file.
Your program should print to the output file a single integer — the
exact value of the square of the wallpaper needed.
Input sample.
5 Output sample.
198
Problem G. Queens in peaceful positions.
Time limit: 10 sec per test.
On a chessboard of size NxN (N<=50) N queens are placed. We'll say that queens are in peaceful position if none of them can attack another. You are to find the total amount of peaceful positions that can be obtained from the given peaceful position by rearranging of exactly three queens.
The first line of input file will contain an integer number N that represents the size of a chessboard (and the number of queens also). It will be followed by N lines describing positions of queens. Each line will contain two integers X and Y separated by a space. These numbers represent horizontal and vertical coordinates and lay in a range from 1 to N.
The output consists of a single integer representing the number of peaceful positions that can be achieved from initial position by moving of exactly three queens. Note: queens are not numbered so if you rearrange them on the chessboard using only squares they already occupied you’ll always get the same peaceful position, not the new one.
Sample input.
4 Sample output.
0
Problem H. Cross-stitch. Time limit: 5 sec per test.
Archaeologists have found a cloth decorated with needlework.
This needlework is a cross-stitch made with several threads.
The following rules have been observed:
Archaeologists want to know if the pattern was made with the least number of threads. You have to write a program, which will determine the minimal number of threads needed to make the given pattern.
The first line of the input file contains two integers N and M separated by a space. They are vertical (N) and horizontal (M) sizes of the grid, i.e. amounts of the cells in a vertical and horizontal rows respectively (1<=N,M<= 200). Each of the following 2*N lines contains M symbols. Each symbol describes one square of the grid. The first N lines correspond to the face of the cloth and the last N lines correspond to the rear of the cloth. The symbols used are У.Ф, У/Ф, У\Ф and УXФ (a dot means an empty square).
For more information see the sample. It corresponds to the cloth drawn at the
figure.
The output file should contain one integer - the minimal number of threads
needed to make the described pattern.
Sample input.
4 5 Output sample.
4
Problem X. Questions. Time limit: 5 sec per test.
Holding a collegiate programming contest is a very exhausting work. There is a well-known proverb that one fool can ask so many questions that a hundred clever men will not answer. And during a collegiate programming contest questions are asked by one hundred clever people.
The jury of the Third Urals Collegiate Programming Contest being clever enough has found a simple way to make its work easier. We have invented a simple algorithm that will help us answer ALL your numerous questions! Moreover, this algorithm guarantees that the same questions will have the same answers (this would be hardly possible, if we would undertook such a task ourselves). According to this algorithm a member of the jury starts to delete characters of the question in the following order: 1. Starting from the first character he or she counts out N-1 characters (spaces, punctuation marks etc. are considered to be characters too) and deletes the Nth character.
2. If a string ends the count continues from the beginning of the string.
3. After deleting a character the count restarts from the character that would be the (N+1)-st in the previous count.
4. If the last remaining character is a question-mark ("?") then the answer to the question is "Yes". If it is a space then the answer is "No". Any other character will lead to "No comments" answer. You should help the jury and write a program that will do a hard work of answering your questions tomorrow. The number N is secret and will not be announced even after the end of the contest. Your program should use N=1999.
For example, taking a string "Is it a good question?" (its length is 22) the characters will be counted in the following way: "Is it a good question?Is it ... quest" and "i" will be deleted. Then the count restarts from "on?Is it..." etc., until "s" will be left (thus the answer is "No comments", as usual).
The input is a question, that is any text file containing at least one character (end of line is not a character). Each character of the input (excepting the ends of lines) is a part of the question. You should read question from file INPUT.TXT.
The size of the input file is not more than 30000.
Sample input 1.
Does the jury of this programming contest use the algorithm described in this problem to answer my questions?
Output for sample input 1.
Yes
Sample input 2.
At least, will anybody READ my question?
Output for the sample input 2:
No
Sample input 3:
This is Output for the sample input 3:
No comments Note: there are no spaces in the sample inputs except for those between words in one line. Thus the first question contain 108 characters, the second - 40 and the third - 14.
Received at 22:30:11.
Current ship’s coordinates are
41^46'00" NL
and 50^14'00" WL.
An iceberg was noticed at
41^14'11" NL
and 51^09'00" WL.
===
DANGER!
1 <= C1 < C2 < C3 <= 10^9) in the specified order with one space between. The second line contains the amount of stations N (2 <= N <= 10000). The third line contains two different integers separated by space. They represent serial numbers of stations, the travel between which must be paid. Next N-1 lines contain distances from the first station (УEkaterinburgФ) on the railway line to others. These distances are given as different positive integers and are arranged in the ascending order. The distance from УEkaterinburgФ to УSverdlovskФ does not exceed 10^9. The distance between any neighboring stations does not exceed L3. The minimal travel cost between two given stations will not exceed 10^9.
7
2 6
3
7
8
13
15
23
1
2
3
4
1
2
3
.....
...##
..#..
..###
.....
2 1
1 3
3 4
4 2
This is an example of a pattern made with six stitches. The grid has size 4*5. The face of the cloth is drawn on the upper half of the figure. The stitches lying on the face are drawn with solid lines. The rear stitches uncovered with those of the face are drawn with dot-lines. On the lower half of the figure the cloth is oriented as on the upper half. All the rear stitches are drawn with solid lines there. The face stitches, which do not cover rear stitches, are drawn with dot-lines. It can be seen that there are the stitches at both sides of one of the cell diagonals. This cross-stitch cannot be made with less than four threads.
.....
.\...
..\..
.....
.....
....\
.\X..
.....
UNFAIR!