175. Counting Calories (Harder Version)

Codeforces

IDCF10269175

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Over the quarantine season, you decide to watch your weight by limiting yourself to a certain amount of calories a day. In this problem, you're given the number of calories of each food item in your house as input. You want to figure out the minimum number of food items that you need to eat in order to have eaten exactly $n$ calories. The first line of input contains a single positive integer $n$: the target number of calories. The second line of input contains a single positive integer $k$: the number of food items. The next $k$ lines each contain a single positive integer $c$: the number of calories of each food item. Output a single positive integer $m$: the minimum number of food items that you need to eat, in order to have eaten exactly $n$ calories. This problem is not as easy as you think it is. The solution to the easier version of the problem does not correctly solve the second example case. ## Input The first line of input contains a single positive integer $n$: the target number of calories.The second line of input contains a single positive integer $k$: the number of food items.The next $k$ lines each contain a single positive integer $c$: the number of calories of each food item. ## Output Output a single positive integer $m$: the minimum number of food items that you need to eat, in order to have eaten exactly $n$ calories. [samples] ## Note This problem is not as easy as you think it is. The solution to the easier version of the problem does not correctly solve the second example case.

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the target calorie count. Let $ k \in \mathbb{Z}^+ $ be the number of food items. Let $ C = \{c_1, c_2, \dots, c_k\} \subset \mathbb{Z}^+ $ be the multiset of calorie values per food item. **Constraints** 1. $ 1 \leq n \leq 10^4 $ 2. $ 1 \leq k \leq 100 $ 3. $ 1 \leq c_i \leq n $ for all $ i \in \{1, \dots, k\} $ **Objective** Find the minimum integer $ m \in \mathbb{Z}^+ $ such that there exist non-negative integers $ x_1, x_2, \dots, x_k $ with $$ \sum_{i=1}^k x_i c_i = n \quad \text{and} \quad \sum_{i=1}^k x_i = m, $$ and $ m $ is minimized.

API Response (JSON)

{
  "problem": {
    "name": "175. Counting Calories (Harder Version)",
    "description": {
      "content": "Over the quarantine season, you decide to watch your weight by limiting yourself to a certain amount of calories a day. In this problem, you're given the number of calories of each food item in your ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10269175"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Over the quarantine season, you decide to watch your weight by limiting yourself to a certain amount of calories a day.\n\nIn this problem, you're given the number of calories of each food item in your ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the target calorie count.  \nLet $ k \\in \\mathbb{Z}^+ $ be the number of food items.  \nLet $ C = \\{c_1, c_2, \\dots, c_k\\} \\subset \\mathbb{Z}^+ $ be the m...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments