Summer Institute '17 Contest 1 P8 - Mo' Money

View as PDF

Submit solution


Points: 5
Time limit: 3.0s
Memory limit: 256M

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Max has a number of coins and wants to know how many ways he can use some or all of the coins to reach a target value. Can you write a program to help him out?

Input Specification

The first line of input will contain two space separated positive integers, n (n \le 15), the number of coins Max has, and t (t \le 10^6), the target value he wants to reach. The second line of input will contain n space separated positive integers, a_1 through a_n, where a_i (a_i \le 5*10^5) is the value of the i^{\text{th}} coin.

Output Specification

Output a single integer on a line by itself, representing the number of ways Max can combine his coins to reach his target value.

Sample Input 1

6 20
3 10 4 7 3 6

Sample Output 1

6

Sample Input 2

10 3500
1000 500 750 250 100 800 1200 900 1300 3000

Sample Output 2

9

Comments