Diferente pentru problema/sieve intre reviziile #2 si #21

Nu exista diferente intre titluri.

Diferente intre continut:

== include(page="template/taskheader" task_id="sieve") ==
Poveste şi cerinţă...
Esti acasa (afara fie e prea cald, fie e prea frig) si citesti problema 'Ciurulet':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:
 
== code(c) |
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.
h2. Date de intrare
Fişierul de intrare $sieve.in$ ...
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$.
h2. Date de ieşire
În fişierul de ieşire $sieve.out$ ...
În fişierul de ieşire $sieve.out$ se vor afla $T$ linii, fiecare continand cate un numar real, reprezentand raspunsul pentru testul corespunzator.
h2. Restricţii
* $... &le; ... &le; ...$
* $1 &le; T &le; 100.000$
* $2 &le; N &le; 100.000$
* Un raspuns este considerat corect daca diferenta absoluta dintre acesta si raspunsul corect este mai mica sau egala cu $10^-4^$.
h2. Exemplu
table(example). |_. sieve.in |_. sieve.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
| 2
9
250
| 5.5
577.8554834
|
h3. Explicaţie
 
...
 
== include(page="template/taskfooter" task_id="sieve") ==

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.