France-IOI – Sujet 5 (E)

Sujet
Résoudre
Conseils
Activité
Correction

Étant donné une formule de logique contenant uniquement les opérateurs "ou", "et" et "non", et des propriétés p₁ jusqu'à p₄₀, vous devez dire s'il existe un jeu de valeurs pour les propriétés tel que la formule est vraie. Par exemple, la formule "p₁ et p₂" est vraie pour p₁ vraie et p₂ vraie. La formule "p₁ et (non p₁)" est par contre toujours fausse.

Limites de temps et de mémoire (Python)

Temps : 1 s sur une machine à 1 GHz.
Mémoire : 8 000 ko.

Entrée

L'entrée du programme contient la version pré-fixée de la formule de logique.

Soyons plus clairs : chaque ligne est soit un entier entre 1 et 40, représentant p₁ jusqu'à p₄₀, soit un opérateur ("et", "ou" ou "non"). Le tout est suivi d'un retour à la ligne. Pour retrouver la formule, on procède comme suit : si on lit un opérateur, on l'applique aux deux prochains (ou au prochain si c'est un "non") éléments "complets" qu'on lira, si c'est un entier i, on considère l'élément p_i qui lui correspond.

Par exemple: la formule "p₁ et ((non p₂) ou (non p₁))" pourra être représentée par:

et
1
ou
non
2
non
1

Ce qui se lit: "Je fais d'abord un "et". Le premier élément du "et" est p₁. Le second est un "ou". Ce "ou" a pour premier élément une négation. C'est la négation de p₂. Il a pour second élément une négation. C'est la négation de p₁." : son écriture infixe est donc "p₁ et ((non p₂) ou (non p₁))".

La formule sera toujours bien formée.

Sortie

La sortie de votre programme doit indiquer "true" si la formule de l'entrée peut être rendue vraie et "false" sinon. La réponse devra être suivie d'un retour à la ligne.

Exemples

Exemple 1

entrée :

et
1
ou
non
2
non
1

sortie :

true

Exemple 2

entrée :

et
1
ou
non
1
non
1

sortie :

false

Exemple 3

entrée :

et
5
non
ou
et
1
2
et
3
4

sortie :

true

Exemple 4

entrée :

et
non
et
et
et
et
14
26
et
21
36
et
et
22
22
et
19
11
et
ou
et
18
21
non
14
et
et
39
35
non
1
et
et
et
et
14
26
et
21
36
et
et
22
22
et
19
11
et
ou
et
18
21
non
14
et
et
39
35
non
1

sortie :

false

Commentaires

Squelettes de codes :

(* Ce fichier contient tout ce qu'il faut pour lire les donnees en entree, les 
mettre dans des variables, et afficher votre resultat final en sortie. *)

(* Fonction pour lire l'entree et la representer dans le format de votre choix --- a completer --- *)
let rec lit_entree () = 
  let ligne = input_line stdin in
  if ligne <> "" then
  begin
    let i = 
      try int_of_string ligne with _ -> 0
    in
    if i = 0
    then 
      (* dans ce cas, ligne est un operateur, soit "non", "et" ou "ou" *)
    else
      (* dans ce cas, i est le numero de la propriete consideree (pi) *)
    ;
    lit_entree ();
  end
;;

lit_entree ();;

(* fonction pour afficher votre solution *)
let affiche_solution b =
  if b then print_string "true" else print_string "false";
  print_newline();;

(* Mettez apres ceci le corps de votre programme *)
(* N'oubliez pas de terminer par un appel a affiche_solution !*)

(* Debut de votre programme *)


(* Fin de votre programme *)

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 détaillée sera disponible lorsque vous aurez résolu le sujet.