[原创]codeforces 664B Rebus [细节]

2016-09-01 15:54:48 Tabris_ 阅读数：491

博客爬取于2020-06-14 22:43:32
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/52400477

题目链接：http://codeforces.com/problemset/problem/664/B
---------------------------------.
B. Rebus
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard 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

------------------------------------------.

题目大意 ：
就是把问好（?）的数用1~n填上 如果存在等式能够成立的情况就输出Possible 和这个等式 （有SPJ）
否则输出Impossible

题目分析：
先把加上的数有几个 减去的数有几个统计一下
然后把每个数都附上1
接着把差的数匀乎匀乎就行了

附本题代码
----------------------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
# include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 505;

char a[101];
int numjia[101];
int numjian[101];

void debug()
{
    printf("%d ",numjia[0]);
    int j=1,jn=0;
    int l = strlen (a);
    for(int i=2; i<l; i++)
    {
        if(a[i-2]=='+')  printf("%d",numjia[j++]) ;
        else if(a[i-2]=='-')  printf("%d",numjian[jn++]) ;
        else printf("%c",a[i]);
    }
    puts("");
}

int main()
{
    while(gets(a))
    {
        for(int i=0;i<101;i++)
        {
            numjian[i]=1;
            numjia[i]=0;
        }

        int l = strlen (a) ;
        int jia=1,jian=0;
        int n=0;
        bool flag = false;
        for(int i=0; i<l; i++)
        {
            if(a[i]=='+') jia++;
            if(a[i]=='-') jian++;

            if(flag||a[i-2]=='=')
            {
                flag = true ;
                n=n*10+a[i]-'0';
            }
        }
        //  printf("%d\n",n);
        int tem = n/jia;

        for(int i=0; i<jia; i++)
            numjia[i] = tem;

        tem = n%jia+jian;
        for(int i=0; i<tem; i++)
            numjia[i%jia]++;

        bool fla = true ,fl = true,f = true;
        int tt = 0;
        for(int i=0; i<jia; i++)
            if(1<=numjia[i]&&numjia[i]<=n)    ;
            else   if(numjia[i] == 0) tt++, numjia[i] = 1,fl=false;
            else   fla = false;


        //printf(" ==  %d\n",fla);
        if(jian)
        {
            tem = tt/jian;

            for(int i=0; i<jia; i++)
                numjian[i] = tem+1;

            tem = tt%jian;
            for(int i=0; i<tem; i++)
                numjian[i%jian]++;

            for(int i=0; i<jian; i++)
                if(1<=numjian[i]&&numjian[i]<=n)    ;
                else   fla = false;

            fl = true;
        }
        // debug();
        // printf(" ==  %d\n",fla);

        int sum = 0;
        for(int i=0; i<jia; i++)
            sum+=numjia[i];
        for(int i=0; i<jian; i++)
            sum-=numjian[i];
        if(sum!=n)f=false;

        if(fla&&fl)
        {
            puts("Possible");
            printf("%d ",numjia[0]);
            int j=1,jn=0;
            for(int i=2; i<l; i++)
            {
                if(a[i-2]=='+')       printf("%d",numjia[j++]) ;
                else if(a[i-2]=='-')  printf("%d",numjian[jn++]) ;
                else                printf("%c",a[i]);
            }
            puts("");
        }
        else       puts("Impossible");

    }
    return 0;
}



/*

? + ? + ? + ? - ? = 1
? + ? + ? + ? - ? + ? + ? = 4

*/