Fişierul intrare/ieşire:groaza.in, groaza.outSursăSummer Challenge 2020
AutorAlexandru PetrescuAdăugată deipus1Stefan Enescu ipus1
Timp execuţie pe test0.05 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Groaza

To avoid fainting keep repeating: it's only a movie, it's only a movie 

"The Last House on the Left (1972)" tagline

Ultima oara cand s-a uitat la un film de groaza, Marcel si-a amintit de vremea cand se inspaimanta (ca un copilas simpatic si inocent ce era) de tunelurile grigoriene. Acum ca a devenit om mare (a dat pe la o facultate, a atins un curs de probabilitati, etc.), si-a pus in gand sa atace aceasta tema dintr-o noua cealalta perspectiva.

... E doar o problema de info. E doar o problema de info.

Se dau doua numere N si M. Sa se construiasca un graf neorientat conex cu N noduri si M muchii distincte cu capetele in noduri diferite, in asa fel incat urmatorul algoritm sa aiba un numar asteptat de pasi cat mai mare (nu neaparat maxim posibil, vezi sectiunea Punctare):

  1. Te aflii afli in nodul 1
  2. Cat timp nu ai ajuns in nodul N
  3.   Dintre muchiile incidente nodului in care te aflii, alegi una aleator (toate muchiile au aceeasi probabilitate sa fie alese) si mergi in nodul indicat de ea.

Date de intrare

Fişierul de intrare groaza.in contine pe prima linie numerele N si M.

Date de ieşire

În fişierul de ieşire groaza.out se afla M linii, pe fiecare dintre ele aflandu-se cate doua numere despartite prin cate un spatiu, reprezentand capetele uneia dintre muchii.

Restricţii

  • 2 ≤ N ≤ 50
  • N - 1 ≤ M ≤ N * (N - 1) / 2

Punctare

Pe fiecare din cele 5 teste de evaluare, punctarea se va face in acelasi fel si independent (testele nu sunt grupate). Astfel, din cele 20 puncte posibile per test, se vor acorda o parte, in functie de caz:

  • Daca graful afisat nu contine exact M muchii, sau muchiile nu sunt distincte, sau vreuna are capetele in acelasi nod, sau graful nu e conex: se acorda 0 puncte
  • Altfel, se va calcula E = numarul asteptat de executari ale instructiunii 3 din pseudocod, si se va compara cu X = aceeasi valoare, doar ca obtinuta pentru graful gasit de ...comisie; se acorda  min(20, [ 20.01 * \frac{E}{X} ]) puncte

Foarte important este ca punctajul obtinut este unul preliminar!: La finalul concursului, comisia isi ia dreptul (vorba vine, ca il are deja) sa ruleze local orice sursa trimisa si sa inlocuiasca numarul X (definit adineauri mai sus) cu numarul E (obtinut de sursa aceasta), in caz ca E > X. Apoi toate sursele la aceasta problema sunt reevaluate. Amintim ca doar ultima submisie conteaza in clasament.

Prima implicatie: Punctajele pot sa scada, adica e posibil ca feedbackul primit in timpul concursului sa nu corespuna cu cel din clasament. (Teoretic, pot si sa creasca, in caz ca anumite solutii nedeterministe gasesc un graf mai avantajos la reevaluare.)

A doua implicatie: Un graf foarte potrivit pentru cerinta problemei va putea fi rasplatit nu doar cu punctajul maxim pe test ci si cu cresterea diferentei de punctaj fata de ceilalti concurenti (alaturi de recunoasterea tacita a comsiei ca a fost depasita intelectual de ingeniozitatea concurentului).

Nota importanta: Referitor la sursele nedeterministe. Atat numarul X initial, cat si numarul X final, vor fi obtinute prin rularea unor surse care afiseaza acelasi graf la fiecare rulare, adica sunt determinste in ceea ce priveste rezultatul. De asemenea, sursele acestea nu ruleaza intr-un timp care sa depaseasca limita de timp a problemei. In primul rand, aceasta inseamna ca tot timpul va exista o solutie determinista care sa ia punctajul maxim. In al doilea rand, sursele nedeterministe nu vor fi luate in calcul pentru aceasta cursa la cel mai bun graf obtinut. De asemenea, e bine de stiut ca reevaluarea surselor se poate face de oricate ori inainte de afisarea rezultatelor la aceasta problema, asa ca sursele nedeterministe s-ar putea sa nu aiba atata noroc cat si-ar dori.

Se cunosc cateva valori pentru valorile lui N si M din teste:

test#1#2#3#4#5
N501023??
M4940?52?

Exemplu

groaza.ingroaza.out
4 3
1 2
2 3
3 4

Explicaţie

Pentru graful afisat, exemplul de la problema Tunelul groazei ne invata ca E ar fi egal cu 9. Fie ca ii credem sau nu pe cei are s-au ocupat de acel exemplu, oricum nu stim care este valoarea lui X, si nici care este maximul posibil pentru N = 4 si M = 3.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?