Prologin
2025
Énoncé¶
Les amis se rendent compte que la machine du mathématicien était en fait un encodeur, le même qu’ils ont utilisé lors de la création de la machine ! Ils peuvent donc s’en servir pour aller à l’année qu’ils souhaitent... Cependant, ils confondent l’entrée et la sortie, et se retrouvent à aller dans le mauvais sens. Ne sachant plus du tout en quelle année ils ont atterri, les jeunes sortent de la machine pour tenter de se repérer avant de faire, ils l’espèrent, un bond final vers leur époque d’origine.
En sortant de la machine, Julie aperçoit immédiatement la pointe de la Tour Eiffel. Cependant, Augustin s’étonne de sa couleur. En effet, les amis remarquent que la Tour Eiffel est faite de bois. Voyant un mammouth s’approcher d’eux, ils comprennent que la Tour Eiffel a été inventée bien avant le ⅩⅨe siècle. Nos amis arrivent vers la tour pour la voir de plus près, ils comprennent que des hommes de Néandertal font une exposition de leurs monuments. La Tour Eiffel étant si belle en bois, les autres monuments leur paraissent fades. Un Néandertalien leur fait comprendre que s'ils décident de remédier à ce problème, il pourra leur offrir de précieuses reliques.
Pour remédier à ce problème, nos amis décident de saboter [1] ce monument.
La Tour Eiffel est formée de plusieurs parties, chaque partie possède un escalier redirigeant vers une partie d'un étage de niveau supérieur. Le sommet de la Tour Eiffel est la partie de niveau maximal, c'est la seule partie ayant ce niveau. Nous pouvons toujours atteindre le sommet en empruntant un certain nombre de fois les escaliers.
Pour déterminer la beauté du monument, une visite est organisée. Une visite est une suite de parties, les visiteurs commencent à une certaine partie puis empruntent les escaliers pour atteindre d'autres parties de niveau supérieur. Une visite est donc toujours ascendante, elle ne commence pas forcément au pied de la tour et ne se termine pas forcément à son sommet.
- Chaque partie a une beauté.
- La beauté d'une visite est la somme des beautés de ses parties.
Une seule visite est organisée pour noter la beauté de ce monument, les parties composant cette visite sont décidées aujourd'hui à 23h00. À 23h42, la visite a lieu.
Pour saboter la visite, nos jeunes aventuriers doivent préparer avant 23h00 des kits de sabotage. Ils ne connaissent donc pas quelles parties composent cette visite lors de cette préparation. Un kit peut permettre de saboter une partie de la tour, et une partie sabotée possède une beauté nulle. À 23h00, la visite est décidée et les jeunes possèdent l'information des parties composant la visite. Ils peuvent décider des parties à saboter en fonction de la visite, seul le nombre maximal de parties à saboter doit être fixé à l'avance.
Lors du sabotage, les parties sabotées doivent être adjacentes sinon cela prendrait trop de temps.
La beauté maximale est notée M. Aidez nos amis à préparer le minimum de kits tel qu'il soit possible de réaliser un sabotage entraînant une beauté n'excèdant pas M, quelle que soit la visite organisée pour noter le monument.
Notes supplémentaires :
- [1] Merci de ne pas reproduire cela dans la vraie vie.
Entrée¶
L’entrée contiendra :
- Sur la première ligne, un entier : N, le nombre de parties du monument.
- Sur la ligne suivante, un entier : M, la beauté maximale.
- Sur la ligne suivante, une liste de N entiers séparés par des espaces : beaute, les beautés de chaque partie.
- Sur la ligne suivante, une liste de N entiers séparés par des espaces : etage, une indication de la partie vers laquelle on est dirigés en empruntant les escaliers, pour chaque partie. Il est garanti que la première valeur, correspondant au sommet, est 1, vous pouvez ignorer cette valeur puisque le sommet n'a pas d'escaliers.
Sortie¶
Afficher le nombre minimal de kits tel qu'il soit possible de réaliser un sabotage entraînant une beauté n'excèdant pas M.
Contraintes¶
- $1 \le N \le 100$
- $1 \le M \le 10^3$
- $0 \le \text{beaute}_i \le 10^3$
- $1 \le \text{etage}_i \le N$
- $\text{etage}_1 = 1$, le sommet de la Tour Eiffel
Il est toujours possible d'atteindre le sommet depuis une partie via les escaliers.
Contraintes de performance¶
- $1 \le N \le 5 \times 10^4$
- $1 \le M \le 5 \times 10^4$
- $0 \le \text{beaute}_i \le 5 \times 10^4$
