Pousse-pousse – Épreuve régionale 2011

É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 N_Pékin d'horaires au départ de Pékin.
• Sur la troisième ligne, le nombre N_Shanghai d'horaires au départ de Shanghai.
• Sur la quatrième ligne, N_Pékin × 4 nombres représentant pour chaque horaire le quadruplet (H^Pékin, M^Pékin, H^Shanghai, M^Shanghai).
• Sur la dernière ligne, N_Shanghai × 4 nombres représentant pour chaque horaire le quadruplet (H^Shanghai, M^Shanghai, H^Pékin, M^Pékin).

Sortie¶

Soit P_Pékin (respectivement P_Shanghai) 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 P_Pékin × 1000 + P_Shanghai.

Contraintes¶

• 1 <= N <= 1 000