ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Сборники > Kovrov IT 2010 > задача:


H. Coins

Задачи сборника

• Задача 7
• A. Провайдеры
• B. Primes
• C. Bishops
• D. Unusual Lottery
• E. Polygons
• F. Liars and Knights
• G. Sequence
• H. Coins
• I. Galls village
• J. String manipulations

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 1500/2000/2000/2000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Автор: Игорь Андрианов, ВоГТУ.

Monetary system in Byteland contains of N kinds of coins of different denominations. During ATM software developing, there occured a problem to give out the requested sum with minimal quantity of coins. To solve it, the following greedy algorithm was introduced. At first, maximal quantity of coins of greatest denomination are taken. Then, for the remaining sum, maximal quantity of coins of lesser denomination (next one in descending order) are taken, and so forth.

For example, we have coins of denominations 1, 2 and 5. To pay sum of 13, two coins of 5 are taken, then one coin of 2 and then one coin of 1 are taken.

Your task is to define, if this algorithm works correctly in all cases for a given monetary system.

Input
The first line of the input contains N (1 ≤ N ≤ 1000). The second line contains N coin denominations in ascending order, separated by single spaces (1 ≤ Di ≤ 1000). The first denomination is always 1.

Output
If the introduced algorithm really gives out any sum with minimal quantity of coins, output 0. Otherwise output the minimal sum, that the algorithm will give out with non-minimal quantity of coins.

Input 1 Output 1
3
1 2 5
0
Input 2 Output 2
4
1 3 4 5
7

Для отправки решений необходимо выполнить вход.

www.contester.ru