Alien – Regional event 2003

Level 6

ENONCE

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ébarasser d'un alien à tous les coups, mais n'a qu'un nombre limité de munitions, et ne peut donc pas se débarasser 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 perde s'il elle décide de contourner la pièce.

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

Ecrivez 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.

CONTRAINTES

  • 1 \<= >I/I\< >= 300, où T est le nombre de secondes dont Ripley dispose.

  • 1 \<= >I/I\< >= 300, où M est le nombre de munitions dont Ripley dispose.

  • 1 \<= >I /I\< >= 100, où P est le nombre de pièces le long du couloir.

  • 1 \<= >I/I\< >= 300, où A est le nombre total d'aliens répartis dans les différentes pièces.

ENTREE

  • La première ligne de l'entrée contient un entier : le nombre de munitions dont dispose Ripley au départ.

  • La deuxième ligne de l'entrée contient un entier : 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 un 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.

Runtime constraints

Maximum memory usage
1000 kilobytes
Maximum execution time
250 milliseconds

Input/output samples

Submit your solution

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