7866.png
ЧЕЛЯБИНСК,ЮУРГУ,ИЕТН

Назад

images/home.png Начало
images/balloon.gif Соревнования
2018

Подразделы

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

Результаты регионального этапа олимпиады школьников по информатике в 2017-2018 учебном году
Задачи личного первенства ИЕТН по спортивному программированию 2018

Дата и время

19/12/2024 18:05:35

Авторизация

Имя:
Пароль:
Зарегистрироваться
Восстановить пароль
 

printЗадачи заочного тура личных соревнований 2018

printA. Беспорядок

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

Гарри взмахнул палочкой над головой и коробки слетели с полок лавки Олливандера. На полу образовалась куча мала из коробок и волшебных палочек разной длины.
Напишите программу, которая определит, можно ли разложить палочки обратно по коробкам. Палочка может поместиться в коробке, если длина палочки меньше или равна длине коробки.
Первая строка входного файла содержит одно натуральное число `n`. Вторая строка содержит `n` целых чисел (`1 ≤ x_i ≤ 10^9`) – длины палочек. Третья строка содержит `n` целых чисел (`1 ≤ y_i ≤ 10^9`) – длины коробок.
Вывести сообщение "YES", если палочки можно разложить обратно по коробкам, иначе вывести сообщение "NO".

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

1
5
6

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

YES

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

2
5 3
4 6

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

YES

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

2
3 7
4 6

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

NO
Описание подзадач и системы оценивания
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача 1 (15 баллов)
`1 ≤ n ≤ 2`
Подзадача 2 (35 баллов)
`1 ≤ n ≤ 100`
Необходимые подзадачи: 1.
Подзадача 3 (50 баллов)
`1 ≤ n ≤ 100\ 000`
Необходимые подзадачи: 1,2.

printB. Проверка заклинания

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

Сломанная волшебная палочка не слушалась Рона на уроке заклинаний и ударила в лоб профессору Флитвику. Теперь за свою неуклюжесть Рон должен сравнить части некоторого сложного заклинания на эквивалентность. Две последовательности букв `X` и `Y` являются эквивалентными, если буквы в `X` можно переставить таким образом, чтобы получилась последовательность `Y`.
Напишите программу, которая сравнивает эквивалентность подстрок некоторого заклинания.
Первая строка входного файла содержит одну строку `S`. Вторая строка содержит одно целое число `n` – количество запросов. Последующие `n` строк содержат по четыре целых числа `i_1,\ j_1,\ i_2,\ j_2` (`1\ ≤\ i_1\ ≤\ j_1\ ≤\ |S|`, `1\ ≤\ i_2\ ≤\ j_2\ ≤\ |S|`) – запрос на проверку эквивалентности.
Для каждого запроса вывести на отдельной строке сообщение "YES", подстрока с `i_1`-го по `j_1`-й символ заклинания `S` эквивалентна подстроке с `i_2`-го по `j_2`-й символ этого заклинания, иначе вывести сообщение "NO".

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

avadakedavra
2
2 4 8 10
1 1 2 2

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

YES
NO

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

apparate
2
1 3 3 4
1 3 3 5

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

NO
NO
Описание подзадач и системы оценивания
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача 1 (50 баллов)
`1\ ≤\ |S|\ ≤\ 1000`, `1 ≤ n ≤ 1000`
Подзадача 2 (50 баллов)
`1\ ≤\ |S|\ ≤\ 50\ 000`, `1 ≤ n ≤ 50\ 000`
Необходимые подзадачи: 1.

printC. Арифмантика

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

При изучении арифмантики Гермиона обнаружила уникальную самоописывающую неубывающую последовательность натуральных чисел `G`, в которой число `n` входит `G(n)` раз.
`n` 12345678910111213141516 …
`G(n)`1223344455 5 6 6 6 6 7 …
`G(1)=1`, так как при `G(1)>1` получаем противоречие в количестве 1 с `G(1)`. `G(2)=2`, так как при `G(2)=1` получим противоречие с `G(1)=1`, а при `G(2)>2` число 2 отсутствует в `G`, а должно входить ровно `G(2)` раз. Последующие элементы последоватетальности определяются по её предыдущим элементам.
Напишите программу, которая найдет значения `G(n)` для некоторых заданных `n`.
Первая строка входного файла содержит одно целое число `Q` – количество запросов. Последующие `Q` строк содержат одно целое число `n`.
Для каждого запроса вывести на отдельной строке значение `G(n)`.

Пример ввода

6
1
2
3
4
5
10

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

1
2
2
3
3
5
Описание подзадач и системы оценивания
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача 1 (20 баллов)
`1\ ≤\ Q\ ≤\ 1000`, `1 ≤ n ≤ 10^6`
Подзадача 2 (20 баллов)
`1\ ≤\ Q\ ≤\ 10`, `1 ≤ n ≤ 10^9`
Подзадача 3 (20 баллов)
`1\ ≤\ Q\ ≤\ 10`, `1 ≤ n ≤ 10^18`
Необходимые подзадачи: 2.
Подзадача 4 (40 баллов)
`1\ ≤\ Q\ ≤\ 50\ 000`, `1 ≤ n ≤ 10^18`
Необходимые подзадачи: 1,2,3.
loading