COCI '08 Contest 6 #4 Cuskija

View as PDF
Submit solution
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 (1 \le N \le 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.

Output Specification

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

Sample Input 1

3
1 2 3

Sample Output 1

2 3 1

Sample Input 2

5
4 6 3 9 8

Sample Output 2

3 4 6 8 9

Sample Input 3

6
3 7 6 4 2 8

Sample Output 3

3 7 4 6 2 8

Sample Input 4

3
3 12 9

Sample Output 4

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