Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | guest.in, guest.out | Sursă | ACM-ICPC Faza Nationala 2018 |
Autor | Alexandru Petrescu, Mihai Calancea | Adăugată de | |
Timp execuţie pe test | 2 sec | Limită de memorie | 524288 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Guest
Consateanul tau Dorel are un hotel, si, ca toti hotelierii, vrea sa isi maximizeze profitul. Hotelul sau poate fi vizualizat ca o insiruire de N camere, unele pline, unele goale, de la 1 la N.
Viata hotelierului nu este totusi atat de simpla. Din cand in cand, el trebuie sa elibereze cate o camera pentru diverse motive (venirea unui VIP,
sau poate dezinsectia). In cazul acesta, el muta omul dintr-acea camera intr-o alta camera, apoi muta omul dintr-acea camera intr-o alta camera, si tot asa, pana muta un om intr-o camera goala. Desigur, daca camera este deja goala, el nu are nimic de facut. Oamenilor mutati clar nu le place acest procedeu, si astfel vor negocia o despagubire monetara pentru deranjul cauzat. Fiecare om este dotat cu un anume skill de negociere natural pozitiv S, si cu el va putea negocia o despagubire de S * x lire elvetiene daca este mutat cu x camere la dreapta sau la stanga.
Dorel iti spune ca daca tu il ajuti sa prezica care ar fi despagubire totala daca el ar fi fortat sa elibereze fiecare camera in parte, atunci iti va plati 10% din toate profiturile sale pe urmatoarea luna. Poti sa-l ajuti ?
Date de intrare
Fişierul de intrare guest.in va contine pe primul rand T numarul de teste in fisier. Urmeaza descrierile celor T teste.
Pe primul rand al fiecarui test se va gasi numarul N.
Pe urmatorul rand se vor gasi N numere. Daca al i-lea numar este egal cu un numar natural nenul x, atunci cea de a i-a camera contine un musafir cu skillul de negociere egal cu x. Altfel, daca al i-lea numar este egal cu 0, atunci cea de a i-a camera este goala.
Date de ieşire
În fişierul de ieşire guest.out va contine T randuri, raspunsurile pentru cele T teste.
Raspunsul pentru un test se calculeaza astfel. Daca costul pentru a elibera cea de a i-a camera este ri, atunci raspunsul este (r1 * 29n-1 + r2 * 29n-2 + ... + rn * 290) mod 1 000 000 007. Sugeram sa folositi urmatorul cod pentru a transforma sirul r in raspunsul pe test:
/* functia ia r ca un sir de long long-uri indexate de la 1, si pe n, si returneaza raspunsul */
long long calculate_raspuns(long long r[], int n){
long long ret = 0;
for(int i = 1; i <= n; ++i){
ret = (29 * ret + r[i]) % 1000000007ll; }
return ret; }
Restricţii
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 100 000
- 1 ≤ x ≤ 1 000 000 000
Exemplu
guest.in | guest.out |
---|---|
3 8 0 1 3 5 5 4 2 0 4 0 5 8 1 4 1 0 0 1 | 683506829 4527 24390 |
Explicaţie
Sirurile r pentru teste sunt:
Pentru primul test: 0 1 4 9 11 6 2 0
Pentru al doilea test: 0 5 11 3
Pentru al treila test: 1 0 0 1