Logical Moos
브론즈 II의견: 0
Farmer John has a boolean statement that is \(N\) keywords long
(\(1 \leq N < 2 \cdot 10^5\), \(N\) odd). Only \(\texttt{true}\) or \(\texttt{false}\)
appear in odd positions, while only \(\texttt{and}\) and \(\texttt{or}\) appear in
even positions.
A phrase of the form \(x\text{ OPERATOR }y\), where \(x\) and \(y\) are either
\(\texttt{true}\) or \(\texttt{false}\), and \(\text{OPERATOR}\) is \(\texttt{and}\) or
\(\texttt{or}\), evaluates as follows:
- \(x\texttt{ and }y\): This evaluates to true if both \(x\) and \(y\) are true, and false otherwise.
- \(x\texttt{ or }y\): This evaluates to true if either \(x\) or \(y\) 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++, \(\texttt{and}\) takes priority over
\(\texttt{or}\). More specifically, to evaluate the statement, repeat the
following step until the statement consists of only one keyword.
- If the statement contains an \(\texttt{and}\), choose any of them and replace the phrase surrounding it with its evaluation.
- Otherwise, the statement contains an \(\texttt{or}\). 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 \(Q\) \((1 \leq Q \leq 2 \cdot 10^5)\) queries. In each query, he gives you
two integers \(l\) and \(r\) (\(1 \leq l \leq r \leq N\), \(l\) and \(r\) are both odd),
and deletes the segment from keyword \(l\) to keyword \(r\) inclusive. In turn, he
wishes to replace the segment he just deleted with just one simple
\(\texttt{true}\) or \(\texttt{false}\) so that the whole statement evaluates to a
certain boolean value. Help FJ determine if it's possible!
Problem credits: Chongtian Ma
SCORING
- Inputs 3-5: \(N,Q\le 10^2\)
- Inputs 6-8: \(N,Q\le 10^3\)
- Inputs 9-26: No additional constraints.
Problem credits: Chongtian Ma
The first line contains \(N\) and \(Q\).
The next line contains \(N\) strings, a valid boolean statement.
The following \(Q\) lines contain two integers \(l\) and \(r\), and a string
\(\texttt{true}\) or \(\texttt{false}\), 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 trueNYYYNYYLet's analyze the first query:
If we were to replace delete the segment \([1, 1]\) and replace it with
\(\texttt{true}\), then the whole statement becomes:
true and true or true
We evaluate the \(\texttt{and}\) keyword from at position \(2\) and obtain
true or true
Since we have no \(\texttt{and}\) keywords left, we have to evaluate the
\(\texttt{or}\) keyword. After evaluation, all that is left is
true
It can be shown that if we were to replace the segment with \(\texttt{false}\),
the statement will still evaluate to \(\texttt{true}\), so we output N since the
statement cannot possibly evaluate to \(\texttt{false}\).
For the second query, we can replace the segment \([1, 3]\) with \(\texttt{true}\)
and the whole statement will evaluate to \(\texttt{true}\), so we output Y.
For the third query, since \([1, 5]\) is the whole statement, we can replace it
with anything, so we output Y.
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 trueYNYYriseoj 작성
출처 올림피아드 > USACO > 2023-2024 > US Open > Bronze
평가 및 의견
Logical Moos
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Logical Moos