Prologin
2024
ENONCE
Vous êtes le directeur d'un centre commercial qui étudie une proposition de construction de patinoire dans son centre commercial. Bien sûr, votre patinoire propose des paires de patins que les clients peuvent louer. Pour chaque pointure (du 15 au 50), vous avez décidé du nombre de patins que vous rendrez disponibles à la location. Par ailleurs, une étude de marché vous donne une estimation du nombre de personnes (pour chaque minute de la journée et pour chaque pointure) qui ira à votre patinoire et qui louera donc des patins. Votre but est de savoir si la quantité de patins achetée est pertinente au vu de l'affluence à votre patinoire, en d'autres termes, vous devez écrire un programme qui prend en entrée le nombre de patins achetés pour chaque pointure, la pointure des personnes voulant louer des paires de patins, et qui simule la file d'attente des patineurs dont le fonctionnement est décrit ci-dessous.
Vous menez votre calcul sur une journée entière, où votre patinoire est ouverte de 14h à 20h. La subdivision du temps sera la minute. La minute 0 correspondra à l'horaire d'ouverture (14h), tandis que la minute 359 correspondra à la dernière minute où la patinoire sera ouverte. Les entrées dans la patinoire ferment une heure avant la fin, c'est-à-dire que les dernières entrées dans la patinoire se feront à la minute 299.
Notez également que nous ferons l'hypothèse que les patineurs patinent exactement une heure. C'est-à-dire, si un patineur entre à la minute 42, sa paire de patin peut être utilisée par un autre patineur dès la minute 102. Par ailleurs, l'essayage de patin, l'achat du billet d'entrée, le rendu des patins se font de façon instantanée. Il n'y a par exemple aucun problème à ce que 15 personnes entrent à la minute 0 dans la patinoire.
La difficulté de la gestion de la file d'attente pour votre patinoire vient du fait que les gens y viennent en groupe, et veulent patiner ensembles. Cela veut dire que quand la pointure d'au moins une personne d'un groupe n'est pas disponible, tout le groupe attend que tous ses membres aient des patins à leur taille. Cependant, vous aurez astucieusement remarqué que lorsqu'un groupe noté A attend une paire de patins dans une pointure pour un de ses membres, il peut être judicieux de faire passer avant A un groupe placé derrière dans la file d'attente. Ainsi, pour accélérer un peu la file d'attente, vous mettez en oeuvre un processus assez simple : votre "politique" est que si le deuxième groupe de la file d'attente peut passer devant le premier groupe de la file d'attente sans retarder celui-ci, alors le deuxième groupe passe devant le premier groupe. De plus, si le premier groupe ne peut jamais passer (soit parce que le temps d'attente fait que l'entrée de la patinoire est fermée, soit parce qu'ils demandent plus de patins que vous ne pouvez leur fournir), on considérera qu'il n'est jamais retardé par le deuxième groupe de la file d'attente.
Si tout le monde parvient à rentrer dans votre future patinoire, votre programme devra renvoyer l'heure (en minutes, suivant les conventions explicités ci-dessus) à laquelle le dernier groupe est entré, et sinon, votre programme devra tout simplement renvoyer le nombre de groupes de personnes n'étant pas parvenus à rentrer dans la patinoire (c'est-à-dire ceux qui n'ont pas pu rentrer avant la minute 300).
ENTREE
-
Sur la première ligne : un entier N indiquant le nombre de groupes de personnes se présentant à l'entrée de votre patinoire. N est compris entre 1 et 10000.
-
Sur la deuxième ligne : la liste du nombre de paires de patins que vous envisagez d'acheter pour chaque pointure, de la pointure 15 à la pointure 50. (Il y a donc 36 entiers sur cette ligne)
-
Sur les N lignes suivante :
* un entier t indiquant l'heure d'arrivée du groupe de personnes au bout de la queue. (t est compris entre 0 et 299).
* un entier p indiquant le nombres de personnes dans ce groupe. (p est compris entre 1 et 100)
* les p entiers qui suivent sont les pointures des personnes composant ce groupe. (avec répétitions éventuelles).
Notez que les groupes sont indiqués par t croissants, et que s'il y a plusieurs groupes qui arrivent à la même heure, l'ordre de l'entrée est l'ordre de la queue.
SORTIE
Un entier. Si tout le monde est rentré dans la patinoire, l'heure (en minutes) à laquelle le dernier groupe est entré. Sinon, le nombre de groupes n'ayant pas réussi à rentrer dans la patinoire.