Néologisme – Regional event 2014

Level 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

Runtime constraints

Maximum memory usage
1000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
9
raspberry
9
6
alesia
4
argh
5
babar
4
blue
6
crayon
7
epsilon
7
jupiter
5
nuage
8
mstrkrft
Sample output
1
Sample input
4
babb
9
1
a
3
aab
2
ab
4
baaa
4
baba
4
babb
2
bb
3
bba
3
cpp
Sample output
0

Submit your solution

You have to register or log in to be able to submit your solution.