Задачи командных соревнований PRIME TIME 2019

1. Простая последовательность Фибоначчи

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

Джон заинтересовался разновидностью последовательности Фибоначчи, в которой каждый элемент является является суммой предыдущих, но если сумма является составным числом, то она делится на её наименьший простой делитель.

Для построения такой последовательности задаются два начальных числа `a_0` и `a_1`. Например, `a_0=1` и `a_1=1` получается следующая последовательность:

1, 1, 2, 3, 5, 4, 3, 7, 5, 6, 11, 17, 14, 31, 15, 23, 19, 21, 20, 41, 61, 51, 56, 107, 163, 135, 149, 142, 97, 239, 168, 37, 41, 39, 40, 79, 17, 48, 13, 61, 37, 49, 43, 46, 89, 45, 67, 56, 41, 97, 69, 83, 76, 53, 43, 48, 13, 61, 37, …

При сложении чисел 3 и 5 на 4-м шаге получается число 8, которое имеет делитель 2, поэтому `a_5`=4. При сложении чисел 5 и 4 на 5-м шаге получается число 9, которое имеет делитель 3, поэтому `a_6`=3.

В отличие от обычной последовательности Фибоначчи, в которой числа возрастают бесконечно, в простой последовательности Фибоначчи вскоре появляется цикл.

Напишите программу, которая поможет Джону найти циклы в простой последовательности Фибоначчи, которая начинается с заданных начальных чисел.

Формат ввода

Первая строка ввода содержит целое число `N` (`1\ ≤\ N\ ≤\ 1000`). Каждая из `N` последующих строк содержит два целых числа `a_0` и `a_1` (`1\ ≤\ a_0,\ a_1\ ≤\ 1000`) – начальные числа последовательности.

Формат вывода

Для каждой пары начальных чисел последовательности вывести на отдельной строке два числа `i` и `j` – индексы начала и конца цикла, т.е. наименьшие номера элементов последовательности, для которых `i<j` и `a_{i-1}=a_{j-1}` и `a_i=a_j`.

Пример ввода

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

38 56
1 2
1 137

2. PRIME

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

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

Напишите программу, которая считает, сколько максимально слов PRIME может получить Сова из последовательности букв на вывесках.

Формат ввода

Первая строка ввода содержит строку `S` из прописных латинских букв – последовательность букв. Длина строки не превышает 100000 символов.

Формат вывода

Вывести одно целое число – сколько слов PRIME можно получить из строки `S`.

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

EMIRP

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

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

PPPPRRRRRIIIIMMEEEEEE

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

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

PRIMERPARTIALMOUSE

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

3. Monster

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

The Alien Monster is a giant squid-like monster with one eye and dozens of long muscular tentacles. It was created by Ozymandias as part of his plan to save the world from a nuclear holocaust. He is going to teleport the Monster to New York at the point `(x,\ y)`, where it will destroy buildings with its tentacles.

Ozymandias wants to keep Manhattan that occupies an axis-aligned rectangle with diagonally opposite corners at the points `(x_1,\ y_1)` and `(x_2,\ y_2)`.

Write a program to help Ozymandias the length of the Monster's tentacles so that Manhattan remains intact.

Input

The input consists of a single line containing six space-separated integers `x`, `y`, `x_1`, `y_1`, `x_2`, and `y_2`, each in the range [-999,999].

It is guaranteed that `x_1` < `x_2` and `y_1` < `y_2`, and that `(x,y)` is strictly outside the axis-aligned rectangle with corners at `(x_1,\ y_1)` and `(x_2,\ y_2)`.

Output

Print the minimum distance from the Monster’s position to Manhattan, with a absolute error no more than 0.001.

Sample Input 1

7 3 0 0 5 4

Sample Output 1

2.000

Sample Input 2

6 0 0 2 7 6

Sample Output 2

2.000

Sample Input 3

3 -4 -3 -1 -1 2

Sample Output 3

5.000

4. Купол на Марсе

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

Доктор Манхэттен решил построить город на Марсе из `K` домов. Каждый дом должен быть построен по собственному уникальному проекту, который выбирается среди `N` проектов. Все проекты предусматривают строительство домов прямоугольной формы, но размеры домов различны – по `i`-му проекту дом имеет ширину `W_i` и высоту `H_i`. Дома строятся на одной линии, рядом друг с другом. После строительства город закрывается куполом, который имеет прямоугольную форму, и заполняется воздухом. Так как доставка воздуха с Земли слишком сложна, то нужно минимизировать размер купола.

Напишите программу, которая выберет `K` проектов для домов из `N` проектов таким образом, чтобы необходимый объем воздуха для заполнения купола (произведение ширины купола на его высоту) был минимальным.

Для первого примера минимальный объем (20 единиц) получается при выборе следующих 3 домов:

Формат ввода

Первая строка ввода содержит два целых числа – количество проектов `N` и количество домов `K` (`1\ ≤\ K\ ≤\ N\ ≤\ 1\ 000\ 000`). Следующие `N` строк содержат по два целых числа – ширина `W_i` и высота `H_i` дома по `i`-му проекту (`1\ ≤\ W_i,\ H_i\ ≤\ 1\ 000\ 000`). Все пары `(W_i,\ H_i)` различны.

Формат вывода

Вывести одно целое число – минимальный объем воздуха для заполнения купола.

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

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

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

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

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

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

Источник: COCI 2018/2019 contest #4

5. Результаты теста

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

Джон Остерман и Адриан Вейдт когда-то учились вместе в колледже. Однажды они сдавали тест, в котором нужно было отвечать на вопросы только "да" или "нет". Они сравнили свои ответы между собой, а затем узнали количество правильных ответов. Джон сказал свой результат Адриану, но Адриан решил преувеличить свои успехи, и вместо реального результата назвать максимальное возможное правильных количество в тесте, которое не противоречит их ответам на тесты и результатам Джона.

Напишите программу, вычисляющую максимальное количество правильных ответов у Адриана.

Формат ввода

Первая строка ввода содержит одно целое число `k` – количество правильных ответов у Джона. Вторая строка содержит последовательность из `n` букв T (ответ "да") и F (ответ "нет") – ответы Адриана. Третья строка содержит последовательность из `n` букв T и F – ответы Джона. Ограничения: `0\ ≤\ k\ ≤\ n`, `1\ ≤\ n\ ≤\ 1000`.

Формат вывода

Вывести одно целое число – максимальное количество правильных ответов, которое может быть у Адриана.

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

3
FTFFF
TFTTT

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

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

6
TTFTFFTFTF
TTTTFFTTTT

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

Источник: ICPC 2018 Mid-Central Regional

6. Маска Роршаха

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

Маска Роршаха покрылась пятнами, и Роршах решил сдать её в химчистку. Стоимость чистки зависит от количества пятен и их размеров.

Напишите программу, которая определяет количество пятен на маске, а также максимальный и минимальный размер пятен.

Формат ввода

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

Формат вывода

Вывести три целых числа – количество пятен на маске, минимальный размер пятна и максимальный размер пятна. Если пятен на маске нет, вывести три нуля.

Пример ввода

5 6
###...
...##.
#..#..
####.#
..##..

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

3 1 10

7. Secret Code

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

Rorschach saw how Ozymandias entered the code and turned on the countdown to teleport the Monster to New York. Rorschach noticed all the digits of the code, except one. To cancel the launch, he needs to enter the code again. Rorschach discovered that the system checks the code using Luhn's algorithm.

This algorithm confirms the correctness of the number using a control digit which is always the last digit in the number. Steps to determine the validity of a number are:

Starting from the second digit from the right in the number (tens of the number), double the value of every second digit to the left. If this product is greater than nine, then the digits of that product should be summed up.
Calculate the sum of all values obtained in the previous step.
The sum thus obtained should be multiplied by nine and it should be determined the remainder of division by ten.
If the resulting remainder is equal to the last digit of the number (unit), the number is considered valid.

E.g. code 79927398713 is considered valid because the end right digit 3 can be obtained from the remaining digits in the way described.

Code	7	9	9	2	7	3	9	8	7	1	3
Double every other	7	18	9	4	7	6	9	16	7	2	–
Sum	7	9 (1+8)	9	4	7	6	9	7 (6+1)	7	2	Sum=67 `(67*9)\ mod\ 10\ =\ 603\ mod\ 10\ =\ 3`

Write a program that loads the secret code as a string that consists only of digits and exactly one sign "x", and prints the smallest one-digit number which we can replace the sign "x" with so that the code is valid.

Input

In the first line there is an integer number `N` (`1\ ≤\ N\ ≤\ 100`), the length of secret code. In the second line there is a string of length `N` consisting of just digits “0”, “1”, “2”, “3”, “4”, “5”, “6”, “7”, “8”, “9” and exactly one sign "x".

Output

In the only line of the output it should be printed the required one-digit number.

Sample Input 1

11
7992739871x

Sample Output 1

Sample Input 2

5
x2464

Sample Output 2

Sample Input 3

10
93380x1696

Sample Output 3

Source: COCI 2018/2019 contest #6

8. Разработка планов

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

Озимандия разрабатывает планы по предотвращению ядерной войны. Начав с базовой идеи (плана №1), он вносит изменения в него изменения и уточнения, создавая новый план (№2). И так далее. На очередном шаге он берет один из имеющихся `N` планов, вносит в него изменения и получает следующий план (с номером `N+1`). Время от времени ему нужно определять, какой план был ближайшим общим предком для некоторой пары планов.

Напишите программу, которая отслеживает добавление новых планов и определяет общего предка двух планов по запросу.

Формат ввода

Первая строка ввода содержит одно целое число `Q` (`1\ ≤\ Q\ ≤\ 10^6`) – количество запросов. Далее следует `Q` строк, каждая строка содержит один из двух запросов.

+ `x` – добавить новый план на основе плана с номером `x`.
? `x\ y` – вывести ближайшего общего предка для планов с номерами `x` и `y`.

`x` и `y` – номера существующих планов к моменту выполения запроса.

Формат вывода

Вывести для каждого запроса ? одно целое число на отдельной строке – номер плана, который является ближайшим общим предком для обоих планов.

Пример ввода

14
+ 1
+ 1
+ 3
+ 2
+ 3
+ 4
? 7 6
+ 2
+ 4
? 5 8
? 2 8
? 5 2
+ 2
? 10 9

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

Рисунок для примера:

9. Сломанный пульт

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

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

Напишите программу, которая за оставшееся до взрыва время найдет способ восстановить схему.

Формат ввода

Первая строка ввода содержит два целых числа `N` и `M` (`2\ ≤\ N,\ M\ ≤\ 8`) – размеры схемы пульта управления. Далее следует `N` строк, в каждой строке `M` символов. Символ 'i' означает элемент, у которого один выход, символ 'r' означает элемент, у которого два выхода под углом 90 градусов, символ '-' означает элемент, у которого два выхода под углом 180 градусов, символ 'T' означает элемент, у которого три выхода, а символ '+' означает элемент, у которого четыре выхода.

Суммарное количество выходов у всех элементов равно `2*(N*M-1)`. Гарантируется, что, поворачивая элементы, их можно соединить между собой таким образом, что каждый выход у всех элементов будет соединен с каким-то выходом другого элемента и все элементы будут прямо или через другие соединены между собой. Между двумя элементами схемы будет ровно один путь по соединениям.

Формат вывода

Вывести `2*N-1` строк по `2*M-1` символов. Соединяемые элементы обозначить символом '*', соединения между ними – символами '-' и '|', пустое место – символом '.'. Если существует несколько вариантов соединения, то можно вывести любой из них.

Пример ввода

3 4
riii
T-+r
riri

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

*-*.*.*
|...|.|
*-*-*-*
|...|..
*-*.*-*

10. Сумма остатков

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

Доктору Манхэттену нужно вычислить сумму `sum_(i=1)^n\ ((p*i)\ mod\ q)`, где `q` – простое число, для некоторых значений `p`, `q` и `n`.

Напишите программу, вычисляющую эту сумму для нескольких наборов параметров.

Формат ввода

Первая строка ввода содержит одно целое число `T` (`1\ ≤\ T\ ≤\ 100000`) – количество тестовых случаев. Далее следует `T` строк, каждая строка содержит три целых числа `p`, `q` и `n` (`1≤\ p,\ q,\ n\ ≤\ 10^6`, `q` – простое число).

Формат вывода

Для каждого тестового случая вывести на отдельной строке одно целое число – вычисленную сумму.

Пример ввода

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

6
10
32

Источник: North American IPC 2019

11. Кусок торта

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

Лори приготовила торт на день рождения в форме выпуклого `N`-угольника.

Джон случайным образом выбрал две вершины многоугольника, которые не являются соседними, и отрезал кусок торта, проведя разрез через эти две вершины. Из двух образовавшихся частей торта он взял себе меньший кусок.

Напишите программу, вычисляющую математическое ожидание для размера куска торта, который отрезал себе Джон.

Формат ввода

Первая строка ввода содержит одно целое число `N` (`4\ ≤\ N\ ≤\ 2500`) – количество вершин в многоугольнике. Далее следует `N` строк, каждая строка содержит два вещественных числа `x_i` и `y_i` (`-10.0\ ≤\ x_i,\ y_i\ ≤10.0`) – координаты вершин в порядке обхода по часовой стрелке. Нет трех вершин, которые лежали бы на одной прямой.

Формат вывода

Вывести одно вещественное число – математическое ожидание для размера куска торта с точностью `10^{-8}`.

Пример ввода

4
0.0 0.0
1.0 1.0
2.0 1.0
1.0 0.0

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

0.50000000

07/04/2019	Открытые командные соревнования по спортивному программированию "PRIME TIME" ( 5)
14/07/2023	Лето 2023-9 (командное) (G)
12/07/2024	Лето 2024-9 (командное) (G)

07/04/2019	Открытые командные соревнования по спортивному программированию "PRIME TIME" ( 6)
16/09/2024	Остовные деревья, СНМ (проводит BOGAT) (E)

07/04/2019	Открытые командные соревнования по спортивному программированию "PRIME TIME" ( 8)
21/10/2024	LCA, обходы (проводит BOGAT) (B)

07/04/2019	Открытые командные соревнования по спортивному программированию "PRIME TIME" (11)
30/11/2023	Геометрия 2 (проводит BOGAT) (D)

Назад

Подразделы

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

Дата и время

Авторизация

Задачи командных соревнований PRIME TIME 2019

1. Простая последовательность Фибоначчи

2. PRIME

3. Monster

4. Купол на Марсе

5. Результаты теста

6. Маска Роршаха

7. Secret Code

8. Разработка планов

9. Сломанный пульт

10. Сумма остатков

11. Кусок торта