Stock Market - Task 2

ATENȚIE: Aceasta problemă valorează $150$ de puncte. La "submissions" scorul maxim este rescalat la $100$ de puncte, dar adevaratul scor va fi vizibil pe leaderboard.

Singura diferență între Task 1 și Task 2 este constituită de conținutul fișierelor bursa.txt și queries.txt.

Evident că o companie gigantică precum Chert And este listată la Bursa de Valori București. Prețul acțiunilor variază într-un mod foarte interesant, dar care le dă bătăi imense de cap analiștilor de piață. Acestia au colectat date despre preturile actiunilor in anumite momente de timp. Ajutați-i pe aceștia să prezică prețul acțiunilor la alte momente de timp. În schimb, veți primi inside-uri referitoare la dezastrul fermei din România.

Problema

Se dau $N$ perechi de valori $x, y$. Acestea reprezintă faptul că la momentul de timp $x$, o acțiune costă $y$ RON.

Trebuie să raspundeți pentru $Q$ valori $x$, reprezentând alte momente de timp, o aproximație a prețului, $y$.

Input

Pe prima linie a fișierului atașat (în dreapta paginii sub „Atașamente”), bursa.txt, se va găsi numărul $N$.

Pe următoarele $N$ linii veți găsi perechi de numere $x,y$, cu semnificația din enunț.

Pe prima linie a fișierului atașat (în dreapta paginii sub „Atașamente”) queries.txt, se va găsi numărul $Q$.

Pe următoarea linie se vor găsi $Q$ valori $x$, cu semnificația din enunț.

Output

Problema este output only.

Submisia voastră va fi un fisier text si trebuie să conțină $Q$ valori, răspunsurile în ordine la întrebările din fișierul queries.txt.

valoare_1
valoare_2
...
valoare_Q

Va rugăm să afișați răspunsul cu o precizie de măcar $3$ zecimale.

Precizări

• Toate valorile date, dar și cele pe care comisia se așteaptă să le primească, sunt în intervalul $-10^9 \dots 10^9$ și sunt de tip double (numere reale).

Punctaj

Definim $avgDeviation = \frac{\sum_{k = 1}^{Q} |g_i - v_i|}{Q}$, iar $p = \frac{|10 - min(10, avgDeviation)|}{10}$. Intuitiv, aceast formula inseamna ca, daca in medie raspunsurile voastre la query difera fata de raspunsurile reale cu mai mult de 10, veti lua 0p. Altfel, veti lua puncte gradual.

Astfel, scorul pe care îl veți primi la problemă va fi: $p \cdot 150$. În plus:

• $\text{p} \ge 0.3$, veți primi un batch de coordonate pentru META-TASK.
• $\text{p} \ge 0.6$, veți primi două batch-uri de coordonate pentru META-TASK.
• $\text{p} \ge 0.9$, veți primi trei batch-uri de coordonate pentru META-TASK.

ATENȚIE: Batch-urile se primesc sub formă de link la Google Drive în verdictul testului de evaluare.