Областная олимпиада по информатике, 2018 год, 10-11 класс

(Склад ручек) Елдан работает охранником на складе с ручками. Все ручки на складе хранятся в запакованных коробках. Елдан заметил, что всего есть $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

2.Вход:

1
1
1

Ответ:

1

3.Вход:

4
5 2 1 3
15

Ответ:

5

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 )

Комментарий/решение

показать/скрыть код

#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define ull unsigned long long
#define mp make_pair
#define si short int
#define speed ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pill pair<ll,ll>
#define f first
#define s second
#define pilc pair<ll,char>
#define all(a) (a).begin(),(a).end()
#define rep(s,e,step) for(int i = (s); i < (e) ; i += step)
#define vrep(s,e,step) for(int j = (s); j < (e) ; j += step)
#define ex exit(0) 
#define sz(a) (a).size()
#define triple pair<pill, ll>
#define pinode pair<node*, node*>
#define quadra pair<pill, pill>
#define ld long double
using namespace std;
 
const ll N = 1e6 + 1;
const ll M = 1e4 + 10;
const ll big = 1e17;
const ll hsh2 = 1964325029;
const long long mod = 1e9 + 7;
const long double EPS = 1e-10;
const ll block = 1e7;
const ll shift = 2e3;
const ld pi = acos(-1.0);

ll sum = 0;
ll n, x;
ll a[N];



int main() {
	speed;
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	sort(a + 1, a + n + 1);
	cin >> x;
	ll s = 0, cnt = 0;
	if(a[1] != 1)
		cout << -1, ex;
	for(int i = 1; i <= n; i++) {	
		if(a[i] > s + 1) {
		    if(a[i] > x) {
		    	ll y = x - s;
		    	cnt += (ll)((y + a[i - 1] - 1) / a[i - 1]);
		        s = x;
		     	break;
		    }
		    else {
				ll y = a[i] - (s + 1);
				ll z = (y + a[i - 1] - 1) / a[i - 1];
				cnt += z;
				s += z * a[i - 1];
			}			
		}
		while(i < n && a[i + 1] <= s + 1)
			i++;
		cnt++;
		s += a[i];
		if(s >= x)break;
	}
	if(s < x) {
		ll y = x - s;
		cnt += (ll)((y + a[n] - 1) / a[n]);
	}
	cout << cnt;
}
/*
Прострессил решение с авторским всё выдавало правильно.
*/