ZOJ Problem Set - 2258
Let's play a simple game. Given three integers n, a and b, write down N numbers from 1 to n on the blackboard. You are only allowed to do one operation, that is, erase some consecutive number(s) from the blackboard, then write back the number of number(s) you have erased in that position. For example, when n = 5, first you have 1, 2, 3, 4 and 5 on the blackboard, if you erase 2, 3, 4, and write back 3(you erased 3 numbers), you will get 1, 3, 5. The problem is, through some operations described above, whether we can come to only two numbers, say, "a b" left on the blackboard? (Note that "a b" is different from "b a").
The input consists of several test cases, each testcase consists of three integers n, a and b in one line. The input is terminated by EOF. Note that all numbers in the input are positive integer smaller than 100,000.
If there exists a way, output the one which uses the least steps. If it still have ties, any one is acceptable. For each testcase, you should output one line. Output the number of steps first, then output each step. Output the step in the format of "S N", where S is the starting position of the series of number(s)(in range of [0, length - 1]), and N is the number of number(s) you would like to erase, separate those steps with a blank. If no such way exists, just output -1.
5 1 3
2 1 2 1 3
Author: DAI, Wenbin
Source: ZOJ Monthly, November 2004