Rikka with Coin

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 1722    Accepted Submission(s): 568

 

Problem Description

Rikka hates coins, and she used to never carry any coins with her. These days, Rikka is doing her summer internship abroad. Without mobile payment, Rikka has to face strange prices of commodities, and as a result of always using paper currency, she has to face mountainous coins on here table.

In the local currency system, there are 4 kinds of coins: 10 cents, 20 cents, 50 cents and 1 dollar. Up to now, Rikka has gained at least 10100 coins for each kind. 

Now, Rikka is going to have dinner in the canteen, and she decides to pay the bill only with coins. There are n different combos in the canteen and the price of the ith is wi cents. Rikka would like to choose one combo as dinner but she has not decided to choose which one yet. Therefore, she wants to take some coins so that whichever she chooses, she can always pay the bill without receiving any change.

Since Rikka hates coins, she wants to carry as few coins as possible with her. As it is generally known that Rikka is not good at math, she wants you to help her make the decision.

 

 

Input

The first line of the input contains a single integer T(1≤T≤500), the number of test cases.

For each test case, the first line contains a single integer n(1≤n≤100), the number of combos sold in the canteen.

The second line contains n positive integers w1,…,wn(1≤wi≤109), which represents the prices.

 

 

Output

For each test case, output a single line with a single integer which represents the minimum number of coins. If there is no valid solution, output −1.

Hint

In the first test case, one optimal solution is to bring one coin of 10 cents and two coins of 20 cents.

In the second test case, one optimal solution is to bring 5 coins of one dollar.

 

 

Sample Input

3 5 10 20 30 40 50 5 100 200 300 400 500 1 1

 

 

Sample Output

3 5 -1

 

 

Source

2019 Multi-University Training Contest 9

 

 

Recommend

chendu

 

 

Statistic | Submit | Discuss | Note

题目大意：有四种硬币，每种硬币无限，给出了n个数字，问能够凑出n个数字的最少硬币数是多少。

解题思路：比赛的时候想的差不多了，就是枚举10 20 50的数量，当时直接给了一个上限5.

无奈T了好几发。

其实 价值位10的硬币最多拿一个  因为两个肯定不如拿 1个10 一个20

20的硬币最多拿 4个

50的最多拿1个。

当时我们就直接对每个数字a/10取最大值，然后加上除以10后的数所需要的硬币数。

这样是不对的。

因为1个10 4个20 1个50 能够凑出来的最大的数是 140.

也就是说这些数有可能使我们100的数量减少1.

什么时候能减少1呢？就是a[i]%100+100能被凑出来的时候。

参考博客：TP

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp(x,y) make_pair(x,y)
typedef pair<ll,ll>pii;
#define pb(x) push_back(x)
#define fir first
#define sec second


int c[100];
int dp[150];
int a[105];

int n;

int solve(int x,int y,int z)
{
    int now=0;
    for(int i=1; i<=x; i++)c[++now]=10;
    for(int i=1; i<=y; i++)c[++now]=20;
    for(int i=1; i<=z; i++)c[++now]=50;
    memset(dp,0,sizeof(dp));
    dp[0]=1;
    for(int i=1; i<=now; i++)
    {
        for(int j=140; j>=0; j-=10)
        {
            if(dp[j]) dp[j]=1;
            if(j-c[i]>=0 && dp[j-c[i]] ) dp[j]=1;
        }
    }

    int res=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]<=140 && dp[a[i]])continue;
        if(a[i]%100<=40 && dp[a[i]%100+100])
        {
            res=max(res,a[i]/100-1);
            continue;
        }
        if(dp[a[i]%100])
        {
            res=max(res,a[i]/100);
        }
        else return 0x3f3f3f3f;
    }
    return res+x+y+z;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        int flag=0;
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
            if(a[i]%10)flag=1;
        }
        if(flag)
        {
            puts("-1");
            continue;
        }

        int ans=10000000;

        for(int i=0; i<=1; i++)
        {
            for(int j=0; j<=4; j++)
            {
                for(int k=0; k<=1; k++)
                {
                    ans=min(ans,solve(i,j,k));
                }
            }
        }
        printf("%d\n",ans);
    }
}