Page 1 of 1

695 - Placing the Ops

Posted: Sun Dec 30, 2001 8:21 am
by 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.

Posted: Sun Dec 30, 2001 8:57 pm
by 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'.

Posted: Mon Dec 31, 2001 3:54 pm
by 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?

695 Placing the Ops (WA)

Posted: Wed Aug 11, 2004 5:36 pm
by 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!

Posted: Mon Jan 17, 2005 3:42 pm
by sidky
leading zeros are not illegal. Your problem must be somewhere else.

Posted: Fri Jul 08, 2005 4:57 am
by 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;
}

Posted: Mon Jan 02, 2006 8:42 am
by 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... :-?