G. Notes

Codeforces

IDCF10110G

Time4000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

_Jordanian notes are 1, 5, 10, 20, and 50 JDs._ Maram is going to the shop and has N JDs, she wants to have the money in a form that will allow her to pay for any single item exactly, which means without waiting for change. Given N and the price of each item in the shop, find the required form, that is, find the number of notes of each type she has to have before going to the shop. The first line of input contains a single integer T, the number of test cases. The first line of each test case contains two integers N and M (1 ≤ N, M ≤ 105), the amount of money Maram has and the number of items in the shop, respectively. The second line contains M space-separated integers, each value represents the price of an item and is between 1 and N. For each test case, print five space-separated integers on a single line, where the first integer represents the number of notes of the first type (1 JD), the second integer represents the number of notes of the second type (5 JDs), and so on. If there’s more than one possible form, find the one that minimizes the total number of notes. Note that the total amount of money in the printed form should be equal to N. ## Input The first line of input contains a single integer T, the number of test cases.The first line of each test case contains two integers N and M (1 ≤ N, M ≤ 105), the amount of money Maram has and the number of items in the shop, respectively. The second line contains M space-separated integers, each value represents the price of an item and is between 1 and N. ## Output For each test case, print five space-separated integers on a single line, where the first integer represents the number of notes of the first type (1 JD), the second integer represents the number of notes of the second type (5 JDs), and so on.If there’s more than one possible form, find the one that minimizes the total number of notes.Note that the total amount of money in the printed form should be equal to N. [samples]

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. Let $ \mathcal{C} = \{1, 5, 10, 20, 50\} $ be the set of Jordanian banknote denominations, indexed in increasing order. For each test case: - Let $ N \in \mathbb{Z} $ be the total amount of money (in JDs). - Let $ M \in \mathbb{Z} $ be the number of items. - Let $ P = \{p_1, p_2, \dots, p_M\} \subseteq \{1, 2, \dots, N\} $ be the set of item prices. **Constraints** 1. $ 1 \le T \le 10^5 $ 2. For each test case: - $ 1 \le N \le 10^5 $ - $ 1 \le M \le 10^5 $ - $ 1 \le p_i \le N $ for all $ i \in \{1, \dots, M\} $ **Objective** Find a 5-tuple $ (x_1, x_2, x_3, x_4, x_5) \in \mathbb{Z}_{\ge 0}^5 $ such that: $$ \sum_{i=1}^{5} x_i \cdot c_i = N \quad \text{where } c_i \in \mathcal{C} $$ and for every price $ p \in P $, there exists a subset of the selected notes summing exactly to $ p $ (i.e., the note multiset is *universal* for $ P $). Among all such tuples, minimize the total number of notes: $$ \min \sum_{i=1}^{5} x_i $$

API Response (JSON)

{
  "problem": {
    "name": "G. Notes",
    "description": {
      "content": "_Jordanian notes are 1, 5, 10, 20, and 50 JDs._ Maram is going to the shop and has N JDs, she wants to have the money in a form that will allow her to pay for any single item exactly, which means wit",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10110G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "_Jordanian notes are 1, 5, 10, 20, and 50 JDs._\n\nMaram is going to the shop and has N JDs, she wants to have the money in a form that will allow her to pay for any single item exactly, which means wit...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nLet $ \\mathcal{C} = \\{1, 5, 10, 20, 50\\} $ be the set of Jordanian banknote denominations, indexed in increasing order.  \nFor ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments