Leonardo y sus juguetes
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 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 .
Salida
La primera línea de la salida estándar debe contener un entero , 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 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 ( juguetes en total),
• tres camiones y dos autos ( juguetes en total),
• cinco camiones y un auto ( juguetes en total),
• Once camiones ( juguetes en total).
Cada una de estas opciones garantiza exactamente días de diversión. Por ejemplo, si tiene once camiones, puede elegir un conjunto de camiones el día (para ).
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 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 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
n ≤ 50 19 Puntos
n ≤ 10 000 20 Puntos
n ≤ 100 000 20 Puntos
n ≤ 100 000 000 20 Puntos
sin restricciones adicionales 21 Puntos
Comments