专栏首页算法修养CodeForces 663A Rebus

CodeForces 663A Rebus

A. Rebus

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a rebus of form ? + ? - ? + ? = n, consisting of only question marks, separated by arithmetic operation '+' and '-', equality and positive integer n. The goal is to replace each question mark with some positive integer from 1 to n, such that equality holds.

Input

The only line of the input contains a rebus. It's guaranteed that it contains no more than 100 question marks, integer n is positive and doesn't exceed 1 000 000, all letters and integers are separated by spaces, arithmetic operations are located only between question marks.

Output

The first line of the output should contain "Possible" (without quotes) if rebus has a solution and "Impossible" (without quotes) otherwise.

If the answer exists, the second line should contain any valid rebus with question marks replaced by integers from 1 to n. Follow the format given in the samples.

Examples

input

? + ? - ? + ? + ? = 42

output

Possible
9 + 13 - 39 + 28 + 31 = 42

input

? - ? = 1

output

Impossible

input

? = 1000000

output

Possible
1000000 = 1000000
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>

using namespace std;
char a[1000];
int n;
int num1,num2;
int b[1000];
int main()
{
    gets(a);
    int len=strlen(a);
    num1=0;num2=0;
    int cnt=1;int pos;int now=1;b[0]=1;
    for(int i=0;i<len;i++)
    {
        if(a[i]=='+') {b[cnt++]=1;now++;}
        if(a[i]=='-') {b[cnt++]=-1;now--;}
        if(a[i]=='=')
        {
            pos=i;
            break;
        }
    }
    n=0;
    for(int i=pos+1;i<len;i++)
    {
        if(a[i]<='9'&&a[i]>='0')
            n=n*10+a[i]-'0';
    }
    for(int i=0;i<cnt;i++)
    {
        while(now<n&&b[i]<n&&b[i]>0)
            now++,b[i]++;
        while(now>n&&b[i]>-n&&b[i]<0)
            now--,b[i]--;
    }
    if(now!=n)
    {
        printf("Impossible\n");
        return 0;
    }
    printf("Possible\n");
    int j=0;
    for(int i=0;i<len;i++)
    {
        if(a[i]!='?')
        printf("%c",a[i]);
        else
        {
            printf("%d",abs(b[j++]));
        }
    }
    cout<<endl;
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HDU 1232 畅通工程(Kruskal)

    畅通工程 Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Jav...

    ShenduCC
  • pta习题集5-16 朋友圈

    某学校有N个学生,形成M个俱乐部。每个俱乐部里的学生有着一定相似的兴趣爱好,形成一个朋友圈。一个学生可以同时属于若干个不同的俱乐部。根据“我的朋友的朋友也是我...

    ShenduCC
  • HDU 2157 How many ways??(简单线性DP | | 矩阵快速幂)

    题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=2157 这道题目很多人的题解都是矩阵快速幂写的,矩阵快速幂倒...

    ShenduCC
  • 1750:全排列

    1750:全排列 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 给定一个由不同的小写字母组成的字符串,输出这个字符串的所...

    attack
  • HDU 1232 畅通工程(Kruskal)

    畅通工程 Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Jav...

    ShenduCC
  • 哈密尔顿环问题

    哈密尔顿环   欧拉回路是指不重复地走过所有路径的回路,而哈密尔顿环是指不重复地走过所有的点,并且最后还能回到起点的回路。 1 #include<iostre...

    attack
  • 洛谷P1420 最长连号

    题目描述 输入n个正整数,(1<=n<=10000),要求输出最长的连号的长度。(连号指从小到大连续自然数) 输入输出格式 输入格式: 第一行,一个数n; 第二...

    attack
  • 1722 最优乘车 1997年NOI全国竞赛

    1722 最优乘车 1997年NOI全国竞赛  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 大师 Master 题解 题目描述 Des...

    attack
  • 24:蛇形填充数组

    24:蛇形填充数组 总时间限制: 1000ms 内存限制: 65536kB描述 用数字1,2,3,4,...,n*n这n2个数蛇形填充规模为n*n的方阵。 ...

    attack
  • 1893. [国家集训队2011]等差子序列(bitset)

    ★★   输入文件:nt2011_sequence.in   输出文件:nt2011_sequence.out 简单对比 时间限制:0.3 s   内存限制:5...

    attack

扫码关注云+社区

领取腾讯云代金券