7866.png
ЧЕЛЯБИНСК,ЮУРГУ,ИЕТН

Назад

images/home.png Начало
images/balloon.gif Соревнования
2002

Подразделы

Другие разделы

Дата и время

24/04/2024 07:38:54

Авторизация

Имя:
Пароль:
Зарегистрироваться
Восстановить пароль
 

printЗадачи 2 тура Чемпионата Урала 2002

print1. Dividing into Groups

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Set of natural numbers must be divided into `G` groups so, that numbers `n`, `2*n`, …, `G*n` correspond to different groups, where `n` is arbitrary natural number.
Input
The first line of the input file contains two integers `M` and `G`, separated by a space, where `M` is the quantity of numbers in the file (`1\ ≤\ M\ ≤\ 10^6`) and `G` is the quantity of groups (`2\ ≤\ G\ ≤\ 5`). The following `M` lines contain a single integer `n` in a line (`1\ ≤\ n\ ≤\ 10^9`).
Output
Write into the output file `M` lines with numbers of groups for all numbers of the input file. If `i`-th number of the input file corresponds to `k`-th group while dividing into `G` groups, then on `i`-th line of the output file there should be the number `k` (`1\ ≤\ k\ ≤\ G`).

Sample Input

5 2
1
2
3
4
6

Sample Output

1
2
1
1
2

print2. The Travel of the Queen

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (1)

Once Alice and Bob decided to play chess, but they found out that a lot of chessmen are missing. Then they invented another game. They needed only chess-clock, chessboard and the queen. The rules of the game are quite easy. The first player puts the queen at any field of the chessboard. Then the players move the queen in turn, starting from the second player. If the player puts the queen on the field, where it has already been, he loses. The game can be completed in a draw, only if the queen has already been on every field of the chessboard, but the player may move the queen on the starting field. The queen can move on any number of fields horizontally, vertically or diagonally.
Suppose, that the game is completed in a draw, and all moves of the first player are known. Restore the moves of the second player.
Input
The input file contains one line with the moves of the first player, separated by one space. Verticals are designated by letters from a through h, and horizontals by numerals.
Output
Write into the output file in the same form the moves made by the second player so, that the game is ended in a draw. If there exist a number of variants, then write any one of them.

Sample Input

a8 a7 c4 d1 b4 a1 a3 c2 b3 b8 c5 d8 b7 c7 d2 d3 h5 e1 h1 f3 f2 g2 e6 f4 g6 e4 f8 g7 e8 g5 h2 h3

Sample Output

a5 a6 a4 b1 c3 a2 c1 b2 b5 d6 b6 c8 c6 d7 d4 d5 e5 h4 f1 e2 g1 g4 e3 g3 f5 e7 f6 f7 g8 h6 h7 h8
Условие задачи на русском языке

print3. Pentium vs ENIAC

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

The calculation of 2000 digits of number `π` on the computer ENIAC in 1949 took 70 hours (not including programming!). Modern computers (and programmers) can find 2000 digits of number `π` much faster.
For calculation a series should be used
   `π/4\ =\ 1\ -\ 1/3\ +\ 1/5\ -\ 1/7\ +\ 1/9\ -\ …`
But this series converges slowly. Much better is series for an arctangent
   `"arctg"\ x\ =\ x\ -\ x^3/3\ +\ x^5/5\ -\ x^7/7\ +\ …,\ |x|<1`.
Combine it with the formula for addition of a tangent
   `"tg"(a+b)\ =\ ("tg"\ a\ +\ "tg"\ b)/(1\ -\ "tg"\ a\ *\ "tg"\ b)`
and select `a` and `b` so that `"tg"\ (a+b)\ =\ 1\ =\ "tg"\ π/4`. In practice usually use the following formulas
   `π\ =\ 16\ "arctg"\ (1/5)\ -\ 4\ "arctg"\ (1/239)`
   `π\ =\ 32\ "arctg"\ (1/10)\ -\ 16\ "arctg"\ (1/515)\ -\ 4\ "arctg"\ (1/239)`
   `π\ =\ 12\ "arctg"\ (1/4)\ +\ 4\ "arctg"\ (1/20)\ +\ 4\ "arctg"\ (1/1985)`
In all formulas it is necessary to calculate `"arctg"\ (1/k)`, where `k\ ≥\ 2`. Write the program that fulfills this calculation.
Input
The first line of the input file contains one integer `k` (`2\ ≤\ k\ ≤\ 10000`).
Output
Write into the output file a value of `"arctg"\ (1/k)` with accuracy `10^{-2000}`.

Sample Input

2

Sample Output

0.46364760900080611621425623146121440...399481324877580713052569525399998448
Условие задачи на русском языке

print4. Search of the Sum

Ограничения: время – 200ms/500ms, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0) idea

The sequence of `M` integers is given. Find here the longest continuous subsequence with the sum of terms equal to given `S`.
Input
The first line of the input file contains two integers `M` and `S`, separated by one space, where `M` is the quantity of numbers in the sequence (`2\ ≤\ M\ ≤\ 30000`) and `S` is the value for the sum of terms of a subsequence (`0\ ≤\ S\ ≤\ 1000`). The following `M` lines contain a single integer `n` in a line (`-10000\ ≤\ n\ ≤\ 10000`).
Output
On the first line of the output file write two integers `F` and `L`, separated by one space, where `F` is the index of the first term of the retrieved subsequence (indexing starts from 1), and `L` is the length of the retrieved subsequence. If there are some equally long subsequences, indicate the first of them in the source sequence. If a subsequence with the given sum of terms is missing, write two zeros, separated by one space.

Sample Input

4 5
2
3
4
1

Sample Output

1 2
Условие задачи на русском языке

print5. Fair Sharing

Ограничения: время – 1s/2s, память – 4MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Gnomes snatched away the sweets from a vase, which Snow-white had place on the round table.
"Stop! You haven't left any sweets for me!" – Snow-white exclaimed. – "We need to share the sweets equally."
Snow-white counted the sweets; there were 15 sweets.
"Fifteen cannot be divided on eight. Let's do it like this. Put your sweets into bowls." – After it had been done, Snow-white continued. – "Let's enumerate bowls clockwise from 1 up to 8. My bowl will be under number 1. I will turn away and call the numbers from 1 to 8. Somebody takes all the sweets from the called bowl and distribute one in each bowl clockwise, starting from the next one after the called. I think, after several such operations the sweets will be distributed on cups in random."
The gnomes agreed, that this sharing would be fairer, as the results will depend on case, but not on "the length of raking arms" (Grumbler said so, who had got only one sweet). But as a result Grumbler got nothing, because Snow-white was offended with him for grumbling about the quality of yesterday's dinner. Snow-white differed from her stepmother not only in beauty, but also in wit (at least, it did not come into her mind to talk to a mirror), therefore Snow-white easily invented, how to achieve more fair distribution (from her point of view) from initial distribution of sweets among bowls.
Write the program, which determines according to initial and finite distribution of 15 sweets among 8 bowls a sequence of numbers, which needs to be pronounced by Snow-white.
Input
The first line of the input file contains 8 integers (in the range from 0 to 15 inclusively, the sum is 15), separated by spaces; this is initial distribution of sweets among bowls (clockwise, starting from a bowl #1). Second line contains 8 integers (in the range from 0 to 15 inclusively, the sum is 15), separated by spaces; this is required finite distribution of sweets among bowls (clockwise, starting from a bowl #1).
Output
On the first line of the output file write one integer `N` representing an amount of called numbers. The following `N` lines of the output file with numbers from 1 up to 8 representing a sequence of called numbers. Any variant, even not necessarily the shortest, may be pointed.

Sample of input

0 3 1 2 1 3 1 4
3 3 0 2 2 3 1 1

Output for the sample input

7
2
4
6
5
8
7
3

print6. The Beach

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Bill has bought some islands at the ocean in the gross and has decided to sell them off piecemeal. But the buyers are interested only in the sites located on the coast of the ocean.
Bill divided the map of islands into square cells and represented each cell by one character. Bill used the character '.' (dot) for the denotation of water and character '*' (asterisk) for the land. Each character '*' corresponds to one site for sale. There are no other characters on the map.
Write the program, which will help Bill to determine an amount of sites having common boundary with the ocean according to this map. The sites, adjoining only to a lake or a pool, are not taken into account. If water square have not common boundary with the ocean, then it is a pool or a lake.
Input
The first line of the input file contains two integers `N` and `M`, separated by one space, where `N` and `M` are the sizes of the map (`3\ ≤\ N\ ≤\ 200`, `3\ ≤\ M\ ≤\ 200`). The following `N` lines contain `M` characters with each line representing a map of the bought islands. NOTE: The islands do not adjoin to the edges of the map.
Output
Write in the output file an amount of sites located on the coast of the ocean.

Sample Input

8 10
..........
..***.....
.*****....
.**..*....
..****....
........*.
......***.
..........

Sample Output

15

print7. Sequence

Ограничения: время – 500ms/1000ms, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Let's take any natural number `K` and generate an infinite sequence `S` according to the following rules.
  • `S_i` is `i`, where `1\ ≤\ i\ ≤\ K`.
  • `S_i` is the least natural number so, that `gcd(S_i,\ S_{i-1})\ ≥\ K` and `S_i\ ≠\ S_j`, where `1\ ≤\ j\ <\ i` and `i\ >\ K` and gcd mean "greatest common divisor".
For example, for `K=3` first twenty terms are 1, 2, 3, 6, 9, 12, 4, 8, 16, 20, 5, 10, 15, 18, 21, 7, 14, 28, 24, 27.
Sooner or later in this sequence there will be all natural numbers. Write the program, which calculates the least natural number that is missing among first `N` terms, the greatest number among first `N` terms, and `N`-th term.
Input
The first line of the input file contains two integers `K` and `N` (`1\ ≤\ K\ ≤\ 100`, `1\ ≤\ N\ ≤\ 10000`), separated by one space. First `N` terms of the sequence `S` do not exceed 30000 for given `K`.
Output
Write into the output file the one line containing three integers, separated by spaces. They are the least natural number that is missing among first `N` terms of the sequence `S`, the greatest number among first `N` terms of the sequence, and `N`-th term.

Sample Input

3 20

Sample Output

11 28 27

print8. Metamorphoses

Ограничения: время – 250ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Take two words of equal length, for example, SEAT and TALE, write them one under another and make the following transformations. At first, replace all appearances of the first character of the second word in the second word with the first character of the first word, and all appearances of the first character of the first word in the first word with the first character of the second word. Similarly, all appearances of the second character of the second word in the second word with the second character of the first word, and all appearances of the second character of the first word with the first word on the second character of the second word. The same must be done for the third pair of characters of the both words, and so on for all characters from left to right.
SEAT TEAT TAAT TLLT ELLE
TALE SALE SELE SEAE STAT
Write the program, which calculates outcome of transformations for the pair of the given words.
Input
Input file contains two lines. Each line contains one word, the length of which is not more than 100 characters consisting of uppercase letters from A through Z. Both words have equal length.
Output
Write into the output file two lines containing the outcome of transformations. On the first line write the transformed first word, and on the second line write the transformed second word.

Sample Input

SEAT
TALE

Sample Output

ELLE
STAT
Условие задачи на русском языке

print9. Lists and Columns

Ограничения: время – 500ms/1000ms, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Write the program, which will transform lists of words into table columns. The first column should contain words of the first list, second column should contain words of the second list, and so on. Words should be written without skips in same order as in the lists. The width of a column is equal to the length of the longest word of this column. Columns should be separated by one space.
Input
The input file contains `N` lines (`1\ ≤\ N\ ≤\ 100`) of length up to 200 characters. Each line contains the nonempty list of words consisting of letters. Words are separated by commas. The lines do not contain spaces. The new-line character ends each line.
Output
Write into the output file the table of `N` columns containing all words from lists. No spaces are allowed at the end of lines.

Sample Input

Bill,Jo,Robert,Sally
Ann,Sam,Carolyn
fire,grain,cat,column,store

Sample Output

Bill   Ann     fire
Jo     Sam     grain
Robert Carolyn cat
Sally          column
               store
loading