715 . 換錢錢

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

jackhuang

User's AC Ratio

95.2% (20/21)

Submission's AC Ratio

37.7% (23/61)

Tags

apcsc apcsc-greedy

Description

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

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

Input Format

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

  • 1≤N≤10
  • 1≤K≤1012
  • 1≤Ai≤1012, ∀ i
  • A1<A2<⋯<AN
  • Ai|Ai+1, ∀ 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