Description

This is a Sierpinski Carpet.

The construction of a Sierpinski Carpet is stated as follows. Initially, you are given a white square.

1. Divide the square into nine subsquares in a 3-by-3 grid.

2. Color the center subsquare with black.

3. For the rest eight subsquare, repeat step 1

For example,

Initially (after zero iteration), there is 0 black square in the Sierpinski Carpet.

After one iteration, there is 1 black square in the Sierpinski Carpet.

After two iterations, there are 9 black squares in the Sierpinski Carpet.

After three iterations, there are 73 black squares in the Sierpinski Carpet

Given an integer k, please output number of black squares after k iterations.

Maybe Useless Hint

• It is suggested to solve this problem using recursion. (Well ... there is mathematic solution, but hope you practice how to design recursion function)

• Be careful with overflow. Suggest to calculate with long long int.

Input

Input contain a single integer k.

Since there will be overflow issue if k is too big, so in this problem 0 <= k < 10.

Output

Output the number of black squares after the k-th iteration.

Note that there is a newline character after the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

There are N stones on the river. The height of the i-th stone is hi for 1 <= i <= N and is colored with color ci. Toad Epep is on the S-th stone (where the leftmost stone is the 1-st stone) and he wants to go the the T-th stone with several jumps.

For each jump from the i-th stone, Epep can jump to the (i-1)-th stone (if it exists), the (i+1)-th stone (if it exists), or any stone colored with the same color c_i (if it exists).

Epep will only visit each stone at most once. That is, if Epep jumped to the k-th stone at some time, he won't jumped to the k-th stone again.

The energy cost of jump from i-th to j-th stone is |i-j| x |h_i - h_j|.

Because Epep ate too much insects and wants to do more exercise, can you help Epep to find the way that cost the most energy (if there are several ways with same maximum energy cost, find the way with maximum jumps) ?

Explanation of Sample IO

All possible moves are listed in the following:

• 2 -> 1 -> 4 -> 3 -> 6 -> 5, which costs 100 energy and 5 jumps

• 2 -> 1-> 4 -> 5, which costs 60 energy and 3 jumps

• 2 -> 3-> 4-> 5, which costs 40 energy and 3 jumps

• 2 -> 3 -> 6 -> 5, which costs 40 energy and 3 jumps

• 2 -> 5, which costs 0 energy and 1 jump

Hint:

1. In this problem, you may need to use an array int jumped[N+1] to record whether a stone i has been visited in the currently expanded path.

2. However, you need to manipulate the int jumped[N+1] array properly as follows:

 

Input

Integers N, S, T are on the first line.

h₁, ..., h_N are on the second line.

c₁, ..., c_N are on the third line.

• 1 <= N <= 15

• 1 <= S, T <= N and S != T

• 1 <= h_i <= 100000

• 1 <= c_i <= 15

Test case description

• Test case 1: all stones have different colors

• Test case 2: all stones have the same color

• The remaining test cases: no additional restrictions

Output

Output two integers E and J, where E is the maximum energy cost and J is the number of jumps in one line. Remember to add \n in the end.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

       
 

Doraemon enjoys solving the Rubik's Cube.
Today, he received a scrambled 2×2×2 Rubik's Cube and wants to know if he can solve it within n moves. 
Can you help him out?

To represent the state of a 2x2x2 Rubik's Cube, we use a string consisting of W, O, B, G, Y and R, representing white, orange, blue, green, yellow, and red colors, respectively, and the string has a length of 24. For more details, you can refer to the above image.

We define a move performed on a Rubik's Cube as a clockwise rotation of one of its six faces (Up, Left, Front, Right, Back, Down). To simplify this problem, the counterclockwise rotation is defined as equivalent to performing three moves.

 

Implementation

 

In this problem, the code for preprocessing the Rubik's Cube state string, I/O and some useful functions are already provided.
--->  Please follow the link to download the code  <---

Your only task is to implement solve(int n) function:
return 1 if the Rubik's Cube can be solved within n moves, otherwise return 0. 
In your implementation, you may need to utilize the following functions:

• move(int face): Use UP/LEFT/FRONT/RIGHT/BACK/DOWN as parameters to perform the move.
• isSolved(): Return 1 if the Rubik's Cube is solved; otherwise, return 0.
• printRubiks(): Print the Rubik's Cube state for debugging purposes.

You can trace the code for more detailed information.

 

Example I/O

 

Sample Input 1	Sample Input 2

 

• In sample input 1, the minimum number of moves required to solve the Rubik's Cube is 3.
  Here is one way to solve it: move(DOWN); move(FRONT); move(LEFT);
  Since 3 ≤ 5, output "Yes".
• In sample input 2, the minimum number of moves required to solve the Rubik's Cube is 6.
  Here is one way to solve it: move(UP); move(DOWN); move(RIGHT); move(BACK); move(FRONT); move(LEFT);
  Since 6 > 5, output "No".

 

Hint

 

You can use recursion to implement the function and explore all possible ways to solve the Rubik's Cube.
To prevent unnecessary searches that could lead to a TLE result, make sure to terminate the function when the number of moves exceeds.

 

Input

• The first line contains a single integer T (1 ≤ T ≤ 10), representing the number of test cases.
• For the next T lines, each line represents a test case.
  • Each test case consists of an integer n (1 ≤ n ≤ 5) and a string that represents the state of a Rubik's Cube.
  • The string has a length of exactly 24 characters and contains only the characters 'Y', 'B', 'O', 'G', 'R', and 'W'.
  • It is guaranteed that the given Rubik's Cube is solvable.

 

Output

Output T lines. For each line, if the given Rubik's Cube can be solved within n moves, print "Yes", Otherwise, print "No".

 

Sample Input  Download

Sample Output  Download

Tags

Discuss