CodeForces 349B--Color the Fence（贪心）

B. Color the Fence

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Igor has fallen in love with Tanya. Now Igor wants to show his feelings and write a number on the fence opposite to Tanya's house. Igor thinks that the larger the number is, the more chance to win Tanya's heart he has.

Unfortunately, Igor could only get v liters of paint. He did the math and concluded that digit d requires a_d liters of paint. Besides, Igor heard that Tanya doesn't like zeroes. That's why Igor won't use them in his number.

Help Igor find the maximum number he can write on the fence.

Input

The first line contains a positive integer v (0 ≤ v ≤ 10⁶). The second line contains nine positive integers a₁, a₂, ..., a₉ (1 ≤ a_i ≤ 10⁵).

Output

Print the maximum number Igor can write on the fence. If he has too little paint for any digit (so, he cannot write anything), print -1.

Examples

Input

5
5 4 3 2 1 2 3 4 5

Output

Input

2
9 11 1 12 5 8 9 10 6

Output

Input

0
1 1 1 1 1 1 1 1 1

Output

-1

思路：

位数越多当然数越大，首先要考虑的是每一位都一样位数最大的情况。

但若每一位都是一样，可能会有剩余的油漆。

所以我们要找到在此长度的情况下，数值的最大值

代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int main()
{
    int a[10], sum, minn, k, i, j, cnt, r;
    while (~scanf("%d", &sum))
    {
        minn = 1000000005;
        k = 0;
        for (i = 1; i <= 9; i++)
        {
            scanf("%d", &a[i]);
            if (a[i] < minn) //找出花费最小的颜料数
            {
                minn = a[i];
                k = i;
            }
            else if (a[i] == minn && k < i) //花费与最少的相等，自然取数字大的
                k = i;
        }
        if (sum < minn) //最少的花费都大于总颜料，自然不行
        {
            printf("-1
");
            continue;
        }
        cnt = sum / minn; //最小花费能得到的数字长度
        r = sum % minn;
        if (!r) //若总颜料能整出最小花费，全部输出这个数一定是最大
        {
            for (i = 1; i <= cnt; i++)
                printf("%d", k);
            printf("
");
            continue;
        }
        while (sum > 0) //总颜料还没用完，找出与最小花费长度相等的最大数
        {
            int x = 0;
            for (i = 1; i <= 9; i++)
            {
                int s = sum - a[i]; //减去这个数字的花费
                if (s < 0) //这个数字会使颜料用完，换下一个颜料
                    continue;
                if (s / minn == cnt - 1 && x < i) //减去该数字的花费之后，剩下的除以最小的长度是原来长度-1，必定是最符合的，在所有最符合的状况中找到最大的
                    x = i;
            }
            if (x)
            {
                sum -= a[x]; //放了一个数字，总花费减少
                cnt--;//长度减一
                printf("%d", x); //输出这个数字
            }
        }
        printf("
");
    }

    return 0;
}

CodeForces 349B--Color the Fence（贪心）

相关推荐