COCI '08 Contest 6 #4 Cuskija

Points: 10

Time limit: 0.6s

Memory limit: 32M

Problem type

Rearrange the given array of integers so that the sum of two adjacent elements is never divisible by three.

Input Specification

The first line contains an integer $N$ $N$ $(1 \le N \le 10\,000)$ $(1 \leq N \leq 10 000)$ , the number of elements in the array. The second line contains the elements of the array separated by single spaces. The elements will be non-negative integers less than $1\,000\,000$ $1 000 000$ .

Output Specification

If any valid rearrangement exists, output it on a single line. Otherwise, output impossible.

Sample Input 1

Copy

3
1 2 3

Sample Output 1

Copy

2 3 1

Sample Input 2

Copy

5
4 6 3 9 8

Sample Output 2

Copy

3 4 6 8 9

Sample Input 3

Copy

6
3 7 6 4 2 8

Sample Output 3

Copy

3 7 4 6 2 8

Sample Input 4

Copy

3
3 12 9

Sample Output 4

Copy

impossible

Comments

3

Daniel_Alp commented on Dec. 25, 2021, 2:37 a.m.

Fun problem, taught me to think before rushing to submit.

11

Tzak commented on Sept. 12, 2019, 8:49 p.m.

It should be noted that you will WA on this question if you don't place a newline character after your line of output.

2

sortSlave commented on May 13, 2022, 6:30 p.m.

thanks