Boîtes factorielles

Un marchand de légumes très maniaque souhaite ranger ses petits pois en les regroupant en boîtes de telle sorte que chaque boîte contienne un nombre factoriel de petits pois. On rappelle qu'un nombre est factoriel s'il est de la forme 1, 1 x 2, 1 x 2 x 3, 1 x 2 x 3 x 4... et qu'on les note sous la forme suivante : $$ n! = 1 \times 2 \times 3 \times \ldots \times (n-1) \times n $$

Il souhaite également utiliser le plus petit nombre de boîtes possible.

Ainsi, s'il a 17 petits pois, il utilisera :

  • 2 boîtes de 3! = 6 petits pois
  • 2 boîtes de 2! = 2 petits pois
  • 1 boîte de 1! = 1 petits pois
ce qui donne bien 2 x 3! + 2 x 2! + 1 x 1! = 12 + 4 + 1 = 17.

D'une manière générale, s'il a nbPetitsPois, il doit trouver une suite $a_1, a_2, \ldots, a_p$ d'entiers positifs ou nuls avec $a_p > 0$ et telle que : $$ nbPetitsPois = a_1 \times 1! + a_2 \times 2! + \ldots + a_p \times p! $$ avec $a_1 + \ldots + a_p$ minimal.

TIME AND MEMORY LIMITS (Python)

  • Time: 0.5s on a 1GHz machine.
  • Memory: 8,000 KB.

CONSTRAINTS

1<= nbPetitsPois <= 500 000 000

INPUT

Un unique entier, nbPetitsPois le nombre total de petits poids.

OUTPUT

  • Sur le première ligne, l'entier p
  • Sur la seconde ligne, les entiers $a_1, a_2, \ldots, a_p$

EXAMPLE

input: 

17

output: 

3
1 2 2
Source: https://www.france-ioi.org.