715 . 換錢錢

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Darren0724

User's AC Ratio

91.7% (11/12)

Submission's AC Ratio

28.2% (11/39)

Tags

apcsc apcsc-greedy

Description

在卡加布列島上發行的硬幣有 $N$ 種，分別價值 $A_1, A_2, \cdots, A_N$ 塊，已知 $1 = A_1 < A_2 < \cdots < A_N$，而且對於所有可能的 $i$，$A_i$ 是 $A_{i+1}$ 的因數。學姐帶了價值 $K$ 塊錢的小說去卡加布列島想要換成現金，但她希望拿到的硬幣越少越好，作為收銀員的你能滿足學姐的需求嗎？

(注意到最小硬幣是 $1$ 塊錢，所以一定有辦法換錢)

Input Format

輸入有兩行，第一行包含兩個正整數 $N, K$，代表硬幣的種數和小說的價值。
第二行則有 $N$ 個正整數 $1 = A_1, A_2, \cdots ,A_N$，分別代表硬幣的價值，保證輸入的數字從小到大排列。

  • $1 \le N \le 10$
  • $1 \le K \le 10^ {12}$
  • $1 \le A_i \le 10^ {12}$, $\forall$ $i$
  • $A_1 < A_2 < \cdots < A_N$
  • $A_i | A_{i+1}$, $\forall$ $i < N$

Output Format

輸出有一行。這一行只有一個正整數，代表可能的最少硬幣數量。

Sample Input 1

5 123
1 5 10 50 100

Sample Output 1

6

Sample Input 2

5 8763
1 31 124 372 4836

Sample Output 2

35

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~31 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
20 1000 524288 65536 2
21 1000 524288 65536 2
22 1000 524288 65536 2
23 1000 524288 65536 2
24 1000 524288 65536 2
25 1000 524288 65536 2
26 1000 524288 65536 2
27 1000 524288 65536 2
28 1000 524288 65536 2
29 1000 524288 65536 2
30 1000 524288 65536 2
31 1000 524288 65536 2
Submit
Back to Top