P2039 - [USACO 2024 US Open Contest Bronze] Problem 1. Logical Moos

文件提交：无需freopen 内存限制：256 MB 时间限制：2.000 S

评测方式：普通裁判命题人：

提交：2 解决：1

Farmer John has a boolean statement that is keywords long (, odd). Only or appear in odd positions, while only and appear in even positions.

A phrase of the form , where and are either or , and is or , evaluates as follows:

: This evaluates to true if both and are true, and false otherwise.
: This evaluates to true if either or is true, and false otherwise.

When evaluating the statement, FJ has to take the order of precedence in Moo Language into account. Similar to C++, takes priority over . More specifically, to evaluate the statement, repeat the following step until the statement consists of only one keyword.

If the statement contains an , choose any of them and replace the phrase surrounding it with its evaluation.
Otherwise, the statement contains an . Choose any of them and replace the phrase surrounding it with its evaluation.

It may be proven that if multiple phrases can be evaluated during a given step, it does not matter which one is chosen; the statement will always evaluate to the same value.

FJ has queries. In each query, he gives you two integers and (, and are both odd), and deletes the segment from keyword to keyword inclusive. In turn, he wishes to replace the segment he just deleted with just one simple or so that the whole statement evaluates to a certain boolean value. Help FJ determine if it's possible!

The first line contains

N

and

Q

The next line contains strings, a valid boolean statement.

The following lines contain two integers and , and a string or , denoting whether he wants the whole statement to evaluate to true or false.

Output a string of length

Q

, where the

i

'th character is Y if the

i

'th query is possible, otherwise N.

5 7
false and true or true
1 1 false
1 3 true
1 5 false
3 3 true
3 3 false
5 5 false
5 5 true

NYYYNYY

Let's analyze the first query:

If we were to replace delete the segment and replace it with , then the whole statement becomes:

true and true or true

We evaluate the keyword from at position and obtain

true or true

Since we have no keywords left, we have to evaluate the keyword. After evaluation, all that is left is

true

It can be shown that if we were to replace the segment with , the statement will still evaluate to , so we output N since the statement cannot possibly evaluate to .

For the second query, we can replace the segment with and the whole statement will evaluate to , so we output Y.

For the third query, since is the whole statement, we can replace it with anything, so we output Y.

2039: [USACO 2024 US Open Contest Bronze] Problem 1. Logical Moos

题目描述

输入

输出

样例输入

样例输出

提示

SAMPLE INPUT:

13 4

false or true and false and false and true or true and false

1 5 false

3 11 true

3 11 false

13 13 true

SAMPLE OUTPUT:

YNYY

SCORING:

来源/分类