3738 - Cut the Chain

Created by Humberto Díaz Suárez
Added by humbertodiaz (2016-09-11)
Limits
Total Time: 3000 MS | Test Time: 1000 MS |Memory: 256 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

Jai was studying hard for an upcoming interview with El Goog, a popular technology company. She would spend hours solving problems, even staying up late. What if they asked her something that she didn't know;jsessionid=C281EA4BDB05E352BB4CBBA83DA92427? It was that fear that kept her going. Finally the interview came around and she was faced with the following question:

"You have a golden chain composed of 5 links. You will pay for your stay at a hotel using some links. Unfortunately, you have no idea how much it will cost. You must prepare by cutting some links so that you can provide any amount of links between 1 and 5. How would you cut as few links as possible?"


Jai's eyes lit up. It was clear that she only had to cut the 3rd link.


That would allow her to form any amount needed.


"Good work," the interviewer said. "But what if there were N links? Please describe an efficient algorithm for finding how to cut the chain so that you can get any amount of links between 1 and N. Using the minimum number of cuts, of course."

Now it's your turn to face this El Goog puzzle. Given the value of N, determine which links must be cut to minimize the number of cuts.
Jai estaba estudiando mucho para una entrevista próxima con El Goog, una compañía de tecnología popular. Se pasaba horas resolviendo problemas, incluso hasta tarde. ¿Que si le preguntaban algo que ella no conocía;jsessionid=C281EA4BDB05E352BB4CBBA83DA92427? Era ese miedo que la mantenía en marcha. Finalmente llegó la entrevista y se enfrentó a la siguiente pregunta:

"Tienes una cadena de oro compuesta de 5 eslabones. Vas a pagar por tu estancia en un hotel usando algunos eslabones. Por desgracia, no tienes idea de cuánto va a costar. Debes prepararte mediante cortar algunos eslabones para que puedas ofrecer cualquier cantidad de eslabones entre 1 y 5. ¿Cómo cortarías el menor número de eslabones posible?"


Los ojos de Jai se iluminaron. Era claro que ella sólo tendría que cortar el 3er eslabón.


Eso le permitiría formar cualquier cantidad necesaria.


"Buen trabajo", dijo el entrevistador. "¿Pero que si hubiese N eslabones? Por favor, describe un algoritmo eficiente para encontrar como cortar la cadena de manera que se pueda obtener cualquier cantidad de eslabones entre 1 y N. Usando el número mínimo de cortes, por supuesto."

Ahora es tu turno para hacer frente a este rompecabezas de El Goog. Dado el valor de N, determina qué enlaces deben ser cortados para minimizar el número de cortes.
Jai was studying hard for an upcoming interview with El Goog, a popular technology company. She would spend hours solving problems, even staying up late. What if they asked her something that she didn't know;jsessionid=C281EA4BDB05E352BB4CBBA83DA92427? It was that fear that kept her going. Finally the interview came around and she was faced with the following question:

"You have a golden chain composed of 5 links. You will pay for your stay at a hotel using some links. Unfortunately, you have no idea how much it will cost. You must prepare by cutting some links so that you can provide any amount of links between 1 and 5. How would you cut as few links as possible?"


Jai's eyes lit up. It was clear that she only had to cut the 3rd link.


That would allow her to form any amount needed.


"Good work," the interviewer said. "But what if there were N links? Please describe an efficient algorithm for finding how to cut the chain so that you can get any amount of links between 1 and N. Using the minimum number of cuts, of course."

Now it's your turn to face this El Goog puzzle. Given the value of N, determine which links must be cut to minimize the number of cuts.

Input specification

The input will begin with a line containing an integer T (1   1000) denoting the number of test cases. Each test case will consist of a line containing an integer N (1   1018), the number of links in the chain.
La entrada comenzará con una línea que contiene un entero T (1 ≤ T ≤ 1000) que indica el número de casos de prueba. Cada caso consistirá de una línea que contiene un entero N (1   1018), que indica el número de eslabones en la cadena.
The input will begin with a line containing an integer T (1   1000) denoting the number of test cases. Each test case will consist of a line containing an integer N (1   1018), the number of links in the chain.

Output specification

The output will consist of one line for each test case. The output will begin with an integer M, the minimum number of cuts required so that any amount of links between 1 and N (inclusive) can be formed. Then M integers will follow, each denoting a link to cut (with links numbered 1 to N). There must be one space between each pair of consecutive values. If multiple solutions are possible, you may output any of them.

The order of the results must follow the same order in which the test cases are provided.
La salida consistirá en una línea para cada caso de prueba. La salida comenzará con un entero M, la cantidad mínima de cortes requeridos para que se pueda formar cualquier cantidad de eslabones entre 1 y N (ambos inclusive). Seguirán M enteros que denotan cada eslabón para cortar (numerando los eslabones desde 1 hasta N). Habrá un espacio entre cada par de números enteros consecutivos. Si existen múltiples soluciones, se puede imprimir cualquiera de ellas.

Los resultados se deben imprimir en el mismo orden en que fueron proporcionados sus datos de entrada.
The input will begin with a line containing an integer T (1   1000) denoting the number of test cases. Each test case will consist of a line containing an integer N (1   1018), the number of links in the chain.

Sample input

2
5
8

Sample output

1 3
2 3 6

Hint(s)

The first case is discussed in the problem statement along with one possible solution. In the second case, 2 links must be cut to form any number of links between 1 and 8. One possible solution is to cut the 3rd and 6th links. That would leave 3 segments of 2 links and 2 cut links, which could be combined to produce any amount desired.
El primer caso se discute en el enunciado con una posible solución. En el segundo caso, se deben cortar 2 eslabones para formar cualquier número de eslabones entre 1 y 8. Una posible solución es cortar el 3er y 6to eslabón. Eso dejaría 3 segmentos de 2 eslabones y 2 eslabones cortados, que se podrían combinar para producir cualquier cantidad deseada.
The first case is discussed in the problem statement along with one possible solution. In the second case, 2 links must be cut to form any number of links between 1 and 8. One possible solution is to cut the 3rd and 6th links. That would leave 3 segments of 2 links and 2 cut links, which could be combined to produce any amount desired.