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

Назад

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

Подразделы

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

Дата и время

19/12/2024 18:02:13

Авторизация

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

printЗадачи Южно-Уральского командного чемпионата 2011

printA. Великий комбинатор

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

У О.Бендера было `N` различных сравнительно честных способов отъема денег у населения. Но так как богатых людей не осталось, Великий комбинатор решил использовать комбинации своих способов для увеличения прибыльности своих мероприятий. Для этого он разделил известные ему способы на две группы, в одной группе было `N_1` способов, в другой – `N_2` способов (`N_1\ +\ N_2\ =\ N`). Сначала он применял способ из первой группы, а затем – из второй группы. Это дало ему `N_1*N_2` комбинаций. Немного подумав, Бендер понял, что каждую группу способов можно аналогичным образом разделить на подгруппы, например, если первую группу на две подгруппы по `N_11` и `N_12` способа (`N_11+N_12=N_1`), то можно получить еще `N_11*N_12` комбинаций. Каждую подгруппу можно также разделить на подподгруппы и получить новые комбинации, и такое деление на две подгруппы можно продолжать, пока есть подгруппы из более чем 1 способа.
Определите, какое максимальное количество комбинаций может получить Бендер, разбивая разным образом способы на группы и подгруппы.
Ввод содержит одно целое число `N` (`2\ ≤\ N\ ≤\ 10^6`) – количество способов.
Вывести одно целое число – максимальное количество комбинаций.

Пример ввода

5

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

10
Пояснение: 10 комбинаций Бендер может получить, сначала разбив 5 способов на группы из 2 и 3 способов (`2*3=6` комбинаций), затем группу из 2 способов на подгруппы из 1 и 1 способа (еще `1*1=1` комбинация), а группу из 3 способов на подгруппы из 1 и 2 способов (еще `1*2=2` комбинации), подгруппа из 2 способов после разбиения дает еще `1*1=1` комбинацию. Итого 6+1+2+1=10.

printB. Автопробег

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

— Объявляю большой скоростной пробег Арбатов-Черноморск открытым,  – торжественно сказал Остап. – Командором пробега назначаю себя.
Автопробег стартует в 08:00 в городе `1` и, проехав через города `2,\ 3,\ …,\ N-1`, должен завершиться в городе `N`. Участники автопробега не могут ехать более 10 часов в день, поэтому, отправляясь в путь утром в 08:00, должны останавливаться на ночлег в городах не позднее 18:00.
Определите время прибытия в город `N` и количество остановок по пути, если цель автопробега – добраться до города `N` как можно скорее.
Первая строка ввода содержит одно целое число `N` (`2\ ≤\ N\ ≤\ 10^5`) – количество городов в маршруте. Во второй строке содержится `(N-1)` целое число – время поездки в минутах между соседними городами маршрута автопробега в диапазоне от 1 до 600.
Вывести количество остановок на ночлег и время прибытия в город `N` в формате `"hh":"mm"` (с ведущими нулями).

Пример ввода

5
200 450 100 110

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

2 09:50
Пояснение: остановки нужно сделать в городах 2 и 4.

printC. Чтение вслух

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

Паниковский и Балабанов вместе читают вслух "дело Корейко". Но первый читает дело с `i`-го символа, а второй – с `j`-го символа. Чтение продолжается, пока читаемые буквы совпадают. Сколько букв они смогут прочитать, прежде чем обнаружат, что читают дело, начиная с разных позиций.
В первой строке ввода дана строка `S` из строчных латинских букв длиной от 1 до 100000 символов. В следующей строке дано одно целое число `Q` – количество запросов (`1\ ≤\ Q\ ≤\ 100000`). В следующих `Q` строках даны запросы. Каждый запрос задаётся парой целых чисел `(i,j)` (`1\ ≤\ i,\ j\ ≤\ |S|`) – индексы символов, с которых надо начинать читать.
Выведите `Q` строк, в каждой из которых должно быть одно целое число – количество символов, совпадающих при чтении подстрок, начинающихся с `i`-го и `j`-го символа (т.е. длина максимального общего префикса этих двух подстрок).

Пример ввода

abacaba
4
1 5
3 5
4 2
2 6

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

3
1
0
2

printD. Коллекционер

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

— Такие строптивые миллионеры могут быть только в Америке. У нас миллионер должен быть более покладистым, – сказал Остап.
— Я не миллионер, а коллекционер! – возмутился Корейко. – Я собираю банкноты, номер которых ровно в `K` раз больше суммы своих цифр.
Для заданного `K` определите количество положительных целых чисел, ровно в `K` раз больших суммы своих цифр, а также найдите минимальное и максимальное числа, обладающие такими свойствами.
Первая строка ввода содержит одно целое число `K` (`1\ ≤\ K\ ≤\ 10^9`).
Вывести в первой строке количество номеров. Если количество больше 0, во второй строке вывести минимальный и максимальный номера с указанными свойствами (без ведущих нулей).

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

7

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

4
21 84

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

75

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

0

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

5

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

1
45 45

printE. Волшебное превращение

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

Далеко за городом в овраге Балаганов и Паниковский пилили гири. Под гирями предусмотрительный Паниковский разостлал газетный лист, дабы ни одна пылинка драгоценного металла не пропала зря. Напуганные скрежетом ножовок суслики разбегались в разные стороны.
Молочные братья не знали, что если разбежавшиеся суслики образуют подобие магического круга – строго выпуклый многоугольник, внутри которого нет других сусликов, то всё золото в гирях превратится в чугун.
Напишите программу, определяющую, сколько времени Балабанову осталось радоваться золотым гирям.
В первой строке ввода содержится одно целое число `N` (`3\ ≤\ N\ ≤\ 50`) – количество сусликов. Далее следует `N` строк, каждая строка содержит три целых числа `x_i` `y_i` `a_i` (`0\ ≤\ x_i,\ y_i\ ≤\ 100`, `0\ ≤\ a_i\ ≤\ 359`) – начальные координаты суслика и направление его движения в градусах. Скорость движения постоянна и равна 1 м/c. Координаты сусликов могут совпадать, а направления движения у всех сусликов разные (для `i\ ≠\ j` `a_i\ ≠\ a_j`).
Вывести одно вещественное число с относительной или абсолютной точностью `10^{-6}` – через сколько времени суслики образуют строго выпуклый многоугольник. Вывести 0, если многоугольник выпуклый в начальный момент времени.

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

4
0 1 90
1 1 0
2 2 180
2 0 270

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

0.618034

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

3
0 0 0
10 0 90
0 4 180

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

0.000000

printF. Доска объявлений

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

В коридоре общежития студентов-химиков имени товарища Семашко висит доска для объявлений размером `n\ times\ m`. Доска покрыта объявлениями размером `1\ times\ 2`, так что каждая клетка доски оказалась покрыта объявлениями в 2 слоя.
Необходимо убрать половину объявлений, чтобы оставшиеся объявления были полностью видны и на доске не было свободного места, т.е. чтобы каждая клетка доски была покрыта объявлениями в один слой.
Первая строка содержит два целых числа `n` и `m` (`2\ ≤\ n,m\ ≤\ 500`, хотя бы одно из чисел `n` или `m` четно). Далее следует `n*m` строк, каждая строка содержит три целых числа `r_i`, `c_i` и `d_i`, где `(r_i,\ c_i)` – координаты верхней левой клетки, покрытой `i`-м объявлением, `d_i=0` если объявление расположено горизонтально, и `d_i=1` если объявление расположено вертикально.
Вывести строку, содержащую `n*m/2` номеров удаляемых объявлений в порядке возрастания номеров.

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

2 2
1 1 0
1 1 1
2 1 0
1 2 1

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

1 3

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

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

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

1 3 5

printG. Погрузка

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

Завхоз 2-го дома Старсобеса хочет вывезти со склада несколько ящиков с продуктами.
14368.jpg
Склад имеет форму прямоугольника размером `N\ times\ M`, каждая клетка либо занята одним ящиком, либо свободна. Дверь склада находится на левой стороне левой верхней клетки. Альхен использует погрузчик, чтобы поднять ящик и погрузить его в грузовик. В начальный момент времени погрузчик находится за пределами склада. Погрузчик имеет размер `1\ times\ 1`, но спереди погрузчика находятся вилы, имеющие длину 1. Вилы погрузчика могут заезжать под ящик (например, чтобы поднять его), но не должны протыкать стены склада.
Погрузчик может ехать по прямой передним и задним ходом. При необходимости можно въехать на склад задним ходом. Погрузчик может поворачивать на свободной площадке `2\ times\ 2`, в том числе задним ходом, как показано на рисунке.
14367.png
Напишите программу, определяющую, сколько ящиков со склада сможет вывезти со склада завхоз, не прибегая к помощи своих родственников для передвижения ящиков на складе.
Первая строка ввода содержит два целых числа `N` и `M` (`1\ ≤\ N,M\ ≤\ 100`). Далее следует `N` строк, содержащих по `M` символов – расположение ящиков на складе. Символ '#' означает клетку, занятую ящиком, а символ '.' – свободную клетку.
Вывести одно целое число – максимальное количество ящиков, которое сможет вывезти завхоз.

Пример ввода

3 4
..##
##..
..##

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

3
Пояснение: оставшиеся ящики на складе будут расположены так:
....
##..
..#.

printH. Инспекция

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

Инспекция, устроенная О.Бендером, встревожила завхоза 2-го дома Старсобеса. "Вслед за пожарным инспектором нужно ждать и других проверяющих", думал Альхен, пробираясь между ящиками на складе. По документам на складе должно быть `a` ящиков с продуктами. А на самом деле их осталось `b`. Внезапно его осенило.
Известно, что самая строгая инспекция никогда не проверяет ничего досконально. И когда инспектор придёт осматривать склад, он не обязательно будет пересчитывать все ящики. Ведь некоторые ящики могут лежать очень далеко, и до них невозможно добраться, не вытащив ящики, которые мешают.
Естественно, что проверяющий не будет вытаскивать ни одного ящика. Он просто посмотрит, сколько ящиков доступно, а всё, что недоступно, также посчитает за ящики.
Довольный собой, завхоз решил разложить ящики на складе, чтобы проверяющему показалось, что ящиков на складе не меньше, чем положено по документам. Не обязательно, чтобы ящиков было ровно столько, сколько нужно по документам – завхоз хорошо знает, что проверяющий не будет спрашивать, почему ящиков слишком много. Проверяющий просто прикажет отдать "лишние" ящики ему. Поэтому, необходимо, чтобы проверяющему показалось, что на складе как можно меньше ящиков (но достаточно для документов), иначе, отдав "лишние" ящики, завхоз ещё больше уменьшит свой и так скудный запас продуктов. Кроме того, если придётся отдавать "лишние" ящики, то для этого должно хватить тех ящиков, которые есть – лишние продукты взять неоткуда.
Склад имеет форму прямоугольника размера `n\ times\ m`, разделённого на квадратные клетки. Каждая клетка либо содержит ящик с продуктами, либо пустая. Ходить на складе можно только по пустым клеткам, так как ящики достаточно высокие, и из-за них ничего не видно. Склад имеет единственный вход, находящийся на левой стороне левой верхней клетки.
Вы можете вывести любой способ расстановки ящиков, который минимизирует количество "лишних" ящиков. Кстати, не обязательно расставлять по складу все имеющиеся в наличии ящики – при необходимости ящики можно спрятать от инспектора на другом складе.
Первая строка ввода содержит четыре целых числа через пробел: `n`, `m` (`1\ ≤\ n,\ m\ ≤\ 1000`), `a`, `b` (`0\ ≤\ b\ ≤\ a\ ≤\ n*m`) – размеры склада, количество ящиков, которое должно быть по документам, и количество ящиков, которое есть на самом деле, соответственно.
Если инспекцию обмануть невозможно, выведите одно слово FAIL. Иначе выведите `n` строк по `m` символов в каждой – расположение ящиков. Символ '#' обозначает клетку с ящиком, символ '.' – пустую клетку.

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

2 2 3 2

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

.#
#.

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

3 4 12 5

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

#...
....
....

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

2 5 4 1

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

FAIL

printI. Пароходы

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

Остап и Ипполит Матвеевич хотят перебраться с одного парохода на другой, плывущий ему навстречу. Остап измеряет с помощью астролябии расстояние между пароходами в разные моменты времени, чтобы узнать, насколько близко будут проходить пароходы, и можно ли будет доплыть до другого парохода на шлюпке.
В начальный момент времени `0` расстояние между кораблями было `R_0`, в момент времени `T_1` секунд расстояние стало равно `R_1`, в момент времени `T_2` секунд – `R_2`. Определите минимальное расстояние между кораблями, если корабли движутся с постоянной скоростью, не меняя курса.
В первой строке ввода находятся пять вещественных чисел `T_1`, `T_2`, `R_0`, `R_1`, `R_2` (`T_1<T_2`, `R_0>R_1>R_2`). Все числа находятся в промежутке `(0,1000]` и измерены с точностью `10^{-3}`.
Выведите минимальное расстояние с точностью `10^{-3}`, или `-1`, если в измерениях расстояний есть ошибка и решения не существует.

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

1.000 2.000 15.000 10.000 5.000

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

0.000

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

1 2 10 2 1

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

-1

printJ. Дворик

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

Шестиугольный дворик в театре Колумба замощен плитками в форме ромба трех различных цветов. Количества плиток разного цвета совпадают.

14355.png

Плитки должны быть ориентированы в соответствии со своим цветом. Разрешается за одну операцию вынимать три плитки разных цветов, расположенные в форме шестиугольника, и, не поворачивая их, переложить так, как показано на рисунке.

14354.png

Напишите программу, определяющую минимальное количество операций, чтобы сложить новый заданный узор.
Первая строка ввода содержит размер стороны шестиугольного дворика `N` (`1\ ≤\ N\ ≤\ 500`). Далее следует `2*N` строк, описывающих начальное расположение плиток в дворике, каждая строка описывает цвета горизонтальной полосы из треугольников. Далее следует пустая строка, затем `2*N` строк, описывающих желаемое расположение плиток в дворике.
Вывести одно целое число – минимальное количество операций.

Пример ввода (соответствует рис.)

2
  1 1 2 3 3
2 3 3 2 1 1 2
2 1 1 2 3 3 2
  3 3 2 1 1

  1 1 1 1 2
2 3 3 3 3 2 2
2 2 3 3 3 3 2
  2 1 1 1 1

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

2

printK. Box Building

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

Any square is a rectangle, any rectangle is a quadrangle, and any quadrangle is composed of four sides. But not all rectangles are squares, not all quadrangles are rectangles, and not all sets of four sides are quadrangles.
Elly has four pieces of plank and she wants to build a square box for her mexican jerbo. If not, she wants to build a rectangular box. If not, she wants to build a quadrangular box at least.
The first line of the input contains four positive integer numbers, between 1 and `2^30` – the length of sides.
The output should consist of a line with the text "square", "rectangle", "quadrangle" or "none", if four sides can form a square, a rectangle, a quadrangle or none, respectively.

Sample Input #1

10 8 7 6

Sample Output #1

quadrangle

Sample Input #2

9 1 9 1

Sample Output #2

rectangle

Sample Input #3

29 29 29 29

Sample Output #3

square

Sample Input #4

5 12 30 7

Sample Output #4

none
loading