Leonardo y sus juguetes


Submit solution

Points: 100 (partial)
Time limit: 4.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Python, Swift, VB

Leonardo colecciona juguetes. Su colección puede contener muchos juguetes de muchos tipos diferentes: autos, camiones, excavadoras y mucho mas. Puede poseer más de una pieza del mismo juguete, por ejemplo cuatro camiones, en cuyo caso todas las piezas son indistinguible para él.

Lidia le preguntó a Leonardo cuántos tipos de juguetes el tiene. No queriendo revelar el secreto, él respondió con un acertijo (es típico de él): si escogiera un conjunto de mis juguetes para cada día, yo podría jugar por n días. En otras palabras, por cada dos días hay un tipo de juguete con una cantidad diferente. Aquí, Leonardo considera un conjunto vacío de juguetes como un conjunto válido.

A Lidia no le gusta ni la respuesta ni este enigma, pero tiene mucha curiosidad por saber cuántos juguetes Leonardo tiene. Ella te pidió ayuda.

Tarea

Determinar todas las posibilidades de los numeros de juguetes que Leonardo puede tener en su coleccion.

Entrada

La primera (y la única) línea de la entrada estándar contiene un entero n (1 \le n \le 10^9).

Salida

La primera línea de la salida estándar debe contener un entero r, el número de soluciones (es decir, el número de posibilidades del número de juguetes en la colección de Leonardo).

La segunda línea debe contener una secuencia estrictamente creciente de r enteros que representa los números de Juguetes que Leonardo puede tener en su colección.

Ejemplo #1 de Entrada

12

Ejemplo #1 de Salida

4
4 5 6 11

Explicación del ejemplo: Leonardo podría tener:

• dos camiones, un auto y una excavadora (4 juguetes en total),

• tres camiones y dos autos (5 juguetes en total),

• cinco camiones y un auto (6 juguetes en total),

• Once camiones (11 juguetes en total).

Cada una de estas opciones garantiza exactamente 12 días de diversión. Por ejemplo, si tiene once camiones, puede elegir un conjunto de i - 1 camiones el i-th día (para i = 1, ..., 12).

Ejemplo #2 de Entrada

36

Ejemplo #2 de Salida

8
6 7 8 10 11 13 18 35

Explicación del ejemplo: tenga en cuenta que hay dos juegos diferentes de 10 juguetes que garantizan 36 días de diverción:

• un camión, un auto y ocho excavadoras,

• Cinco camiones y cinco excavadoras.

Aún así, solo uno de ellos es de salida.

Para obtener 6 juguetes en total, Leonardo podría tener un camión, un auto, dos excavadoras y dos autobuses.

Calificación

El conjunto de prueba se divide en las siguientes subtareas con restricciones dicionales. Cada una de las subtareas consisten en uno o más grupos de prueba separados. Cada grupo de prueba puede contener uno o más casos de prueba.

Subtarea Restricciones y Puntos

1   n ≤ 50   19 Puntos

2   n ≤ 10 000   20 Puntos

3   n ≤ 100 000   20 Puntos

4   n ≤ 100 000 000   20 Puntos

5   sin restricciones adicionales   21 Puntos


Comments

There are no comments at the moment.