Loading...
Loading...
Loading...
For the annual day photo, n students stand in one row. The photographer wants the heights to zig-zag: the first student is shorter than the second, the second is taller than the third, the third is shorter than the fourth, and so on. Equal heights side by side are not allowed.
Many rows may work, so use this exact rule. Sort the heights from shortest to tallest. The shorter half is the first (n + 1) / 2 heights (rounded down), and the taller half is the rest. Fill the places 1, 3, 5, … with the shorter half from tallest to shortest. Fill the places 2, 4, 6, … with the taller half, also from tallest to shortest.
If the row made this way zig-zags, print it. Otherwise print -1. (When this rule fails, no zig-zag row exists at all.)
-1.Example 1
Input
6 150 160 155 170 165 158
Output
158 170 155 165 150 160
Sorted: 150 155 158 | 160 165 170. Places 1, 3, 5 get 158 155 150 and places 2, 4, 6 get 170 165 160, giving 158 170 155 165 150 160.
Example 2
Input
4 160 155 160 160
Output
-1
Three of the four students have height 160. Two of them must stand side by side, so the answer is -1.
Try the problem first. Open one hint at a time.
In a zig-zag row, every place 2, 4, 6, … holds a student taller than both neighbours. That is why the taller half goes there.
The danger is the middle value: it can appear at the end of the shorter half and the start of the taller half. Filling both halves from tallest to shortest keeps those copies far apart.
Build the row with the rule, then check it once from left to right. If any pair breaks the zig-zag, print -1.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor