13149 - Ternary Expression Evaluation
|
Time |
Memory |
| Case 1 |
1 sec |
32 MB |
| Case 2 |
1 sec |
32 MB |
| Case 3 |
1 sec |
32 MB |
| Case 4 |
1 sec |
32 MB |
| Case 5 |
1 sec |
32 MB |
Description
The ternary operator is an operator in C. Its syntax is as follows:
(condition) ? (expression when true) : (expression when false)
It is often used to replace a simple if-else statement such as:
max = a > b ? a : b;
You can also combine several ternary operators together such as:
max = a > b ? (a > c ? a : c) : (b > c ? b : c);
Now you are given a ternary expression, in which all the values are either true or false. Next you must evaluate the ternary expression with different combinations of values.
More specifically, a valid ternary expression is either:
value
or
value ? VALID_TERNARY_EXPRESSION : VALID_TERNARY_EXPRESSION
And the evaluation order of a ternary expression can be explained as follows:
- If the valid ternary expression is a single value, then just return the value.
- Otherwise:
- if the value before ? is true then replace this ternary expression as the value of the ternary expression between ? and :
- if the value before ? is false then replace this ternary expression as the value of the ternary expression after :
Hint: You can apply the idea of a syntax tree to solve this problem.
Input
The first line of the input is a valid ternary expression that contains the ternary operators and value indices.
- It is guaranteed that the value indices are pairwise distinct and range from 1 to the number of values in this ternary expression.
- For example, in the sample input below, the number of values is 5, and the value indices from left to right is 5, 3, 2, 4, 1, respectively.
The next line contains a single integer T, (T <= 5000), representing the number of combinations you have to evaluate.
For the next T lines, each line contains a binary string whose length is equal to the number of values in the ternary expression, giving the setting of each value.
- Note that the i-th character in this binary string (counted from left) is for the value index i. (1 represents true and 0 represents false)
- For string "01101", value indices 1-5 are set as 0,1,1,0,1, respectively.
There are 5 testcases in this problem.
For the first 3 testcases: 1 <= number of values <= 5
For the rest of the testcases: 1 <= number of values <= 3001
Output
For each combination, output the value of the ternary expression. (1 represents true and 0 represents false)
Remember to add a newline character at the end of every line.
Tags