Sujet 5 (E)

Étant donné une formule de logique contenant uniquement les opérateurs "ou", "et" et "non", et des propriétés p1 jusqu'à p40, 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 "p1 et p2" est vraie pour p1 vraie et p2 vraie. La formule "p1 et (non p1)" 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 p1 jusqu'à p40, 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 pi qui lui correspond.

Par exemple: la formule "p1 et ((non p2) ou (non p1))" 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 p1. Le second est un "ou". Ce "ou" a pour premier élément une négation. C'est la négation de p2. Il a pour second élément une négation. C'est la négation de p1." : son écriture infixe est donc "p1 et ((non p2) ou (non p1))".

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 *)


Source : http://www.france-ioi.org/