Bowling

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.

Limites de temps et de mémoire (Python)

  • Temps : 1 s sur une machine à 1 GHz.
  • Mémoire : 32 000 ko.

Contraintes

  • 2 <= L <= 1 000 000, où L est la largeur de la piste.
  • 1 <= Q <= 100 000, où Q est le nombre de quilles placées au départ.
  • 1 <= N <= 100 000, où N est le nombre de boules lancées.
  • 0 < Xi < L, où Xi est l'abscisse de la quille i.
  • 1 <= Rj, avec 2Rj <= L, où Rj est le rayon de la jème boule lancée.
  • Rj <= Bj <= L - Rj, où Bj l'abscisse du centre de la jème boule lancée.

De plus, dans 40% des tests, on a L <= 10 000, Q <= 1 000 et N <= 1 000.

Entrée

  • La première ligne de l'entrée contient deux entiers : la largeur L de la piste, et le nombre Q de quilles au départ.
  • La deuxième ligne contient Q entiers séparés par des espaces : les abscisses Xi des quilles, dans l'ordre croissant. Plusieurs quilles peuvent avoir la même abscisse.
  • La troisième ligne contient un entier : le nombre N de boules lancées
  • Les N lignes suivantes décrivent les boules lancées, dans l'ordre. Chaque ligne contient deux entiers séparés par un espace : le rayon Rj de la boule, et l'abscisse Bj de son centre

Sortie

Vous devez écrire N lignes sur la sortie, contenant pour chaque lancer le nombre de quilles qui tombent.

Exemple

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

Commentaires

L'exemple correspond à l'illustration ci-dessus, où l'on représente la première boule lancée. Les illustrations ci-dessous représentent le lancement de la deuxième et troisième boule. Les quilles barrées sont celles que la boule fait tomber, et les quilles en pointillés sont les quilles renversées par les boules précédentes.

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

Source : http://www.france-ioi.org/ Créé par : Mathias Hiron et Jacques-Henri Jourdan.