Andrey Kim

Задача №1. (Склад ручек) Елдан работает охранником на складе с ручками. Все ручки на складе хранятся в запакованных коробках. Елдан заметил, что всего есть

$n$ типов коробок, в коробке типа

$i$ лежит

$a_i$ ручек и на складе коробок каждого типа очень много (больше

$10^{12}$ ). Скоро должен приехать грузовик, чтобы забрать

$s$ ручек в магазин. Елдану не сообщили, сколько ручек требуется в магазине, но он знает, что это значение не больше

$x$ . Поэтому он хочет подготовить минимальное количество коробок, чтобы мог отдать любое количество ручек от

$1$ до

$x$ , не открывая коробок. Помогите Елдану посчитать, какое минимальное количество коробок ему нужно подготовить, либо сообщите, что это невозможно.

Формат входных данных:

В первой строке входных данных задано одно число

$n$ . Во второй строке заданы через пробел

$n$ различных чисел

$a_1, a_2, \dots, a_n$ . В третьей строке задано одно число

$x$ . Все числе во входных данных являются целыми положительными.

Формат выходных данных:

Выведите ответ на задачу, если ответа не существует выведите

$-1$ .

Примеры:

1.Вход:

2
2 1
3

Ответ:

2.Вход:

1
1
1

Ответ:

3.Вход:

4
5 2 1 3
15

Ответ:

4.Вход:

2
5 3
2

Ответ:

-1

Замечание:

В первом примере Елдан может подготовить коробки с типами

${a_1, a_2}$ .
При

$s = 1$ он отдаст одну коробку

$a_2$ .
При

$s = 2$ он отдаст одну коробку

$a_1$ .
При

$s = 3$ он отдаст две коробки

$a_1, a_2$ (2 + 1 = 3).
Во втором примере Елдан подготовит одну коробку

${a_1}$ .
В третьем примере Елдан может подготовить коробки с типами

${a_1, a_1, a_2, a_2, a_3}$ .
При

$s = 1$ он отдаст коробку

$a_3$ .
При

$s = 2$ он отдаст коробку

$a_2$ .
При

$s = 3$ он отдаст коробки

$a_2, a_3$ .
При

$s = 4$ он отдаст коробки

$a_2, a_2$ .
При

$s = 5$ он отдаст коробки

$a_2, a_2, a_3$ .
При

$s = 6$ он отдаст коробки

$a_1, a_3$ .
При

$s = 7$ он отдаст коробки

$a_1, a_2$ .
При

$s = 8$ он отдаст коробки

$a_1, a_2, a_3$ .
При

$s = 9$ он отдаст коробки

$a_1, a_2, a_2$ .
При

$s = 10$ он отдаст коробки

$a_1, a_1$ .
При

$s = 11$ он отдаст коробки

$a_1, a_1, a_3$ .
При

$s = 12$ он отдаст коробки

$a_1, a_1, a_2$ .
При

$s = 13$ он отдаст коробки

$a_1, a_1, a_2, a_3$ .
При

$s = 14$ он отдаст коробки

$a_1, a_1, a_2, a_2$ .
При

$s = 15$ он отдаст коробки

$a_1, a_1, a_2, a_2, a_3$ .
Обратите внимание, что в данном тесте есть и другие варианты выбрать коробки, например

${a_1, a_1, a_3, a_3, a_4}$ .
В четвертом примере Елдан не может выбрать какие-либо коробки, чтобы отдать две ручки.

Система оценки:

Задача содержит 50 тестов, каждая из которых весят 2 балла.
Ограничения которые присутствуют в тестах:

4 теста: $n = 1$ , $a_i \le 25, x \le 25$
6 тестов: $n \le 3$ , $a_i \le 25, x \le 25$
6 тестов: $n \le 5$ , $a_i \le 25, x \le 25$
14 тестов: $n \le 10^5, a_i \le 10^5, x \le 10^5$
20 тестов: $n \le 10^5, a_i \le 10^{12}, x \le 10^{12}$

( Andrey Kim )
комментарий/решение(1) олимпиада

Задача №2. (Склад ручек) Елдан работает охранником на складе с ручками. Все ручки на складе хранятся в запакованных коробках. Елдан заметил, что всего есть

$n$ типов коробок, в коробке типа

$i$ лежит

$a_i$ ручек и на складе коробок каждого типа очень много (больше

$10^{12}$ ). Скоро должен приехать грузовик, чтобы забрать

$x$ . Поэтому он хочет подготовить минимальное количество коробок, чтобы мог отдать любое количество ручек от

$1$ до

Формат входных данных:

В первой строке входных данных задано одно число

$n$ . Во второй строке заданы через пробел

$n$ различных чисел

$a_1, a_2, \dots, a_n$ . В третьей строке задано одно число

$x$ . Все числе во входных данных являются целыми положительными.

Формат выходных данных:

Выведите ответ на задачу, если ответа не существует выведите

$-1$ .

Примеры:

1.Вход:

2
2 1
3

Ответ:

2.Вход:

1
1
1

Ответ:

3.Вход:

4
5 2 1 3
15

Ответ:

4.Вход:

2
5 3
2

Ответ:

-1

Замечание:

В первом примере Елдан может подготовить коробки с типами

${a_1, a_2}$ .
При

$s = 1$ он отдаст одну коробку

$a_2$ .
При

$s = 2$ он отдаст одну коробку

$a_1$ .
При

$s = 3$ он отдаст две коробки

$a_1, a_2$ (2 + 1 = 3).
Во втором примере Елдан подготовит одну коробку

${a_1}$ .
В третьем примере Елдан может подготовить коробки с типами

${a_1, a_1, a_2, a_2, a_3}$ .
При

$s = 1$ он отдаст коробку

$a_3$ .
При

$s = 2$ он отдаст коробку

$a_2$ .
При

$s = 3$ он отдаст коробки

$a_2, a_3$ .
При

$s = 4$ он отдаст коробки

$a_2, a_2$ .
При

$s = 5$ он отдаст коробки

$a_2, a_2, a_3$ .
При

$s = 6$ он отдаст коробки

$a_1, a_3$ .
При

$s = 7$ он отдаст коробки

$a_1, a_2$ .
При

$s = 8$ он отдаст коробки

$a_1, a_2, a_3$ .
При

$s = 9$ он отдаст коробки

$a_1, a_2, a_2$ .
При

$s = 10$ он отдаст коробки

$a_1, a_1$ .
При

$s = 11$ он отдаст коробки

$a_1, a_1, a_3$ .
При

$s = 12$ он отдаст коробки

$a_1, a_1, a_2$ .
При

$s = 13$ он отдаст коробки

$a_1, a_1, a_2, a_3$ .
При

$s = 14$ он отдаст коробки

$a_1, a_1, a_2, a_2$ .
При

$s = 15$ он отдаст коробки

$a_1, a_1, a_2, a_2, a_3$ .
Обратите внимание, что в данном тесте есть и другие варианты выбрать коробки, например

${a_1, a_1, a_3, a_3, a_4}$ .
В четвертом примере Елдан не может выбрать какие-либо коробки, чтобы отдать две ручки.

Система оценки:

Задача содержит 50 тестов, каждая из которых весят 2 балла.
Ограничения которые присутствуют в тестах:

4 теста: $n = 1$ , $a_i \le 25, x \le 25$
6 тестов: $n \le 3$ , $a_i \le 25, x \le 25$
6 тестов: $n \le 5$ , $a_i \le 25, x \le 25$
14 тестов: $n \le 10^5, a_i \le 10^5, x \le 10^5$
20 тестов: $n \le 10^5, a_i \le 10^{12}, x \le 10^{12}$

( Andrey Kim )
комментарий/решение(1) олимпиада

Задача №3. (Склад ручек) Елдан работает охранником на складе с ручками. Все ручки на складе хранятся в запакованных коробках. Елдан заметил, что всего есть

$n$ типов коробок, в коробке типа

$i$ лежит

$a_i$ ручек и на складе коробок каждого типа очень много (больше

$10^{12}$ ). Скоро должен приехать грузовик, чтобы забрать

$x$ . Поэтому он хочет подготовить минимальное количество коробок, чтобы мог отдать любое количество ручек от

$1$ до

Формат входных данных:

В первой строке входных данных задано одно число

$n$ . Во второй строке заданы через пробел

$n$ различных чисел

$a_1, a_2, \dots, a_n$ . В третьей строке задано одно число

$x$ . Все числе во входных данных являются целыми положительными.

Формат выходных данных:

Выведите ответ на задачу, если ответа не существует выведите

$-1$ .

Примеры:

1.Вход:

2
2 1
3

Ответ:

2.Вход:

1
1
1

Ответ:

3.Вход:

4
5 2 1 3
15

Ответ:

4.Вход:

2
5 3
2

Ответ:

-1

Замечание:

В первом примере Елдан может подготовить коробки с типами

${a_1, a_2}$ .
При

$s = 1$ он отдаст одну коробку

$a_2$ .
При

$s = 2$ он отдаст одну коробку

$a_1$ .
При

$s = 3$ он отдаст две коробки

$a_1, a_2$ (2 + 1 = 3).
Во втором примере Елдан подготовит одну коробку

${a_1}$ .
В третьем примере Елдан может подготовить коробки с типами

${a_1, a_1, a_2, a_2, a_3}$ .
При

$s = 1$ он отдаст коробку

$a_3$ .
При

$s = 2$ он отдаст коробку

$a_2$ .
При

$s = 3$ он отдаст коробки

$a_2, a_3$ .
При

$s = 4$ он отдаст коробки

$a_2, a_2$ .
При

$s = 5$ он отдаст коробки

$a_2, a_2, a_3$ .
При

$s = 6$ он отдаст коробки

$a_1, a_3$ .
При

$s = 7$ он отдаст коробки

$a_1, a_2$ .
При

$s = 8$ он отдаст коробки

$a_1, a_2, a_3$ .
При

$s = 9$ он отдаст коробки

$a_1, a_2, a_2$ .
При

$s = 10$ он отдаст коробки

$a_1, a_1$ .
При

$s = 11$ он отдаст коробки

$a_1, a_1, a_3$ .
При

$s = 12$ он отдаст коробки

$a_1, a_1, a_2$ .
При

$s = 13$ он отдаст коробки

$a_1, a_1, a_2, a_3$ .
При

$s = 14$ он отдаст коробки

$a_1, a_1, a_2, a_2$ .
При

$s = 15$ он отдаст коробки

$a_1, a_1, a_2, a_2, a_3$ .
Обратите внимание, что в данном тесте есть и другие варианты выбрать коробки, например

${a_1, a_1, a_3, a_3, a_4}$ .
В четвертом примере Елдан не может выбрать какие-либо коробки, чтобы отдать две ручки.

Система оценки:

Задача содержит 50 тестов, каждая из которых весят 2 балла.
Ограничения которые присутствуют в тестах:

4 теста: $n = 1$ , $a_i \le 25, x \le 25$
6 тестов: $n \le 3$ , $a_i \le 25, x \le 25$
6 тестов: $n \le 5$ , $a_i \le 25, x \le 25$
14 тестов: $n \le 10^5, a_i \le 10^5, x \le 10^5$
20 тестов: $n \le 10^5, a_i \le 10^{12}, x \le 10^{12}$

( Andrey Kim )
комментарий/решение олимпиада