10-11 класс

(Қаламдар қоймасы) Елдан қаламдары бар қоймада күзетші болып жұмыс істейді. Қоймадағы барлық қаламдар қораптарда сақталады. Елдан қораптардың $n$ типі бар екенін және $i$ типті қорапта $a_i$ қалам бар екенін байқады. Қоймада қораптың әрбір типінен өте көп дана бар ($10^{12}$-нен көп). Көп ұзамай жүк машинасы дүкенге $s$ қаламды алып кету үшін келу керек. Елдан дүкенге қанша қалам қажет екендігі туралы хабардар болмады, бірақ ол қажетті қаламның саны $x$-тен артық емес екенін біледі. Сондықтан, ол қаламдардың $1$-ден $x$-ке дейінгі кез келген санын қораптарды ашып отырмай тез бере алатындай, қораптардың ең санын тапқысы келеді. Елданға қораптардың ең аз санын есептеуге немесе оның мүмкін емес екенін табуға көмектесініз.

Кіріс деректер форматы:

Бірінші қатарда $n$ саны берілген. Екінші қатарда бос орын арқылы әр түрлі $n$ сан $a_1, a_2, \dots, a_n$ берілген. Үшінші қатарда $x$ саны берілген. Барлық берілетін сандар бүтін және оң.

Шығыс деректер форматы:

Есептің жауабын шығарыңыз.

Мысалдар:

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$ типті бір, жалпы екі қорап $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$ типтері сәйкесінше бес қорап береді.
Төртінші мысалда Елдан екі қаламды алатындай ешқандай тәсілмен қораптарды таңдай алмайды.

Бағалау:

Есеп 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;
}
/*
Прострессил решение с авторским всё выдавало правильно.
*/