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.


Được gửi lên bởi:Kata
Ngày:2014-03-30
Thời gian chạy:1.5s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED

hide comments
2015-10-14 16:30:11 Huy Luu
22 số thì có 21 lỗ. Chia làm 2 mảng.
Mảng đầu quét hết 11 lỗ đầu mất 4^11 = 2 ^ 22 (OK!). Nhét vào heap tree mất 2^22 log2(2^22) = 11 * 2^23 (OK)
Quét hết 10 lỗ còn lại vào mảng thứ 2. Binary search trên heap tree, mất 2^20 * log2(2^22)
Kết hợp chồng chéo nhau để tối ưu hóa.
2014-05-11 10:19:40  
Sau khi nâng time limit lên mình đã ac... cơ mà không biết p/s chấm lại lúc nào :))
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.