Andrey Kim

Есеп №1. (Қаламдар қоймасы) Елдан қаламдары бар қоймада күзетші болып жұмыс істейді. Қоймадағы барлық қаламдар қораптарда сақталады. Елдан қораптардың $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.Мысал:

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$ типті бір, жалпы екі қорап $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 )
комментарий/решение(1) олимпиада

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

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

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

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

Мысалдар:

1.Мысал:

2
2 1
3

Жауап:

2.Мысал:

1
1
1

Жауап:

3.Мысал:

4
5 2 1 3
15

Жауап:

4.Мысал:

2
5 3
2

Жауап:

-1

Түсініктеме:

Бағалау:

Есеп 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}$-нен көп). Көп ұзамай жүк машинасы дүкенге $s$ қаламды алып кету үшін келу керек. Елдан дүкенге қанша қалам қажет екендігі туралы хабардар болмады, бірақ ол қажетті қаламның саны $x$-тен артық емес екенін біледі. Сондықтан, ол қаламдардың $1$-ден $x$-ке дейінгі кез келген санын қораптарды ашып отырмай тез бере алатындай, қораптардың ең санын тапқысы келеді. Елданға қораптардың ең аз санын есептеуге немесе оның мүмкін емес екенін табуға көмектесініз.

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

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

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

Мысалдар:

1.Мысал:

2
2 1
3

Жауап:

2.Мысал:

1
1
1

Жауап:

3.Мысал:

4
5 2 1 3
15

Жауап:

4.Мысал:

2
5 3
2

Жауап:

-1

Түсініктеме:

Бағалау:

Есеп 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 )
комментарий/решение олимпиада