BLOPER2 - Operators (new ver)


Given a sequence a1, a2,..., an and a integer S, your task is find a way to insert an operator ‘+’ , ‘-‘, ‘.‘, ‘~‘  to every neighbor pair of A, that the result of the expression after insert equal to S.

Note that :

  • a . b = a + 2 * b
  • a ~ b = a - 2 * b

Input

First line : N and S (2 ≤ N ≤ 22, |S| ≤ 5 * 1016)

Second line : N integers, a1, a2,..., an  (|ai| ≤ 1015)

Output

If there are way(s) to insert, output any of them, otherwise output “Impossible” (without quotes).

Example

Input:
9 5
1 2 3 4 5 6 7 8 9

Output:
-~~~++++
Input:
3 -1
-2 5 7

Output:
Impossible

Details:

In first test case : 1 - 2 - 2 * 3 - 2 * 4 - 2 * 5 + 6 + 7 + 8 + 9 = 5

You may want to try another version here.


hide comments
Rohit Agarwal: 2018-11-18 16:55:52

@Kata: Hi! I have a query, my ideone submission for worst case take 836ms (22 elements and Impossible answer) and yet it times out here. How is that possible? Could you please explain it?

Edit: I managed to solve it. The time constraints are incredibly strict. I didn't expect that much optimization seriously. Took me almost a day to solve it.

Last edit: 2018-11-18 23:50:33
shubham9261: 2017-07-30 09:31:57

there is not given any thing about precedence of operators:i.e,1-2~3=1~3 or 1-2-2*3????
suggest me something on it

sushantgokhale: 2017-04-18 10:35:00

Kata, could u check ID19236413 ? I dont know which test case failing

Last edit: 2017-04-18 10:41:54
pavan26: 2017-03-17 05:04:59

can you check my code ?? ID 18993235

Last edit: 2017-03-17 05:09:37
pavan26: 2017-03-17 05:00:46

Any test cases please!!

san93st: 2016-07-16 11:28:39

Input is not number of test case. I can't terminate my program.

sushantgokhale: 2016-06-01 15:13:22

Kata, could you publish the test cases? My code is failing after 15 or 16th test case. If you publish, I will be able to correct my code. It would be great help.

[Kata] :
SPOJ judge will run all test cases althought you have already fallen at some test cases. Your code fails from first test case, check your algorithm.

Last edit: 2016-06-10 01:02:52
ISHANI: 2014-11-25 23:44:10

Kata,
(1)
3-2~4=1~4=not valid
or
3-2~4=3-2-2*4=-7
(2)
as '~' will always come after '-',is there vice-versa will be true.
i.e- (1-2+3)=2 is true or not/
please plz reply fast

[Kata] :
(1) 3-2~4 = 3-2-2*4 = -7
(2) (1-2+3) = 2 is true

Last edit: 2014-10-10 18:14:22
fitcat: 2014-11-25 23:44:10

Are the following valid?
1. a1.a2
2. a1~a2
3. a1+a2.a3
4. a1+a2~a3
If yes, what are the values?

Edit: Never mind. I misinterpreted the '-' as a minus operator. It should be treated as a bullet.

Last edit: 2014-04-12 06:51:36

Added by:Kata
Date:2014-03-30
Time limit:1.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64