プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
- 作者: 渡部有隆,Ozy(協力),秋葉拓哉(協力)
- 出版社/メーカー: マイナビ
- 発売日: 2015/01/30
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (7件) を見る
Quiz
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0041
AC Code
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3999801#1
関連(他の人の解法)
解法
- 構文解析+全探索
- ei1333さんが書いている通り、括弧のパターンは以下の通り
((a.b).(c.d)) (((a.b).c).d) ((a.(b.c)).d)
string ops = "+-*"; void insert(string& s, VC& nums, VC& operators){ // num s[2]=nums[0]; s[6]=nums[1]; s[11]=nums[2]; s[16]=nums[3]; // ops s[4]=operators[0]; s[9]=operators[1]; s[14]=operators[2]; // 空白除去 stringstream ss; for(char c : s){ if(c!=' ') ss<<c; } s = ss.str(); } VS f(VI V){ VC C; for(ll v : V){ char c = '0' + v; C.push_back(c); } VS ret; // 演算子全探索 rep(i, 3){ rep(j, 3){ rep(k, 3){ vector<char> operators = {ops[i], ops[j], ops[k]}; string s; s = "( x . x) .(x . x)"; insert(s, C, operators); ret.push_back(s); s = "((x . x) . x) . x "; insert(s, C, operators); ret.push_back(s); s = "( x .(x . x)). x"; insert(s, C, operators); ret.push_back(s); } } } return ret; } int main(){ cin.tie(0); ios::sync_with_stdio(false); // input ll a,b,c,d; MyParser par; while(cin>>a>>b>>c>>d){ if(a==0) return 0; VI V = {a,b,c,d}; SORT(V); do{ VS lst = f(V); for(string s : lst){ ll v = par.parse(s); debug(s, v); if(v==10){ p(s); goto HERE; } } }while(next_permutation(ALL(V))); p(0); HERE: ll a = 123; } return 0; }