抱歉，您的浏览器无法访问本站

本页面需要浏览器支持（启用）JavaScript


了解详情 >

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

Tabris

CSDNcodeforces各OJ

发布于：2016年9月1日

次浏览

[原创]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
接着把差的数匀乎匀乎就行了

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

# 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

*/



博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：http://blog.tabris.top/2016-09-01-52400477/

本页文档最后更新于：2021年5月4日

CSDN

codeforces

评论