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

Назад

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

Подразделы

2405. Последовательность
2404. Искусственное освещение
2403. Школьный автобус
2402. Работа для Золушки
2401. Supermind
2400. Делёж
2399. Карты, замок, два сапога
2398. Средний балл
2397. Накопление

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

Результаты регионального этапа олимпиады школьников по информатике в 2017-2018 учебном году

Дата и время

18/04/2024 18:43:21

Авторизация

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

printЗадачи личного первенства ИЕТН по спортивному программированию 2018

printA. Накопление

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

Вернувшись после месяца отдыха в деревне у папы Карло, Буратино решил в следующий отпуск поехать на морской курорт. Для поездки ему необходимо накопить `Y` золотых. Буратино решил откладывать по `X` золотых каждый месяц и класть их на накопительный счет с фиксированным доходом в банке "Поле чудес", чтобы через 11 месяцев у него на счету получилась сумма не менее `Y` золотых. На каждый золотой на счету за месяц начисляется доход `K` медяков (100 медяков = 1 золотой), при этом доход не учитывается при начислении дохода в следующие месяцы.
Определите минимальную сумму, которую нужно ежемесячно откладывать Буратино, чтобы накопить на поездку. Например, если Буратино откладывать по 8 золотых, то на первые 8 золотых, положенных на счет с доходом 1 медяк, за 11 месяцев будет начислен доход 88 медяков, на следующие 8 золотых – 80 медяков, на следующие 8 – 72 медяка и так далее. Добавив в 12-й раз на счет 8 золотых, Буратино получит 96 золотых накоплений и 528 медяков дохода, т.е. 101 золотой и 28 медяков.
Первая строка ввода содержит два целых числа – стоимость поездки `Y` (`100\ ≤\ Y\ ≤\ 10^6`) и доход в медяках на каждый золотой за месяц `K` (`1\ ≤\ K\ ≤\ 10`).
Вывести одно целое число `X` – минимальную сумму в золотых, которую нужно ежемесячно откладывать Буратино.

Пример ввода

100 1

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

8

printB. Средний балл

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

Незнайка получил `N` оценок по математике и хочет найти свой средний балл. Он знает, что среднее для двух чисел можно вычилить по формуле `(a+b)/2`, но не знает, как это сделать для нескольких чисел, поэтому он выбирает любые два числа из списка оценок и заменяет их на среднее значение. После `N-1` шагов у Незнайки остается одно число, которое он считает средним баллом.
Определите, какой максимальный средний балл может получить Незнайка, если будет вычислять его таким образом.
Первая строка ввода содержит одно целое число – количество оценок `N` (`1\ ≤\ N\ ≤\ 20`). Далее следует `N` строк, в каждой строке по одному целому числу от 1 до 5 – оценки Незнайки.
Вывести одно число – максимальный средний балл, который может получить Незнайка с точностью `10^{-6}`.

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

3
5
5
4

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

4.750000

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

4
4
2
5
2

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

4.000000

printC. Карты, замок, два сапога

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

Кот в сапогах пытается выиграть в карты замок у Людоеда. Для этого Кот должен набрать из колоды карты с суммой значений равной 21 или больше, чем у Людоеда, но при этом не более 21. В колоде 52 карты, по 4 карты с номиналами от 2 до 10, которые имеют значение равное номиналу, 4 валета (J), 4 королевы (Q) и 4 короля (K), которые имеют значение 10, и 4 туза (A), которые которые имеют значение 11. Кот решил брать новую карту из колоды только в том случае, если вероятность получить карту со значением, при котором общая сумма не будет превышать 21, будет выше, чем вероятность получить карту со значением, при котором сумма станет больше 21.
Первая строка ввода содержит одно целое число – количество уже взятых карт `N` (`1\ ≤\ N\ ≤\ 10`). Далее следует `N` строк, в каждой строке содержится целое число от 1 до 10 или буквы J, Q, K или A – номинал карты.
Вывести сообщение LOSE, если сумма значений карт больше 21, сообщение WIN, если сумма значений равна 21, сообщение STOP, если вероятность получить карту со значением, при котором сумма станет больше 21, выше, чем вероятность получить сумму карт меньшую и равную 21, сообщение TAKE, если вероятность получить сумму карт меньшую и равную 21 выше, или сообщение EQUAL, если эти вероятности равны.

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

6
2
3
3
2
2
3

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

STOP

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

1
K

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

TAKE

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

2
10
A

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

WIN

printD. Делёж

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

Али-баба решил раздать сокровища из пещеры разбойников бедным. Али-Баба достает предметы из пещеры по одному и отдает их самым бедным среди присутствующих (с наименьшей суммарной стоимостью уже полученных предметов). Если есть несколько человек с одинаковой минимальной суммарной стоимостью предметов, то очередной предмет отдается человеку с наименьшим номером среди них.
Напишите программу, которая определяет конечное распределение сокровищ среди бедняков.
Первая строка ввода содержит два целых числа – количество предметов в пещере `N` (`1\ ≤\ N\ ≤\ 10^5`) и количество бедняков `K` (`1\ ≤\ K\ ≤\ 10^5`). Вторая строка ввода содержит `N` целых чисел в диапазоне от 1 до 10000 – стоимость предметов в пещере в порядке распределения.
Для каждого человека вывести на отдельной строке по два целых числа – количество предметов, которое достанется ему при дележе, и суммарную стоимость предметов. В `i`-й строке нужно вывести результат для `i`-го человека.

Пример ввода

6 3
10 1 2 3 20 30

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

1 10
3 34
2 22

printE. Supermind

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

Шерлок тренирует свои логические способности с помощью усложненного варианта игры Mastermind. Вместо 4- или 6-разрядного числового кода Ватсон должен задумать перестановку из 52 строчных и прописных букв английского алфавита (каждая буква встречается в перестановке ровно один раз). Шерлок называет последовательность из 52 букв (при этом можно указывать одну букву несколько раз), а Ватсон сообщает, сколько букв оказалось на той же позиции, что и в задуманной перестановке. Шерлоку требуется не более 300 попыток, чтобы угадать перестановку, задуманную Ватсоном.
Напишите программу, которая продемонстрирует логические способности не хуже, чем у Шерлока.
Протокол взаимодействия
Программа должна вывести строку, содержащую символы ? и пробел, после которых указывается последовательность из 52 строчных и прописных букв английского алфавита. После вывода программа должна сделать принудительную запись буфера вывода (в C++ это делает endl, в C нужно использовать fflush(stdout), в Pascal – flush(output)). После вывода попытки программа получает строку, содержащую одно целое число – количество букв, находящихся на той же позиции, что и в задуманной перестановке. Когда последовательность будет угадана, программа должна вывести содержащую символы ! и пробел, после которых следует угаданная перестановка. Если программа не найдет перестановку за 300 попыток, то программа получает вердикт "Неверный ответ".

Вывод программы

? AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
? ABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
? ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
? ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxzy
! ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxzy

Ответы системы

1
2
50
52

printF. Работа для Золушки

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

На следующий вечер мачеха и сводные сестры снова собрались на бал.
- На этот раз у тебя будет больше работы, – сказала мачеха и разломала выпуклый многоугольник на мелкие кусочки. – Собери его к нашему приезду, а не то плохо тебе придется!
Золушка осталась одна. Но через минуту комната озарилась чудесным светом и появилась фея.
- Не будем терять времени, – сказала добрая фея, – нужно скорее собираться на бал, Золушка.
Одним взмахом волшебной палочки фея вызвала программиста и поручила ему написать программу, определяющую, как из отрезков четырех видов можно собрать выпуклый многоугольник. Имеются следующие отрезки:
- `a` горизонтальных отрезков единичной длины;
- `b` вертикальных отрезков единичной длины;
- `c` диагональных отрезков длины `sqrt{2}` под углом `45^o` к оси `X`;
- `d` диагональных отрезков длины `sqrt{2}` под углом `135^o` к оси `X`.
Первая строка ввода содержит четыре целых числа `a,\ b,\ c,\ d` (`0\ ≤\ a,\ b,\ c,\ d\ ≤\ 100`, `a+b+c+d\ ≥\ 3`) – количество отрезков каждого вида. Гарантируется, что выпуклый многоугольник из этого набора отрезков существует.
Вывести `a+b+c+d` строк, содержащих по два целых числа, не более 1000 по модулю – координаты точек, через которые проходят стороны выпуклого многоугольника, собранного из всех отрезков. Координаты точек должны быть перечислены против часовой стрелки. Если существует несколько вариантов построения многоугольника, то вывести любой из них.

Пример ввода

4 2 2 2

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

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

printG. Школьный автобус

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

Водитель школьного автобуса Отто живет на улице из `N` домов в доме с номером `K`. В 7:00 `M` школьников выходят из своих домов и ожидают некоторое время на улице, а Отто выезжает из своего дома. Если автобус не приезжает к моменту, когда школьник устанет ждать, он возвращается домой и ложится досыпать. Школьники отранжированы по важности (отличник имеет важность 100, хулиган – 1), и Отто может выбрать порядок, в котором он объезжает улицу, чтобы собрать школьников с максимальной суммарной важностью.
Напишите программу, которая поможет Отто спланировать маршрут автобуса.
Первая строка ввода содержит три целых числа – количество домов на улице `N`, номер дома `K`, в котором живет Отто, (`1\ ≤\ K\ ≤\ N\ ≤\ 1000`) и количество школьников `M` (`1\ ≤\ M\ ≤\ 100`). Далее следует `M` строк, в каждой строке по три целых числа – номер дома `A_i` (`1\ ≤\ A_i\ ≤\ N`, `A_i\ <\ A_{i+1}`, `A_i\ ≠\ K`), в котором живет школьник, важность его доставки в школу `B_i` (`1\ ≤\ B_i\ ≤\ 100`) и время ожидания автобуса `T_i` (`1\ ≤\ T_i\ ≤\ 2000`). За одну единицу времени Отто проезжает между двумя соседними домами. Посадка в автобус происходит мгновенно.
Вывести одно целое число – максимальную суммарную важность школьников, которых Отто сможет доставить в школу.

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

10 5 4
1 100 4
3 5 7
7 20 12
10 100 24

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

125

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

20 8 7
1 35 14
4 57 1
6 32 2
9 94 28
14 78 8
15 8 1
17 55 3

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

172
Пояснение к примеру 1:
Отто едет к дому №3, затем к дому №7 и к дому №10, затем везёт трех школьников в школу.
Отто не успевает доехать до дома №1 от стартового дома №5, чтобы забрать школьника.

Пояснение к примеру 2:
Отто едет по маршруту `8->9->14->`школа

printH. Искусственное освещение

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

Астронавт сажает растения на далекой планете. Растения необходимо освещать, но у астронавта только один источник света, поэтому астронавт после посадки старается разместить лампу таким образом, чтобы расстояние от лампы до самого дальнего растения было минимальным. Посадка выполняется в течение нескольких дней, каждый день астронавт высаживает дополнительно несколько растений.
Напишите программу, которая поможет определить, как расположить лампу после каждого дня.
Первая строка ввода содержит одно целое число `D` (`1\ ≤\ N\ ≤\ 10`) – количество дней высадки растений. Далее следует `D` блоков, в первой строке блока содержится одно целое число – количество посаженных в этот день растений `K_i` (`1\ ≤\ K_i\ ≤\ 5000`), далее следует `K_i` строк, в каждой строке по два целых числа в диапазоне от `-10^6` до `10^6` – координаты места посадки растений.
Для каждого дня вывести на отдельной строке три числа с точностью `10^{-5}` – координаты расположения лампы, при котором расстояние от источника света до самого дальнего саженца минимально, и само минимальное расстояние. При выборе места для лампы нужно учитывать все растения (высаженные в текущий день и в предыдущие дни).

Пример ввода

2
4
0 0
10 0
10 10
0 10
2
20 10
20 0

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

5.00000 5.00000 7.07107
10.00000 5.00000 11.18034

printI. Последовательность

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

Дана бесконечная арифметическая последовательность, элементы которой вычисляются по формуле `A_n\ =\ C*n\ +\ D`, где `n\ ≥\ 1`.
Найдите `M` различных элементов этой последовательности, номера которых не превышают `10^{15}`, таких, что у них совпадает сумма цифр в системе счисления по основанию B.
Первая строка ввода содержит четыре целых числа `C,\ D,\ B` и `M` (`1\ ≤\ C,\ D\ ≤\ 10000`, `2\ ≤\ B\ ≤\ 5000`, `1\ ≤\ M\ ≤\ 250000`).
Вывести `M` различных целых чисел – номера элементов последовательности, имеющих указанное свойство, в произвольном порядке.

Пример ввода

5 3 2 2

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

2 5
Пояснение к примеру:
`A_2\ =\ 5\ *\ 2\ +\ 3\ =\ 13\ =\ 1101_2`, `A_5\ =\ 5\ *\ 5\ +\ 3\ =\ 28\ =\ 11100_2`.
Сумма цифр обоих чисел в системе счисления по основанию 2 равна 3.
loading