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$.