Mock CCC '24 Contest 1 S2 - Owen the Toucan

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

Once upon a time, in a quaint village surrounded by lush forests, there lived a toucan named Owen, who was also a mathematician. Owen, being quite the playful bird, wrote down an array a on a piece of paper, consisting of a permutation of positive integers from 1 to N. Then, he wrote down an array b of length N on the paper. The array b is constructed by taking the Greatest Common Divisor (GCD) of each element a_i and the corresponding element a_{a_i}. Namely, b_i = \gcd(a_i, a_{a_i}). However, he purposely accidentally lost the paper and cannot remember what the arrays a and b were. Fortunately, he still remembers that there are exactly K unique integers in array b. Can you please help him find a possible array a?

Note: A permutation of length n is an array consisting of n distinct integers from 1 to n in any order.

Input Specification

The first line of input contains two integers N and K.

The following table shows how the available 15 marks are distributed.

Marks AwardedNK
3 marks1 \leq N \leq 10^6K \in \{1, N\}
12 marks1 \leq N \leq 10^61 \leq K \leq N

Output Specification

Output a possible array a, a permutation of positive integers from 1 to N.

It can be proven that there is always a valid array a.

Sample Input

5 3

Sample Output

5 4 3 2 1

Explanation for Sample

The array b for sample output is [\gcd(a_1, a_5), \gcd(a_2, a_4), \gcd(a_3, a_3), \gcd(a_4, a_2), \gcd(a_5, a_1)] which is [1, 2, 3, 2, 1]. In array b, there are exactly 3 unique integers: 1, 2, and 3.


There are no comments at the moment.