Sous-somme multiple de N – Qualification 2004

Level 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$

Runtime constraints

Maximum memory usage
1000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
10
1 1 2 0 1 2 0 1 2 1
3
Sample output
8

Submit your solution

You have to register or log in to be able to submit your solution.