SAC '22 Code Challenge 3 P3 - Bob Sort - DMOJ: Modern Online Judge

SAC '22 Code Challenge 3 P3 - Bob Sort

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$ $⌊ \log_{10} (max (A_{i})) + 1 ⌋$ rounds of sorting.

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

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

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

Can you Bob Sort the array into increasing order?

$1 \le N \le 100\,000$ $1 \leq N \leq 100 000$

$1 \le A_i \le 10^9$ $1 \leq A_{i} \leq 10^{9}$

All $A_i$ $A_{i}$ are distinct.

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

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

Output $\lfloor \log_{10}(\max(A_i)) + 1 \rfloor$ $⌊ \log_{10} (max (A_{i})) + 1 ⌋$ 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$ $d_{i}$ .

Copy

6
2 105 12 1 15 65

Copy

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

Copy

1
100

Copy

100
100
100

-1

Casio991ms commented on Jan. 22, 2023, 5:51 p.m.

Stupid problem. Gives wrong answer for printing extra space after line.