Fişierul intrare/ieşire:guest.in, guest.outSursăACM-ICPC Faza Nationala 2018
AutorAlexandru Petrescu, Mihai CalanceaAdăugată de
Timp execuţie pe test2 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/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
  • Exista cel putin o camera libera pentru fiecare test.

Exemplu

guest.inguest.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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?