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.

Limites de temps et de mémoire (Python)

  • Temps : 0,5 s sur une machine à 1 GHz.
  • Mémoire : 8 000 ko.

Contraintes

1<= nbPetitsPois <= 500 000 000

Entrée

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

Sortie

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

Exemple

entrée : 

17

sortie : 

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