An Animal Contest 1 P3 - Happy Alpacas - Olympiads Online Judge

An Animal Contest 1 P3 - Happy Alpacas

Points: 7 (partial)

Time limit: 2.0s

Memory limit: 256M

Author:

Problem types

Night has fallen, and $N$ $N$ alpacas have gathered around a campfire. They sit in a circle, that is, alpaca $1$ $1$ is to the right of alpaca $N$ $N$ , alpaca $2$ $2$ is to the right of alpaca $1$ $1$ , alpaca $3$ $3$ is to the right of alpaca $2$ $2$ , and so on. Each alpaca is waiting to be assigned a happiness index, $h_i$ $h_{i}$ . The $i^\text{th}$ $i^{th}$ alpaca is happy if the sum of its happiness index and the happiness index of the alpaca to its right is even. Otherwise, it is sad. Being a diligent herdsman, you decide to assign each of the $N$ $N$ alpacas a happiness index such that there are exactly $X$ $X$ happy alpacas.

Constraints

$2 \le N \le 10^6$ $2 \leq N \leq 10^{6}$

$0 \le X \le N$ $0 \leq X \leq N$

Subtask 1 [15%]

$2 \le N \le 15$ $2 \leq N \leq 15$

Subtask 2 [85%]

No additional constraints.

Input Specification

The first line contains two space-separated integers, $N$ $N$ and $X$ $X$ .

Output Specification

If no solution exists, output $-1$ $- 1$ . Otherwise, output $N$ $N$ space-separated integers, the happiness index $h_i$ $h_{i}$ for the $i^{th}$ $i^{t h}$ alpaca $(0 \le h_i \le 10^9)$ $(0 \leq h_{i} \leq 10^{9})$ . If there are multiple solutions, output any.

Note: Output must end with a newline with no trailing whitespace.

Sample Input 1

Copy

6 4

Sample Output 1

Copy

7 27 196 50 3 17

Explanation for Sample Output 1

The happy alpacas in this arrangement are alpaca $1$ $1$ , alpaca $3$ $3$ , alpaca $5$ $5$ , and alpaca $6$ $6$ . Note that this is not the only solution.

Sample Input 2

Copy

2 1

Sample Output 2

Copy

-1

Comments

0
pargatsingh commented 5 days ago
Hint

The happiness index doesn't have to be unique per alpaca so feel free to reuse values for simplicity

Try drawing out a few examples with odd/even N with odd/even X and see what pattern you notice.

3

PenguinPush commented on April 26, 2024, 5:18 p.m.

i love an animal contest