695 - Placing the Ops

[wyvmak]

i understand division is only for integers. can anyone tell me what is the trick? and is it really "If there are multiple correct answers, then any one of them will be acceptable"? or need special way to put the operators? and it seems that there're space in the line of input of operators.

[Ivan Golubev]

Yes, multiple correct answers are accepted normal (after several rejudjements corrector works OK). If there is a space somewhere just ignore it. The only trick I've found that there cannot be leading zeroes. I.e. for such input:

01=10
+

There cannot be answer 01=1+0, correct answer is 'no solution'.

[wyvmak]

thanks a million and more! i get AC, i can't imagine that can be the trick. but, i wonder how you find the trick? or any hints on facing such tricks?

[justforfun]

I got WA in this problem.
But I have no idea what's wrong with my code.
I deal with the leading zero, and make it illigal.
Cound anyone give me some test cases???
Thank you!

[sidky]

leading zeros are not illegal. Your problem must be somewhere else.

[minskcity]

Can anybody post some critical test? I keep getting WAs...

Code: Select all

#include <algorithm>
#include <iostream>
#include <string>
#include <ctype.h>
using namespace std;
typedef long long ll;

string s, ss;
int n;

ll evaluate(string s, string ss){
   ss = " " + ss;
   char o = '+';
	ll out = 0, now = 0;

   for(int i = 0; i < (int)s.size(); i++){
   	if(ss[i] == ' ') now = now*10 + s[i] - '0';
      else{
      	if(o == '+') out += now;
         else if(o == '-') out -= now;
         else if(o == '*') out *= now;
         else if(o == '/' && now) out /= now;
         else return 2000000000;
         now = s[i] - '0', o = ss[i];
      }
   }
      	if(o == '+') out += now;
         else if(o == '-') out -= now;
         else if(o == '*') out *= now;
         else if(o == '/' && now) out /= now;
         else return 2000000000;
   return out;
}

bool good(){
	ll left = evaluate(s.substr(0, n), ss.substr(0, n - 1));
   ll right = evaluate(s.substr(n + 1), ss.substr(n - 1));
	return left < 2000000000 && right < 2000000000 && left == right;
}

void print(){
	int p = 0;
   for(int i = 0; i < (int)s.size(); i++){
    	cout << s[i];
      if(i + 1 < (int)s.size() && isdigit(s[i]) && isdigit(s[i + 1])){
      	if(ss[p] != ' ') cout << ss[p];
      	p++;
      }
   }
   cout << endl;
}

int main(){

	int test = 1;
	while(getline(cin, s) && getline(cin, ss) && s[0] != '$'){
   	n = s.find('=', 0);
   	ss.resize(s.size() - 3, ' ');
   	sort(ss.begin(), ss.end());
      bool solved = false;
      cout << "Case " << test++ << ": ";
      do{
      	if(good()){
         	solved = true;
            print();
            break;
         }
      }while(next_permutation(ss.begin(), ss.end()));
      if(!solved) cout << "NO SOLUTION" << endl;

   }

	return 0;
}

[minskcity]

For everybody who still cannot get it...
intput:

Code: Select all

11=1
**
$

output:

Code: Select all

Case 1: NO SOLUTION

Hope this helps...