695 - Placing the Ops

All about problems in Volume 6. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

695 - Placing the Ops

Post 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.

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post 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'.

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

Post 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?

justforfun
New poster
Posts: 5
Joined: Sun Feb 23, 2003 7:33 pm

695 Placing the Ops (WA)

Post 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!

sidky
New poster
Posts: 50
Joined: Wed Nov 06, 2002 1:37 pm
Location: Planet Earth, Universe
Contact:

Post by sidky »

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

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post 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;
}

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post 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... :-?

Post Reply

Return to “Volume 6 (600-699)”