Néologisme – Épreuve régionale 2014

Niveau 2

Énoncé

Joseph Marchand a souvent des mots incongrus sur le bout de la langue, il aimerait bien savoir si ces mots sont de réelles inventions (potentiellement brevetables) ou simplement un manque de vocabulaire de sa part.

Pour l'aider, considérons un dictionnaire (une liste de n mots triés par ordre alphabétique), permettant de dire si le mot donné en entrée est un néologisme.

Un néologisme (du grec ancien νέος/néos, « nouveau », et λόγος/lógos, « parole ») est un mot nouveau : il n'existe pas dans le dictionnaire.

Rechercher si le mot existe dans le dictionnaire :

Entrée

  • Sur la première ligne, m, la taille du mot
  • Sur la seconde ligne, mot, le mot à tester
  • Sur la troisième ligne, un entier n, la taille du dictionnaire
  • Sur les 2N lignes suivantes, un tableau dictionnaire[n] :
    • sur la ligne 2i : la taille du mot i
    • sur la ligne 2i+1 : le mot i

Sortie

  • Sur la première ligne, 1 si "mot" est un néologisme, 0 sinon

Contraintes

  • 1 <= N <= 400000

Contraintes d'exécution

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

Exemples d'entrée/sortie

Exemple d'entrée
9
raspberry
9
6
alesia
4
argh
5
babar
4
blue
6
crayon
7
epsilon
7
jupiter
5
nuage
8
mstrkrft
Exemple de sortie
1
Exemple d'entrée
4
babb
9
1
a
3
aab
2
ab
4
baaa
4
baba
4
babb
2
bb
3
bba
3
cpp
Exemple de sortie
0