Somme divisible [algorithme]

c.candide · July 2013

Bonjour

L'exercice provient d'un concours de programmation [détail en fin de message] et je vous le soumets car il est intéressant et pour faire une perf valable, il faut se livrer à une petite étude mathématique (niveau lycée).

On donne une suite de $N$ entiers positifs ($N\leq 10000$). On demande d'afficher, si c'est possible, une sous-suite dont la somme des termes soit multiple de $N$. S'il existe plusieurs sous-suites, on affiche celle de son choix. La question que je pose est juste : trouver un algorithme efficace. L'algorithme naïf sera incapable de traiter le problème en un temps raisonnable et l'algorithme classique pour ce type de question ne sera pas suffisamment rapide.

On trouvera l'exercice ICI : 1032. Find a Multiple. Pour ceux qui veulent aller plus loin, ils peuvent soumettre sur le serveur du site une solution codée en Python, Java, C/C++ ou Pascal (entre autres mais pas Ocaml). Les contraintes sont les mêmes pour tous les langages : temps exécution < 1s, utilisation mémoire < 64 Mo.

Guego · July 2013

Ce n'est pas trop difficile : si on note les nombres $x_1,\ldots,x_N$, il suffit de calculer les sommes partielles $S_1 = x_1$, $S_2 = x_1+x_2$, $S_3=x_1+x_2+x_3$, etc. jusqu'à ce qu'on en trouve deux qui soient égales modulo $N$, disons $S_i$ et $S_j$ avec $i<j$.
On a a alors $S_j - S_i = x_{i+1}+\ldots+x_j$ qui est bien divisible par $N$.

Tout ça doit se faire avec une complexité $\mathcal{O}(N)$ en temps et en espace, ce qui remplit les conditions pour $N=10000$.

c.candide · July 2013

Guego écrivait:

> $S_3=x_1+x_2+x_3$, etc. jusqu'à ce qu'on
> en trouve deux qui soient égales modulo $N$,

Bien vu. Juste un point : il se peut que deux sommes ne soient jamais égales mézalor l'une d'entre elles est multiple de $N$.

Somme divisible [algorithme]

Réponses

Bonjour!

Catégories

In this Discussion