E. The Great Mixing

Codeforces

IDCF789E

Time1000ms

Memory256MB

Difficulty—

brute forcedfs and similardpgraph matchingsgraphsmathshortest paths

English · Original

Chinese · Translation

Formal · Original

Sasha and Kolya decided to get drunk with Coke, again. This time they have _k_ types of Coke. _i_\-th type is characterised by its carbon dioxide concentration . Today, on the party in honour of Sergiy of Vancouver they decided to prepare a glass of Coke with carbon dioxide concentration . The drink should also be tasty, so the glass can contain only integer number of liters of each Coke type (some types can be not presented in the glass). Also, they want to minimize the total volume of Coke in the glass. Carbon dioxide concentration is defined as the volume of carbone dioxide in the Coke divided by the total volume of Coke. When you mix two Cokes, the volume of carbon dioxide sums up, and the total volume of Coke sums up as well. Help them, find the minimal natural number of liters needed to create a glass with carbon dioxide concentration . Assume that the friends have unlimited amount of each Coke type. ## Input The first line contains two integers _n_, _k_ (0 ≤ _n_ ≤ 1000, 1 ≤ _k_ ≤ 106) — carbon dioxide concentration the friends want and the number of Coke types. The second line contains _k_ integers _a_1, _a_2, ..., _a__k_ (0 ≤ _a__i_ ≤ 1000) — carbon dioxide concentration of each type of Coke. Some Coke types can have same concentration. ## Output Print the minimal natural number of liter needed to prepare a glass with carbon dioxide concentration , or _\-1_ if it is impossible. [samples] ## Note In the first sample case, we can achieve concentration using one liter of Coke of types and : . In the second case, we can achieve concentration using two liters of type and one liter of type: .

Sasha 和 Kolya 再次决定用可乐醉酒。这次他们有 #cf_span[k] 种可乐。第 #cf_span[i] 种可乐的二氧化碳浓度为 #cf_span[a_i]。今天，在为温哥华的 Sergiy 庆祝的派对上，他们决定准备一杯二氧化碳浓度为 #cf_span[n] 的可乐。饮料还应该美味，因此玻璃杯中每种可乐的体积只能是整数升（某些类型可以不出现）。此外，他们希望最小化可乐的总体积。二氧化碳浓度定义为可乐中二氧化碳的体积除以可乐的总体积。当你混合两种可乐时，二氧化碳的体积相加，可乐的总体积也相加。帮助他们，找出制备一杯二氧化碳浓度为 #cf_span[n] 的可乐所需的最小自然数升数。假设朋友拥有每种可乐类型的无限量。第一行包含两个整数 #cf_span[n], #cf_span[k] (#cf_span[0 ≤ n ≤ 1000], #cf_span[1 ≤ k ≤ 10^6]) —— 朋友想要的二氧化碳浓度和可乐类型的数量。第二行包含 #cf_span[k] 个整数 #cf_span[a_1, a_2, ..., a_k] (#cf_span[0 ≤ a_i ≤ 1000]) —— 每种可乐类型的二氧化碳浓度。某些可乐类型可能具有相同的浓度。请输出制备一杯二氧化碳浓度为 #cf_span[n] 的可乐所需的最小自然数升数，如果不可能则输出 _-1_。在第一个样例中，我们可以使用一升 #cf_span[100] 类型和一升 #cf_span[500] 类型的可乐来实现浓度：#lt.eq(\frac{100 + 500}{1 + 1}, 300)。在第二个样例中，我们可以使用两升 #cf_span[100] 类型和一升 #cf_span[25] 类型的可乐来实现浓度：#lt.eq(\frac{2 \cdot 100 + 1 \cdot 25}{2 + 1}, 75)。 ## Input 第一行包含两个整数 #cf_span[n], #cf_span[k] (#cf_span[0 ≤ n ≤ 1000], #cf_span[1 ≤ k ≤ 10^6]) —— 朋友想要的二氧化碳浓度和可乐类型的数量。第二行包含 #cf_span[k] 个整数 #cf_span[a_1, a_2, ..., a_k] (#cf_span[0 ≤ a_i ≤ 1000]) —— 每种可乐类型的二氧化碳浓度。某些可乐类型可能具有相同的浓度。 ## Output 请输出制备一杯二氧化碳浓度为 #cf_span[n] 的可乐所需的最小自然数升数，如果不可能则输出 _-1_。 [samples] ## Note 在第一个样例中，我们可以使用一升 #cf_span[100] 类型和一升 #cf_span[500] 类型的可乐来实现浓度：#lt.eq(\frac{100 + 500}{1 + 1}, 300)。在第二个样例中，我们可以使用两升 #cf_span[100] 类型和一升 #cf_span[25] 类型的可乐来实现浓度：#lt.eq(\frac{2 \cdot 100 + 1 \cdot 25}{2 + 1}, 75)。

**Definitions** Let $n, k \in \mathbb{Z}$ such that $0 \le n \le 1000$ and $1 \le k \le 10^6$. Let $A = \{a_1, a_2, \dots, a_k\}$ be a sequence of integers where $0 \le a_i \le 1000$ for all $i$. **Decision Variables** Let $x_i \in \mathbb{Z}_{\ge 0}$ represent the integer quantity of the $i$-th component used, for $i \in \{1, \dots, k\}$. **Objective Function** Minimize total quantity $S$: $$ S = \sum_{i=1}^k x_i $$ **Constraints** 1. Non-empty set: $$ S \ge 1 $$ 2. Weighted average condition: $$ \frac{\sum_{i=1}^k x_i a_i}{S} = n \quad \iff \quad \sum_{i=1}^k x_i (a_i - n) = 0 $$ **Output** * If a solution exists, output $\min(S)$. * If no solution satisfies the constraints, output $-1$.

Samples

Input #1

400 4
100 300 450 500

Output #1

Input #2

50 2
100 25

Output #2

API Response (JSON)

{
  "problem": {
    "name": "E. The Great Mixing",
    "description": {
      "content": "Sasha and Kolya decided to get drunk with Coke, again. This time they have _k_ types of Coke. _i_\\-th type is characterised by its carbon dioxide concentration . Today, on the party in honour of Sergi",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF789E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Sasha and Kolya decided to get drunk with Coke, again. This time they have _k_ types of Coke. _i_\\-th type is characterised by its carbon dioxide concentration . Today, on the party in honour of Sergi...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Sasha 和 Kolya 再次决定用可乐醉酒。这次他们有 #cf_span[k] 种可乐。第 #cf_span[i] 种可乐的二氧化碳浓度为 #cf_span[a_i]。今天，在为温哥华的 Sergiy 庆祝的派对上，他们决定准备一杯二氧化碳浓度为 #cf_span[n] 的可乐。饮料还应该美味，因此玻璃杯中每种可乐的体积只能是整数升（某些类型可以不出现）。此外，他们希望最小化可乐的总体积。\n\n...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**\nLet $n, k \\in \\mathbb{Z}$ such that $0 \\le n \\le 1000$ and $1 \\le k \\le 10^6$.\nLet $A = \\{a_1, a_2, \\dots, a_k\\}$ be a sequence of integers where $0 \\le a_i \\le 1000$ for all $i$.\n\n**D...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments