Vous adorez le bowling : tous les week-ends, vous faites quelques parties avec vos amis. Ce week-end, vous décidez d'organiser un petit tournoi chez vous, et de parier sur le score qu'atteindra chacun des participants. Vous pouvez regarder les joueurs lorsqu'ils lancent la boule, et prévoir la trajectoire de celle-ci, mais de là où vous êtes, il est difficile de déterminer sans erreur combien de quilles la boule fait tomber à l'autre bout de la salle. Vous décidez donc d'écrire un programme qui le calcule pour chaque boule. |
Toutes les boules sont envoyées bien parallèlement aux bords de la piste, et leurs trajectoires ne sont pas perturbées par les quilles. De plus, il se trouve que ces joueurs utilisent des quilles spéciales qui ne peuvent pas se faire tomber mutuellement. La partie de bowling se passe chez vous, dans une salle que vous avez spécialement aménagée. Il n'y a pas de machine pour remettre les quilles en place, donc entre chaque lancer, les quilles tombées ne sont pas remplacées. De plus, la salle ne dispose pas de pistes bien séparées, donc les quilles sont partagées par tous les joueurs.
On vous donne les abscisses initiales de Q quilles dans un repère dont l'origine est le coin bas gauche de la salle. On vous décrit également chacun des N lancers par l'abscisse du centre de la boule et son rayon (chacun a une boule adaptée à sa force). Vous devez, pour chaque lancer, déterminer le nombre de quilles qui tombent. Si une quille se trouve sur le chemin de la boule, même au bord, elle tombe.
De plus, dans 40% des tests, on a L <= 10 000, Q <= 1 000 et N <= 1 000.
entrée :
17 10 2 3 4 5 8 8 10 13 15 16 3 2 5 1 15 3 5
sortie :
3 2 3
Squelette de code C++ :
#include <cstdio> int main() { int largeur, nbQuilles, nbBoules; scanf("%d%d", &largeur, &nbQuilles); for (int quille = 0; quille < nbQuilles; quille++) { int xQuille; scanf("%d", &xQuille); ... } scanf("%d", &nbBoules); for (int boule = 0; boule < nbBoules; boule++) { int rBoule, xBoule; scanf("%d%d", &rBoule, &xBoule); int nbQuillesTouches = ...; printf("%d\n", nbQuillesTouches); } }Squelette de code Caml :
open Printf let scan_int () = Scanf.scanf " %d" (fun x -> x) let scan_2int () = Scanf.scanf " %d %d" (fun x y -> x,y) let larguer = scan_int() let nb_quilles = scan_int() let quilles = Array.init nb_quilles (fun _ -> scan_int()) let nb_boules = scan_int() let boules = Array.init nb_boules (fun _ -> scan_2int()) (* Le tableau quilles contient les abscisses des quilles, et le tableau boules contient des paires de la forme (rayon_boule, abscisse_boule) décrivant chaque boule. *) let _ = (* pour chaque boule, faire : *) let nbQuillesTouchees = ... in printf "%d\n" nbQuillesTouchees