Sanrd(sanrd)

Sanrd(sanrd)

【题目描述】
L 君是一个热爱学习的女孩子。
一天,她翻阅自己的笔记本时,看到了一个形如a1 op1 a2 op2    opk􀀀1 ak = n 的等
式,其中opi 是一个运算符,可以为加号或者减号。不幸的是,由于某些不明原因,这
个等式中除了n 之外的数字已经模糊不清,我们用问号来表示这些数。
L 君想知道自己到底写了什么,然而她只记得,a1; a2; : : : ; ak 都是[1; n] 之间的正整
数了。你能帮她还原出这个等式吗?
【输入格式】
从文件sanrd.in 中读入数据。
一行一个字符串,表示残缺的等式,其中问号代表未确定的数。问号、运算符、等
号和n 之间用空格隔开。
【输出格式】
输出到文件sanrd.out 中。
如果不存在一种还原的方法,输出一行Impossible。
否则,输出一行Possible,第二行输出一个等式,表示一组合法的将问号替换为
[1; n] 间的正整数的方案。
你可以参考样例来更好地理解题意。
【样例1 输入】
? + ? - ? + ? + ? = 42
【样例1 输出】
Possible
9 + 13 - 39 + 28 + 31 = 42
【样例2 输入】
? - ? = 1
【样例2 输出】
Impossible
【样例3 输入】
? = 1000000
【样例3 输出】
Possible
1000000 = 1000000
【子任务】
记q 为等式中问号的数量。
对于20% 的数据,q <=5; n<=20;
对于50% 的数据,n <=50;
对于另外10% 的数据,运算符均为+;
对于另外10% 的数据,运算符均为-;
对于100% 的数据,1 <= q<= 100; 1 <=n <= 10^6。