結果

問題 No.1196 A lazy student
ユーザー lam6er
提出日時 2025-03-26 15:48:52
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 231 ms / 1,000 ms
コード長 3,058 bytes
コンパイル時間 223 ms
コンパイル使用メモリ 82,508 KB
実行使用メモリ 180,524 KB
最終ジャッジ日時 2025-03-26 15:49:57
合計ジャッジ時間 2,732 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

def tokenize(s):
    tokens = []
    i = 0
    n = len(s)
    while i < n:
        if i + 5 < n and s[i:i+6] == 'random':
            tokens.append('random')
            i += 6
        elif i + 2 < n and s[i:i+3] == 'YES':
            tokens.append('YES')
            i += 3
        elif i + 2 < n and s[i:i+3] == 'and':
            tokens.append('and')
            i += 3
        elif i + 1 < n and s[i:i+2] == 'NO':
            tokens.append('NO')
            i += 2
        elif i + 1 < n and s[i:i+2] == 'or':
            tokens.append('or')
            i += 2
        elif s[i] in '()':
            tokens.append(s[i])
            i += 1
        else:
            raise ValueError(f"Unexpected character at position {i} in {s}")
    return tokens

def shunting_yard(tokens):
    output = []
    stack = []
    precedence = {'or': 1, 'and': 2, 'random': 3}
    function_names = {'random'}

    for token in tokens:
        if token in ['YES', 'NO']:
            output.append(token)
        elif token in ['and', 'or']:
            while stack and stack[-1] != '(' and precedence.get(stack[-1], 0) >= precedence[token]:
                output.append(stack.pop())
            stack.append(token)
        elif token == 'random':
            stack.append(token)
        elif token == '(':
            stack.append(token)
        elif token == ')':
            while stack[-1] != '(':
                output.append(stack.pop())
            stack.pop()  # Remove '('
            if stack and stack[-1] in function_names:
                output.append(stack.pop())
        else:
            raise ValueError(f"Unexpected token {token}")
    while stack:
        output.append(stack.pop())
    return output

def evaluate_postfix(postfix, P, Q, R):
    stack = []
    for token in postfix:
        if token == 'YES':
            stack.append(1.0)
        elif token == 'NO':
            stack.append(0.0)
        elif token == 'and':
            b = stack.pop()
            a = stack.pop()
            res = a * b
            flipped = res * (1 - R) + (1 - res) * R
            stack.append(flipped)
        elif token == 'or':
            b = stack.pop()
            a = stack.pop()
            res = 1 - (1 - a) * (1 - b)
            flipped = res * (1 - R) + (1 - res) * R
            stack.append(flipped)
        elif token == 'random':
            y = stack.pop()
            x = stack.pop()
            both_yes = x * y
            res = both_yes * P + (1 - both_yes) * Q
            stack.append(res)
        else:
            raise ValueError(f"Unknown postfix token {token}")
    return stack[0]

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    P = float(input[ptr])
    ptr += 1
    Q = float(input[ptr])
    ptr += 1
    R = float(input[ptr])
    ptr += 1
    S = input[ptr].strip()
    tokens = tokenize(S)
    postfix = shunting_yard(tokens)
    prob = evaluate_postfix(postfix, P, Q, R)
    result = prob * 100
    print(int(result // 1))

if __name__ == '__main__':
    main()
0