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 Int128[](Q); Int128 eval (Int128 x) { int cur = 0; foreach (i; 0..Q) { if (s[i] == "max") { A[cur - 2] = max(A[cur - 1], A[cur - 2]); cur--; continue; } if (s[i] == "min") { A[cur - 2] = min(A[cur - 1], A[cur - 2]); cur--; continue; } if (s[i] == "+") { A[cur - 2] = A[cur - 1] + A[cur - 2]; cur--; continue; } // リテラル if (s[i] == "X") { A[cur] = x; } else { A[cur] = Int128(s[i].to!long); } cur++; } return A[0]; } if (Y < eval(Int128(0L))) { writeln(-1); return; } bool f (Int128 x) { return Y <= eval(x); } Int128 ng = -1L, ok = 10L ^^ 14; while (1 < abs(ok - ng)) { auto 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)); } }