қазақша
русский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Ответ:
22.Вход:
1 1 1Ответ:
13.Вход:
4 5 2 1 3 15Ответ:
54.Вход:
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}$
комментарий/решение(1) олимпиада
Задача №2. (Склад ручек) Елдан работает охранником на складе с ручками. Все ручки на складе хранятся в запакованных коробках. Елдан заметил, что всего есть $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Ответ:
22.Вход:
1 1 1Ответ:
13.Вход:
4 5 2 1 3 15Ответ:
54.Вход:
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}$
комментарий/решение(1) олимпиада
Задача №3. (Склад ручек) Елдан работает охранником на складе с ручками. Все ручки на складе хранятся в запакованных коробках. Елдан заметил, что всего есть $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Ответ:
22.Вход:
1 1 1Ответ:
13.Вход:
4 5 2 1 3 15Ответ:
54.Вход:
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}$
комментарий/решение олимпиада