Fişierul intrare/ieşire:sieve.in, sieve.outSursăACM-ICPC Faza Nationala 2017
AutorMihai CalanceaAdăugată deklamathixMihai Calancea klamathix
Timp execuţie pe test1 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Sieve

Esti acasa (afara fie e prea cald, fie e prea frig) si citesti problema Ciurulet. Te intrebi: oare in cate feluri pot gresi Algoritmul lui Eratosthene astfel incat comportamentul lui sa fie semi-interesant?

Raspunsul pare sa fie "suficiente".

In aceasta problema vei analiza cum se comporta Ciurul lui Eratosthene daca in loc sa parcurgi numerele in ordinea {2, 3, 4, .. N}, le parcurgi 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;
}

int identity = countSteps(8, {2, 3, 4, 5, 6, 7, 8});
int misplaced_four = countSteps(8, {4, 2, 3, 5, 6, 7, 8});

//identity are valoarea 4, iar misplaced_four are valoarea 5.

Dandu-ti-se un numar N, te intrebi care este valoarea medie asteptata intoarsa de functia countSteps(N, p) daca permutarea p este generata aleator si uniform. Daca nu stii ce inseamna valoare medie (ceea ce ar fi ciudat, fiindca ti-ai pus singur intrebarea), sa stii ca este numarul obtinut prin calcularea mediei aritmetice a tuturor rezultatelor functiei atunci cand o executi pe toate permutarile posibile.

Date de intrare

Fişierul de intrare sieve.in va contine pe prima sa linie numarul T reprezentand numarul de teste. Urmatoarele T teste contin cate o valoare N.

Date de ieşire

În fişierul de ieşire sieve.out se vor afla T linii, fiecare continand cate un numar real, reprezentand raspunsul pentru testul corespunzator.

Restricţii

  • 1 ≤ T ≤ 100.000
  • 2 ≤ N ≤ 100.000
  • Un raspuns este considerat corect daca diferenta absoluta dintre acesta si raspunsul corect este mai mica sau egala cu 10-4.

Exemplu

sieve.insieve.out
2
9
250
5.5
577.8554834
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?