Pousse-pousse – Épreuve régionale 2011

Niveau 3

Énoncé

Ce matin-là, au réveil, Joseph Marchand s'est dit : « Et si je créais une entreprise de pousse-pousse en Chine ? »

Les pousse-pousse vont de Pékin à Shanghai (avec un peu d'opium, tout est possible) et inversement. Vous disposez des horaires d'une journée, dans chacune des stations.

Hélas, même en Chine, même sur DealExtreme, un pousse-pousse, ça coûte cher, c'est pourquoi Joseph Marchand veut en acheter le moins possible.

Il vous faut déterminer le nombre minimal de pousse-pousse qui doivent être présents au début de la journée à Pékin et à Shanghai pour que tous les transports soient assurés.

Entrée

  • Sur la première ligne, le temps que met un pousse-pousse à faire demi-tour, une fois qu'il est arrivé à destination.
  • Sur la deuxième ligne, le nombre NPékin d'horaires au départ de Pékin.
  • Sur la troisième ligne, le nombre NShanghai d'horaires au départ de Shanghai.
  • Sur la quatrième ligne, NPékin × 4 nombres représentant pour chaque horaire le quadruplet (HPékin, MPékin, HShanghai, MShanghai).
  • Sur la dernière ligne, NShanghai × 4 nombres représentant pour chaque horaire le quadruplet (HShanghai, MShanghai, HPékin, MPékin).

Sortie

Soit PPékin (respectivement PShanghai) le nombre de pousse-pousse qui doivent être à Pékin (respectivement à Shanghai) au début de la journée pour que les horaires puissent être respectés.

Votre programme doit renvoyer PPékin × 1000 + PShanghai.

Contraintes

  • 1 <= N <= 1 000

Contraintes d'exécution

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

Exemples d'entrée/sortie

Exemple d'entrée
6
1
2
15 42 17 5
13 45 14 18 23 13 23 49
Exemple de sortie
1
Exemple d'entrée
13
3
5
2 37 17 2 11 26 18 41 6 49 18 30
6 33 20 50 0 54 17 51 0 57 23 43 4 59 22 36 6 30 20 17
Exemple de sortie
3005