C. ATM withdrawal

Codeforces

IDCF10054C

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Vinh works for an ATM machine manufacturing company. The basic functionality of an ATM machine is cash withdrawal. When a user requests a cash withdrawal of W VND (Vietnamese Dong), the ATM has to dispense N money notes such that they sum up to W. For the next generation of ATM machine, Vinh is working on an algorithm to minimize the number N of money notes for each cash withdrawal transaction. Your task is to help Vinh to do his job given that the money notes come in the values of 1000, 2000, 3000, 5000, 1000 * 101, 2000 * 101, 3000 * 101, 5000 * 101, ..., 1000 * 10c, 2000 * 10c, 3000 * 10c, 5000 * 10c where c is a positive integer and Vinh has unlimited supply of money notes for each value. The input file consists of several datasets. The first line of the input file contains the number of datasets which is a positive integer and is not greater than 1000. The following lines describe the datasets. For each dataset, write in one line two space-separated integers N and S where S is the number of ways to dispense the fewest number N of money notes. In case there is no way to serve the cash withdrawal request, write out 0 in one line instead. ## Input The input file consists of several datasets. The first line of the input file contains the number of datasets which is a positive integer and is not greater than 1000. The following lines describe the datasets. The first line consists of one positive integer W (W ≤ 1018); The second line consists of one positive integer c (c ≤ 15). ## Output For each dataset, write in one line two space-separated integers N and S where S is the number of ways to dispense the fewest number N of money notes. In case there is no way to serve the cash withdrawal request, write out 0 in one line instead. [samples]

**Definitions** Let $ c \in \mathbb{Z}^+ $ be the exponent parameter. Let $ V = \{1000 \cdot 10^k, 2000 \cdot 10^k, 3000 \cdot 10^k, 5000 \cdot 10^k \mid k \in \{0, 1, \dots, c\}\} $ be the set of available banknote denominations. **Given** For each dataset: - $ W \in \mathbb{Z}^+ $: the requested withdrawal amount in VND. - $ V $: denominations as defined above, with unlimited supply of each. **Objective** For each dataset, find: - $ N = \min \left\{ \sum_{v \in V} x_v \,\middle|\, \sum_{v \in V} x_v \cdot v = W,\, x_v \in \mathbb{Z}_{\ge 0} \right\} $: the minimum number of notes. - $ S $: the number of distinct combinations $ (x_v)_{v \in V} $ achieving this minimum $ N $. If no such combination exists, output $ 0 $. **Constraints** - Number of datasets $ \le 1000 $. - $ W \ge 1 $. - $ c \in \mathbb{Z}^+ $ (implicitly defined by the denomination set).

API Response (JSON)

{
  "problem": {
    "name": "C. ATM withdrawal",
    "description": {
      "content": "Vinh works for an ATM machine manufacturing company. The basic functionality of an ATM machine is cash withdrawal. When a user requests a cash withdrawal of W VND (Vietnamese Dong), the ATM has to dis",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10054C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Vinh works for an ATM machine manufacturing company. The basic functionality of an ATM machine is cash withdrawal. When a user requests a cash withdrawal of W VND (Vietnamese Dong), the ATM has to dis...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ c \\in \\mathbb{Z}^+ $ be the exponent parameter.  \nLet $ V = \\{1000 \\cdot 10^k, 2000 \\cdot 10^k, 3000 \\cdot 10^k, 5000 \\cdot 10^k \\mid k \\in \\{0, 1, \\dots, c\\}\\} $ be the set of...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments