結果

問題 No.193 筒の数式
コンテスト
ユーザー ty70
提出日時 2015-05-15 09:01:21
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 3,524 bytes
コンパイル時間 1,543 ms
コンパイル使用メモリ 118,500 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-06 03:54:18
合計ジャッジ時間 1,834 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>	// require sort next_permutation count __gcd reverse etc.
#include <cstdlib>	// require abs exit atof atoi 
#include <cstdio>		// require scanf printf
#include <functional>
#include <numeric>	// require accumulate
#include <cmath>		// require fabs
#include <climits>
#include <limits>
#include <cfloat>
#include <iomanip>	// require setw
#include <sstream>	// require stringstream 
#include <cstring>	// require memset
#include <cctype>		// require tolower, toupper
#include <fstream>	// require freopen
#include <ctime>		// require srand
#define rep(i,n) for(int i=0;i<(n);i++)
#define ALL(A) A.begin(), A.end()
#define INF 1<<28

using namespace std;

typedef long long ll;
typedef pair<int, int> P;


vector<string> pre_trans (string eq ){
	vector<string> res; res.clear();
	int n = eq.length();
	string ope = "";
	rep (i, n ){
		if (isdigit(eq[i] ) ){
			ope += eq[i];
		}else{
			res.push_back (ope );
			ope = "";
			ope += eq[i];
			res.push_back (ope );
			ope = "";
		} // end if
	} // end if
	if (!ope.empty() ) res.push_back (ope );

	return res;
}

// 中置記法を逆ポーランド記法に変換
vector<string> trans (string q ){

	// 式に出て来るオペランド（数値）とオペレーター（演算子）に優先順位の番号を付ける
	map<char,int> pri;
	rep (i, 10 ) pri[(char)('0'+i)] = 0;
//	pri['*'] = 1, pri['/'] = 1, pri['%'] = 1;
	pri['+'] = 2, pri['-'] = 1;
//	pri['('] = 3, pri[')'] = 3;

	vector<string> p;
	stack<string> s;

	vector<string> eq = pre_trans (q );
	string ope = "";
	if (!isdigit(eq[0][0] ) ) return vector<string>();

	s.push(eq[0]);
	string ss = "";
	int n = eq.size();
	for (int i = 1; i < n; i++ ){
		int cp = pri[eq[i][0]];
		ss = s.top();
		while (!s.empty() && cp > pri[ss[0]] ){
			p.push_back (s.top() ); s.pop();
		} // end while
		s.push (eq[i] );
	} // end for			

	while (!s.empty() ){
		p.push_back (s.top() ); s.pop();
	} // end while

	return p;				 
}

int s2i(string s ){
	stringstream ss (s );
	int res;
	ss >> res;

	return res;	
}

int calc (vector<string> s ){
	if (s.empty() ) return INF;

	int n = s.size();

	stack<int> num;
	stack<char> ope;

	rep (i, n ){
		if (isdigit(s[i][0] ) ){
			num.push (s2i(s[i] ) );
		}else{
			int a, b;
			char c;
			int curr;
			ope.push (s[i][0] );

			if (!num.empty() ){
				b = num.top(); num.pop();
			}else{
				return INF;
			} // end if
			if (!num.empty() ){
				a = num.top(); num.pop();
			}else{
				return INF;
			} // end if
			if (!ope.empty() ){
				c = ope.top(); ope.pop();
			}else{
				return INF;
			} // end if

			switch (c ){
				case '+': curr = a + b; num.push (curr ); break;
				case '-': curr = a - b; num.push (curr ); break;
			} // end switch
		} // end if
	} // end rep

	if (num.empty() ) return INF;
	
	return num.top(); 
}

string disp(vector<string> s ){
	string res = "";
	int n = s.size();
	rep (i, n ){
		res += s[i];
		res += (i != n - 1 ? ',' : ' ');
	} // end rep

	return res;
}

int main()
{
	ios_base::sync_with_stdio(0);
	string s; cin >> s;
	int n = s.length();
	int res = -INF;
	rep (i, n ){
		string t = s.substr(i) + s.substr(0,i);

		vector<string> curr = trans (t );
		int cur2 = calc(curr );
//		cerr << t << ' ';
//		cerr << disp(curr );
//		cerr << cur2 << endl;
//		cerr << t << endl;
		if (cur2 == INF ) continue;
		res = max (res, cur2 );
	} // end rep
	cout << res << endl;
	
	return 0;
}
0