Photo daltonique – Épreuve régionale 2019

Énoncé¶

En ce moment, ne me demandez pas pourquoi, mais les animaux ont deux passions : la photographie, et trier par ordre décroissant.

Ils adorent prendre des photos tous ensemble, et compter le nombre de configuration dite « daltonique » (attention, rien à voir avec un trouble de perception des couleurs !). On définit une configuration comme étant daltonique si ses éléments sont dans l'ordre décroissant. Ici on compare avec la taille des animaux.

Vu que les animaux aiment bien compter (finalement cela fait 3 passions, j'ai menti), ils se mettent à déterminer le nombre de configuration daltonique de $K$ éléments dans la photo.

Notez qu'une configuration peut être constituée d'éléments non consécutifs !

Entrée¶

L’entrée contiendra :

• Sur la première ligne, un entier : N, nombre d'animaux présents lors de la photo.
• Sur la ligne suivante, un entier : K, la taille des configurations que l'on souhaite compter.
• Sur la ligne suivante, une liste de N entiers séparés par des espaces : liste taille, liste des tailles respectives des $N$ animaux.

Sortie¶

Un seul entier, le nombre de configuration daltoniques de taille $K$ de la photo. On garantit que ce nombre peut être contenu dans un entier 32 bits signé.

Contraintes¶

• $1 \le N \le 20$
• $1 \le K \le 5$
• $1 \le taille \le 1000$

Contraintes de performance¶

• $1 \le N \le 500$
• $1 \le K \le 100$
• $1 \le taille \le 10^5$