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

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

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

Первая строка входного файла содержит одно натуральное число `n`. Вторая строка содержит `n` целых чисел (`1 ≤ x_i ≤ 10^9`) – длины палочек. Третья строка содержит `n` целых чисел (`1 ≤ y_i ≤ 10^9`) – длины коробок.

Вывести сообщение "YES", если палочки можно разложить обратно по коробкам, иначе вывести сообщение "NO".

1
5
6

YES

2
5 3
4 6

YES

2
3 7
4 6

NO

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

Необходимые подзадачи: 1.

Необходимые подзадачи: 1,2.

Сломанная волшебная палочка не слушалась Рона на уроке заклинаний и ударила в лоб профессору Флитвику. Теперь за свою неуклюжесть Рон должен сравнить части некоторого сложного заклинания на эквивалентность. Две последовательности букв `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".

avadakedavra
2
2 4 8 10
1 1 2 2

YES
NO

apparate
2
1 3 3 4
1 3 3 5

NO
NO

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

`1\ ≤\ |S|\ ≤\ 1000`, `1 ≤ n ≤ 1000`

`1\ ≤\ |S|\ ≤\ 50\ 000`, `1 ≤ n ≤ 50\ 000`

Необходимые подзадачи: 1.

При изучении арифмантики Гермиона обнаружила уникальную самоописывающую неубывающую последовательность натуральных чисел `G`, в которой число `n` входит `G(n)` раз.

`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\ ≤\ Q\ ≤\ 1000`, `1 ≤ n ≤ 10^6`

`1\ ≤\ Q\ ≤\ 10`, `1 ≤ n ≤ 10^9`

`1\ ≤\ Q\ ≤\ 10`, `1 ≤ n ≤ 10^18`

Необходимые подзадачи: 2.

`1\ ≤\ Q\ ≤\ 50\ 000`, `1 ≤ n ≤ 10^18`

Необходимые подзадачи: 1,2,3.