All submissions for this problem are available.
Sarah is on a trip to the capital city of Earth, United City. She’s saved up a lot of money for this trip and plans to spend every last unit of it. Being the meticulous person that she is, she wrote her own program that when given a particular list of items and prices, will output the number of combinations of which she can buy without leaving any money left over. In your own programming language, what is your rendition of Sarah’s program?
Your program should take input from stdin and display output to stdout.
An input from stdin would start with the amount of money that she has (say M) followed by the number of items available (say N), before listing N items and prices (say P).
M > 10 && M < 10^5
N > 0 && N < 20
P > 0 && P <= M
The item name may contain more than one word (e.g. “Beach Ball”). The output to stdout should be the number of possible combinations that Sarah can buy.
Beach Ball 32
Mermaid Fin 97
Coconut Juice 254
Note: There is NO newline character at the end of the output.
There are two combinations of items that can be purchased without leaving any money left over:
Combination #1: 6 Caps, 1 Coconut Juice
Combination #2: 7 Beach Balls, 2 Caps, 2 Mermaid Fins
|Time Limit:||1 - 4 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.