Назад
 Начало |
 Соревнования |
| 2018 |
Подразделы
Другие разделы
| Результаты регионального этапа олимпиады школьников по информатике в 2017-2018 учебном году |
| Задачи личного первенства ИЕТН по спортивному программированию 2018 |
Дата и время
25/04/2024 20:23:53
Задачи командных соревнований PRIME TIME 2018
1. Букет из простых чисел
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 07/04/2018 | Открытые командные соревнования по спортивному программированию "PRIME TIME" ( 1) |
Ограничения: время – 4s/4s, память – 512MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Финн нашёл в Цифровом мире полянку, на которой росло множество простых чисел и среди них
не было одинаковых. Финн решил собрать букет из простых чисел для Принцессы Бубльгум,
которой нравятся всякие научные штуки. Так как букет будет подарком на день рождения, то сумма
чисел в букете должна быть равна возрасту Принцессы. Кроме того, чтобы букет выглядел внушительно,
количество чисел в нём должно быть как можно больше.
Напишите программу, которая поможет Финну выбрать простые числа для букета.
Формат ввода
Первая строка ввода содержит одно целое число `T` (`1\ ≤\ T\ ≤\ 1000`) — количество тестовых случаев.
Далее следует `T` строк, каждая строка содержит одно целое число `N_i` (`7\ ≤\ N_i\ ≤\ 200000`).
Формат вывода
Для каждого тестового случая вывести строку, содержащую сначала целое число `K_i` — максимальное
количество простых чисел, которое нужно взять для составления букета, а затем `K_i` простых чисел в
порядке возрастания, сумма которых равна `N_i`. Если существует несколько вариантов для букета, то
можно вывести любой из них.
Пример ввода
2 828 11
Пример вывода
21 2 5 7 11 13 17 19 23 29 31 37 41 47 53 59 61 67 71 73 79 83 1 11
2. Shattered Cake
Преобразование или подсчет характеристики (например, сумма) заданной или вычисляемой последовательности
Олимпиадные задачи на английском языке
| 07/04/2018 | Открытые командные соревнования по спортивному программированию "PRIME TIME" ( 2) |
Ограничения: время – 250ms/500ms, память – 512MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Cinnamon Bun was carrying a rectangular cake to dinning room. On the way to the destination, he stumbled,
which shatters the cake in `N` rectangular pieces. Princess Bubblegum decides to order a replacement cake of the
same dimensions. Unfortunately, only the width `W` of the cake is known. But all pieces of the shattered
cake have been kept and measured.
The Princess asks for your help to find out the length `L` of the cake (`1\ ≤\ L\ ≤\ 10000`).
Input
The input consists of the following integers:
- on the first line, the width `W` of the cake (`1\ ≤\ W\ ≤\ 10000`);
- on the second line, the number `N` of shattered pieces (`2\ ≤\ N\ ≤\ 100000`);
- on each of the next `N` lines, the width `w_i` and length `l_i` of each piece (`1\ ≤\ w_i,\ l_i\ ≤\ max(W,L)`).
Output
The output should be the integer `L`, on a line by itself.
Sample Input
4 7 1 2 2 2 2 3 1 4 1 2 2 2 2 1
Sample Output
6
3. Dice
Теория вероятностейОлимпиадные задачи на английском языке
| 07/04/2018 | Открытые командные соревнования по спортивному программированию "PRIME TIME" ( 3) |
Ограничения: время – 250ms/500ms, память – 512MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
BMO and Jake play, roll the dice. It is a standard six-sided dice, with sides labelled 1 through 6. Jake the Dog changed the dice balance and some sides fall out more often than others.
For any dice, define the expected value of rolling the dice to be equal to the average of the values of the sides weighted by the probability of those sides coming up. Intuitively, this is the number you would get if you rolled the dice many times and averaged all the results together. A fair dice has an expected result of 3.5. That is, since all sides are weighed the same, they each have probability of 1/6, and we get:
`1*1/6\ +\ 2*1/6\ +\ 3*1/6\ +\ 4*1/6\ +\ 5*1/6\ +\ 6*1/6\ =\ 3.5`
BMO want make the dice more closely resemble a fair dice. To do so, BMO is going erase one side's label and replace it with a new number. But BMO don’t have a program for calculating.
You want to do so in such a way that
- The expected result of rolling the dice is 3.5, just like a fair dice, and
- The absolute value of difference between the old label and the new label on the side you change is as small as possible.
Input
The input consists of a single line with six decimal numbers, where the `i`th number (`i\ =\ 1..6`) is the probability that the side with value `i` is rolled. All of these numbers will be between 0.0 and 1.0, and they are guaranteed to sum to 1.0.
Output
Output two numbers on a single line: the label that BMO must erase and the label that he write in. Output the second number to exactly 6 decimal places, rounded.
Sample Input 1
0.16667 0.16666 0.16667 0.16667 0.16666 0.16667
Sample Output 1
1 1.000000
Sample Input 2
0.2 0.2 0.1 0.2 0.2 0.1
Sample Output 2
1 2.000000
Sample Input 3
0.0 1.0 0.0 0.0 0.0 0.0
Sample Output 3
2 3.500000
4. Острова
Аналитическое решение уравнений, неравенств, систем уравненийОлимпиадные задачи на русском языке
| 07/04/2018 | Открытые командные соревнования по спортивному программированию "PRIME TIME" ( 4) |
Ограничения: время – 250ms/500ms, память – 512MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Во время морского путешествия на яхте Финн проплыл мимо двух скал необычной формы. Финн хочет сфотографировать
эти скалы так, чтобы угол между этими скалами с точки съёмки был наибольшим.
Напишите программу, определяющую точку, с которой будет лучший ракурс для съёмки.
Формат ввода
Первая строка ввода содержит три числа – коэффициенты уравнения прямой `A` и `B` (`y\ =\ A\ x\ +\ B`), по которой движется яхта (`0.001\ ≤\ A,B\ ≤\ 1000`) и
расстояние между островами `C` (`1\ ≤\ C\ ≤\ 10`). Скалы находятся в координатах `(0,0)` и `(C,0)`.
Формат вывода
Вывести два вещественных числа – координаты точки съёмки с точностью `10^{-9}`.
Пример ввода
0.5 1.0 2.0
Пример вывода
0.529822128 1.264911064
5. Идеальные простые числа
Системы счисления с другим основаниемПростые числа, разложение на множители
Олимпиадные задачи на русском языке
| 07/04/2018 | Открытые командные соревнования по спортивному программированию "PRIME TIME" ( 5) |
Ограничения: время – 250ms/500ms, память – 512MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
БиМО нравятся простые числа. И так как БиМО рассматривает любые числа в двоичном представлении,
то идеальными среди простых чисел он считает такие, у которых количество нулей и количество единиц
также являются простыми числами.
Напишите программу, которая определяет тип числа, заданного в двоичной системе счисления.
Формат ввода
Первая строка ввода содержит одно целое число `T` (`1\ ≤\ T\ ≤\ 10`) – количество тестовых случаев.
Далее следует `T` строк, каждая строка содержит одно целое число `N_i` в двоичном представлении (`2\ ≤\ N_i\ <\ 2^{40}`).
Формат вывода
Для каждого тестового случая вывести строку, содержащую сначала целое число `N_i` в двоичном представлении,
а затем тип этого числа — одну из строк "is a composite number", "is a prime number" или "is a ideal prime number".
Пример ввода
3 11000 11 1101101
Пример вывода
11000 is a composite number 11 is a prime number 1101101 is a ideal prime number
6. Встреча
Кратчайшие пути из одной вершиныОлимпиадные задачи на русском языке
| 07/04/2018 | Открытые командные соревнования по спортивному программированию "PRIME TIME" ( 6) |
Ограничения: время – 500ms/1000ms, память – 512MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Финну нужно срочно встретиться с Принцессой Бубльгум, которая в данный момент совершает утреннюю
пробежку по круговому маршруту.
Напишите программу, которая найдет минимальное время до встречи Финна и Принцессы.
Формат ввода
Первая строка ввода содержит одно целое число — количество дорог `M` (`2\ ≤\ M\ ≤\ 100000`).
Далее следует `M` строк, содержащих по три целых числа — номера перекрестков `a_i` и `b_i`, которые
соединяет дорога, и длина дороги `c_i` (`1\ ≤\ a_i,\ b_i,\ c_i\ ≤\ 5000`, `a_i\ ≠\ b_i`).
Далее следует строка, содержащая два целых числа — скорость Принцессы `V_P` (`1\ ≤\ V_P\ ≤\ 100`) и
количество дорог `K` (`2\ ≤\ K\ ≤\ 1000`), по которым пробегает Принцесса.
Следующая строка содержит `K+1` целое число — последовательность номеров перекрестков в маршруте
Принцессе. Первый и последний номера в маршруте совпадают. В начальный момент
времени Принцесса находится на первом перекрестке маршрута. В следующей строке содержится
два целых числа — скорость Финна `V_F` (`1\ ≤\ V_F\ ≤\ 100`) и номер перекрестка `S` (`1\ ≤\ S\ ≤\ 5000`),
на котором находится Финн в начальный момент времени. Гарантируется, что маршрут Принцессы проходит
по существующим дорогам, между перекрестками не более одной дороги, и есть путь от `S` до маршрута Принцессы.
Формат вывода
Вывести одно вещественное число — время до встречи Финна с Принцессой с точностью `10^{-2}`.
Пример ввода
4 1 2 4 2 3 5 3 4 3 2 4 3 4 3 2 3 4 2 2 1
Пример вывода
2.50
7. Заполнение бассейна
Полный переборОлимпиадные задачи на русском языке
| 07/04/2018 | Открытые командные соревнования по спортивному программированию "PRIME TIME" ( 7) |
Ограничения: время – 250ms/500ms, память – 512MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Джейк должен наполнить бассейн водой из емкостей, стоящих на краю бассейна.
Емкости вмещают разный объем воды и вода в них имеет разную температуру. Джейк хочет,
чтобы бассейн был наполнен не менее чем наполовину, но также вода не должна вылиться из
бассейна из-за переполнения. С другой стороны, Джейк хочет, чтобы температура воды в
бассейне, получившаяся в результате смешивания, была как можно ближе к некоторой желательной
температуре `T` и отличалась от `T` не более чем на 5 градусов. Чтобы не запутаться в
вычислениях, Джейк выливает воду из только емкостей, стоящих подряд.
Напишите программу, которая поможет выбрать Джейку выбрать ряд емкостей для выливания в бассейн.
Формат ввода
Первая строка ввода содержит два целых числа — объем бассейна `V` (`100\ ≤\ V\ ≤\ 10000`) и
желаемую температуру `T` (`1\ ≤\ T\ ≤\ 100`). Вторая строка ввода содержит одно
число `N` (`1\ ≤\ N\ ≤\ 3000`) – количество емкостей. Далее следует `N` содержащих по два
целых числа — объем емкости `v_i` (`1\ ≤\ v_i\ ≤\ 1000`) и температуру воды в
ней `t_i` (`1\ ≤\ t_i\ ≤\ 100`).
Формат вывода
Вывести два целых числа — начальный и конечный номера емкостей, которые нужно вылить
Джейку. Если заполнить бассейн для указанных выше ограничений
невозможно, то вывести одно число `-1`. Если существует несколько вариантов,
минимизирующих разницу с желательной температурой `T`, то можно вывести любой из них.
Пример ввода 1
200 19 5 45 23 20 41 67 22 109 11 9 56
Пример вывода 1
2 4
Пример ввода 2
100 20 3 10 20 70 50 15 100
Пример вывода 2
-1
Примечание к примеру 1: Суммарный объем емкостей со 2 по 4 равен 20+67+109=196,
а результирующая температура будет равна (20*41+67*22+109*11)/196=17.821.
8. Сравнение ДНК
СортировкаОлимпиадные задачи на русском языке
| 07/04/2018 | Открытые командные соревнования по спортивному программированию "PRIME TIME" ( 8) |
Ограничения: время – 250ms/500ms, память – 512MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Принцесса Бубльгум создает новые виды конфетных людей с помощью редактирования базовой ДНК.
Она может заменить в ДНК одну аминокислоту на другую, удалить аминокислоту из ДНК или вставить новую.
В своих записях она нашла две последовательности действий по изменению ДНК и хочет определить,
приводят ли эти действия к одинаковым результатам или к разным.
Формат ввода
Первая строка ввода содержит одно целое число `N_1` (`0\ ≤\ N_1\ ≤\ 2000`) — количество действий в
первой последовательности действий по изменению ДНК, далее следует `N_1` строка, каждая из которых
содержит одну из трех команд:
- R `p` `x` – замена аминокислоты в позиции `p` на аминокислоту `x`;
- D `p` – удаление аминокислоты;
- I `p` `x` – вставка аминокислоты `x` в позицию `p`.
Здесь `p` — целое число от 1 до `10^{10}`, `x` – строчная латинская буква от 'a' до 'z'.
Далее следует строка, содержащая одно целое число `N_2` (`0\ ≤\ N_2\ ≤\ 2000`) — количество
действий во второй последовательности действий по изменению ДНК, далее следует `N_2` строка,
каждая из которых содержит одну из вышеуказанных команд.
Формат вывода
Вывести сообщение "Equal", если последовательности действий приводят к одному результату,
или сообщение "Different", если к разным.
Пример ввода 1
2 D 1 D 12 2 D 13 D 1
Пример вывода 1
Equal
Пример ввода 2
2 D 1 I 12 a 2 I 12 a D 1
Пример вывода 2
Different
Пример ввода 3
1 R 10 x 2 I 11 x D 10
Пример вывода 3
Equal
9. Тайная переписка
Поиск подстроки, префикс-функция, z-функцияОлимпиадные задачи на русском языке
| 07/04/2018 | Открытые командные соревнования по спортивному программированию "PRIME TIME" ( 9) |
Ограничения: время – 1s/2s, память – 512MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Ледяной Король похитил Принцессу и держит её в заточении. Принцесса пересылает регулярно сообщения
Финну, используя следующий простой шифр. Сначала Принцесса в каждом появлении секретного слова, которое
может вызвать гнев Ледяного Короля, заменяет `K` букв, идущих подряд, на случайные буквы.
При этом существует вероятность,
что буквы будут заменены на те же буквы. Затем она из текста убирает все пробелы и знаки препинания и
заменяет все буквы на строчные.
Ледяной Король перехватил сообщение Принцессы и хочет узнать, сколько раз секретное слово
возможно присутствует в сообщении.
Формат ввода
Первая строка ввода содержит одно целое число `T` (`1\ ≤\ T\ ≤\ 10`) — количество тестовых случаев.
Каждый тестовый случай состоит из трёх строк. Первая строка содержит сообщение `M`, перехваченное
Ледяным Королем (`1\ ≤\ |M|\ ≤\ 10^5`) . Вторая строка содержит секретное слово `S` (`1\ ≤\ |S|\ ≤\ |M|`).
Третья строка содержит одно целое число `K` (`1\ ≤\ K\ ≤\ |S|`) – количество заменяемых букв. Сообщение и
секретное слово содержат только строчные латинские буквы.
Формат вывода
Для каждого тестового случая вывести одно целое число — сколько раз секретное слово возможно встречается
в сообщении. Возможные расположения секретного слова могут накладываться.
Пример ввода
3 ilcweyoufinnwithflameloveprincess love 2 ahcahcahcahcahc aha 1 yuoyuoyuoyuoyuo you 2
Пример вывода
3 5 9
10. РБНФ
Грамматики, рекурсивный разборОлимпиадные задачи на русском языке
| 07/04/2018 | Открытые командные соревнования по спортивному программированию "PRIME TIME" (10) |
Ограничения: время – 250ms/500ms, память – 512MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Бетти изучает синтаксис сложного языка заклинаний. К сожалению, его синтаксис описан с
помощью расширенной формы Бэкуса-Наура (РБНФ), а Бетти пока понимает только описания, сделанные
с помощью простой БНФ. Правила РБНФ имеют следующий синтаксис:
rule = ?symbol? "=" variant-list ";"
variant-list = elem-list | variant-list "|" elem-list
elem-list = | elem-list elem
elem = ?symbol? | ?literal? | “{“ variant-list “}” | “(“ variant-list “)” | “[“ variant-list “]”
где ?symbol? — это последовательность латинских букв, цифр и символов _ и -(минус),
начинающаяся с буквы или символа _, ?literal? – последовательность непробельных символов в
кавычках, апострофах или между символами ??. Через | указываются возможные варианты
получения символа. Скобки { } означают повторение значения в скобках 0 или более раз.
Скобки [ ] означают повторение значения в скобках 0 или 1 раз. Скобки ( ) служат для группировки,
указания порядка применения операций.
В БНФ нет { }, ( ) и [ ], поэтому при переводе необходимо ввести вспомогательные символы и
правила, как показано в таблице ниже. Введённые вспомогательные символы должны начинаться со
знака подчеркивания, затем следует номер вспомогательного символа. Нумерация должна быть
сквозная, по всем правилам, начиная с 1. Меньший номер получает символ, соответствующий
более левой скобке.
| РБНФ | БНФ |
| a = { b } ; | a = _1 ; _1 = | _1 b ; |
| a = b ( c | d ) ; | a = b _1 ; _1 = c | d ; |
| a = [ b ] ; | a = _1 ; _1 = | b ; |
Напишите программу, которая переведёт описание синтаксиса языка заклинаний в БНФ.
Формат ввода
Ввод содержит не более 10 строк длиной до 1000 символов. Каждая строка содержит
правило в РБНФ. Лексемы в правиле разделены ровно одним пробелом. Гарантируется,
что в правилах нет символов, начинающихся с символа _.
Формат вывода
Для каждого правила выведите его представление в БНФ в аналогичной форме.
Правила для новых символов должны быть выведены после правил, в которых они
используются, в порядке возрастания номеров символов. Для каждой пары скобок должен быть добавлен ровно один вспомогательный символ и правило для него, как показано в таблице выше.
Пример ввода
cast = "cast" ?id? "(" [ a { "," a } ] ")" ;
a = ?id? | ?num? | a ( '+' | '-' ) a ;
Пример вывода
cast = "cast" ?id? "(" _1 ")" ;
_1 = | a _2 ;
_2 = | _2 "," a ;
a = ?id? | ?num? | a _3 a ;
_3 = '+' | '-' ;
11. В поисках Принцессы
Разбор случаевИнтерактивные задачи
Олимпиадные задачи на русском языке
| 07/04/2018 | Открытые командные соревнования по спортивному программированию "PRIME TIME" (11) |
Ограничения: время – 250ms/500ms, память – 512MiB Ввод: интерактивная задача Вывод: интерактивная задача
Послать решение Blockly Посылки Темы Где Обсудить (0)
Конфетный город разделен перпендикулярными улицами на квадратные кварталы. На каждом перекрестке
стоит банановый стражник. Финн хочет встретиться с Принцессой и расспрашивает стражников на перекрестках о
её местонахождении. Стражники знают о местоположении Принцессы, но путаются с направлениями, поэтому могут
показать на дорогу, ведущую в прямо противоположном направлении. Формально,
если `|X_i\ -\ X_P|\ >\ |Y_i\ -\ Y_P|`, где `(X_i,\ Y_i)` – координаты стражника, `(X_P,\ Y_P)` – координаты Принцессы,
то стражник может с равной вероятностью показать направление W (запад) или E (восток).
Если `|X_i\ -\ "XP"|\ <\ |Y_i\ -\ Y_P|`, то стражник может показать направление N (север) или S (юг).
Если `|X_i\ -\ X_P|\ =\ |Y_i\ -\ Y_P|`, то стражник может показать любое из четырех направлений.
Стражники не меняют своих указаний.
Гарантируется, что в начальный момент `1\ ≤\ |X_F\ -\ X_P|\ +\ |Y_F\ -\ Y_P|\ ≤\ 300`, где `(X_F,\ Y_F)` – координаты Финна.
Напишите программу, которая поможет Финну найти Принцессу, пройдя не более 2000 перекрестков.
Протокол взаимодействия
При старте программа получает строку, содержащую первое указание от стражника на местоположение принцессы.
Программа должна вывести строку, содержащую один символ N, S, W или E — в каком направлении нужно идти дальше.
После вывода программа должна сделать принудительную запись буфера вывода (в C++ это делает endl, в C
нужно использовать fflush(stdout), в Pascal – flush(output)). После вывода программа получает указания от
стражника на очередном перекрестке или сообщение "PRINCESS!", если Принцесса была обнаружена на этом перекрестке.
При появлении такого сообщения программа должна завершить работу. Если программа не найдет Принцессу
за 2000 перемещений, то программа получает вердикт WA "Неверный ответ".
Пример ввода
N S PRINCESS!
Вывод программы
S S
