An Animal Contest 5 P4 - Number Game

View as PDF

Submit solution


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

Author:
Problem type

For Christmas, Larry the magical panda received a board game! This board game consists of a game board with N spaces numbered from 1 to N, a piece of bamboo, and a set of N-1 numbers \{1, 2, \dots, N-2, N-1\}. Larry opened up and started reading the instructions sheet:

To play the game, start by placing the bamboo in square X. Then, perform a series of moves, where a move consists of the following:

If the bamboo is at square p, select some number s from the set of numbers such that p+s \le N or p-s \ge 1. Discard s from the set of numbers. Then, move the bamboo s spaces forwards (allowed if p+s \le N) or s spaces backwards (allowed if p-s \ge 1).

If a valid move exists, Larry must make a move. If it is impossible to perform a move, the bamboo is stuck, and the game is over.

Larry made the mistake of boasting to his friends that he could get the bamboo stuck using the minimum number of moves possible, when in reality he possessed no such skill. However, being a magical panda, Larry went home and calculated the minimal number of moves to get the object stuck as well as a valid sequence of moves that accomplishes this task. However, not wanting to be made fun of by his friends, he wants you to check over his work. Please help Larry by calculating the minimum number of moves to get the bamboo stuck as well as a valid sequence of moves that accomplishes this, and he will check his answer against yours!

Constraints

1 \le N \le 10^6

1 \le X \le N

Input Specification

The first and only line consists of two space-separated integers N and X.

Output Specification

First, output the minimal number of moves M (0 \le M \le N-1) required to get the object stuck.

Then, output M lines, with the i^\text{th} of these lines containing an integer s_i (1 \le s_i \le N-1), the number chosen from the set of numbers on the i^\text{th} move. This number should be negative if the object was moved backwards, and positive if moved forwards. All |s_i| over 1 \le i \le M should be distinct, and the object should not exit the game board at any time while performing these moves. In addition, the object must be stuck at the end of these M moves.

If M is minimized and the sequence of M moves is valid, you will receive 100 points for that test case and a verdict of Accepted. If only M is correct, you will receive 25 points for that test case and a verdict of Partially Accepted. If M is incorrect, you will receive 0 points for that test case and a verdict of Wrong Answer. After a Wrong Answer verdict, no more test cases will run and judging will terminate.

Your overall score is the minimum number of points achieved over all test cases.

Sample Input 1

5 4

Sample Output 1

2
-2
1

Explanation for Sample Output 1

Initially, the object starts at space 4 and the set of numbers available is \{1, 2, 3, 4\}.

After the first move, the object moves to space 2 and the set of numbers available after this move is \{1, 3, 4\}.

After the second move, the object moves to space 3 and the set of numbers available after this move is \{3, 4\}.

It can now be shown that no more moves can be made and the object is stuck after 2 moves. Moreover, it can be shown that this is the minimum number of moves required.

Sample Input 2

8 8

Sample Output 2

4
-4
-2
-1
3

Sample Input 3

1 1

Sample Output 3

0

Comments

There are no comments at the moment.