Question

După ce și-a cumpărat biscuiți, Costy, eroul nostru, ajunge acasă și se apucă de teme. Astfel, dă peste următoarea problemă:

“La o probă de maraton participă N maratonişti. Ştiind că la secunda 0, un maratonist se află la Xi metri de linia de sosire și aleargă cu o viteză de Yi metri/secundă, să se răspundă la Q întrebări de tipul:

Câți maratonişti au trecut linia de sosire după Qi secunde ? “
Cerința
Ajutați-l pe Costy să răspundă la cele Q întrebări.

Date de intrare
Fișierul maraton.in conține:

pe prima linie numărul N, reprezentând numărul de maratoniști;
pe următoarele N linii, câte 2 numere, Xi Yi, reprezentând distanța fată de linia de sosire și viteza fiecărui maratonist;
pe următoarea linie, numărul Q reprezentând numărul de întrebări;
pe următoarele Q linii se află câte un număr Qi reprezentând întrebarea i;
Date de ieșire
Fișierul de ieșire maraton.out conţine:
Q linii, linia i reprezentând răspunsul la întrebarea i;

Restricții și precizări
1 <= N, Q, Qi, Xi <= 100 000
1 <= Yi <= 1000



Exemplu
maraton.in

5
100 4
12 3
101 5
20 1
44 7
4
20
12
7
21
maraton.out

3
2
2
4
Explicație
La secunda 20 au trecut linia de sosire maratoniștii cu indicii 2, 4, 5.
La secunda 12 au trecut linia de sosire maratoniștii cu indicii 2, 5.
La secunda 7 au trecut linia de sosire maratoniștii cu indicii 2, 5.
La secunda 21 au trecut linia de sosire maratoniștii cu indicii 2, 3, 4, 5.​

Answer 1

#include <fstream>

#include<algorithm>

using namespace std;

ifstream fin("maraton.in");

ofstream fout("maraton.out");

int main()

{

   int a[100001], n, q, mr, v, p;

   fin >> n;

   for(int i = 1; i <= n; ++i){

       fin >> mr >> v;

       if(mr % v == 0)

           a[i] = mr / v;

       else

           a[i] = mr / v + 1;

   }

   sort(a + 1, a + n + 1);

   fin >> q;

   for(int i = 1; i <= q; ++i){

       int x;

       fin >> x;

       if(a[n] <= x)

         fout << n << '\n';

       else if(a[1] > x)

          fout << 0 << '\n';

       else{

           int st = 1, dr = n, p;

           while(st <= dr){

             int mij = (st + dr) / 2;

             if(a[mij] <= x){

               p = mij;

               st = mij + 1;

           }

            else

              dr = mij - 1;

           }

          fout << p << '\n';

   }

   }

   return 0;

}

Am folosit cautarea binara pentru a rezolva aceasta problema.

mr = metri ramasi

v = viteza

Daca ai nelamuriri, ma poti intreba!

P.S.  A luat 100 de pct. pe PbInfo.