Vacances spatiales – Épreuve régionale 2020

Niveau 2

Énoncé

Chewbacca souhaite partir en vacances retrouver sa famille sur la planète Kashyyyk. Le problème est que Han Solo a besoin de son fidèle copilote sur le Faucon Millenium. Notons que la période des vacances dure $P$ jours.

Après négociations, Han Solo accepte la requête de Chewie, mais seulement sous certaines conditions. En effet, Han a prévu plusieurs missions durant cette période et a besoin de Chewie pour celles-ci. La famille de Chewbacca habite loin, et Chewie se refuse à faire des aller-retours pour des périodes de moins de $mn$ jours. De plus, pendant ses vacances, Chewbacca aimerait voir sa famille au moins $D$ jours au total. Notons que Chewbacca a un vaisseau pouvant atteindre la vitesse de la lumière, le temps de trajet est donc considéré comme instantané.

Chewie a besoin de votre aide pour trouver comment organiser son emploi du temps pour pouvoir profiter de sa famille tout en étant disponible pour Han.

Entrée

Les trois premières lignes contiennent chacune un entier, dans l'ordre suivant :

  • $P$ représentant le nombre de jours durant lesquels Chewbacca peut partir voir sa famille.
  • $D$ correspondant au nombre total de jours minimums que Chewie veut passer avec sa famille.
  • $mn$ est le minimum de jours consécutifs pour un voyage.

La quatrième ligne contient $P$ entiers correspondant à tous les jours de la période donnée. Un jour est indiqué par un 0 si Chewbacca peut partir ou un 1 s'il doit être sur le vaisseau.

Sortie

Vous devrez afficher 1 s'il est possible pour Chewbacca de passer au moins $D$ jours avec sa famille. Si cet objectif n'est pas atteignable, vous devrez retourner 0.

Contraintes

  • $7 \le P \le 100$
  • $3 \le D \le P$
  • $1 \le mn \le 7$

Contraintes d'exécution

Utilisation mémoire maximum
1000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
15
7
3
0 0 0 1 0 0 1 0 0 0 0 1 0 0 0
Exemple de sortie
1
Commentaire

Sur les trois premiers jours, Chewbacca peut partir voir sa famille puis revenir sur le vaisseau. Sa deuxième période de temps libre ne dure que deux jours, donc il ne veut pas prendre la peine de voyager (car $mn = 3$). Enfin sa troisième période libre dure 4 jours ce qui au total permet à Chewbacca de voir sa famille 7 jours.

Exemple d'entrée
10
5
2
0 1 0 1 0 0 1 0 0 1
Exemple de sortie
0
Commentaire

Chewbacca ne peut pas cumuler 5 jours de vacances avec sa famille sans faire de voyages de moins de deux jours ($mn = 2$).