結果

問題 No.1196 A lazy student
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:42:04
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 5,140 bytes
コンパイル時間 150 ms
コンパイル使用メモリ 82,520 KB
実行使用メモリ 160,456 KB
最終ジャッジ日時 2025-03-31 17:43:26
合計ジャッジ時間 5,364 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12 RE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

class YesNode:
    pass

class NoNode:
    pass

class AndNode:
    def __init__(self, left, right):
        self.left = left
        self.right = right

class OrNode:
    def __init__(self, left, right):
        self.left = left
        self.right = right

class RandomNode:
    def __init__(self, x, y):
        self.x = x
        self.y = y

def tokenize(s):
    tokens = []
    n = len(s)
    pos = 0
    while pos < n:
        if pos + 6 <= n and s[pos:pos+6] == 'random':
            tokens.append('random')
            pos += 6
            continue
        if pos + 3 <= n and s[pos:pos+3] == 'YES':
            tokens.append('YES')
            pos += 3
            continue
        if pos + 3 <= n and s[pos:pos+3] == 'and':
            tokens.append('and')
            pos += 3
            continue
        if pos + 2 <= n and s[pos:pos+2] == 'NO':
            tokens.append('NO')
            pos += 2
            continue
        if pos + 2 <= n and s[pos:pos+2] == 'or':
            tokens.append('or')
            pos += 2
            continue
        if s[pos] == '(' or s[pos] == ')':
            tokens.append(s[pos])
            pos += 1
            continue
        raise ValueError(f"Invalid token at position {pos} in string {s}")
    return tokens

class Parser:
    def __init__(self, tokens):
        self.tokens = tokens
        self.pos = 0
    
    def parse(self):
        return self.parse_expr()
    
    def parse_expr(self):
        return self.parse_or_expr()
    
    def parse_or_expr(self):
        node = self.parse_and_expr()
        while self.has_next() and self.current_token() == 'or':
            self.consume()
            right = self.parse_and_expr()
            node = OrNode(node, right)
        return node
    
    def parse_and_expr(self):
        node = self.parse_primary()
        while self.has_next() and self.current_token() == 'and':
            self.consume()
            right = self.parse_primary()
            node = AndNode(node, right)
        return node
    
    def parse_primary(self):
        token = self.current_token()
        if token == 'YES':
            self.consume()
            return YesNode()
        elif token == 'NO':
            self.consume()
            return NoNode()
        elif token == 'random':
            self.consume()
            self.consume('(')
            x = self.parse_expr()
            y = self.parse_expr()
            self.consume(')')
            return RandomNode(x, y)
        elif token == '(':
            self.consume()
            expr = self.parse_expr()
            self.consume(')')
            return expr
        else:
            raise SyntaxError(f"Unexpected token {token} at position {self.pos}")
    
    def has_next(self):
        return self.pos < len(self.tokens)
    
    def current_token(self):
        if self.pos >= len(self.tokens):
            return None
        return self.tokens[self.pos]
    
    def consume(self, expected=None):
        if expected is not None:
            if not self.has_next() or self.tokens[self.pos] != expected:
                raise SyntaxError(f"Expected {expected}, got {self.tokens[self.pos] if self.has_next() else 'EOF'}")
        self.pos += 1

def main():
    import sys
    input = sys.stdin.read().splitlines()
    N = int(input[0])
    P, Q, R = map(float, input[1].split())
    S = input[2].strip()
    
    tokens = tokenize(S)
    parser = Parser(tokens)
    root = parser.parse()
    
    memo = {}
    stack = [ (root, False) ]
    
    while stack:
        node, is_processed = stack.pop()
        if node in memo:
            continue
        if isinstance(node, YesNode):
            memo[node] = 1.0
            continue
        if isinstance(node, NoNode):
            memo[node] = 0.0
            continue
        if not is_processed:
            stack.append( (node, True) )
            if isinstance(node, (AndNode, OrNode)):
                stack.append( (node.right, False) )
                stack.append( (node.left, False) )
            elif isinstance(node, RandomNode):
                stack.append( (node.y, False) )
                stack.append( (node.x, False) )
        else:
            if isinstance(node, AndNode):
                left = memo[node.left]
                right = memo[node.right]
                original = left * right
                res = original * (1 - R) + (1 - original) * R
                memo[node] = res
            elif isinstance(node, OrNode):
                left = memo[node.left]
                right = memo[node.right]
                original = 1 - (1 - left) * (1 - right)
                res = original * (1 - R) + (1 - original) * R
                memo[node] = res
            elif isinstance(node, RandomNode):
                x_p = memo[node.x]
                y_p = memo[node.y]
                prob_both = x_p * y_p
                res = prob_both * P + (1 - prob_both) * Q
                memo[node] = res
            else:
                raise TypeError(f"Unexpected node type {type(node)}")
    
    result = memo[root] * 100
    print(int(result // 1))

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