SPOJ.com - Problem BLOPER2

BLOPER2 - Operators (new ver)

#sorting #binary-search #backtracking

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 * 10¹⁶)

Second line : N integers, a1, a2 ... an (|ai| ≤ 10¹⁵)

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.

Submit solution!

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-24=-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-24 = -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

Submit solution!

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