Vous êtes directeur technique d'un club amateur de parachutisme dont la particularité est de se situer dans une zone très humide, avec de nombreux lacs. Votre problème est de savoir où lâcher les parachutistes pour qu'ils ne tombent pas dans un lac. Pour simplifier, on supposera que les parachutistes tombent verticalement, et que les lacs sont rectangulaires. Notez que les différents lacs peuvent se superposer.
Plus précisément, la carte de la région est carrée, quadrillée en D lignes et D colonnes (les lignes et colonnes sont numérotées de 0 à D - 1). La carte contient précisément L lacs rectangulaires. Étant donné N points de largage possibles, on vous demande de dire pour chaque point s'il se trouve au-dessus d'un lac ou non.
Voici un exemple de terrain de dimension 10 par 10 dans lequel les lacs sont coloriés en bleu et les points de largage marqués par des croix :
La sortie doit être composée de N lignes. La i-ème ligne doit contenir l'entier 1 si le i-ème point de larguage se situe au-dessus d'un lac, et l'entier 0 sinon.
entrée :
10 3 8 2 5 5 8 4 2 8 5 0 0 2 1 7 0 1 8 8 8 7 3 5 1 0 0 3 4 5 5
sortie :
0 0 0 1 0 1 0 1
Cet exemple correspond à la carte donnée précédemment.