游客 注册 | 登录
中文 | En

1711 - 麦香牛肉

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

农夫约翰的奶牛几乎要武装暴动，因为他们听说麦当劳要推出新产品麦香牛肉。奶牛们要尽力阻止这种产品的上市。他们研究了一种“劣等包装”策略。奶牛们说： “如果麦香牛肉有3块，6块以及10块装这三种，那么想买 1, 2, 4, 5, 7, 8, 11, 14, 或17块牛肉的顾客就得不到满足了。劣等的包装，劣等的产品！” 帮助奶牛们。给出N (不同包装的种类数, 1 <= N <= 10)，以及N个正整数 (1 <= i <= 256)表示每种包装中牛肉数量，输出最大的不能买到的牛肉数量。如果任何消费要求都可以被满足或不能满足的牛肉数量没有上界，则输出0。最大的可能值 （如果存在）不超过2,000,000,000。

题目输入

　　第1行: N

　　第2..N+1行: 一个盒子里的牛肉数量。

题目输出

输出题目中要求的单个整数。

输入/输出样例

输入格式

3 
3 6 10

输出格式

17

C语言解答

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char a[256*256];
int b[305];
int gcd(int a, int b){
if(a % b)return gcd(b,a%b);
else return b;
}

int cmp(const void *a, const void *b){
return (*(int*)a)-(*(int*)b);
}

int main()
{
    int n;
    while(scanf("%d",&n) != EOF){
        char ff = 0;
        int gys;
        for(int i = 1;i <= n; i++){
            scanf("%d",&b[i]);
            if(b[i] == 1)ff = 1;
        }
        gys = gcd(b[1],b[2]);
        for(int i = 3;i <= n; i++){
            gys = gcd(gys,b[i]);
        }
        if(ff || gys != 1){
            printf("0\n");
            continue;
        }
        memset(a,0,sizeof(a));
        a[0] = 1;
        qsort(b+1,n,sizeof(int),cmp);
        int mm = b[n]*b[n];
        int mi = b[1];
        for(int i = mi;i <= mm; i++){
            for(int j = 1;j <= n;j ++){
                if(i >= b[j]){
                    if(a[i-b[j]]==1){
                        a[i] = 1;
                    }
                }
            }
        }
        int kk = 0;
        for(int i = mm;i >= 1; i--){
            if(a[i]==0){
                kk=i;
                break;
            }
        }
        printf("%d\n",kk);
    }

    return 0;
}

C++解答

#include<iostream>
#include<algorithm>
using namespace std;
const int N(70000);
int n,a[15];
bool f[N];
//ifstream cin("nuggets.in");
//ofstream cout("nuggets.out");
int gcd(int x,int y)
{
    int z;
    for (z=x%y;z;x=y,y=z,z=x%y);
    return y;
}
bool possible()
{
    if (n==1) return false;
    int t=a[0];
    for (int i=1;i<n;i++) t=gcd(t,a[i]);
    if (t==1) return true;
    else return false;
}
void solve()
{
    fill(f,f+N,false);    
    for (int i=0;i<n;i++) f[a[i]]=true;
    for (int i=1;i<N;i++)
    {
        for (int j=0;j<n;j++)
            if (a[j]<=i)
                if (f[i-a[j]])
                {
                    f[i]=true;
                    break;
                }
    }
    for (int i=N-1;i>0;i--)
        if (!f[i])
        {
            cout<<i<<endl;
            break;
        }
}
int main()
{    
    while (cin>>n)
    {
        fill(f,f+N,0);        
        for (int i=0;i<n;i++) cin>>a[i];
        if (!possible()) cout<<0<<endl;
        else solve();
    }
    return 0;
}
请先登陆