Fişierul intrare/ieşire:	sieve.in, sieve.out	Sursă	ACM-ICPC Faza Nationala 2017
Autor	Mihai Calancea	Adăugată de	Mihai Calancea •klamathix
Timp execuţie pe test	0.5 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Sieve

//Povestea va fi schimbata

In aceasta problema vom analiza cum se comporta Ciurul lui Eratosthene daca in loc sa parcurgem numerele in ordinea {2, 3, 4, .. N}, le parcurgem in ordinea data de o permutare aleatoare a acestor numere. Mai exact, dandu-se acest pseudocod:

int countSteps(int n, vector<int> p) {
    vector<bool> Composite(n + 1, false);
    int steps = 0;

    // p este o permutare a multimii {2, 3, ..., n}

    for(int index = 0; index < n - 1; ++index) {
        if(not Composite[p[index]]) {
            for(int multiple = 2 * p[index]; multiple <= n; multiple += p[index]) {
                Composite[multiple] = true;
                steps += 1;
            }
        }
    }

    return steps;
}

Ne intrebam care este valoarea medie intoarsa de functia countSteps() daca permutarea p este generata aleator si uniform.

Date de intrare

Fişierul de intrare sieve.in ...

Date de ieşire

În fişierul de ieşire sieve.out ...

Restricţii

• ... ≤ ... ≤ ...

Exemplu

Cum se trimit solutii?