Yet Another Contest 5 P3 - Potted Plants

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem type

Nils, Canada's most popular interior designer, has been tasked with selecting aesthetically pleasing potted plants!

There are K species of plants, labelled between 1 and K, where plants of the same species look identical. Nils has been asked to form a straight line of N pots, where each pot contains one of the K types of plants, subject to the following constraints:

  • The display of plants is symmetrical, that is, the sequence of plants is palindromic.
  • For visual appeal, no two different contiguous sections of pots should contain identical sequences of plants, with both sequences containing more than one plant. Formally, every contiguous subsequence of the plants with a length greater than 1 should be unique.

Nils will be paid more for selecting a greater number of plants, so he wishes to maximise the value of N.

Can you help him find an optimal selection of plants?


1 \le K \le 2000

Subtask 1 [40%]

K is prime.

Subtask 2 [60%]

No additional constraints.

Input Specification

The only line contains a single integer, K.

Output Specification

Output N space-separated integers, corresponding to the sequence of selected plants. Any valid sequence which maximises N will be accepted.

Sample Input


Sample Output

1 2 2 1


This sequence has N = 4, is palindromic, and satisfies the condition that every contiguous subsequence with a length greater than 1 is unique. It can be shown that this is the largest possible value of N.


There are no comments at the moment.