| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 11283 | rotate linked list |
|
| 12183 | Fairy Testing |
|
| 12729 | Cocoa the Abstract Artist |
|
Description
Given a link list structure named Node.
typedef struct _Node {
int data;
struct _Node *next;
} Node;
Given a list, rotate the list to the left by k places, where k is non-negative and k is smaller than the count of nodes in linked list.
For example:
Given 1->2->3->4->5->NULL and k = 3,
return 4->5->1->2->3->NULL.
Input
The input contains 2 sequence of positive integers.The first sequence is to create a linked list of integers, except the last one, which is -1, indicating the end of the sequence. The second line is an integer k.
Output
The output contains the sequence of resulting linklist.
Sample Input Download
Sample Output Download
Partial Judge Code
11283.cPartial Judge Header
11283.hTags
Discuss
Description
In this problem, you are given a prefix Boolean expression, which has at most N=10^5 variables and 2 kinds of operators ‘&’ and ‘|’. Each variable has an ID number. The values of these variables can be either 0 or 1, and are all initialized as 0.
You will be given M ID numbers. For each ID number, you should flip (0 will become 1, 1 will become 0) the value of the corresponding variable and then compute/output the result of the prefix Boolean expression.
Example:
Assume the prefix Boolean expression is &[1][2] and the given ID numbers are “2 1”. First the value of variable 2 will change from 0 to 1. The output of &[1][2] is 0&1=0. Next, the value of variable 1 will change from 0 to 1. The output of &[1][2] is 1&1=1.
Hint: (You can go to the Input/Output description directly, and come back for hints if necessary.)
Hint 1: To solve this problem, you can parse the input and derive the output recursively each time a variable is flipped. Unfortunately, this brute-force approach is not efficient and can lead to TLE, in particular the 3rd and 4th testcases in this problem. We encourage you to use the syntax tree of the prefix Boolean expression for better efficiency.
Hint 2: The key idea behind the syntax-tree approach is to avoid re-evaluation of the whole expression every time a bit is flipped. Some more hints are provided for you as follows:
- [Data structure] Use a tree node pointer array to record the address of each variable (leaf) node of the syntax tree: you can locate each variable to be flipped directly;
- [Data structure] For each tree node i, record the value of its subtree (rooted at node i);
- [Algorithm] Starting from the variable node to be flipped, move upward following the syntax tree and update the node values until the output of the syntax tree (or the Boolean expression) can be determined.
Example:
Consider the following syntax tree for "|&|[1][2][3][4]". Assume [1] is flipped. You will find that the value of node A should be changed to 1|0=1. Moreover, you note that the value of B remains unchanged, i.e., 1&0=0, and the checking process can stop.
Later, when [3] is flipped, both the values of node B and the root node should be changed. In this case, the output is also changed.
Sample structure:
typedef struct node{
int value; // This is the value of the subtree, not the ID number
int tokentype;
struct node *leftchild;
struct node *rightchild;
struct node *parent; //pointing to the parent node
}Node;
Node* variable[100001]; // This array stores the pointers pointing to the tree nodes. For example, variable[0] points to the node with ID number 0.
Input
The first line has one number T, 0<T<= 7, indicating the number of testcases.
The following lines are the inputs of the testcases.
Each testcase contains three lines:
1. N, M (0<N<=100000, indicating the number of variables in a given prefix Boolean expression. 0<M<=100000, indicating how many times the values are flipped).
2. A string S, describing the prefix Boolean expression (& means and gate, | means or gate, [i] means a variable ID)
3. M numbers, where each number i means the value of variable i is flipped. The order matters.
Note that all the variables are initially 0.
Each ID number only appears once in the prefix Boolean expression.
The depth of the tree is no more than 30.
Output
For each testcase, you should output M lines, each showing the output of the prefix Boolean expression after a variable is flipped.
0 for false, 1 for true.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Problem brought to you by NTHU Order a Rabbit Club.
A reliable oneesan, a genius in arithmetics, an amazing baker… that is our protagonist - Hoto Cocoa. The young girl has many talents for sure, but art seems to be not one of them.
As much as Cocoa wants to appear reliable, she is so depressed how bad her art homework turns out, that she asks Chino to help her improve her drawing.
Cocoa’s drawing can be represented as a 2D array of size N*M: N rows with M integers in each row. Each integer represents the color on that position; two positions have the same color iff they have the same integers, to be more precise.
Chino is doubtlessly great at art, but only abstract art. She will view a piece of drawing acceptable, if and only if each color that appears in the drawing forms a single connected component.
That is, for any two blocks that share the same color ci, one can find a way to walk from one to the other using only 4 directions: up, down, left, right, while only walking on blocks of color ci.
For example, in the drawing below, there are two colors 0 and 6 that fail to form a single connected component.
If Cocoa’s drawing fails this criteria for a good abstract art, Chino wants to point out what colors violate the rules, and should be eliminated in order for the drawing to be acceptable. But since Cocoa has made a very big painting, Chino wants you to write a program to help her find these colors.
(If you help Chino maybe she’ll let you pat her head!)
Input
Each input file contains only one testcase. For each test case, there will be one line and a 2D array A that describes Cocoa’s drawing.
The first line contains a pair of integers N M, denoting the size of the drawing. Both N and M will not exceed 1000.
Hence come N lines, each having M integers. The j-th integer in the i-th line, Aij, has the range 0 to 65535.
Output
For each testcase, if the drawing is an acceptable abstract art (by Chino’s standards), print a single word “ABSTRACT”(without quotation marks); else, if there are k colors that need to be eliminated, print the numbers of these colors on k separate lines in ascending order.