Digit tiles on the scoreboard
Statement
The scoreboard of a stadium shows a number by slotting one digit tile into each place. Right now the scoreboard shows the natural number N.
The staff member in charge of the scoreboard can pull out every tile that is slotted in and put the tiles back in other places. No tile can be fetched or thrown away, and every tile that is slotted in right now is used again, with none left out.
Write a program that finds the largest number that can be made by moving the tiles to other places.
For example, suppose the scoreboard shows 2143. The slotted tiles are the four tiles 2, 1, 4 and 3. The further forward a large digit sits, the larger the number gets, so slotting the tiles in the order 4, 3, 2, 1 is best.
| Place | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| Tile slotted in now | 2 | 1 | 4 | 3 |
| Tile slotted back in | 4 | 3 | 2 | 1 |
Now look at a case with several tiles of the same digit. If the scoreboard shows 9792382, the tiles are the seven tiles 9, 7, 9, 2, 3, 8 and 2. Counting how many tiles carry each digit gives the following.
| Digit | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|---|---|
| Number of tiles | 2 | 1 | 1 | 0 | 0 | 0 | 1 | 2 | 0 | 0 |
Laying the digits out from the largest one, as many times as its count, gives 9, 9, 8, 7, 3, 2, 2, and slotting those in from the first place gives 9987322. When two tiles carry the same digit, both of them have to be used.
Now look at a case with ten tiles. If the scoreboard shows 1234567890, one tile for each digit from 0 to 9 is slotted in. Slotting the larger digits into the forward places gives the following.
| Place | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| Tile slotted in now | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 |
| Tile slotted back in | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
No tile can be thrown away, so the answer always has as many digits as N. A tile carrying 0 is not taken out either, and it goes into the last place. And because N is a natural number, at least one tile carries a digit other than 0, and that tile comes to the first place. The answer therefore never starts with 0.
Given the number shown on the scoreboard, write a program that finds the largest number that can be made by moving the tiles to other places.
Input and output examples
Example 1
Input
2143
Output
4321
Example 2
Input
9792382
Output
9987322
Example 3
Input
1234567890
Output
9876543210
Input
The first line gives the number N shown on the scoreboard. N is a natural number with at most 10 digits, so it is less than or equal to 9,999,999,999.
The input ends with this one line. The number of tiles slotted into the scoreboard is not given separately and equals the number of digits of N.
N does not start with 0. The digit written on a tile is from 0 to 9, and several tiles can carry the same digit.
Output
Print the largest number that can be made by moving the tiles to other places on the first line.
Print one number and then a newline. Do not add any other character or space before or after it. Printing a space between the digits is marked wrong.
Requirements
- Read the input from standard input and write the answer to standard output
- Use every tile that is slotted in right now, with none left out. When several tiles carry the same digit, use all of them
- No tile can be fetched or thrown away, so the answer has as many digits as N
- N goes up to 10 digits. It does not fit in a 32-bit integer, so handling it as characters rather than converting it to a number is easier
- The output is one number and a newline, nothing else
- Grading compares the output with the expected value down to the last character
- You must write a program that reads from standard input and writes to standard output
- Trailing spaces at the end of a line and blank lines at the end of the output are ignored when grading
- The languages you can use are Python and JavaScript
- The memory limit is 256MB. The browser does not measure it, it only states it
- The time limit is set by measuring the setter's reference solution on the same runtime
- On this problem you submit code, not a prompt. That code runs in the browser on this device, and all that goes to the server is a fingerprint of the output and the time it took. Whether it is correct is decided by the server. The run time is a number each device reports, so the code and the device details are posted next to it on the leaderboard.
- There are 16 cases, and 3 of them show the input together with the expected output. The rest are used only when you submit and are not shown on this page.
- You have to pass all 16 cases to solve this.
Examples
3 public cases. Judging also uses hidden cases. You have to pass all 16 cases to solve this.
2143
4321
9792382
9987322
1234567890
9876543210
Solution
Your code runs on this device. Only the fingerprint of the output and the elapsed time go to the server. The server decides whether it is correct.
Submitting requires you to log in. Running against the public cases works without one.
You can test with 3 public cases. Submitting runs the hidden cases too.
People who solved this problem
Nobody yet. You could be the first.