Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | kinetic.in, kinetic.out | Sursă | Algoritmiada 2013, Runda 1 |
| Autor | Cosmin Gheorghe | Adăugată de |  Adrian Budau •freak93 |
| Timp execuţie pe test | 0.3 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Kinetic
Se dau N puncte care circula pe axa Ox. Pozitia celui de-al i-lea punct la momentul de timp t este dat de formula: ai + bi * t. Vi se mai dau deasemenea M query-uri de forma x y t. Pentru fiecare vi se cere sa ziceti cate puncte sunt intre coordonatele x si y (inclusiv) la momentul de timp t.
Date de intrare
Fişierul de intrare kinetic.in va contine pe prima linie 2 numere naturale N, si M, numarul de puncte, respectiv numarul de query-uri.
Urmatoarele N linii vor contine fiecare 2 valori. Astfel cea de-a i + 1 linie va contine valorile ai, respectiv bi.
Urmatoarele M linii vor contine fiecare 3 valori, x, y si t reprezentand intervalul de pe axa Ox la timpul t pentru care se intreaba.
Date de ieşire
În fişierul de ieşire kinetic.out trebuie sa se gaseasca M linii, cate una pentru fiecare query. Astfel cea de-a i-a linie din fisierul de iesire trebuie sa contina raspunsul pentru cel de-al i-lea query.
Restricţii
- 1 ≤ N ≤ 500
- 1 ≤ M ≤ 200.000
- -10.000 ≤ ai, bi ≤ 10.000
- -1.000.000.000 ≤ x, y ≤ 1.000.000.000
- 0 ≤ t ≤ 10.000
Exemplu
| kinetic.in | kinetic.out |
|---|---|
| 3 3 -9 -1 -2 -5 5 -8 91 -66 10 -73 38 4 86 23 7 | 2 3 0 |
Explicaţie
La momentul de timp 10 punctele se vor afla la coordonatele -9 + 10 * (-1) = -19, -2 + 10 * (-5) = -52 si 5 + 10 * (-8) = -75. Dintre acestea doar primele 2 se afla intre 91 si -66 pe axa Ox.
