12088 - Expression

All about problems in Volume 120. 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
3tito
New poster
Posts: 2
Joined: Fri Aug 31, 2012 1:05 pm

12088 - Expression

Post by 3tito » Thu Oct 03, 2013 12:23 am

i can't figure out why my solution getting WA.

am using greedy approach and it passed many cases.

there's any cases fail my code ?

Code: Select all

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
void Simplify(string &Exp)
{
	bool neg[100000];
	memset(neg, false, sizeof(neg));
	long long Depth = 0;

	for (int i = 0; i < Exp.size(); ++i)
	{
		if (i < Exp.size() - 1)
		
		if (Exp[i] == '-' && Exp[i + 1] == '(')
		{
			if (Exp[i] == '-')
			if (neg[Depth])
				Exp[i] = '+';
			Depth++;
			neg[Depth] = neg[Depth-1] == true ? false : true;
			i++;
		}
		else if (Exp[i] == '(')
		{
			Depth++;
			neg[Depth] = neg[Depth - 1];
		}
		else if (Exp[i] == ')')
			Depth--;

		if (Exp[i] == '+' || Exp[i] == '(')
		{
			if (neg[Depth])
				Exp[i] = '-';
			else Exp[i] = '+';
		}
		else if (Exp[i] == '-')
		if (neg[Depth])
			Exp[i] = '+';
	}
}
void Solve(string &Exp, string nums)
{
	int limdown = 0, limup = nums.size() - 1;
	bool positive = true;
	vector<vector <pair<int , bool> > > digit;
	digit.resize(10);
	int count = 0;
	for (int i = 0; i < Exp.size(); ++i)
	{
		if (Exp[i] == '+')
			positive = true;
		else if (Exp[i] == '-')
			positive = false;
		if (Exp[i] == '#')
		{
			count++;
			digit[count].push_back(make_pair(i,positive));
		}
		else
			count = 0;
	}
	for (int i = 0 ; i < digit.size() ; ++i)
	for (int j = digit[i].size() - 1; j >= 0 ; --j)
	{
		if (digit[i][j].second == true)
			Exp[digit[i][j].first] = nums[limup--];
	}

	for (int i = 0; i < digit.size(); ++i)
	for (int j = 0; j < digit[i].size(); ++j)
	{
		if (digit[i][j].second == false)
			Exp[digit[i][j].first] = nums[limdown++];
		
	}

		digit.clear();
}
vector <int>  selectedNums; 
int calculate(string Exp)
{
	long long count = 0;
	bool positive = true;
	int digits = 1;
	long long num = 0;
	
	for (int i = Exp.size()-1; i >=0 ; --i)
	{
		 if (Exp[i] >= '0' && Exp[i] <= '9')
		{
			num += (Exp[i] - '0')*digits;
			digits *= 10;
		}
		 else
		 {
			 if (digits!=1)
				 selectedNums.push_back(num);
			 digits = 1;
			 num = 0;
		 }
	}
	if (digits != 1)
		selectedNums.push_back(num);

	int j = selectedNums.size() - 1;
	bool bnum = true;
	for (int i = 0; i < Exp.size(); ++i)
	{
		if (Exp[i] == '+')
			positive = true;
		else if (Exp[i] == '-')
			positive = false;
		else if (Exp[i] >= '0' && Exp[i] <= '9' && bnum)
		{
			if (positive)
				count += selectedNums[j];
			else
				count -= selectedNums[j];
			j--;
			bnum = false;
		}
		if (!(Exp[i] >= '0' && Exp[i] <= '9'))
			bnum = true;
	}
	
	return count;
}
void printFormula(string form)
{
	int j = selectedNums.size() - 1;
	bool num = true;
	for (int i = 0; i < form.size(); ++i)
	{
		if (form[i] == '#'&&num)
		{
			cout << selectedNums[j--];
			num = false;
		}
		else if (form[i] != '#')
		{
			cout << form[i];
			num = true;
		}
	}
	selectedNums.clear();

}
int main()
{
	int cases;
	cin >> cases;
	cin.ignore();
	for (int c = 0; c < cases; c++)
	{
		string exp, nums , cpy;
		
		getline(cin, exp);
		cpy = exp;
		getline(cin, nums);
		sort(nums.begin(), nums.end());
		Simplify(exp);
		//cout << exp << endl;
		Solve(exp , nums);
		//cout << exp << endl;
		int out = calculate(exp);

		cout << "Case " << c+1 << ":" << endl;
		printFormula(cpy);
		cout << endl; 
		cout << out << endl;
		
	}
	return 0;
}
thanks in advance.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12088 - Expression

Post by brianfry713 » Fri Oct 04, 2013 3:49 am

Input:

Code: Select all

1
#-##
012
AC output:

Code: Select all

Case 1:
2-01
1
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 120 (12000-12099)”