import std; void main () { int Q; long Y; readln.read(Q, Y); auto s = readln.split; // minとmaxが一つでも入り込んでしまうと再帰的に評価せざるを得なくなる。 // XはXのまま与えられるので、どうやっても係数が負にはならない // -> 最終的な評価値はXに対して単調な関数となる。 // -> 二分探索できますね。 // 式の評価をどうやって行うかが鬼門 // -> Xは二分探索毎で確定しているので順番に行えばよいのではないでしょうか。 auto A = new BigInt[](0); BigInt eval (long x) { A.length = 0; foreach (i; 0..Q) { if (s[i] == "max") { A[$ - 2] = max(A[$ - 1], A[$ - 2]); A.length--; continue; } if (s[i] == "min") { A[$ - 2] = min(A[$ - 1], A[$ - 2]); A.length--; continue; } if (s[i] == "+") { A[$ - 2] = A[$ - 1] + A[$ - 2]; A.length--; continue; } // リテラル if (s[i] == "X") { A ~= x.to!BigInt; } else { A ~= s[i].to!BigInt; } } return A[0]; } if (Y < eval(0)) { writeln(-1); return; } bool f (long x) { return Y <= eval(x); } long ng = -1, ok = 10L ^^ 14; while (1 < abs(ok - ng)) { long mid = (ok + ng) / 2; if (f(mid)) { ok = mid; } else { ng = mid; } } if (eval(ok) == Y) { writeln(ok); } else { writeln(-1); } } void read (T...) (string S, ref T args) { import std.conv : to; import std.array : split; auto buf = S.split; foreach (i, ref arg; args) { arg = buf[i].to!(typeof(arg)); } }