[蓝桥杯 2017 省 AB] 包子凑数

Luogu

IDLGP8646

Time1000ms

Memory256MB

DifficultyP3

2017数论背包 DP蓝桥杯省赛

小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有 $N$ 种蒸笼，其中第 $i$ 种蒸笼恰好能放 $A_i$ 个包子。每种蒸笼都有非常多笼，可以认为是无限笼。每当有顾客想买 $X$ 个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有 $X$ 个包子。比如一共有 $3$ 种蒸笼，分别能放 $3$ 、 $4$ 和 $5$ 个包子。当顾客想买 $11$ 个包子时，大叔就会选 $2$ 笼 $3$ 个的再加 $1$ 笼 $5$ 个的（也可能选出 $1$ 笼 $3$ 个的再加 $2$ 笼 $4$ 个的）。当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有 $3$ 种蒸笼，分别能放 $4$ 、 $5$ 和 $6$ 个包子。而顾客想买 $7$ 个包子时，大叔就凑不出来了。小明想知道一共有多少种数目是包子大叔凑不出来的。 ## Input 第一行包含一个整数 $N$。$(1 \le N \le 100)$。以下 $N$ 行每行包含一个整数 $A_i$。$(1 \le A_i \le 100)$。 ## Output 一个整数代表答案。如果凑不出的数目有无限多个，输出 `INF`。 [samples] ## Note 对于样例 $1$，凑不出的数目包括：$1,2,3,6,7,11$。对于样例 $2$，所有奇数都凑不出来，所以有无限多个。蓝桥杯 2017 省赛 A 组 H 题。

Samples

Input #1

2  
4  
5

Output #1

Input #2

2  
4  
6

Output #2

INF

API Response (JSON)

{
  "problem": {
    "name": "[蓝桥杯 2017 省 AB] 包子凑数",
    "description": {
      "content": "小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有 $N$ 种蒸笼，其中第 $i$ 种蒸笼恰好能放 $A_i$ 个包子。每种蒸笼都有非常多笼，可以认为是无限笼。 每当有顾客想买 $X$ 个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有 $X$ 个包子。比如一共有 $3$ 种蒸笼，分别能放 $3$ 、 $4$ 和 $5$ 个包子。当顾客想买 $11$ 个包子时，大叔就",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8646"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有 $N$ 种蒸笼，其中第 $i$ 种蒸笼恰好能放 $A_i$ 个包子。每种蒸笼都有非常多笼，可以认为是无限笼。\n\n每当有顾客想买 $X$ 个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有 $X$ 个包子。比如一共有 $3$ 种蒸笼，分别能放 $3$ 、 $4$ 和 $5$ 个包子。当顾客想买 $11$ 个包子时，大叔就...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments