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

Назад

images/home.png Начало
images/balloon.gif Соревнования
2009
Задачи очного тура личного первенства

Подразделы

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

Дата и время

16/11/2024 15:20:23

Авторизация

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

printЗадачи очного тура личного первенства Южного Урала 2009

A. Социальная сеть

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

Каждый участник социальной сети Among Class-Mates может разослать не более `K` предложений дружбы другим участникам. Участники становятся друзьями только в том случае, если они послали взаимные предложения дружбы друг другу. Организаторы сети хотят подсчитать максимальное и минимальное количество пар друзей, которые могут образоваться в сети после рассылки всеми участниками `K` предложений дружбы.
Первая строка ввода содержит два целых числа – количество участников сети `N` (`2\ ≤\ N\ ≤\ 10^9`) и ограничение на количество предложений дружбы `K` (`1\ ≤\ K\ <\ N`).
Вывести два целых числа – максимальное и минимальное количество пар друзей, образовавшихся в сети из `N` участников, разославших ровно `K` предложений дружбы.

Пример ввода

4 2

Пример вывода

4 2

B. Counting Stars

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

People generally don't care to give attention to stars in a moonlit night. In most cases the attention goes towards the moon. Sadly, you have to write a program now that can count the stars in the sky. For this problem a sky is a two dimensional grid. Empty pixel is denoted by a '.' (ASCII value 46) and a non-empty pixel is denoted by a '*' (ASCII value 42). As a star is a very small object so it cannot occupy more than two adjacent pixels and in our sky two stars are never adjacent. So three or more adjacent non-empty pixels can denote some larger objects like moon, comet, sun or UFOs but they never represent a star. All the eight possible pixels around a pixel are adjacent to it. In the figure below the black pixel at the center have eight adjacent pixels. Of them three pixels are non-empty.
  *..
  .**
  ..*
The input file contains at most 100 sets of inputs. The description of each set is given below:
Each set starts with two integer number `r` and `c` (`1\ ≤\ r,\ c\ ≤\ 100`), which indicates the row and column number of the image to follow. Next `r` rows describe the sky as mentioned in the problem statement. Input is terminated by a line containing two zeroes.
For each set of input produce one line of output. This line contains a decimal integer which denotes the number of stars in the given sky.

Sample Input

5 5
.....
....*
....*
...*.
*....
4 4
*...
*...
...*
*.*.
0 0

Sample Output

1
3

C. Cube Numbers

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

A cube number is an integer number whose cube root is also an integer. For example 1, 8, 125 are some cube numbers. Given two numbers `a` and `b` you will have to find out how many cube numbers are there between `a` and `b` (inclusive).
The input file contains at most 201 lines of inputs. Each line contains two integers `a` and `b` (`0\ <\ a\ ≤\ b\ ≤\ 10^9`). Input is terminated by a line containing two zeroes. This line should not be processed.
For each line of input produce one line of output. This line contains an integer which denotes how many cube numbers are there between `a` and `b` (inclusive).

Sample Input

1 8
5 100
0 0

Sample Output

2
3

D. Удаление букв

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

Из слова длиной `n` букв можно удалить `k` из них `C_n^k` способами (если рассматривать только позиции букв в слове). Например, удалив 2 буквы из слова above, можно получить 10 слов: ove, bve, boe, bov, ave, aoe, aov, abe, abv, abo. Если упорядочить эти слова по алфавиту, то получим следующий список слов: abe, abo, abv, aoe, aov, ave, boe, bov, bve, ove.
Напишите программу, которая выводит первое и последнее слово из отсортированного в лексикографическом порядке списка всех возможных слов, полученных из заданного с помощью удаления ровно `k` букв.
Первая строка ввода содержит два целых числа – длина слова `n` (`2\ ≤\ n\ ≤\ 10^5`) и количество удаляемых букв `k` (`1\ ≤\ k\ <\ n`). Вторая строка содержит слово из `n` строчных латинских букв.
В первой строке вывести первое слово, а во второй строке – последнее слово из отсортированного списка слов.

Пример ввода

5 2
above

Пример вывода

abe
ove

E. Задача Тамерлана

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

На доске размером `N\ times\ M` разложено несколько монет разного номинала. В клетке может лежать не более одной монеты. Можно поставить шахматного коня на любую клетку доски, в том числе занятую монетой, и затем, делая ходы по шахматным правилам, собирать монеты на клетках. В конце путешествия конь должен вернуться на начальную клетку. За выполнение каждого хода нужно заплатить одну денежную единицу. Можно проходить по клеткам доски несколько раз и собрать не все монеты. Допустимо также круговое путешествие в 0 ходов, при котором конь не двигается с начальной клетки. Выигрыш в этой задаче определяется как разница между стоимостью собранных монет и количеством ходов, сделанных конем.
Напишите программу, вычисляющую максимальный выигрыш и последовательность ходов, которая позволит его получить.
Первая строка ввода содержит три целых числа – размеры доски `N` и `M` (`4\ ≤\ N,\ M\ ≤\ 100`) и количество монет `K` (`1\ ≤\ K\ ≤\ 15`). Далее следует `K` строк, содержащих по три целых числа – номера строки `r_i` (`1\ ≤\ r_i\ ≤\ N`) и столбца `c_i` (`1\ ≤\ c_i\ ≤\ M`) клетки, в которой находится `i`-я монета, и номинал монеты `a_i` (`1≤\ a_i\ ≤\ 100`).
В первой строке вывести одно целое число – максимальный выигрыш, во второй строке вывести последовательность номеров строк и столбцов клеток в порядке посещения их шахматным конем. Если существует несколько вариантов последовательности ходов с одинаковым выигрышем, то можно вывести любой из них.

Пример ввода

8 8 4
2 6 10
4 8 2
6 5 15
7 5 2

Пример вывода

19
4 6 3 4 2 6 3 8 5 7 6 5 4 6

F. Генератор текста

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

Возьмем какой-нибудь осмысленный текст, предварительно удалив из него все знаки препинания, например, "alice was beginning to get very tired of sitting by her sister on the bank and of having nothing to do" и подсчитаем частоту появления каждой буквы или пробела в этой фразе. Мы можем сгенерировать текст, выбирая очередной символ с вероятностью, с которой этот символ встречаются в исходной фразе, но результат будет слишком отличаться от естественного текста: "iehehgv bwbertieitneisediiigiiidgrhs sn obi b i nlo nntthtesi oiin oihaetengdet ditfaoo hrhbebc". Cлова невозможно произнести, они часто слишком длинные или совсем короткие. Намного лучший результат дает использование алгоритма цепей Маркова, в котором анализируются вероятности появления пар символов и очередной символ генерируется с учетом предыдущего символа текста: "sinnk ve her walindof thinoto d tink aninged tind histo nof othe of bang tisingite oto to singing to". Вероятность выбора очередного символа текста `A_i` прямо пропорцинальна вероятности появления пары `A_{i-1}A_i` в исходной фразе. Для первого символа текста предыдущим (`A_0`) является пробел, также пробелы добавляются в начале и в конце исходной фразы перед вычислением вероятности появления пар. Длина слов в получившемся тексте более естественна, их можно произнести, можно отметить появление английских слов bang и singing, отсутствовавших в исходной фразе. Неспециалист даже может принять этот текст за текст на незнакомом ему языке.
Напишите программу, которая подсчитывает количество различных слов длины `N` в бесконечном тексте, сгенерированном указанным алгоритмом. Словом считается часть текста между пробелами, состоящая только из букв.
Первая строка ввода содержит два целых числа – длина слов `N` (`1\ ≤\ N\ ≤\ 10^9`) и число `P` (`10\ ≤\ P\ ≤\ 10^9`). Вторая строка ввода содержит исходную фразу длиной не более 1000 символов, состоящую только из строчных латинских букв и символов пробела.
Вывести одно целое число – остаток от деления на число `P` количества различных слов длины `N` в бесконечном сгенерированном тексте.

Пример ввода

2 100
alice was beginning to get very tired of sitting by her sister on the bank and of having nothing to do

Пример вывода

20
Пояснение в ходе соревнований:
Пусть пара символов `A_{i-1}B_j` встречается в исходной фразе `K_j` раз, где `B_j` кандидат на `i`-й символ генерируемого текста, тогда вероятность выбора символа `B_j` в качестве `A_i` равна `K_j/{sum_m\ K_m}`. Т.е. если пара символов `"xy"` не встречается в исходной фразе, то она никогда не появится в генерируемом тексте.

G. Складывание карты

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

Джордж и Фред, чтобы не скучать во время поездки, играют в следующую игру при помощи дорожной карты. Карта имеет прямоугольную форму и сгибами разделена на квадраты. Карта имеет размеры `W` квадратов по горизонтали и `H` квадратов по вертикали (`1≤\ W,\ H\ ≤\ 10^6`). Ходы в игре делаются по очереди. Тот из игроков, который не может сделать очередной ход, проигрывает. Ход заключается в выполнении сгиба по вертикали или горизонтали по линии сгиба. Таким образом игра заканчивается, когда карта превратится в квадрат `1\ times\ 1`.
Вы должны написать подпрограмму с именем game, реализующую выигрышную стратегию для этой игры. Подпрограмме в качестве параметров передаются размеры карты.
void game(int *w, int *h); // С/С++
procedure game(var W,H:integer); // Pascal
Для выполнения хода ваша подпрограмма должна вызывать подпрограмму robot с указанием хода.
void robot(int t); // С/С++
procedure robot(t:integer); // Pascal
Эта подпрограмма делает изменения значений `W` и `H`, вводит ход соперника и опять изменяет эти переменные. Аргумент `t\ >\ 0` используется для сгибания карты по горизонтали – сгибается полоса карты слева шириной `t` (`t\ <\ W`), карта при этом уменьшается до размера `max(t,W-t)\ times\ H`; `t\ <\ 0` используется для сгибания карты по вертикали – сгибается полоса карты сверху высотой `-t` (`-t\ <\ H`). В случае, если компьютер не может сделать ход, вы должны выйти из подпрограммы game. В качестве начальной позиции подпрограмме game передается позиция, в которой существует выигрышный ход.
Пересылаемое на проверку решение должно содержать только подпрограмму game, вспомогательные функции, команды #include (в C/C++) и глобальные переменные. В подпрограммах не должен выполняться ввод или вывод.
Пример подпрограммы на C/C++
void game(int *w, int *h)
{ while(*w>1 || *h>1)
  {
    if(*w>1)
      robot(*w/2);
    else
      robot(-(*h/2));
  }
}
Пример подпрограммы на Pascal
procedure game(var W,H:integer);
begin
  while (W>1) or (H>1) do
    if W>1 then
      robot(W div 2)
    else
      robot(-(H div 2));
end;

H. Под колпаком

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

На плоскости в первом квадранте системы координат находится несколько точек, требуется накрыть их "колпаком" – равнобедренным треугольником с основанием на оси абсцисс.
Напишите программу, которая по заданным координатам точек вычисляет координаты вершин "колпака" минимальной площади.
Первая строка ввода содержит одно целое числа – количество точек `N` (`2\ ≤\ N\ ≤\ 100`). Далее следует `N` строк, содержащих по два целых числа `X_i`, `Y_i` (`0\ <\ X_i,\ Y_i\ <\ 1000`) – координаты точек. Все точки различны, есть не менее двух точек с различными абциссами.
Вывести шесть вещественных чисел – координаты вершин "колпака", накрывающего заданные точки, с точностью не менее `10^{-6}`. Если существует несколько вариантов "колпака" с минимальной площадью, то можно вывести любой из них.

Пример ввода

3
1 1
3 1
4 2

Пример вывода

0.0 0.0 6.0 0.0 3.0 3.0
loading