Description

Bob is a man who wants to climb 3 step stairs.

Suppose he can only climb 1 or 2 step at a time.

Then , there are 3 possible ways to climb 3 step stairs

          (1)  1 step + 1 step + 1 step
          (2)  1 step + 2step
          (3)  2 step + 1step

The question is : if Bob want to climb X step stairs. 

How many possible ways are there to climp X step stairs.
 

Input

An integer N represents the number of testcases.

Then , there are following N lines.

Each line contain an integer X that  represents the number of stairs in that testcase.

P.S. 1<= X <=40

Output

An integer represents the number of possible way to climb N stairs.

Note that you have to add '\n' at the end of output

Sample Input  Download

Sample Output  Download

Tags

Discuss

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

The "Mannulus" casino is now celebrating its grand opening in Canterlot! The owner, Lightyear, introduces the cutting-edge technology to the casino : Farseer Cards Auto Detect System. If it works well, the casino will no longer need to employ any dealer!

The question is : the system cannot automatically rank the cards in the correct order. So Lightyear decides to hire a group of programmers to improve the whole system. You, as a beginning programmer, is assigned to write a program to check whether a set of five cards forms a full house or not. Lightyear will then give you T sets of cards to verify the correctness of your program.

Do not disappoint him.

** For someone who doesn't know the definition of full house : https://en.wikipedia.org/wiki/List_of_poker_hands#Full_house

Input

The first line contains an integer T, representing the number of sets Lightyear gives to you.

The next T lines contain 5 cards in each given set, separated by whitespaces.

The cards would range from : {A, 2, 3, 4, 5, 6, 7, 8 ,9 ,10, J, Q, K}.

(In this problem, you don't need to consider the suit of each card.)

• 1 ≤ | T | ≤ 10000

Output

For each set of card, please print 'YES' if the set is a full house, otherwise please print 'NO'.

Remember to print '\n' after each answer.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Determine the positions of each letter in a given string (with length < 1000001). Then output the positions of each letters in lexicographical order. For each letter, output its positions in increasing order. 

For example, “AbAABBCAaa”

A is at position 0, 2, 3, 7; B is at position 4, 5; C is at position 6; a is at position 8, 9; b is at position 1.

Input

There is only one row, and it is a string S with length smaller than 1000001. 

Output

Please output the answer according to the above requirements, and remember to add ‘\n’ at the end of the outcome of every letter.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a series of numbers, e₁, e₂, e₃, ..., e_N.

With these numbers, we want to know what the sum is in some consecutive range.

In every testcase, you will be given M queries.

Each of them contains two integers which represent left bound (L) and right bound (R) respectively.

Your mission is to give the result of e_L + e_L+1 + ... + e_R,

-

Hint 0 : If you get WA for testcase 1, sample input and output might help you.

Hint 1 : If you get TLE for next three testcases, you should think how to decrease some redundant operations for calculations. Try to store other useful information in the array, instead of sum up all the elements for every query! You may search for the problem's title: "prefix sum".

Hint 2 : If you get MLE, you have to reduce the size of array you created and decide what exactly should be in the array.

Input

First line contains one integer N which is the size of elements.

Second line will have N integers representing all elements in the testcase.

Third line contains one integer M which is the number of queries.

For following M lines, each line contains exactly two integers that stand for left bound (L) and right bound (R) respectively.

It is guaranteed that:

1. 10 ≦ N ≦ 1,000,000

2. 0 ≦ e_i ≦ 100,000, for 1 ≦ i ≦ N

3. L must be less than or equal to R, and R won't exceed the size of elements.

Output

For each query, just give the answer in one line.

Also, remember to print '\n' in the end of line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The midterm is coming.
However, as a lazy CS student, John doesn’t want to make an effort to review lectures from handouts or notes. He decides to do questions from the past exams.

There’re N past exams John has collected from his firends.
The number of questions in the i-th past exam is xi.
It’s very dangerous to take only one past exam for certain lectures.
Therefore, John picks yi questions from the i-th past exam to form a practice for himself.
In other words, there will be  kinds of selections for the i-th past exam.

Can you find how many kinds of practices John may take?
If you can, John will give you his past-exam collections to make you get A+ in every exam.

Because the result may be too large to represent in computer, you’re asked to print the result module 10007, which means you should answer “70” if result = 10077.

Suggestion for 3^rd ~ 5^th testcases

Input

There’re 3 lines for input.
The first line has one number N, representing the number of past exams.
There’re x1,x2,...,xN and y1,y2,...,yN on the second and third lines, respectively, denoting the total numbers of questions and the numbers of picked questions in the past exams.

It is guaranteed that:

• 1 ≤ N ≤ 10⁵
• 0 ≤ yi ≤ xi ≤ 100, xi != 0

Output

Let Z = the number of possible kinds of practices.
Because Z may be too large to represent in computer,
please print Z module 10007 ( Z % 10007 ) in one line, which means you should print “70” if Z = 10077.

Remember the ‘\n’ on the end of line.

Explaination of Sample

x1, x2 = 4, 3.  y1, y2 = 1, 2
There’re 4 and 3 kinds of selections from the 1-st and 2-nd past exams.
Therefore, there’re 4*3 = 12 kinds of practices.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Megumin, a talent explosion magic archwizard, spends a lot of time studying explosion magic spells. For two magic spells A and B, she found that she can combine them together to create a powerful magic spell. Moreover, if the last k characters of A matches the first k characters of B, they can be merged to obtain a more powerful spell. Megumin finds out that the shortest combination of the two spells has maximum power.

For example, if A = "xxxababa" and B = "babayyy", there are severals ways to combine them together:

1. "xxxababababayyy", by simply concatenating A and B, sharing no common characters.

2. "xxxabababayyy", by sharing "ba", the last 2 characters of A and the first 2 characters of B.

3. "xxxababayyy", by sharing "baba", the last 4 characters of A and the first 4 characters of B.

Among all ways of combination, "xxxababayyy" has the maximum power.

Given two magic spells A and B, please output the combination of A and B with maximum power.

Implementation Hints

1. Use strlen() to retrieve length of a string. Remember to #include <string.h>

2. Be careful when using strlen(), or your program might run slowly.

Input

The first line is an integer T, meaning that the input has T test data. Each test data contains a single line.

In each test data, there are two magic spells A and B. Is is guaranteed that A and B only contains lower case alphabets (a-z).

Input consists of two lines. The first line contains A and the second line contains B. It is guaranteed that A and B only contains lower case alphabets (a-z).

• 1 <= T <= 10

• 1 <= |A|, |B| <= 1000

Output

For each test data, please output the answer in one line.  Remember to add new line character ('\n') in the end of each test data.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The floor in Winnie the Pooh’s house is made of N row *M column square woods. 

Today, Winnie wants to mop the floor.

Winnie is standing on the wooden floor in the upper right corner at the beginning, and his big belly can mop 1 or 2 adjacent pieces of wood at the same time. 

Besides, Winnie is a lazy bear, so the next starting position must be adjacent to the last end one.

In problem 13261 - Mop the Floor, we know the answer that the times he need to clean the entire house at least is (n*m+1)/2.

And one strategy is that he goes clockwise.

So please print the position of each step follow the strategy that he goes clockwise.

Input

In a single line you are given two integers N and M  (1 ≤ N, M ≤ 2500).

Output

(n*m+1)/2 line — the position of each step. note you should add '\n' in the last line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

There are N students in line according to the seat number, then M pairs of students exchanged their positions in the sequence.

Can you help the teacher find the positions of students K₁ ~ K_Q? 

For example, N = 4 M = 3, and three exchanges are:

1 2

2 3

3 4

The seat arrangement of students during the exchange process:

1 2 3 4

-> 2 1 3 4

-> 2 3 1 4

-> 2 3 4 1

The final positions of students 1 ~ N are 4 1 2 3

Input

The first line contains three integers N M Q, the number of students, the number of pairs who exchange positions and the number of students whose positions the teacher wants to know.

Each of the next M lines contains two integers a b, indicating the seat exchange.

The last line contains Q integers that mean K₁ ~ K_Q, giving the id. of the students whose positions the teacher wants to know.

test cases:

(4/6) 1 <= a, b, K_i <= N, M, Q <= 1000

(1/6) 1 <= a, b, K_i <= N, M <= 1000, 1 <= Q <= 1000000

(1/6) 1 <= a, b, K_i <= N, M <= 100000, 1 <= Q <= 1000000

NOTE:

To pass test cases 5 and 6, please consider how to reduce unnecessary loop iterations.

Output

The positions of students K₁ ~ K_Q

Note that you need to print ‘\n’ at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a series of numbers, a₁, a₂, a₃, ..., an.

With these numbers, we want to know which is the greatest consecutive sum.

A consecutive sum(L,R) is the sum of a_L, a_L+1, a_L+2, ..., a_R.

Input

First line is a integer N, representing there're N integers.

Next, N integers are provided a₁, a₂, a₃, ..., an.

0 < N <= 2*10⁵

0 <= |a_i| <= 1000

Output

Output the greatest consecutive sum.

Sample Input  Download

Sample Output  Download

Tags

Discuss