結果
問題 | No.2927 Reverse Polish Equation |
ユーザー |
|
提出日時 | 2024-10-12 16:12:11 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 405 ms / 2,000 ms |
コード長 | 2,021 bytes |
コンパイル時間 | 3,554 ms |
コンパイル使用メモリ | 172,928 KB |
実行使用メモリ | 8,056 KB |
最終ジャッジ日時 | 2024-10-16 00:25:15 |
合計ジャッジ時間 | 10,398 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 43 |
ソースコード
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 ulong[](Q); ulong eval (ulong 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.to!ulong; } else { A[cur] = s[i].to!ulong; } cur++; } 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)); } }