Problem A. Square sort

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:8 Mb
Output file:output.txt  

Statement

You are to write a program that receives a sequence of integer numbers and sorts it, i. e. writes out all elements in ascending order.

Input file format

Input file contains integer N — length of the sequnece, followed by N integer numbers — elements of the sequence.

Output file format

Output file must contain N integer numbers, which must be elements of the source sequence printed in ascending order.

Constraints

0 ≤ N ≤ 3000. Sequence elements are less than 109 by absolute value.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 4 3 10 3 1
1 3 3 4 10

Problem B. Lin-log sort

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:8 Mb
Output file:output.txt  

Statement

You are to write a program that receives a sequence of integer numbers and sorts it, i. e. writes out all elements in ascending order.

Input file format

Input file contains integer N — length of the sequnece, followed by N integer numbers — elements of the sequence.

Output file format

Output file must contain N integer numbers, which must be elements of the source sequence printed in ascending order.

Constraints

0 ≤ N ≤ 100000. Sequence elements are less than 109 by absolute value.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 4 3 10 3 1
1 3 3 4 10

Problem C. Bucket sort

Author:StdAlg   Time limit:3 sec
Input file:input.txt   Memory limit:16 Mb
Output file:output.txt  

Statement

You are to write a program that receives a sequence of words and sorts it in lexicographical order. Linear order on characters is given by ASCII codes.

Input file format

First line of input file contains integer N — the sequence length. Following N lines contain one word per line. Each word is exactly three letters long.

Output file format

Output file must consist of N lines, each containing one word from sorted sequence.

Constraints

0 ≤ N ≤ 1000000.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
4
KVN
ACM
FSB
GGG
ACM
FSB
GGG
KVN

Problem D. Heapsort

Author:Andrew Stankevich (original idea, text, solution)   Time limit:2 sec
Input file:heapsort.in   Memory limit:64 Mb
Output file:heapsort.out  

Statement

A well known algorithm called heapsort is a deterministic sorting algorithm taking O(n log n) time and O(1) additional memory. Let us describe ascending sorting of an array of different integer numbers.

The algorithm consists of two phases. In the first phase, called heapification, the array of integers to be sorted is converted to a heap. An array a[1…n] of integers is called a heap if for all 1 ≤ i ≤ n the following heap conditions are satisfied:

- if 2in then a[i] > a[2i];

- if 2i + 1 ≤ n then a[i] > a[2i + 1].

We can interpret an array as a binary tree, considering children of element a[i] to be a[2i] and a[2i + 1]. In this case the parent of a[i] is a[i div 2], where i div 2 = floor(i / 2). In terms of trees the property of being a heap means that for each node its value is greater than the values of its children.

In the second phase the heap is turned into a sorted array. Because of the heap condition the greatest element in the heapified array is a[1]. Let us exchange it with a[n], now the greatest element of the array is at its correct position in the sorted array. This is called extract-max.

Now let us consider the part of the array a[1 ... n-1]. It may be not a heap because the heap condition may fail for i=1. If it is so (that is, either a[2] or a[3], or both are greater than a[1]) let us exchange the greatest child of a[1] with it, restoring the heap condition for i=1. Now it is possible that the heap condition fails for the position that now contains the former value of a[1]. Apply the same procedure to it, exchanging it with its greatest child. Proceeding so we convert the whole array a[1 ... n-1] to a heap. This procedure is called sifting down. After converting the part a[1 ... n-1] to a heap by sifting, we apply extract-max again, putting second greatest element of the array to a[n-1], and so on.

For example, let us see how the heap a=(5, 4, 2, 1, 3) is converted to a sorted array. Let us make the first extract-max. After that the array turns to (3, 4, 2, 1, 5). Heap condition fails for a[1] = 3 because its child a[2] = 4 is greater than it. Let us sift it down, exchanging a[1] and a[2]. Now the array is (4, 3, 2, 1, 5). The heap condition is satisfied for all elements, so sifting is over. Let us make extract-max again. Now the array turns to (1, 3, 2, 4, 5). Again the heap condition fails for a[1]; exchanging it with its greatest child we get the array (3, 1, 2, 4, 5) which is the correct heap. So we make extract-max and get (2, 1, 3, 4, 5). This time the heap condition is satisfied for all elements, so we make extract-max, getting (1, 2, 3, 4, 5). The leading part of the array is a heap, and the last extract-max finally gives (1, 2, 3, 4, 5).

It is known that heapification can be done in O(n) time. Therefore, the most time consuming operation in heapsort algorithm is sifting, which takes O(n * log (n)) time.

In this problem you have to find a heapified array containing different numbers from 1 to n, such that when converting it to a sorted array, the total number of exchanges in all sifting operations is maximal possible. In the example above the number of exchanges is 1+1+0+0+0 = 2, which is not the maximum. (5, 4, 3, 2, 1) gives the maximal number of 4 exchanges for n=5.

Input file format

Input file contains n.

Output file format

Output the array containing n different integer numbers from 1 to n, such that it is a heap, and when converting it to a sorted array, the total number of exchanges in sifting operations is maximal possible. Separate numbers by spaces.

Constraints

1 ≤ n ≤ 50000

Sample tests

No. Input file (heapsort.in) Output file (heapsort.out)
1
6
6 5 3 2 4 1

0.089s 0.004s 17