| Fişierul intrare/ieşire: | formulaone.in, formulaone.out | Sursă | IIOT 2021-22 Runda 4 |
| Autor | Ioan Popescu | Adăugată de |  Stefan Dascalescu •stefdascalescu |
| Timp execuţie pe test | 3 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Formulaone
Formula One (also known as Formula 1 or F1) is the highest class of international racing for open-wheel single-seater formula racing cars sanctioned by the Federation Internationale de l’Automobile (FIA). Matthew is a die-hard fan of F1 and an outstanding programmer. As he watched an F1 race with N cars, he found some strange patterns. Mainly, he observed that the distance traveled by the i-th car up to the moment of time T is equal to T^2 * a[i] + T * b[i] + c[i], where a[i], b[i] and c[i] are some constants.
Matthew decided to implement an interactive scoreboard, where someone can see what car occupies a certain position at a certain moment. Strictly speaking, there are Q queries ($P, T$), which ask for the index of the car occupying the P-th position at the moment T. The position of a car is related to the distance it traveled, more distance meaning a better place (the first car traveled the most, the second car traveled the second most, and so on). If two cars travel the same distance, the lower index one is ahead.
As Matthew is busy watching the races, he asks you to implement the scoreboard for him.
Date de intrare
The input file formulaone.in contains on the first line an integer N, the number of cars taking part in the race.
On each of the following N lines there are 3 integers separated by a space: a[i], b[i] and c[i].
The next line of the input contains an integer Q, the number of queries you need to answer.
On each of the following Q lines, there are 2 integers separated by a space: P and T
Date de ieşire
The output file formulaone.out will contain Q lines, containing the answer for each query.
Restricţii
- 1 ≤ P ≤ N ≤ 2000
- 0 ≤ T, a[i], b[i], c[i] ≤ 10^6
- 1 ≤ Q ≤ 2 * 10^5
- For tests worth 20 points, 1 ≤ N ≤ 10
- For tests worth 30 more points, 1 ≤ Q ≤ 5 * 10^4
Exemplu
| formulaone.in | formulaone.out |
|---|---|
| 5 5 7 1 4 7 2 3 3 3 7 6 9 10 2 3 10 1 0 3 1 4 2 5 3 1 4 5 656300 2 632744 3 549544 5 60828 2 67803 | 4 1 2 3 5 3 4 1 3 4 |
