Skip to content

11295: 【原1295】nuggets

题目

题目描述

author: Xutong Chen 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1295

Description

大一鸣正在和主任大魔王进行斗争,他们选择用卡牌游戏决一胜负,这种卡牌很特殊,有N种牌,每种牌面的数字分别不同,但每种牌的数量无限。胜利规则是,给定一组牌,问是否存在这组牌无法加出来的数字。(例如N=3,牌组为面值为3、面值为6、面值为10的三张牌,则你不可能加出1、2、4、5等数字,而可以加出3、6、9、12等数字)如果有的话进一步问最大的无法加出来的数字是多少,请帮助帮助大一鸣获得胜利。

Input Format

第一行:牌组的种类数N(1<=N<=10)

第二行到第N+1行:每种牌的数值(1<=Ai<=256)

Output Format

只有一行:不能加出的最大数字或0(所有数字都能加出来或者能加出来的数字没有上限)

Sample Input

3
3
6
10

Sample Output

17

Hint

答案不超过100000

yyong119's solution

#include <cstdio>
#define MAX_T 1010000
#define MAX_N 15
using namespace std;

bool possible[MAX_T];
int card[MAX_N], n;

int main(){
    scanf("%d", &n);
    for (register int i = 0; i < n; ++i) {
        scanf("%d", &card[i]);
        if (card[i] == 1) {
            printf("0\n");
            return 0;
        }
        possible[card[i]] = 1;
    }
    for (register int i = 0; i < MAX_T; ++i)
        if (possible[i])
            for (register int j = 0; j < n; ++j)
                possible[i + card[j]] = 1;
    register int i;
    for (i = 1000000 ;possible[i]; --i);
    if (i > 100000) printf("0\n");
    else printf("%d\n", i);
    return 0;
}