Alien – Épreuve régionale 2003

Énoncé¶

Ripley cherche à atteindre sa capsule de sauvetage, pour s'échapper de son vaisseau infesté d'aliens. Elle dispose d'une arme puissante, permettant de se débarrasser d'un alien à tous les coups, mais n'a qu'un nombre limité de munitions, et ne peut donc pas se débarrasser de tous les aliens.

Elle a également un détecteur, lui permettant de savoir où se trouvent les aliens, et peut ainsi les contourner. Malheureusement, elle ne peut pas se permettre de tous les contourner, car le compte à rebours est en marche, et elle a un temps limité pour atteindre sa capsule, avant que le vaisseau ne se désintègre par une explosion thermonucléaire.

Son vaisseau se trouve à l'autre extrémité d'un long couloir, dans lequel se trouvent un certain nombre de pièces contenant des aliens. Tant qu'elle reste dans ce couloir, et qu'elle traverse les pièces en poutrant les aliens, elle peut aller très vite, et ne perd qu'un temps négligeable, qu'on ne comptera pas.

Pour chaque pièce se trouvant le long du couloir, Ripley a le choix entre deux solutions : poutrer les aliens, ce qui lui demande autant de munitions qu'il y a d'aliens dans la pièce, ou bien contourner la pièce, ce qui lui fait perdre un certain temps.

On vous passe en paramètre une liste des pièces à traverser, dans l'ordre, et pour chaque pièce, le nombre d'aliens qu'elle contient, et le temps (un nombre entier de secondes) que Ripley doit perdre si elle décide de contourner la pièce.

On vous donne également le temps et le nombre de munitions dont elle dispose au départ.

Écrivez une fonction qui détermine si Ripley a une chance d'atteindre sa capsule à temps. Bien sûr, si Ripley traverse une pièce contenant plus d'aliens qu'il ne lui reste de munitions, elle servira de repas aux aliens qu'elle ne pourra pas tuer.

Votre fonction doit retourner 1 si Ripley peut atteindre sa capsule avant, 0 sinon. S'il lui reste exactement un temps de 0 après avoir traversé ou contourné la dernière pièce, elle atteint sa capsule in-extremis, mais survit.

Entrée¶

• La première ligne de l'entrée contient un entier $M$ : le nombre de munitions dont dispose Ripley au départ.
• La deuxième ligne de l'entrée contient un entier $T$ : le temps en secondes dont Ripley dispose pour atteindre sa capsule de sauvetage.
• La troisième ligne de l'entrée contient un entier $P$ : le nombre de pièces du couloir.
• Chacune des $P$ lignes suivantes contient deux entiers séparés par une espace : le nombre d'aliens se trouvant dans la pièce, et le temps en secondes nécessaire à Ripley pour contourner cette pièce.

Sortie¶

Vous devez écrire une ligne sur la sortie :

• Un entier, valant 1 ou 0, suivant si Ripley peut ou non atteindre sa capsule avant que le vaisseau n'explose.

Contraintes¶

• $1 \le M, T, P \le 300$