Questions: Checkpoint 3 — Mock Contest 3

The first line contains R C, and the next R lines form a garden map whose open cells are . and whose hedges are #. Print the number of different routes from the top-left cell to the bottom-right cell that move one cell up, down, left, or right at a time, enter only open cells, and never visit the same cell twice. Use recursive backtracking with a list of visited flags: mark the current cell before trying its neighbours, and un-mark it after those recursive calls come back so that other routes may use it. In the sample, 4 routes take the fewest steps, and 3 longer routes wander up or left before finishing, so counting only the shortest routes gives the wrong answer.

Constraints. 1 <= R, C <= 5. Every row has exactly C characters, and the top-left and bottom-right cells are open. When the garden is a single cell, its one route makes no moves and counts as 1.

Sample Input

3 4
....
.#..
....

Sample Output

7

The input is one valid space-separated postfix expression whose tokens are the bits 0 and 1 or the gate names AND, OR, IMP, and NOT. NOT takes one operand and flips it; AND gives 1 only when both operands are 1; OR gives 1 when at least one operand is 1; and left IMP right gives 0 only when left is 1 and right is 0, and 1 otherwise. Evaluate the expression from left to right using a deque as a stack: push with appendleft, remove with popleft, and for a two-operand gate remove the right operand first and the left operand second. Print the final bit. In the sample, both IMP gates depend on operand order, and swapping left and right changes the result from 0 to 1.

Constraints. The expression contains between 1 and 200000 tokens and is guaranteed to be valid. Every gate finds enough operands on the stack, and exactly one bit remains after the final token.

Sample Input

1 1 0 IMP NOT AND 0 IMP

Sample Output

0

The input contains a non-negative decimal integer n and a base B. Write n in base B by hand with repeated remainder and integer-division operations, not a built-in conversion, and print that representation with no leading zeroes on the first line; 0 is written as 0. On the second line, print YES if the representation reads the same from left to right as from right to left, or NO otherwise. In the sample, 131 is 11212 in base 3, so a digit string built in remainder order prints 21211 instead, and the last digit differs from the first.

Constraints. 0 <= n <= 1000000000000000000 and 2 <= B <= 10. Every digit of the representation is between 0 and B - 1.

Sample Input

131 3

Sample Output

11212
NO

The first line contains L S: a panel of L lamps numbered 0 through L - 1, all off at the start, and S switches. Each of the next S lines describes one switch as a count k followed by k distinct lamp numbers, and pressing that switch flips each of those lamps between off and on. Each switch is pressed at most once, and the order of presses does not matter. Print the fewest switches you must press to turn every lamp on, or -1 if no choice of switches does it. Turn each switch into a bitmask with 1 << lamp, examine every choice of switches as a mask from 0 through (1 << S) - 1, combine the chosen switches with ^, and compare the result with (1 << L) - 1. In the sample, the largest switch flips lamps 1 2 4 but belongs to no working choice, and the only three-switch answer needs the final switch.

Constraints. 1 <= L <= 30 and 1 <= S <= 16. Every switch flips between 1 and L distinct lamps, each numbered from 0 through L - 1.

Sample Input

5 4
3 1 2 4
1 3
2 0 2
2 1 4

Sample Output

3

The first line is N, and each of the next N lines contains the integer coordinates x y of one corner of a hiking route, in walking order; consecutive corners are different points. The hiker walks in a straight line from each corner to the next and stops at every point with two integer coordinates along the way. Print the total number of stops: the first corner counts once at the start, and each leg adds every integer point after the leg's start up to and including its end, so a point the route visits again is counted again. A leg that moves dx across and dy up adds gcd(|dx|, |dy|) stops, so compute each GCD with Euclid's algorithm instead of walking the leg one unit at a time. In the sample, the vertical leg from 4 6 to 4 1 adds gcd(0, 5) = 5, and the final leg to -2 -2 has negative differences and adds gcd(6, 3) = 3, for 11 stops in all.

Constraints. 2 <= N <= 50000. Every coordinate is between -1000000000 and 1000000000. A leg can be two billion units long, so stepping along it one unit at a time will not finish in time.

Sample Input

4
0 0
4 6
4 1
-2 -2

Sample Output

11

The input is one integer N. Two primes form a twin pair when they differ by exactly 2, like 11 and 13. Print the number of twin pairs p and p + 2 with both primes at most N. Build one Sieve of Eratosthenes through N, crossing off multiples of each prime beginning at p * p, and then check each candidate pair in the finished sieve. In the sample, N is 13 * 13 and 167 is prime, so a sieve that never crosses off the square 169 reports one pair too many.

Constraints. 2 <= N <= 2000000. Testing every candidate by trial division will not finish in time.

Sample Input

169

Sample Output

12

The first line contains N root, followed by N lines in node-index order from 0 through N - 1; each node line contains value left right, where value is the node's integer value and each child is a node index or -1 when that child is missing. A leaf is a node whose two children are both missing. Print the greatest total of node values along a path that starts at the root, moves down one child at a time, and ends at a leaf. Use a recursive function that gives back the best path total starting at a node, and recurse only into children that exist. In the sample, node 1 has only a right child, so no path may stop there; treating its missing left child as a path worth 0 changes the answer from 8 to 9.

Constraints. 1 <= N <= 100000. Every node value is between -1000000000 and 1000000000; the root and non-missing child indices are between 0 and N - 1. The input describes one valid binary tree containing every node exactly once, and its height is at most 900.

Sample Input

5 0
5 1 2
4 -1 3
1 4 -1
-10 -1 -1
2 -1 -1

Sample Output

8