codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1934B.md (1657B)


      1 Source: https://codeforces.com/problemset/problem/1934/B
      2 
      3 B. Yet Another Coin Problem
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You have $5$ different types of coins, each with a value equal to one of the first $5$ triangular numbers: $1$, $3$, $6$, $10$, and $15$. These coin types are available in abundance. Your goal is to find the minimum number of these coins required such that their total value sums up to exactly $n$.
     22 
     23 We can show that the answer always exists.
     24 
     25 Input
     26 
     27 The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.
     28 
     29 The first line of each test case contains an integer $n$ ($1 \leq n \leq 10^9$) — the target value.
     30 
     31 Output
     32 
     33 For each test case, output a single number — the minimum number of coins required.
     34 
     35 Example
     36 
     37 Input
     38 
     39 ```
     40 14
     41 
     42 1
     43 
     44 2
     45 
     46 3
     47 
     48 5
     49 
     50 7
     51 
     52 11
     53 
     54 12
     55 
     56 14
     57 
     58 16
     59 
     60 17
     61 
     62 18
     63 
     64 20
     65 
     66 98
     67 
     68 402931328
     69 ```
     70 
     71 Output
     72 
     73 ```
     74 1
     75 2
     76 1
     77 3
     78 2
     79 2
     80 2
     81 3
     82 2
     83 3
     84 2
     85 2
     86 8
     87 26862090
     88 ```
     89 
     90 Note
     91 
     92 In the first test case, for $n = 1$, the answer is $1$ since only one $1$ value coin is sufficient. $1 = 1 \cdot 1$.
     93 
     94 In the fourth test case, for $n = 5$, the answer is $3$, which can be achieved using two $1$ value coins and one $3$ value coin. $5 = 2 \cdot 1 + 1 \cdot 3$.
     95 
     96 In the seventh test case, for $n = 12$, the answer is $2$, which can be achieved using two $6$ value coins.
     97 
     98 In the ninth test case, for $n = 16$, the answer is $2$, which can be achieved using one $1$ value coin and one $15$ value coin or using one $10$ value coin and one $6$ value coin. $16 = 1 \cdot 1 + 1 \cdot 15 = 1 \cdot 6 + 1 \cdot 10$.