問題一覧 > 通常問題

No.1196 A lazy student

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が$2$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 24
作問者 : capra314cabracapra314cabra / テスター : ThistleThistle
0 ProblemId : 5023 / 出題時の順位表
問題文最終更新日: 2020-08-22 21:45:05

問題文

capra君はとても優柔不断で何も決めることが出来ない.
会議に参加してもYESかNOかはっきりせず, 本質ではない話しかしない.
そんな彼を利用しようとしたautumn君はcapra君に長さ $N$ の文字列 $S$ を渡し, これの通りに動くよう指示した.

この文字列 $S$ は["YES", "NO", "and", "or", "random", "(", ")"]の7種類の文字列のみで構成されており,
capra君はその文字列 $S$ を以下の様な方法で評価し, 最終的に得られた結果を言う.

以下、$x$ と $y$ は評価されてYESかNOとなる式を表す.

1. 式 `$x\ or\ y$` はどちらかが $\mathrm{YES}$ ならば $\mathrm{YES}$ となり, それ以外の時に $\mathrm{NO}$ となる.
2. 式 `$x\ and\ y$` はどちらも $\mathrm{YES}$ ならば $\mathrm{YES}$ となり, それ以外の時に $\mathrm{NO}$ となる.
3. 式 `$random(x\ y)$` はどちらも $\mathrm{YES}$ ならば確率 $P$ で $\mathrm{YES}$ となり, それ以外の時は確率 $Q$ で $\mathrm{YES}$ となる.
    $\mathrm{YES}$とならなかった場合は$\mathrm{NO}$となる.
4. 括弧の中は先に計算する.
5. $\mathrm{and}$ を $\mathrm{or}$ よりも優先して計算する.
6. 優先順位が同じ計算は左から行う.
7. capra君は, 指示通りだとつまらないので$\mathrm{or}$ か $\mathrm{and}$ を評価する度にその結果を確率 $R$ で, $\mathrm{YES}$を$\mathrm{NO}$に, $\mathrm{NO}$を$\mathrm{YES}$に変える.
8. 全ての確率は独立で一様である.

指示書を極秘入手したThistle君はどれくらいの確率でcapra君がYESと言うか知りたい.
Thistle君の為に確率を100分率で返すプログラムを作成してほしい.

この問題はPyPy3で余裕を持って正解できる事が確認されています.
答え(真の値)と提出された値の差が1以下であればこのケースは正答と見なされる. (08/22 19:31追記)

入力

$N$
$P$ $Q$ $R$
$S$

$N$ は整数で $2\leq N\leq 10^6$ を満たす.

$P,Q,R$ は実数で $0\leq P,Q,R\leq 1$ を満たす.
小数点以下は最大3桁まで与えられる.

$S$ は長さ $N$ の文字列である. ["YES", "NO", "and", "or", "random", "(", ")"]のみで構成されており, 文法的に間違っていない事が保証されている.

出力

確率を100分率で計算してから小数点以下を切り捨てて一行で出力せよ.
行の最後には改行をすること.

サンプル

サンプル1
入力
3
0.8 0.2 0.5
YES
出力
100

常に $\mathrm{YES}$ なので100%の確率で YES と答える.

サンプル2
入力
15
0.8 0.2 0.5
YESand(YESorNO)
出力
50

capra君が50%の確率で $\mathrm{or}$ の演算結果を変更するので ($\mathrm{YES}\ \mathrm{or}\ \mathrm{NO}$) の結果は50%の確率で $\mathrm{YES}$ となり, 50%の確率で $\mathrm{NO}$ となる.
次の $\mathrm{and}$ の演算でも50%で演算結果を変更するので答えは50%である.

サンプル3
入力
13
1.0 0.8 0.4
random(YESNO)
出力
80

$\mathrm{random}$ の処理に対して値が $\mathrm{YES}$ と $\mathrm{NO}$ であるので80%の確率でYESと言う. 即ち答えは80%となる.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。