Начало
Соревнования
Задачи командных соревнований PRIME TIME 2017
1. Метод дедукции
Разделение на 2 (или более) подзадачиОлимпиадные задачи на русском языке
| 02/04/2017 | Открытые командные соревнования по спортивному программированию "PRIME TIME" ( 1) |
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: интерактивная задача Вывод: интерактивная задача 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Ватсон хочет научиться методу дедукции. Для обучения Шерлок использует
перемешанную случайным образом последовательность целых чисел от 1 до `N`, состоящих
ровно из `K` бит. Шерлок убирает одно из чисел, а Ватсон вслепую пытается определить,
какое из чисел пропало. Ватсон может проверить равенство двух битов одного числа или
соответствующих битов двух чисел. Гарантируется, что Шерлок выбирает такие `N` и `K`, которые позволяют однозначно определить пропавшее число. Задача оказалась слишком сложной для Ватсона,
поэтому напишите программу, выполняющую эту работу.
Протокол взаимодействия
При старте программа получает в первой строке ввода два целых числа: начальное
количество чисел `N` (`3\ ≤\ N\ ≤\ 1000`) и количество бит `K` (`log_2\ N\ <\ K\ ≤\ 10`).
Программа должна вывести запрос или сообщить, какое число пропало. После вывода программа
должна сделать принудительную запись буфера вывода (в C++ это делает endl, в C нужно
использовать fflush(stdout), в Pascal – flush(output)).
Допускаются два типа запросов:
"B `a\ i\ j`" – сравнение двух битов одного числа, где `a` (`1\ ≤\ a\ ≤\ N-1`) – номер числа,
`i,\ j` (`0\ ≤\ i,\ j\ ≤\ K-1`) – номера битов;
"С `a\ b\ i`" – сравнение `i`-х битов двух чисел, где `a,\ b` (`1\ ≤\ a,\ b\ ≤\ N-1`) – номера
чисел, `i` (`0\ ≤\ i\ ≤\ K-1`) – номер бита. 0-й бит является самым младшим.
После запроса программа получает результат проверки и может сделать очередной запрос
или сообщить, что пропавшее число было определено с помощью сообщения
"A `x`", где `x` – число от 1 до `N`. Если программа не найдет пропавшее число
за 2111 запросов, то программа получает вердикт "Неверный ответ".
Пример ввода
3 2 0 1
Вывод программы
C 1 2 1 B 2 1 0 A 2
2. Шифр
Простые числа, разложение на множителиОлимпиадные задачи на русском языке
| 02/04/2017 | Открытые командные соревнования по спортивному программированию "PRIME TIME" ( 2) |
| 22/07/2019 | Лето 2019 - 10 (упрощенное) (E) |
Ограничения: время – 200ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Проникнув в логово преступной организации Мориарти, Шерлок обнаружил в пепельнице не сгоревший
обрывок бумаги, на котором были написаны какие-то цифры. Шерлок предположил, что Мориарти записал
на листке разложение на простые множители модуля для алгоритма шифрования RSA. Помогите Шерлоку
найти наименьшее простое число, начинающее с обнаруженных цифр.
Формат ввода
Первая строка ввода содержит одно число `N` (`1\ ≤\ N\ <\ 10^7`) – найденное Шерлоком число.
Формат вывода
Вывести наименьшее простое число, начинающее с `N`.
Пример ввода 1
133
Пример вывода 1
13309
Пример ввода 2
7
Пример вывода 2
7
3. Elephants
Жадные алгоритмыСортировка
Олимпиадные задачи на английском языке
| 02/04/2017 | Открытые командные соревнования по спортивному программированию "PRIME TIME" ( 3) |
| 04/07/2018 | Лето 2018 - 5 (упрощенное) (C) |
| 08/07/2020 | Лето 2020 - 4 (упрощенное) (C) |
Ограничения: время – 200ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
On the screen Moriarty began to sing nursery rhyme.
One elephant went out to play
Upon a Spiders web one day
He had such enormous fun
That he called for another elephant to come.
Two elephants went out to play
Upon a Spiders web one day
They had such enormous fun
That they called for another elephant to come…
Sherlock thought. "Suppose we have a set of `M` elephants, each one with a
weight `w_i`, and we know the maximum weight that the spider's web supports,
what is the largest number of elephants that we can put in the spider web
without breaking it?"
Input
The first line of input contains two integers `M` and `W`, the number of elephants
and the maximum weight that the spider web supports (`1\ ≤\ M\ ≤\ 1000` and `1\ ≤\ W\ ≤\ 10^8`).
The next line contains `M` numbers `w_i` representing the weight of each elephant (`1\ ≤\ w_i\ ≤\ 10^5`).
Output
Print a single line with the largest number of elephants that we can put in the spider's web without breaking it.
Sample Input 1
5 14 11 16 3 17 18
Sample Output 1
2
Sample Input 2
4 15 1 2 3 4
Sample Output 2
4
4. Теорема Мориарти
Простые числа, разложение на множителиОлимпиадные задачи на русском языке
| 02/04/2017 | Открытые командные соревнования по спортивному программированию "PRIME TIME" ( 4) |
Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Изощренный ум профессора Мориарти проявил себя не только в организации преступлений,
но и в решении математических проблем. Наибольшую известность получили его монографии
"Трактат о биноме" и "Планетная динамика". Также он вел переписку со многими математиками.
В номере гостиницы в Мейрингеме было найдено неоконченное письмо, адресованное Каталану.
В нем Мориарти писал "Существует бесконечно много таких простых `p`, что и `p+2` - тоже простое.
Я обнаружил поистине чудесное доказательство этого, но смогу записать его полностью только
после неотложной встречи". В номер он уже не вернулся.
Только в 2013 математик Чжан Итан сумел доказать, что существует бесконечное количество
пар простых чисел на расстоянии менее `7*10^7`. К настоящему времени эту оценку
расстояния удалось уменьшить до 246.
Напишите программу, подсчитывающую количество пар простых
чисел `(p_i,\ p_j)`, таких что `A\ ≤\ p_i\ <\ p_j\ \ ≤\ B` и `p_j-p_i\ ≤\ D`.
Формат ввода
Первая строка ввода содержит три целых числа – `A,\ B` (`1\ ≤\ A\ <\ B\ ≤\ 10^{14}`, `B-A\ ≤\ 10^7`)
и `D` (`2\ ≤\ D\ ≤\ 10^7`).
Формат вывода
Вывести одно целое число – количество пар простых чисел на расстоянии не
более `D` в диапазоне от `A` до `B`.
Пример ввода
1 10 2
Пример вывода
3
5. Acronym
Обработка строкОлимпиадные задачи на английском языке
| 02/04/2017 | Открытые командные соревнования по спортивному программированию "PRIME TIME" ( 5) |
Ограничения: время – 200ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Inspector Lestrade discovered that Moriarty’s criminal organization
has acronym ICPC, and he is trying to find the full name of the organization.
An acronym is a word or name formed as an abbreviation from the initial letters
in a phrase.
Input
Input consists of two lines:
- The acronym.
- The words separated by spaces.
The acronym and all the words consist of lowercase english letters.
The number of words is greater than 1 and less than 10.
This number may be different from the number of letters in the acronym.
Output
Print 'yes', if the acronym may have come from the given words. Print 'no' otherwise.
Sample Input
icpc ingenious criminal powerful company
Sample Output
yes
6. Прорыв
Задачи на построениеОлимпиадные задачи на русском языке
| 02/04/2017 | Открытые командные соревнования по спортивному программированию "PRIME TIME" ( 6) |
Ограничения: время – 200ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Мориарти скрылся в коридоре. Шерлок выстрелил ему вслед, но пуля только оставила трещины в пуленепробиваемом
стекле. Шерлок решил обдумать ситуацию. Стекло состоит из `N` рядов по `M` клеток, при выстреле добавляется
по одной трещине в пораженной клетке и в соседних с ней клетках (соседними считаются клетки, имеющие общую
сторону или угол). Чтобы стекло разрушилось целиком, каждый раз нужно стрелять в клетки, имеющие
наименьшее количество трещин. Если существует несколько клеток с минимальным количеством трещин, то
можно стрелять по любой из этих клеток. Как только в какой-то из клеток появится ровно `K` трещин, стекло
разрушится. Сколько потребуется выстрелов, чтобы разрушить стекло?
Формат ввода
Первая строка ввода содержит три целых числа – размеры стекла `N`, `M` (`1\ ≤\ N,M\ ≤\ 20`) и предел прочности
стекла `K` (`1\ ≤\ K\ ≤\ 20`).
Формат вывода
В первой строке вывести одно целое число `S` – минимальное количество выстрелов.
Далее вывести `S` строк – последовательность выстрелов, в каждой строке два целых числа `r` (`1\ ≤\ r\ ≤\ N`)
и `c` (`1\ ≤\ c\ ≤\ M`) – координаты поражаемой выстрелом клетки. Если существует несколько
минимальных вариантов, то можно вывести любой из них.
Пример ввода
4 5 4
Вывод программы
4 2 2 2 4 4 2 4 4
7. Два шарика мороженого
Использование теорем из геометрии, формулы ПикаОлимпиадные задачи на русском языке
| 02/04/2017 | Открытые командные соревнования по спортивному программированию "PRIME TIME" ( 7) |
Ограничения: время – 200ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Мориарти считает идеальным рожок с мороженым, в котором второй
шарик мороженого касается первого и стенок рожка. Помогите мороженщику выбрать радиус
второго шарика, если известен угол раствора конуса рожка и радиус первого шарика.
Формат ввода
Первая строка ввода содержит два целых числа – угол раствора рожка `A` (`1\ ≤\ A\ ≤\ 90`) и
радиус первого шарика `R` (`1\ ≤\ R\ ≤\ 100`).
Формат вывода
Вывести одно число – радиус второго шарика с точностью `10^{-6}`.
Пример ввода
60 10
Пример вывода
30
8. Числа с простой суммой цифр
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 02/04/2017 | Открытые командные соревнования по спортивному программированию "PRIME TIME" ( 8) |
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Кроме простых чисел-близнецов Мориарти интересовался числами, у которых сумма цифр является простым
числом. Про плотность распределения простых чисел известно, что она примерно обратно пропорциональна
логарифму. Для определения асимптотики распределения чисел, у которых сумма цифр является простым числом,
нужно выполнить несколько расчетов.
Напишите программу, которая подсчитает количество чисел с простой суммой цифр в заданном диапазоне.
Формат ввода
Первая строка содержит два целых числа `L` и `R` (`1\ ≤\ L,\ R\ ≤\ 10^{100}`)
Формат вывода
Вывести в первой строке одно целое число – количество чисел с простой суммой цифр в диапазоне от `L` до `R`.
Пример ввода
1 15
Пример вывода
7
9. Гиперкик
Предрасчеты, кэширование вычисленийОлимпиадные задачи на русском языке
| 02/04/2017 | Открытые командные соревнования по спортивному программированию "PRIME TIME" ( 9) |
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
В недалеком будущем искусственный интеллект "Ватсон" изобрел новый вид
транспорта – гиперкик. Перемещение по гиперкику происходит почти мгновенно, независимо от длины и
формы линии. Также очень быстро происходит пересадка с одной линии на другую. Но строительство станций
и линий гиперкика стоит дорого, поэтому станции будут построены только в городах. Стоимость строительства
линии прямо пропорциональна её длине. Ведение строительства затрудняет горный хребет, через который невозможно
построить линию, поэтому линии гиперкика должны идти в обход хребта. Для упрощения будем считать хребет
отрезком прямой линии. Необходимо связать все города страны линиями гиперкика таким образом, чтобы можно
было попасть из любого города в любой другой и стоимость строительства была минимальна.
Формат ввода
Первая строка ввода содержит пять целых чисел – количество городов `N` (`2\ ≤\ N\ ≤\ 3000`)
и координаты концов отрезка-хребта `X_1,\ Y_1,\ X_2,\ Y_2` (`0\ ≤\ X_1,\ Y_1,\ X_2,\ Y_2\ ≤\ 10000`).
Далее следует `N` строк, содержащих по два целых числа в диапазоне от 0 до 10000 – координаты городов.
Гарантируется, что координаты городов не совпадают и не попадают на хребет.
Формат вывода
Вывести одно число – минимальную суммарную длину линий с точностью `10^{-5}`.
Пример ввода
3 1 5 4 1 2 2 3 5 5 3
Пример вывода
7.30056
10. Сейф
Поиск в ширину (BFS)Олимпиадные задачи на русском языке
| 02/04/2017 | Открытые командные соревнования по спортивному программированию "PRIME TIME" (10) |
| 08/07/2020 | Летние сборы - 5 (A) |
| 07/07/2021 | Лето 2021-5 (D) |
| 10/12/2022 | «Базовая олимпиадная подготовка» (second level) - Поиск в ширину (BFS) (проводит novink) (E) |
Ограничения: время – 200ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Шерлок обнаружил за картиной сейф и хочет его открыть, чтобы узнать секретные планы Мориарти.
У сейфа есть дисплей, на котором выводится числовой код, но вместо обычной клавиатуры только четыре
кнопки: 2, 3, 5 и 7. Шерлок выяснил, что кнопка 2 делит число на дисплее на 2 нацело,
кнопка 3 – умножает на 3, кнопка 5 – увеличивает на 5, а кнопка 7 – уменьшает на 7. Все операции, кроме деления,
выполняются по модулю 101111. Также Шерлок нашел код, который должен высвечиваться на дисплее, чтобы
сейф открылся, У Шерлока мало времени, поэтому ему нужно найти минимальную последовательность нажатий
на кнопки, позволяющую получить код для открытия.
Формат ввода
Ввод содержит два целых числа – код на дисплее `K` и код для открытия `N` (`0\ ≤\ K,\ N\ <\ 101111`, `K≠N`).
Формат вывода
В первой строке вывести одно целое число – минимальное количество нажатий.
Во второй строке вывести найденную последовательность без пробелов. Если существует несколько
минимальных вариантов, то можно вывести любой из них.
Пример ввода
21 29
Вывод для примера
4 3275
11. Розыск автомобиля
Полный переборОлимпиадные задачи на русском языке
| 02/04/2017 | Открытые командные соревнования по спортивному программированию "PRIME TIME" (11) |
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Инспектор Лестрейд разыскивает автомобиль, скрывшийся с места ДТП. Свидетели
запомнили несколько букв и цифр, которые были в номере автомобиля.
Автомобилей в Лондоне уже достаточно много, поэтому Лестрейду
необходима помощь в поиске номера скрывшегося автомобиля.
Формат ввода
Первая строка ввода содержит одно целое число – количество
показаний свидетелей `K` (`1\ ≤\ K\ ≤\ 100`). Далее следует `K` строк,
содержащих непустые последовательности из цифр и прописных латинских
букв, длиной не более 100 символов. Следующая содержит
одно целое число – количество номеров `N` (`1\ ≤\ N\ ≤\ 10000`). Далее
следует `N` строк, содержащих непустые последовательности из цифр
и прописных латинских букв, длиной не более 100 символов.
Формат вывода
Вывести в первой строке количество номеров, соответствующих
показаниям свидетелей. Если найден только один подходящий номер,
то вывести во второй строке этот номер.
Пример ввода
2 A1 211 3 B211 AX112A 1A22
Пример вывода
1 AX112A
