Sam, The Charming Angel
All submissions for this problem are available.
"Ron : Harry!!! Let's go!!"
Ron and Harry just entered Aragog's Colony. Some hungry children of Aragog come running to them for food. Suddenly they see a bright light emerging from nothingness. From the bright light a tiny, cute and charming angel named Sam emerged. She promised to rescue them, if they make her a wand of exactly length N.
Sam had K different types of wands having different lengths. Each type of wand having infinite supply. Harry can join/combine any two wands end to end to make a newer wand, i.e. if two wands of length x and y are joined, then the length of the new wand will be x + y. Now Harry is interested in knowing the minimum and the maximum number of wands he can join in order to produce a wand of length N. If it is not possible to produce such wand then print -1 in both cases.
The first line of input contains two space separated integers N and K denoting the desired wand length and number of types of wands available.
The second line contains K space separated integers where ith integer is lengthi, the length of ith type of wand.
Print two space separated integers in one line where first and second integer denotes the minimum and maximum number of wands needed to join to form a wand of length N respectively. Print -1 in both cases if wand of length N cannot be formed.
- 1 ≤ N < 10000
- 1 ≤ K < 10000
- 1 ≤ lengthi < 10000
- All values of lengthi are distinct
Input : 7 3 5 2 3 Output : 2 3
Join wands of length 2 and 5 to produce a wand of length 7. Join wands of length 2, 2 and 3 to produce a wand of length 7.
Input : 4 3 3 5 7 Output : -1 -1
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions