Parenthèses Capitales – Épreuve régionale 2023

Niveau 4

Énoncé

Le présent du mathématicien tout juste récupéré, les jeunes commencent à essayer de comprendre son utilité. Alors que Raphaël avait commencé à appuyer sur la totalité des boutons pour voir ce qu'il se passait, Oscar propose de démonter la machine. Les jeunes découvrent alors un petit compartiment déboîtable, dans lequel ils y trouvent une liste d'instructions. Serait-ce la première documentation d'un langage de programmation ?

Il semble exister dans le langage de la machine N types de parenthèses différentes. Un type de parenthèse est composé d'une parenthèse ouvrante et d'une parenthèse fermante. Dans le manuel, il est décrit deux listes de parenthèses, parentheses ouvrantes et parentheses fermantes. Il est indiqué qu'un type de parenthèse correspond aux deux parenthèses situées à la même position dans les deux listes.

Un programme est dit valide si au moins l'une de ces conditions est vérifiée :

  • Le programme est vide ;
  • Le programme est la concaténation de deux programmes valides ;
  • Le programme est une parenthèse ouvrante, suivie d'un programme valide, suivie de la parenthèse fermante du même type que la parenthèse ouvrante.

Les jeunes essayent alors de retrouver le programme de la machine. Ils font alors Q propositions de programmes qui pourraient être le programme de la petite machine. Vous devez alors, pour chaque proposition de programme, indiquer si le programme est valide ou non.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, le nombre de types de parenthèses différentes.
  • Sur les lignes suivantes, une liste de N éléments : parentheses ouvrantes, tous les types de parenthèses ouvrantes existantes.
    • Une ligne par élément de la liste : une chaîne de caractères.
  • Sur les lignes suivantes, une liste de N éléments : parentheses fermantes, tous les types de parenthèses fermantes existantes.
    • Une ligne par élément de la liste : une chaîne de caractères.
  • Sur la ligne suivante, un entier : Q, le nombre de phrases à vérifier.
  • Sur les lignes suivantes, une liste de Q éléments : programmes, la liste des programmes à vérifier.
    • Une ligne par élément de la liste : une chaîne de caractères. Les caractères peuvent être n'importe quel caractère ASCII entre 33 et 126, c'est-à-dire n'importe quel caractère imprimable, excepté l'espace (32).

Sortie

Afficher, sur une ligne pour chaque programme, VALIDE si le programme est valide, ou INVALIDE si le programme ne l'est pas.

Contraintes

  • $1 \le N \le 10$
  • $1 \le Q \le 10$
  • Les programmes font au plus 20 caractères
  • Les parenthèses font au plus 10 caractères
  • Toutes les parenthèses sont distinctes

Contraintes de performance

  • $1 \le N \le 100$
  • $1 \le Q \le 100$
  • Les programmes font au plus 100 caractères
  • Les parenthèses font au plus 50 caractères

Contraintes d'exécution

Utilisation mémoire maximum
100000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
3
(
[
{
)
]
}
10
()
[]
([])
{}()
[()(){{}}]
)(
[)
([)]
{{}()
[(}{}(()}]
Exemple de sortie
VALIDE
VALIDE
VALIDE
VALIDE
VALIDE
INVALIDE
INVALIDE
INVALIDE
INVALIDE
INVALIDE
Commentaire

Le langage comporte trois casses de parenthèses différentes:

  • (, )
  • [, ]
  • {, }

Le premier programme, (), est un programme valide, car il est composé d'une parenthèse ouvrante, puis d'un programme vide, puis de la parenthèse fermante correspondante.

Le deuxième programme, [], est également un programme valide.

Le troisième programme, ([]), est aussi un programme valide, car il est composé d'une parenthèse ouvrante, (, puis d'un programme valide, [], puis de la parenthèse fermante correspondante, ).

Le quatrième programme, {}(), est tout autant un programme valide, car il est composé d'un programme valide, {}, concaténé à un second programme valide, ().

Exemple d'entrée
3
(:
(::
:(
:)
::)
):
10
(::)
(::::)
:():
(:::():::)
(::):():
(:)
(:::::)
::()::
(:::()::)
(:(:::)::)
Exemple de sortie
VALIDE
VALIDE
VALIDE
VALIDE
VALIDE
INVALIDE
INVALIDE
INVALIDE
INVALIDE
INVALIDE
Commentaire

On peut décomposer le premier programme en (: :). Cela correspond bien à un programme valide.

De même, on peut décomposer le deuxième programme en (:: ::).

On peut décomposer le troisième programme en :( ):.

On peut décomposer à son tour le quatrième programme en (:: :( ): ::).

Enfin, on peut décomposer le cinquième programme en (: :) :( ):.

Les cinq dernièrs programmes ne peuvent pas décrire un programme valide.