Teleport Route
Time limit1sMemory limit128 MB
Given 2^n planets and one usable teleport for each distance from 1 to 2^n-1, find an ordering starting at k that visits the maximum number of distinct planets and print the signed teleport sequence.
- Level
Hard8 of 10
- Topics
- Math, Greedy, Bit manipulation, Simulation
- Solved
- No attempts yet
Problem
A planetary system has 2^n planets numbered from 0 to 2^n - 1. Think of the planets as lying on one line in increasing order of their numbers.
Stancho first reaches planet k by using a space stop. There is also one teleport for each number from 1 to 2^n - 1. A teleport numbered t can be used at most once, and from the current planet m it can move to planet m + t or planet m - t if that planet exists.
Find an order for using teleports so that Stancho visits as many distinct planets as possible. The starting planet k is not counted.
Input
The single line of standard input contains the positive integer n and the integer k, separated by a space.
Output
On the first line, print the maximum number p of planets Stancho can visit, excluding planet k.
On the second line, print the numbers of the p teleports to use, in order. A teleport that moves from a larger-numbered planet to a smaller-numbered planet must be printed as a negative number.
If several valid orders are possible, print any one of them.
Constraints
1 <= n <= 200 <= k <= 2^n - 1