Задачи личных соревнований ИЕТН по спортивному программированию 2017

A. Ошибка копирования

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

При копировании условия задачи из браузера в текстовый редактор в некоторых числах может исчезнуть верхний индекс для показателя степени. Например, `10^9` может превратиться в 109. Петя пытается решить задачу, но не зная исходных ограничений, предполагает, что верхний индекс в последовательности цифр установлен так, чтобы число было максимальным из возможных.

Ввод содержит последовательность из трех цифр от 100 до 999 без пробелов.

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

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

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

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

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

9^99

Пояснение к примеру 2: среди вариантов 999, `99^9`, `9^{99}` наибольшим числом является `9^{99}`.

B. Ввод текста

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

Пете нужно ввести текст. При вводе текстовый редактор автоматически заменяет первую букву прописной в словах в начале текста и после символов '.', '!' и '?'. Но в тексте могут встречаться собственные имена и названия, и Пете при вводе первых букв таких слов нужно будет нажимать клавишу Shift.

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

Ввод содержит от 1 до 100 строк, длиной от 1 до 250 символов. В тесте могут встречаться только латинские буквы и знаки препинания. Слова состоят из букв и возможно знаков препинания и разделяются пробелами или символами перехода на новую строку. Символы '.', '!' и '?' могут появляться только в конце слов, а прописные латинские буквы могут появляться только в начале слова.

Вывести одно число – сколько раз Пете придётся нажать клавишу Shift.

Пример ввода

Dorothy lived in the midst of the great Kansas prairies, with Uncle Henry, 
who was a farmer, and Aunt Em, who was the farmer's wife. Their house was small, 
for the lumber to build it had to be carried by wagon many miles. Uncle Henry 
and Aunt Em had a big bed in one corner, and Dorothy a little bed in another corner.

Вывод для примера

Пояснение к примеру: Пете придётся нажимать клавишу Shift при вводе слов Kansas, Uncle, Henry, Aunt, Em, Henry, Aunt, Em, Dorothy.

C. Передача сообщений

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

В аудитории стоит ряд из `N` столов. За некоторыми из них сидят студенты. Петя сидит за первым столом, Маша – за `N`-м. Петя хочет незаметно от преподавателя передавать и получать сообщения от Маши. Для незаметной передачи разница между номерами столов не должна превышать `D`, т.е. записка может быть переброшена со стола `i` на стол `j` только если `|i-j|\ ≤\ D` и за обоими столами сидят студенты.

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

Первая строка ввода содержит два целых числа `N` (`2\ ≤\ N\ ≤\ 300\ 000`) и `D` (`1\ ≤\ D\ <\ N`). Вторая строка содержит `N` целых чисел от 0 до 1. Число 1 соответствует столу, за которым сидит студент, а число 0 – пустому столу.

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

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

4 1
1 0 1 1

Вывод для примера 1

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

5 2
1 0 0 0 1

Вывод для примера 2

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

8 2
1 1 0 0 1 0 0 1

Вывод для примера 3

D. Расшифровка сообщения

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

Чтобы перехваченную записку было сложно прочитать, Маша рисует буквы, закрашивая клетки в матрице 5x3, соответствующей одной букве, и не оставляя интервалов между буквами.

В сообщении могут встречаться только буквы A, B, C, D, E, которые изображаются следующим образом:

*** *** *** *** ***
*.* *.* *.. *.* *..
*** *** *.. *.* ***
*.* *.* *.. *.* *..
*.* *** *** *** ***

Напишите программу для расшифровки сообщения.

Ввод содержит 5 строк длиной от 3 до `3*2017` символов '*' и '.' – изображение букв в записке. Символ '*' изображает закрашенную клетку, а '.' – пустую.

Выведите расшифрованное сообщение.

Пример ввода

***************
*.**.**..*.**..
*******..*.****
*.**.**..*.**..
*.*************

Вывод для примера

ABCDE

E. Игра

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

Петя проходит видеоигру, в которой нет возможности сохранения. В игре `N` уровней, которые можно проходить в любом порядке. Каждый уровень можно проходить только один раз. За успешное прохождение `i`-го уровня начисляется `B_i` баллов. Если Петя не может пройти уровень, то игра заканчивается. Петя знает вероятность `P_i` успешного прохождения каждого уровня.

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

Первая строка ввода содержит `N` (`2\ ≤\ N\ ≤\ 100`) – количество уровней. Далее следует `N` строк, в каждой строке два целых числа – вероятность успешного прохождения уровня`P_i` в процентах (`1\ ≤\ P_i\ ≤\ 100`) и начисляемые за уровень баллы `B_i` (`1\ ≤\ B_i\ ≤\ 1000`).

Вывести `N` целых чисел в диапазоне от 1 до `N` – порядок прохождения уровней, при котором математическое ожидание суммарного количества баллов является максимальным. Если существует несколько вариантов, максимизирующих математическое ожидание, то можно вывести любой из них.

Пример ввода

Вывод для примера

2 3 1

F. Сумма несовершенства

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

Число называется совершенным, если оно равно сумме его делителелей, меньших самого числа. Например, число 28 является совершенным, так как 28=1+2+4+7+14.

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

Например, для 24 несовершенство равно |24-(1+2+3+4+6+8+12)|=12, а для 11 равно |11-1|=10.

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

Первая строка ввода содержит два целых числа `A` и `B` (`1\ ≤\ A\ ≤\ B\ ≤\ 10^7`).

Вывести одно целое число – сумму несовершенства.

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

1 9

Вывод для примера 1

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

24 24

Вывод для примера 2

Пояснение к примеру 1: 1+1+2+1+4+0+6+1+5=21

G. Фуршет

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

Маша знает 26 рецептов закусок, которые она обозначает буквами от a до z. Для фуршета она приготовила несколько закусок, выбирая перед началом приготовления очередной закуски совершенно случайным образом один из 26 рецептов, и расставила их на круглом столе в порядке приготовления.

Пришедшие гости подходят к любой точке стола и, двигаясь по часовой или против часовой стрелки, пробуют от 1 до `N` закусок подряд.

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

Первая строка ввода содержит `N` (`2\ ≤\ N\ ≤\ 100000`). Вторая строка ввода содержит последовательность из строчных латинских букв длиной от 2 до 50000 – порядок приготовления закусок, полученный указанным выше способом.

Вывести одно целое число – количество вариантов проб.

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

3
ab

Вывод для примера 1

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

3
erjej

Вывод для примера 2

Пояснение к примеру 1: возможны следующие пробы a, b, ab, ba, aba, bab.

Пояснение к примеру 2: возможны следующие пробы e, r, j, er, re, rj, jr, je, ej, erj, jre, rje, ejr, jej, eje, jer, rej.

H. Интервалы

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

Дан набор из `N` целых чисел `a_1,\ …,\ a_N`. Найти минимальную длину интервала `L`, для которой можно найти `N` целых чисел `x_1,\ …,\ x_N` таких, что каждый интервал `[\ x_i,\ x_i\ +\ L\ ]` содержит не менее `K` точек из набора `a_1,\ …,\ a_N`, в том числе `a_i`.

Первая строка ввода содержит два целых числа `N` и `K` (`1\ ≤\ K\ ≤\ N\ ≤\ 2*10^5`). Вторая строка содержит `N` целых чисел `a_1,\ ….\ a_N` (`-10^9\ ≤\ a_i\ ≤\ 10^9`).

Вывести одно целое число – минимальную длину интервала `L`.

Пример ввода

5 3
1 -2 10 5 4

Вывод для примера

Пояснение для примера: можно взять набор точек `x_1\ =\ -1,\ x_2\ =\ -2,\ x_3\ =\ 4,\ x_4\ =\ 0,\ x_5=0`.

I. Потерянная строка

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

Наибольшей общей подпоследовательностью (LCS) двух строк `A` и `B` называется строка, которая является подпоследовательностью обеих строк и имеет наибольшую длину среди таких строк. Например, строка "et" является LCS строк "petr"и "best". Может быть несколько различных строк, являющихся LCS.

Петя изучает алгоритм для нахождения LCS. Петя нашел длину LCS двух строк `A` и `B`, но потом потерял строку `B`. Строки `A` и `B` имели одинаковую длину и состояли из строчных латинских букв. Для заданной строки `A` и длины LCS `K` помогите Пете подобрать строку `B` такую, чтобы длина LCS строк `A` и `B` была равна `K`.

Первая строка ввода содержит два целых числа – длина строка `N` (`1\ ≤\ N\ ≤\ 2000`) и длина LCS `K` (`0≤\ K\ ≤2000`). Втроая строка ввода содержит `N` строчных латинских букв – строку `A`.

Вывести возможную строку `B` из `N` строчных латинских букв. Если Петя ошибся при вычислении длины LCS, то вывести сообщение WRONGANSWER.

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

4 2
petr

Вывод для примера 1

best

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

4 5
petr

Вывод для примера 2

WRONGANSWER

14/10/2017	Открытые личные соревнования по спортивному программированию (C)
04/07/2018	Лето 2018 - 5 (упрощенное) (B)
08/07/2019	Лето 2019 - 4 (упрощенное) (D)
08/07/2020	Лето 2020 - 4 (упрощенное) (B)

14/10/2017	Открытые личные соревнования по спортивному программированию (G)
15/07/2020	Летние сборы - 8 (E)

14/10/2017	Открытые личные соревнования по спортивному программированию (H)
03/07/2023	Лето 2023-4 простые (D)

Назад

Подразделы

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

Дата и время

Авторизация

Задачи личных соревнований ИЕТН по спортивному программированию 2017

A. Ошибка копирования

B. Ввод текста

C. Передача сообщений

D. Расшифровка сообщения

E. Игра

F. Сумма несовершенства

G. Фуршет

H. Интервалы

I. Потерянная строка