.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » reducere

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
reducere


Timp maxim de execuţie / test:
0.7s
Memorie totala disponibilă / stivă:
2MB / 1MB

Fie A[1...n] un vector de 9c(n numere naturale. Considerăm operația reducere, care procedează după cum urmează: se aleg doi indici i, j din mulțimea {1, ..., n}, cu |i-j| > 0; se calculează b=A[i]A[j]+A[i]+A[j]; A[i] se înlocuiește cu b; A[j] se șterge. După o aplicare a operației reducere, vectorul A va avea n-1 componente. Se aplică operația reducere până se ajunge la un vector cu o singură componentă.

Cerinţă

Se cere să se scrie un program care să determine cea mai mică valoare posibilă care se poate obține pornind de la un vector dat A, după aplicarea operației reducere de n-1 ori.

Date de intrare

Programul citește din fișierul reducere.in. Pe prima linie se găsește numărul natural n, urmat de n numere naturale A[1], ..., A[n].

Date de ieşire

Programul scrie pe prima linie din fișierul reducere.out valoarea cerută modulo 666013. Numărul natural scris este urmat de caracterul sfârșit de linie.

Restricţii

1n, A[i]≤106

Exemple

reducere.inreducere.outExplicaţii
3 1 1 1 7 Numărul n de numere este 3. Numerele sunt A[1]=1, A[2]=1, A[3]=1. Minimul obținut din vectorul A este 7.
4 1 2 3 4 119 Numărul n de numere este 4. Numerele sunt A[i]=i. Minimul obținut din vectorul A este 119.

autor: Prof. Dr. Cornelius Croitoru
propunător: Stud. Vlad Manea
FII
vlad.c.manea@gmail.com
Probleme recomandate
surse trimise | ajutor