Начало
Соревнования
Задачи командных соревнований 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/400ms, память – 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/400ms, память – 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