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

Infix notation: X + Y

• Operators are written in-between their operands. This is the usual way we write expressions. An expression such as A * ( B + C ) / D is usually taken to mean something like: "First add B and C together, then multiply the result by A, then divide by D to give the final answer."

Prefix notation (also known as "Polish notation"): + X Y

• Operators are written before their operands. The expressions given above are equivalent to / * A + B C D

Now, please write a program to convert the given expressions from prefix to infix.

Input

The first line contains a positive integer N, indicating the number of testcases in this input.

In the following N lines, each line contains a prefix expression.

In each prefix expression, there is a space between numbers and operators, and operators and operators.

Output

Output the infix expression and its answer of each given prefix expression.

Note that

• There is a space between numbers and operators, and operators and operators.
• If the answer is integer, there is no need to print decimal point. Otherwise, you should print only one digit after the decimal point.
• You have to print a '\n' at the end of each ouput.
• Add a pair of parentheses to wrap around each operator and its operands.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

There’re N stones on the river. The height of the i-th stone is hi for 1≤i≤N.
Frog Pepe is on the 1-st stone at the beginning and he wants to cross this river with several jumps.
For each jump, Pepe can jump to the (i+1)-th or the (i+2)-th stone from the i-th stone.
The energy cost of jump is |hi−hj|, where j is the stone to land on.

Because Pepe is too lazy to move, can you help Pepe to find out the minimun energy cost as few jumps as possible to cross the river?

Explantation of Sample I/O:
The mininum energy is 40. There’re 3 routes having the same cost:

• Stone 1 -> 2 -> 4 -> 5 -> 6, 4 jumps
• Stone 1 -> 2 -> 4 -> 6, 3 jumps
• Stone 1 -> 3 -> 5 -> 6, 3 jumps.

Choose jumps as few as possible.
Therefore, the output is 40, 3.

Input

An integer N on the first line.
h1,h2...hN on the second line.

• 1≤N≤25
• 1≤hi≤100,000

Output

On the first line, two integers C and J, which mean the minimun energy cost and the number of jumps.
Remember ‘\n’ on the end of line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

There are n cookies on the table, the i-th one has c_i calories. Sandy wants to eat them but she is on a diet and can only consume exactly k calories a day. She wants to know whether it is possible for her to consume exactly k calories by eating some of the cookies.

Notes for sample IO

There are 4 cookies, and Sandy can consume exactly 13 calories.

Each cookie has calories 1, 2, 4, 7, respectively.

Sandy can choose the second, third, and fourth cookie so that the sum of their calories is 2+4+7=13.

Input

The first line of the input are two integers n and k.

The second line are n numbers c₁, c₂, ..., c_n.

• 1 <= n <= 20

• 0 <= a_i, k < 10⁹, for i=1~n

Output

Output "YES" (without quotation mark) in one line if it is possible to consume exactly k calories, outplut "NO" (without quotation mark) in one line otherwise.

Sample Input  Download

Sample Output  Download

Tags

Discuss