All submissions for this problem are available.
A mall has N coconut production device numbered from 1 to N. Each device has a multiplier number associated with it. Ai is the multiplier for the ith device. If one coconut is put into device i, then it produces Ai coconuts. Ashish has X coconuts but his friend wants exactly Y coconuts on his birthday. Help Ashish to guess if he can obtain exactly Y coconuts from X coconuts using the production devices.
For each test case, first line contains a single integer N, the number of production devices. Next line contains two space separated integers X and Y. Next line contains N spaced integers, A1A2 . . AN
Print "POSSIBLE" if Ashish can obtain exactly Y coconuts from X coconuts using the production devices.
Otherwise print "IMPOSSIBLE"
ConstraintsSubtask 1: 30 points
1 ≤ N ≤ 10Subtask 2: 70 points
1 ≤ N ≤ 105
For both subtasks:
1 ≤ Ai ≤ 109
0 < X < Y ≤ 109
1 ≤ Y - X ≤ 104
Input: 4 27 34 1 3 5 7 Output: IMPOSSIBLE
|Time Limit:||1 - 3 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, PYP3, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.