Description

The Tower of Hanoi is a mathematical game puzzle. It consists of three rods, which are A, B and C. The puzzle starts with n disks in ascending order of size on rod A, the smallest at the top.

The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

1.   Only one disk can be moved at a time.

2.   Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.

3.   No disk may be placed on top of a smaller disk.

Write a program to simulate the moves of the disks. Print the number of disk which is moved in each step.

 

For example, if n = 3, the moves of each steps are:

move disk 1 from rod A to rod C
move disk 2 from rod A to rod B
move disk 1 from rod C to rod B
move disk 3 from rod A to rod C
move disk 1 from rod B to rod A
move disk 2 from rod B to rod C
move disk 1 from rod A to rod C

You should print out:

1
2
1
3
1
2
1

HINT : You can modify this sample code and implement the function 'hanoi'

#include <stdio.h>
void hanoi(int n, char A, char B, char C);

int main(){
    int n;
    scanf("%d", &n);
    hanoi(n, 'A', 'B', 'C');
    return 0;
}

Input

An integer n (0<n<20), which means the number of disk.

Output

Print out the number of disk which is moved in each step, and there is a '\n' at the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Fibonacci's soup is one of the most well-known recipe in Fibonacci's hometown. Besides making soup, Fibonacci also enjoys seeking weird sequences. 

We all know that we would not like to add two days before yesterday's soup into Fibonacci's soup, otherwise, It would cause food safety issues, and it would become "Bad Fibonacci's soup", aka "BFS".

One day, Fibonacci found a new sequence again. Since Fibonacci just eat Bad Fibonacci's soup for his lunch and was vomiting, he decided to name this newly found sequence "Bad Fibonacci's sequence".

 

The following is the formula for the sequence:

 

Hint:

If your program gets a "Time Limit Exceeded", your program may solve a same problem (e.g., f(m) or g(n)) too many times. We suggest that you use the dynamic programming method as follows:

• Use a global array to store the solutions to the problems that have been solved so far.
• Then, whenever we attempt to solve a problem, we first check the array to see if the problem is already solved.
  • ​If a solution has been recorded, we can use it directly (that is, no further recursive calls).
  • Otherwise, we solve the problem and record its solution in the array.

In this way, we can avoid repeated computation and reduce the computation time significantly.

Input

The input contains one line: nonnegative integers a, b, c, d and n.  

Testcase constraints

• For all the testcases: a, b, c, d ≤ 100
• Testcase 1~3: n ≤ 40
• Testcase 4~7: n ≤ 60
• Testcase 8~10: n ≤ 80

Output

Output one line, including f(n) and g(n).

Please remember to print '\n' at the end.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Koying is rich and, in an attempt to address the issue of the bumpy road (崎嶇不平的道路) in Hsinchu, has bought a road roller.

However, he realized after the purchase that he didn't have a driver's license.

As a temporary solution, he has decided to write a program to simulate how the road roller should move. His program simulates the following environment:

There is a grid of N × M cells, representing the map of Hsinchu City. Each cell has a bumpy value (崎嶇值).

A higher bumpy value means a more bumpy, and a bumpy value of 0 represents a flat (平整的) area.

Whenever the road roller passes over a cell, the ground becomes flattened, and the cell's bumpy value is set to 0.

Koying's movement rules are as follows:

1. Koying starts from the top-left corner of Hsinchu City, at coordinates (1, 1).
2. Koying will not drive outside the boundaries of Hsinchu City, which range from (1, 1) to (N, M).
3. Koying will choose the moving direction first.
   Let X be the neighboring cell in one of the four directions (up, down, left, right) with the highest bumpy value and has not been flattened (bumpy value > 0). Koying will choose the direction of X as his moving direction.
4. Koying will start driving the road roller to the direction of X.cKoying will stop until he is on a cell with a higher bumpy value than X or he is on the last cell in that direction. When Koying stops on a cell, he will flatten it. After flattening the cell he stopped on, he will find a new direction to move on (go to step 3).
   (Hint: in this step, Koying won't stop when he reaches a cell with a bumpy value of 0, or all his surrounding cells' bumpy values are 0.)
5. Koying will stop rolling the road when all four neighboring directions around Koying have been flattened.

Your task is calculating the total sum of flattened ground's bumpy values.

Note that if a cell is passed over multiple times, its bumpy value should not be accumulated more than once since each area can only be flattened once.

If Koying manages to flatten all the roads in Hsinchu City, you should output "Road Roller Da!!".

As Koying is currently occupied with helping the power plant at National Tsing Hua University generate electricity, and his absence might lead to a power outage, he has requested you finish this program so that he can focus on power generation.

No recursion is required in this problem! :)

Input

The first line contains two positive integers, N and M, representing the size of the grid.

Following that, there are N lines, each containing M positive integers A_{i, j}, indicating the bumpy value of the grid cell at row i and column j.

Constraints:

• 1 ≤ N, M ≤ 100
• 1 ≤ A_{i, j} ≤ 10,000
• It is guaranteed that no two grid cells have the same bumpy value.

Output

In the first line, please output a positive integer, representing the total sum of flattened ground's bumpy values.

If the road roller manages to pass over every grid cell, please output "Road Roller Da!!" (without quotation marks) on the second line.

Remember to print a ‘\n’ at the end of the output.

Sample IO Description

Sample I/O 2:

Hsinchu City

Koying starts from the top-left corner of Hsinchu City.

right(39) > down(37), so drive the road roller to right, until he met a cell with a higher bumpy value than 39. (but there is no bumpy value greater than 39, so koying stop at the last cell in this direction.)

go down, until he met a cell with a higher bumpy value than 3. (so Koying will stop at 6.)

down(49) > left(17), so koying go down until he met a cell with a higher bumpy value than 49. (but there is no bumpy value greater than 49, so koying stop at the last cell in this direction.)

go left, until he met a cell with a higher bumpy value than 32. (so Koying will stop at 38.)

up(36) > left(31), so koying go up until he met a cell with a higher bumpy value than 36. (but there is no bumpy value greater than 36, so koying stop at the last cell in this direction.)

four neighboring directions around Koying have been flattened, so the simuates is stop.

the total sum of flattened ground's bumpy values is 18 + 39 + 14 + 13 + 25 + 3 + 6 + 49 + 41 + 32 + 1 + 38 + 36 + 27 + 7 = 349 .

Sample Input  Download

Sample Output  Download

Tags

Discuss