Sous-somme multiple de N – Qualification 2004

Niveau 2

Énoncé

Soient un tableau d'entiers positifs et un entier positif $N$. Écrire une fonction prenant en arguments ce tableau et cet entier, et renvoyant la taille du plus grand sous-tableau dont la somme des éléments est un multiple de $N$.

Entrée

Vous devez lire trois lignes sur l'entrée standard.

  • La première ligne de l'entrée contient un entier, $L$, le nombre d'éléments du tableau.
  • La deuxième ligne de l'entrée contient $L$ entiers, séparés par des espaces : le contenu du tableau.
  • La troisième ligne de l'entrée contient un entier, $N$.

Sortie

Vous devez écrire un entier sur la sortie : la taille du plus grand sous-tableau dont la somme soit multiple de $N$.

Contraintes

  • $1 \le L \le 10\,000$
  • $1 \le N \le 1\,000$

Contraintes d'exécution

Utilisation mémoire maximum
1000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
10
1 1 2 0 1 2 0 1 2 1
3
Exemple de sortie
8