### 引言

Acquire fundamental elements of algorithms and data structures.

### Topic #1 Getting Started

#### ALDS1_1_A Insertion Sort

Time Limit : 1 sec , Memory Limit : 131072 KB

Write a program of the Insertion Sort algorithm which sorts a sequence A in ascending order. The algorithm should be based on the following pseudocode:

Note that, indices for array elements are based on 0-origin.

To illustrate the algorithms, your program should trace intermediate result for each step.

##### Input

The first line of the input includes an integer N, the number of elements in the sequence.

In the second line, N elements of the sequence are given separated by a single space.

##### Output

The output consists of N lines. Please output the intermediate sequence in a line for each step. Elements of the sequence should be separated by single space.

1 ≤ N ≤ 100

##### 問題を解く

###### 代码实现

• i：循环变量，表示未排序部分的开头元素
• key：临时保存arr[i]值的变量
• j：循环变量，用于在已排序部分寻找key的插入位置

###### 注意点
• 数组长度是否足够长
• 是否搞错了0起点和1起点的数组下标
• 是否误用了循环变量（比如ij
• 是否输出了多余的空格或换行

#### ALDS1_1_B Common Divisor Greatest

Time Limit : 1 sec , Memory Limit : 131072 KB

Write a program which finds the greatest common divisor of two natural numbers a and b

##### Input

a and b are given in a line sparated by a single space.

##### Output

Output the greatest common divisor of a and b.

1 ≤ a, b ≤ 109

##### Hint

You can use the following observation:

For integers x and y, if xy, then gcd(x, y) = gcd(y, x%y)

#### ALDS1_1_C Prime Numbers

Time Limit : 1 sec , Memory Limit : 131072 KB

A prime number is a natural number which has exactly two distinct natural number divisors: 1 and itself. For example, the first four prime numbers are: 2, 3, 5 and 7.

Write a program which reads a list of N integers and prints the number of prime numbers in the list.

##### Input

The first line contains an integer N, the number of elements in the list.

N numbers are given in the following lines.

##### Output

Print the number of prime numbers in the given list.

##### Constraints

1 ≤ N ≤ 10000

2 ≤ an element of the list ≤ 108

#### ALDS1_1_D Maximum Profit

Time Limit : 1 sec , Memory Limit : 131072 KB

You can obtain profits from foreign exchange margin transactions. For example, if you buy 1000 dollar at a rate of 100 yen per dollar, and sell them at a rate of 108 yen per dollar, you can obtain (108 - 100) × 1000 = 8000 yen.

Write a program which reads values of a currency $R_t$ at a certain time $t$ ($t=0,1,2,…n−1$), and reports the maximum value of $R_j−R_i$ where $j>i$ .

##### Input

The first line contains an integer nn. In the following nn lines, $R_t$ ($t=0,1,2,…n−1$) are given in order.

##### Output

Print the maximum value in a line.

##### Constraints
• 2≤n≤200,000
• 1≤$R_t$≤$10^9$

### Topic # 2 Sort I

#### ALDS1_2_A Bubble Sort

Write a program of the Bubble Sort algorithm which sorts a sequence A in ascending order. The algorithm should be based on the following pseudocode:

Note that, indices for array elements are based on 0-origin.

Your program should also print the number of swap operations defined in line 4 of the pseudocode.

##### Input

The first line of the input includes an integer N, the number of elements in the sequence.

In the second line, N elements of the sequence are given separated by spaces characters.

##### Output

The output consists of 2 lines.

In the first line, please print the sorted sequence. Two contiguous elements of the sequence should be separated by a space character.

In the second line, please print the number of swap operations.

1 ≤ N ≤ 100

#### ALDS1_2_B Selection Sort

Time Limit : 1 sec , Memory Limit : 131072 KB

Write a program of the Selection Sort algorithm which sorts a sequence A in ascending order. The algorithm should be based on the following pseudocode:

Note that, indices for array elements are based on 0-origin.

Your program should also print the number of swap operations defined in line 6 of the pseudocode in the case where i ≠ mini.

##### Input

The first line of the input includes an integer N, the number of elements in the sequence.

In the second line, N elements of the sequence are given separated by space characters.

##### Output

The output consists of 2 lines.

In the first line, please print the sorted sequence. Two contiguous elements of the sequence should be separated by a space character.

In the second line, please print the number of swap operations.

1 ≤ N ≤ 100

#### ALDS1_2_C Stable Sort

Time Limit : 1 sec , Memory Limit : 131072 KB

Let’s arrange a deck of cards. There are totally 36 cards of 4 suits(S, H, C, D) and 9 values (1, 2, … 9). For example, ‘eight of heart’ is represented by H8 and ‘one of diamonds’ is represented by D1.

Your task is to write a program which sorts a given set of cards in ascending order by their values using the Bubble Sort algorithms and the Selection Sort algorithm respectively. These algorithms should be based on the following pseudocode:

Note that, indices for array elements are based on 0-origin.

For each algorithm, report the stability of the output for the given input (instance). Here, ‘stability of the output’ means that: cards with the same value appear in the output in the same order as they do in the input (instance).

##### Input

The first line contains an integer N, the number of cards.

N cards are given in the following line. Each card is represented by two characters. Two consecutive cards are separated by a space character.

##### Output

In the first line, print the arranged cards provided by the Bubble Sort algorithm. Two consecutive cards should be separated by a space character.

In the second line, print the stability (“Stable” or “Not stable”) of this output.

In the third line, print the arranged cards provided by the Selection Sort algorithm. Two consecutive cards should be separated by a space character.

In the fourth line, print the stability (“Stable” or “Not stable”) of this output.

1 ≤ N ≤ 36

#### ALDS1_2_D Shell Sort

Time Limit : 6 sec , Memory Limit : 131072 KB

Shell Sort is a generalization of Insertion Sort to arrange a list of nn elements AA.

A function shellSort(A, n) performs a function insertionSort(A, n, g), which considers every g-th elements. Beginning with large values of gg, it repeats the insertion sort with smaller g.

Your task is to complete the above program by filling ?. Write a program which reads an integer n and a sequence A, and prints m, $G_i(i=0,1,…,m−1)$ in the pseudo code and the sequence A in ascending order. The output of your program must meet the following requirements:

• 1 ≤ m ≤ 100
• 0 ≤ $G_i$ ≤ n
• cnt does not exceed ⌈$n^{1.5}$⌉
##### Input

In the first line, an integer nn is given. In the following nn lines, $A_i(i=0,1,…,n−1)$ are given for each line.

##### Output

In the first line, print an integer mm. In the second line, print m integers $G_i(i=0,1,…,m−1)$ separated by single space character in a line.
##### Notes

You can solve this problem by a Burte Force approach. Suppose solve(p, t) is a function which checkes whether you can make t by selecting elements after p-th element (inclusive). Then you can recursively call the following functions:

solve(0, M)
solve(1, M-{sum created from elements before 1st element})
solve(2, M-{sum created from elements before 2nd element})

The recursive function has two choices: you selected p-th element and not. So, you can check solve(p+1, t-A[p]) and solve(p+1, t) in solve(p, t) to check the all combinations.

For example, the following figure shows that 8 can be made by A[0] + A[2].