Codeforces Round #347 (Div. 2) B. Rebus(给你一个等式里面只含加减号凑出一个数)

最新推荐文章于 2020-09-14 01:54:40 发布

_zidaoziyan

最新推荐文章于 2020-09-14 01:54:40 发布

阅读量555

点赞数

分类专栏： codeforces

本文链接：https://blog.csdn.net/acm_fighting/article/details/51242539

版权

codeforces 专栏收录该内容

48 篇文章

订阅专栏

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, integern 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 1to 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
 
         
 
        
题意:给你一个等式 ? + ? - ? + ? = x,其中等式的长度小于等于100,x<=1000000
每个?号都是小于等于x,输出这个等式。
思路:
方法一:
假设’+’号的个数为count1,’-’的个数为count2,那么如果加上第一个?,实际的’+’的个数为count1+1个,我们可以把等式经过移向,使得左边全为加号,右边也全为加号,
所以左边的值大于等于count1+1,小于等于(count1+1)*x,右边的值大于等于count2+x,小于等于(count2+1)*x,
因为(count2+1)*x<=1e8,所以我们可以枚举右边的值是多少,然后判断这个值是不是大于等于count1+1,小于等于(count1+1)*x,如果这个值存在,那么有解,否则无解。

 
接下来的问题便是输出答案了,输出时我们只需要选择每个数此时能选择的最大值输出便可以了。
 
方法二:
刚开始把每个数都初始化为1,如果当前左边等式的值小于ANS,那么使加号的值增大,如果大于ANS,那么使减号的值增大。(时间复杂度O(n))

           方法一代码 
         
 
          #include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define inf -0x3f3f3f3f
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long ll;
string s;
char s1[100];

int main(){
    s="";
    int count1=0,count2=0,ans=0;
    while(scanf("%s",s1)!=EOF){
        if(s1[0]>='0'&&s1[0]<='9'){
            int len=strlen(s1);
            for(int i=0;i<len;i++)
                ans=ans*10+s1[i]-'0';
            break;
        }
        if(s1[0]!='?')
            s+=s1[0];
        if(s1[0]=='+')
            count1++;
        else if(s1[0]=='-')
            count2++;
    }
    int ans1,ans2;
    int flag=0;
    count1++;
    for(int i=count2;i<=count2*ans;i++){
        int num=i+ans;
        if(count1*ans>=num&&count1<=num){
            flag=1;
            ans1=num,ans2=num-ans;
            break;
        }
    }
    if(flag==0)
        printf("Impossible\n");
    else{
        printf("Possible\n");
        printf("%d",min(ans1-(count1-1),ans));
        ans1-=min(ans1-(count1-1),ans);
        count1--;
        int len=s.size();
        for(int i=0;i<len-1;i++){
            if(s[i]=='+'){
                printf(" %c %d",s[i],min(ans1-(count1-1),ans));
                ans1-=min(ans1-(count1-1),ans);
                count1--;
            }
            else{
                printf(" %c %d",s[i],min(ans2-(count2-1),ans));
                ans2-=min(ans2-(count2-1),ans);
                count2--;
            }
        }
        printf(" = %d\n",ans);
    }
} 
          
 
          
 
         
 方法二代码 
        
 
         #include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define inf -0x3f3f3f3f
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long ll;
string s;
char s1[100];
int a[110];

int main(){
    int count1=0,count2=0,ans=0;
    for(int i=0;i<=110;i++)
        a[i]=1;
    while(scanf("%s",s1)!=EOF){
        if(s1[0]>='0'&&s1[0]<='9'){
            int len=strlen(s1);
            for(int i=0;i<len;i++)
                ans=ans*10+s1[i]-'0';
            break;
        }
        if(s1[0]!='?')
            s+=s1[0];
        if(s1[0]=='+')
            count1++;
        else if(s1[0]=='-')
            count2++;
    }
    count1++;
    int ANS=ans-(count1-count2),cnt=0;
    if(ANS>0){
        ANS++;
        a[cnt]=min(ans,ANS);
        ANS-=a[cnt];
    }
    cnt++;
    int len=s.size();
    for(int i=0;i<len-1;i++){
        if(ANS==0)
            break;
        if(s[i]=='+'){
            if(ANS>0){
                ANS++;
                a[cnt]=min(ans,ANS);
                ANS-=a[cnt];
            }
        }
        else{
            if(ANS<0){
                ANS--;
                a[cnt]=min(ans,-ANS);
                ANS+=a[cnt];
            }
        }
        cnt++;
    }
    if(ANS!=0)
        printf("Impossible\n");
    else{
        printf("Possible\n");
        printf("%d",a[0]);
        for(int i=0;i<len-1;i++)
            printf(" %c %d",s[i],a[i+1]);
        printf(" = %d\n",ans);
    }
}
/*
? - ? - ? - ? + ? = 6
*/
 
         
 
         
 
        