Nemo est un petit poisson insouciant dont le poids initial est $w_0$. L'adorable Nemo souhaite grandir le plus vite possible et doit donc manger autant que possible. Son aliment préféré est la petite crevette de mer.
Voici ce que Nemo sait de sa nourriture : la mer contient $n$ petites crevettes, numérotées de $1$ à $n$. La crevette $i$ pèse $w_i$. Représentons la mer par un repère $X$-$Y$. À l'instant $0$, la crevette $i$ se trouve en $(x_i,y_i)$. Les crevettes se déplacent en ligne droite à vitesse constante. Le vecteur vitesse de la crevette $i$ est $(p_i,q_i)$ : à l'instant $t$, elle se trouve donc en
$$ (x_i+p_i t,y_i+q_i t). $$
À l'instant $0$, Nemo se trouve en $(x_0,y_0)$. Il peut se déplacer librement dans la mer, mais sa vitesse ne doit pas dépasser $V$. Il souhaite maximiser le poids total des crevettes mangées en $T$ unités de temps (instant $T$ inclus). Lorsque Nemo et une crevette se trouvent au même endroit au même instant, et que la crevette pèse strictement moins que Nemo à cet instant, il peut la manger. Lorsqu'il mange une crevette de poids $w_i$, son propre poids augmente de $w_i$. Attention : les crevettes ne mangent pas Nemo et ne se mangent pas non plus entre elles.
Nemo souhaite que vous l'aidiez à élaborer un plan de croissance maximisant le poids total des crevettes qu'il mange.
Entrée
Il s'agit d'un problème à soumission de réponses. Tous les fichiers d'entrée, de nemo1.in à nemo10.in, se trouvent déjà dans le répertoire du problème.
Pour chaque jeu de données, la première ligne du fichier d'entrée contient cinq réels $w_0,V,T,x_0,y_0$, représentant respectivement le poids initial de Nemo, sa vitesse maximale, la limite de temps et sa position à l'instant $0$.
La deuxième ligne contient un entier $n$, le nombre de crevettes dans la mer.
Chacune des $n$ lignes suivantes contient cinq réels $w_i,x_i,y_i,p_i,q_i$, représentant respectivement le poids de la crevette $i$, sa position à l'instant $0$ et son vecteur vitesse.
Sortie
Pour les dix fichiers d'entrée fournis, de nemo1.in à nemo10.in, vous devez soumettre les fichiers de sortie correspondants, de nemo1.out à nemo10.out.
La première ligne du fichier de sortie contient un entier $k$, indiquant que Nemo mangera $k$ crevettes dans votre plan de croissance.
La deuxième ligne contient un réel $w$, le poids total des crevettes mangées par Nemo dans votre plan.
Chacune des $k$ lignes suivantes contient quatre nombres $t,x,y,s$, indiquant qu'à l'instant $t$, Nemo mange la crevette numéro $s$ à la position $(x,y)$. $t,x,y$ sont des réels et $s$ est un entier.
Pour garantir la précision du vérificateur, il est conseillé d'afficher tous les réels avec au moins six chiffres après la virgule. Le vérificateur considère deux réels comme égaux si leur écart absolu ne dépasse pas $10^{-4}$.
Exemples
Entrée 1
5 1 6 0 0 1 5 2 2 0 0
Sortie 1
1 5 5 2 2 1
Remarque
Dans cet exemple, Nemo mange la crevette numéro $1$ à l'instant $5$, à la position $(2,2)$. Il pourrait en fait atteindre $(2,2)$ plus tôt, mais l'énoncé exige seulement que sa vitesse ne dépasse pas $V$.
Sous-tâches
Pour chaque jeu de données, nous définissons neuf paramètres de score $a_{10},a_9,\dots,a_2$. Si votre sortie est invalide, vous obtenez zéro point. Sinon, en notant $w_{\mathrm{user}}$ l'augmentation de poids de Nemo dans votre plan, votre score est donné par le tableau suivant :
| Score | Condition | Score | Condition |
|---|---|---|---|
| 10 | $w_{\mathrm{user}}\ge a_{10}$ | 5 | $w_{\mathrm{user}}\ge a_5$ |
| 9 | $w_{\mathrm{user}}\ge a_9$ | 4 | $w_{\mathrm{user}}\ge a_4$ |
| 8 | $w_{\mathrm{user}}\ge a_8$ | 3 | $w_{\mathrm{user}}\ge a_3$ |
| 7 | $w_{\mathrm{user}}\ge a_7$ | 2 | $w_{\mathrm{user}}\ge a_2$ |
| 6 | $w_{\mathrm{user}}\ge a_6$ | 1 | $w_{\mathrm{user}}>0$ |
Si plusieurs conditions sont satisfaites, le score le plus élevé parmi elles est retenu.