Vous avez la reçu la mission de débarrasser le royaume de tous les monstres qui l'habitent. Il y a deux types de monstres, les grands monstres squelettiques et les petits monstres grassouillets.
Pour tuer un grand monstre squelettique, il vous faut une épée suffisamment longue. La longueur exacte dépend du monstre en question. Pour tuer un petit monstre grassouillet, il vous faut une épée suffisamment solide, et donc suffisamment large. La largeur exacte dépend là encore du monstre considéré.
Vous avez bien étudié le profil de chacun des monstres habitant le royaume, et vous connaissez donc le type de chaque monstre ainsi que la longueur ou bien la largeur minimum d'une épée qui peut le tuer.
Vous vous rendez maintenant à l'armurerie pour vous équiper. On vous y propose un ensemble d'épées, chaque épée étant d'une certaine longueur et d'une certaine largeur. Quel est le nombre minimum d'épées qu'il vous faut acheter afin de pouvoir tuer tous les monstres ? Notez qu'il se peut que cette mission soit impossible.
Les N lignes suivantes décrivent les monstres un par un. Chacune contient ainsi deux entiers séparés par un espace :
La ligne suivante contient un entier : P.
Les P lignes suivantes décrivent les épées une par une. Chacune contient ainsi deux entiers séparés par un espace :
Vous devez afficher exactement un entier sur une ligne, représentant le nombre minimal d'épées à acheter pour pouvoir tuer tous les monstres, ou bien -1 si c'est impossible.
entrée :
4 1 6 0 12 0 18 1 4 5 14 7 9 3 1 1 18 2 7 15
sortie :
2
L'armurier vous propose 5 épées différentes :
Squelette de code C++ :
#include <cstdio> #include <cstdlib> int main() { // pour lire un nombre dans la variable X, faire : int X; scanf("%d", &X); // pour afficher un entier X sur une ligne, faire : printf("%d\n", X); return 0; }Squelette de code Caml :
let scan_int () = Scanf.scanf " %d" (fun x -> x) let show_int n = Printf.printf "%d\n" n let _ = (* votre code ici *) (* pour lire un nombre, utilisez la ligne suivante *) let x = scan_int() in (* pour afficher le nombre x sur une ligne, faire *) show_int x;