Voir les cours et résoudre les problèmes en :
Le C est un langage de programmation impératif conçu pour la programmation système. Inventé au début des années 1970 avec UNIX, C est devenu un des langages les plus utilisés. De nombreux langages plus modernes se sont inspirés de sa syntaxe. Il privilégie la performance sur la simplicité de la syntaxe. [En savoir plus]
Le C++ est un langage de programmation impératif. Inventé au début des années 1980, il apporte de nouveaux concepts au langage C (les objets, la généricité), le modernise et lui ajoute de nombreuses bibliothèques. C++ est devenu l'un des langages les plus utilisés. Sa performance et sa richesse en font le langage de prédilection pour les concours. [En savoir plus]
Pascal est un langage de programmation impératif inventé dans les années 1970 dans un but d'enseignement. Quoiqu'encore utilisé à cette fin, l'absence de bibliothèque standard en limite son utilisation malgré une grande efficacité. Sa syntaxe a été reprise par d'autres langages plus modernes avec plus ou moins de succès. [En savoir plus]


Remarque : Les cours pour ce langage ne sont disponibles que jusqu'au chapitre 4, « Lecture de l'entrée ». Les corrections sont toutefois toujours fournies.
OCaml est un langage de programmation fonctionnel inventé au milieu des années 1990. Il permet aussi une programmation impérative ou objet. Il permet d'écrire des programmes courts et faciles à vérifier et est ainsi utilisé pour certains systèmes embarqués très sensibles comme ceux des avions. Il est utilisé dans l'enseignement en classes préparatoires aux grandes écoles. [En savoir plus]


Remarque : Les cours pour ce langage ne sont disponibles que jusqu'au chapitre 4, « Lecture de l'entrée ». Les corrections sont toutefois toujours fournies.
Java est un langage de programmation impératif et orienté objet. Inventé au début des années 1990, il reprend en grande partie la syntaxe du langage C++ tout en la simplifiant, au prix d'une performance un peu moins bonne. S'exécutant dans une machine virtuelle, il assure une grande portabilité et ses très nombreuses bibliothèques en font un langage très utilisé. On lui reproche toutefois la « verbosité » de son code. [En savoir plus]


Remarque : Pour un débutant souhaitant apprendre Java, nous conseillons fortement de commencer par JavaScool, plus facile à apprendre, bien que fortement similaire.
Java's Cool (alias JavaScool) est conçu spécifiquement pour l'apprentissage des bases de la programmation. Il reprend en grande partie la syntaxe de Java sur laquelle il s'appuie, mais la simplifie pour un apprentissage plus aisé. La plateforme JavaScool est accompagnée d'un ensemble d'activités diverses de découverte de la programmation. [En savoir plus]
Python est un langage de programmation impératif inventé à la fin des années 1980. Il permet une programmation orientée objet et admet une syntaxe concise et claire qui en font un langage très bien adapté aux débutants. Étant un langage interprété, il n'est cependant pas aussi performant que d'autres langages. [En savoir plus]

Lors d'un séjour à Las-Vegas, vous vous balladez dans les allées d'un casino, observant avec curiosité les très nombreux joueurs assis devant les machines à sous qui, tels des automates, exécutent une routine toujours identique : insérer une pièce, tirer le levier, regarder les roues tourner, attendre le résultat, insérer une pièce, tirer le levier, etc. Certains essaient d'augmenter leurs chances de gains, par exemple en soufflant sur leur pièce avant de l'insérer, sans compter les nombreux grigris, fers à cheval et autres porte-bonheur. Vous êtes convaincu qu'aucune de ces techniques n'a le moindre effet sur le résultat.

Après de nombreuses heures d'observation, vous commencez à comprendre la manière dont ces machines infernales fonctionnent, et réalisez qu'il est en fait possible de jouer d'une manière qui augmente vos chances de gain. En effet, sur le modèle de machines à sous de ce casino, les chances de gains au prochain coup varient suivant la configuration initiale de ses roues ! Si ceci ne permet en rien d'influencer le résultat pour une machine donnée, vous pouvez choisir à chaque tour, de jouer sur la machine qui a le plus de chances de remporter le jackpot !

Une machine à sous est composée de N roues. Sur chacune des roues sont représentés S symboles que l'on identifiera par des entiers. Lorsque l'on abaisse le levier, une quantité d'énergie E bien précise est répartie aléatoirement entre les différentes roues. Chaque unité d'énergie transmise à une roue la fait tourner d'un cran, toujours dans le même sens, faisant apparaître le symbole suivant dans la fenêtre affichant le résultat. La somme des énergies transmises aux N roues est toujours exactement égale à E.

Vous devez écrire un programme qui détermine, pour une configuration initiale donnée d'une machine à sous, quel est le meilleur score que vous pouvez espérer obtenir au prochain tour, c'est-à-dire le nombre maximal de symboles identiques qui peuvent être alignés sur la fenêtre centrale, une fois que l'ensemble de l'énergie disponible a été dépensée pour faire tourner les diverses roues.

Limites de temps et de mémoire (Python)

  • Temps : 2 s sur une machine à 1 GHz.
  • Mémoire : 64 000 ko.

Contraintes

  • 1 <= N <= 1000, où N est le nombre de roues de la machine à sous.
  • 1 <= S <= 1000, où S est le nombre de symboles (tous distincts) présents sur une roue.
  • 0 <= V <= 1 000 000, où V est l'identifiant numérique représentant un symbole présent sur une roue.
  • 0 <= E <= 100 000 000, où E est l'énergie répartie aléatoirement entre les roues lorsque l'on actionne la machine.
De plus, on a :
  • dans 40% des tests au total, N <= 75, S <= 75 et V <= 1 000.
  • dans 20% autres tests, on a toujours N <= 75 et S <= 75, mais V <= 100 000.

Entrée

La première ligne de l'entrée contient trois entiers séparés par un espace : N, S et E.

Chacune des N lignes suivantes contient S entiers séparés par des espaces, décrivant les identifiants des symboles présents sur une roue, dans l'ordre dans lesquels ils défilent, et en commençant par celui qui apparaît sur la zone du résultat dans la configuration initiale.

Sortie

Vous devez afficher un entier sur la sortie : le nombre maximum de symboles identiques pouvant être alignés sur la zone du résultat, une fois toute l'énergie dépensée pour faire tourner les roues.

Exemple

entrée :

4 7 11
0 1 2 3 4 5 6
2 4 6 8 10 12 14
1 13 4 7 10 19 16
5 2 8 11 7 4 1

sortie :

3

Commentaires

Cette machine à sous contient quatre roues de 7 symboles chacune. 11 points d'énergie sont répartis aléatoirement lorsqu'elle est activée.

L'état initial correspond à l'illustration fournie dans le problème. On le représente ci-dessous avec les roues horizontales, et la fenêtre à gauche, pour faire facilement le lien avec l'entrée. Une unité d'énergie fait toujours tourner une roue vers la gauche, la fenêtre du résultat étant toujours la colonne de gauche.

0123456
2468101214
11347101916
52811741

Si l'on a de la chance, l'énergie peut être répartie de telle sorte que trois symboles identiques soient alignés. En effet, si 2 unités d'énergie sont affectés à la première roue, 0 à la deuxième, 1 à la quatrième, et les 8 qui restent à la troisième, on obtient la configuration suivante, en ayant dépensé exactement les 11 unités d'énergie :

2345601
2468101214
13471019161
28117415

On se retrouve avec trois fois le symbole "2" dans la zone du résultat.

Une autre possibilité est que les symboles "1" soient alignés : en partant de la configuration initiale, si 1 unité d'énergie est affectée à la première roue, 4 à la deuxième, 0 à la troisième et 6 à la quatrième, on obtient la situation suivante :

1234560
1012142468
11347101916
15281174

Il n'est par contre pas possible d'aligner 4 symboles identiques. Le seul symbole qui soit sur les 4 roues est le symbole 4, et il faudrait 12 points d'énergie au minimum pour atteindre la configuration correspondante. Notez qu'on peut d'ailleurs également l'obtenir avec 19 points, 26, etc : il est possible de faire faire plusieurs tours à une même roue.

Squelette de code C++ :

#include <cstdio>
#include <cstdlib>
using namespace std;

int main()
{
   int nbRoues, nbSymboles, energie;
   scanf("%d%d%d", &nbRoues, &nbSymboles, &energie);
   for (int roue = 0; roue < nbRoues; roue++)
   {
      for (int cran = 0; cran < nbSymboles; cran++)
      {
         int symbole;
         scanf("%d", &symbole);
         // ...
      }
   }
   int maxAlignes;  // ...
   printf("%d\n", maxAlignes);
}
Squelette de code Caml :
let scan_int () = Scanf.scanf " %d" (fun x -> x)

let nbRoues = scan_int()
let nbSymboles = scan_int()
let energie = scan_int()

let etat = 
   Array.init nbRoues (fun _ ->
      Array.init nbSymboles (fun _ ->
         scan_int()))

(* "etat" est une matrice représentant l'état initial.
   "etat.(id_roue).(cran)" contient ainsi la valeur du symbol
   qui se trouve sur la machine sur la roue "id_roue" au cran
   "cran". *)

let _ =
   let maxAlignes = 0 (* compléter ici *) in
   Printf.printf "%d\n" maxAlignes
Vous devez être connecté pour résoudre cet exercice.

Vous devez être connecté(e) pour résoudre ce problème.

L'inscription ne prendra qu'une minute et vous pourrez alors résoudre les exercices puis faire valider automatiquement vos solutions.

Une fois identifié(e), vous pourrez demander sur cette page des conseils pour résoudre le sujet ou demander de l'aide sur le forum d'entraide.

Lorsque vous serez connecté(e), vous pourrez voir vos actions ici.

Une correction sera mise en ligne après la fin de l'épreuve.