SAC '22 Code Challenge 3 P3 - Bob Sort

View as PDF

Submit solution


Points: 5 (partial)
Time limit: 1.0s
Java 1.5s
Python 2.0s
Memory limit: 256M

Author:
Problem type

To celebrate the upcoming CCC (Canadian Computing Contest), Max decided to define a new sorting algorithm called Bob Sort.

Bob Sort involves \lfloor \log_{10}(\max(A_i)) + 1 \rfloor rounds of sorting.

For the r^\text{th} round, Bob Sort looks at the r rightmost digits, d_i:

If there are fewer than r digits in element i, the left-aligned missing digits are set to 0.

Then, Bob Sort sorts the elements by their corresponding value (d_i) in non-decreasing order.

Can you Bob Sort the array into increasing order?

Constraints

1 \le N \le 100\,000

1 \le A_i \le 10^9

All A_i are distinct.

Input Specification

The first line will contain N, the number of elements in the array.

The next line will contain N space-separated integers, the elements of the array.

Output Specification

Output \lfloor \log_{10}(\max(A_i)) + 1 \rfloor lines, the array after each round of sorting.

Note: Within a round, ties do not need to be broken between elements with the same value, d_i.

Sample Input 1

6
2 105 12 1 15 65

Sample Output 1

1 2 12 105 15 65
1 2 105 12 15 65
1 2 12 15 65 105

Sample Input 2

1
100

Sample Output 2

100
100
100

Comments

There are no comments at the moment.