| Fişierul intrare/ieşire: | maxim2.in, maxim2.out | Sursă | Concursul National de Informatica "Adolescent Grigore Moisil" 17 |
| Autor | Florin Chirica | Adăugată de |  AGMInformatica •AGMinformatica |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Maxim2
"Maxim am spus!"
La cazinoul din coltul blocului s-au adus aparate noi. Obiectul problemei este un anume aparat ce este continuu frecventat de un anume maestru Hapsan, pe care prietenii il cunosc ca pe un adevarat erou. Putini sunt cei care vor sa recunoasca ca Hapsan se afla in realitate intr-o misiune extraordinara de a falimenta industria cazinourilor prin cat mai multe castiguri colosale.
Aparatul in cauza nu este cu mult diferit de o pacanea clasica. Maşinaria ofera un caştig jucatorului cand pe panoul de afişare video apar anumite configuratii de fructe in urma rotirii independente, cu viteza aleatoare, a tamburilor circulari. Pentru simplitate vom presupune ca pacaneaua are N tamburi, iar fructele sunt de N tipuri, indexate prin numere de la 1 la N, in ordinea valorii asociate.
Ceea ce este special la aceasta pacanea este ca mereu apar exact aceleasi N imagini intr-o ordine aleatoare. Cum nicio fructa nu se repeta pe ecranul aparatului indiferent de numarul de jocuri jucate, cazinoul s-a vazut in timp nevoit sa modifice modul in care acesta recompenseaza jucatorii. Asadar, jucatorul este recompensat doar daca reuseste sa ghiceasca numarul de maxime locale ce urmeaza sa apara. O pozitie i este considerata maxim local doar daca valoarea fructei de pe pozitia i este mai mare decat cea a vecinilor sai.
Cum maestrul Hapsan cel mai probabil deja s-a umplut de bani de pe urma acestui aparat, in mod evident nu v-ar cere voua ajutorul, insa doreste sa va ajute folosindu-si vasta experienta in ale aparatelor. El va dicteaza un sir de numere reprezentand configuratia ce urmeaza sa apara, iar strategia optima de castig este aceea de a determina numarul mediu de maxime locale ce ar putea aparea.
Date de intrare
Fişierul de intrare maxim2.in va contine pe prima linie numarul N, urmand pe linia a doua N numere reprezentand valorile fructelor dictate de maestru. Elementele despre care nu avem nicio informatie sunt marcate cu 0.
Date de ieşire
În fişierul de ieşire maxim2.out se va scrie numarul mediu de maxime locale ce ar putea aparea in urma spin-ului.
Restricţii
- 1 ≤ N ≤ 100.000
- Raspunsul va fi considerat corect doar daca |rezultat_comisie - rezultat_participant| <= 0.0000001
- Se considera ca oricare configuratiile finala poate aparea in mod echiprobabil.
Exemplu
| maxim2.in | maxim2.out |
|---|---|
| 5 4 0 0 0 1 | 1.83333333 |
Explicatie
Configuratiile finale posibile sunt:
- 4 2 3 5 1: 2 maxime (4 si 5)
- 4 2 5 3 1: 2 maxime (4 si 5)
- 4 3 2 5 1: 2 maxime (4 si 5)
- 4 3 5 2 1: 2 maxime (4 si 5)
- 4 5 2 3 1: 2 maxime (3 si 5)
- 4 5 3 2 1: 1 maxim (5)
Raspuns: (2+2+2+2+2+1)/6 = 11/6
