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.

#include
#include


using namespace std;

int main()
{
ifstream in("maraton.in");
ofstream out("maraton.out");
long n,q,i,j,s,z;
in>>n;double x,y,t[n];
for(i=1;i<=n;i++){in>>x>>y;t[i]=x/y;}
in>>q;
for(j=1;j<=q;j++)
{
s=0;
in>>z;
for(i=1;i<=n;i++)
if(t[i]<=z) s++;
out< }
in.close();
out.close();
return 0;
}

Answer 1

Este vorba despre aceasta problema, nu?
http://www.pbinfo.ro/?pagina=probleme&id=1594

Iti pun aici solutia mea:

# include <iostream>
# include <fstream>

# define MAX_X 100000

using namespace std;

int f[MAX_X + 1];

int main() {
    ifstream fin("maraton.in");
    ofstream fout("maraton.out");

    int N, Q, x, y, q, i;

    fin >> N;

    for ( i = 0; i < N; i ++ ) {
        fin >> x >> y;
        f[x / y + ( x % y > 0 )] ++;
    }

    for ( i = 1; i <= MAX_X; i ++ )
        f[i] += f[i - 1];

    fin >> Q;

    for ( i = 0; i < Q; i ++ ) {
        fin >> q;
        fout << f[q] << endl;
    }

    fin.close();
    fout.close();

    return 0;
}