| Fişierul intrare/ieşire: | palind2.in, palind2.out | Sursă | ONI 2008, clasa a 9-a |
| Autor | Adrian Airinei | Adăugată de |  Gabriel Bitis •gabitzish1 |
| Timp execuţie pe test | 0.075 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Palind2
Ana a descoperit ca are o adevarata pasiune pentru palindroame. Un sir de numere este palindrom daca se citeste la fel de la stanga la dreapta si de la dreapta la stanga (primul numar este egal cu ultimul, al doilea cu penultimul etc). Ea are un sir cu N numere naturale si vrea ca orice subsecventa de lungime impara a sirului sa fie palindrom. Pentru a-si indeplini dorinta ea poate efectua asupra sirului mai multe operatii. O operatie consta in alegerea unui element din sir si incrementarea sau decrementarea lui cu o unitate. Bineinteles, Ana doreste sa utilizeze un numar minim de operatii pentru ca sirul obtinut sa respecte proprietatea amintita mai sus (orice subsecventa de lungime impara sa fie palindrom).
Cerinta
Determinati pentru Ana numarul minim de operatii pe care trebuie sa-l efectueze pentru ca orice subsecventa de lungime impara a sirului obtinut in urma efectuarii operatiilor sa fie palindrom. De asemenea aflati si numarul de siruri finale distincte pe care le poate obtine efectuand acest numar minim de operatii.
Date de intrare
Fisierul de intrare palind2.in va contine pe prima linie numarul T, reprezentand numarul de seturi de date de intrare care urmeaza. In continuare urmeaza seturile de date de intrare, fiecare pe cate doua linii. Pe prima linie a unui set de date se afla numarul N, avand semnificatia din enunt. Pe urmatoarea linie se afla elementele sirului initial, separate prin cate un spatiu.
Date de iesire
Fisierul de iesire palind2.out va contine T linii, pe linia i aflandu-se doua numere, reprezentand raspunsul pentru al i-lea set de date de intrare. Primul numar este numarul minim de operatii, iar al doilea numarul de siruri distincte finale care se pot obtine efectuand numarul minim de operatii.
Restrictii
- 1 ≤ T ≤ 20;
- 1 ≤ N ≤ 10.000;
- Elementele sirului sunt numere naturale din intervalul [1, 7.000];
- Subsecventa a unui sir este un subsir de numere care apar pe pozitii consecutive;
- Toate testele folosite la corectare vor avea T = 20;
- Pentru 20% din teste 1 ≤ N ≤ 100;
- Pentru 20% din teste valoarea maxima din oricare sir este cel mult 500 si 101 ≤ N.
Exemplu
| palind2.in | palind2.out |
|---|---|
| 2 3 1 2 3 1 3 | 2 3 0 1 |
Explicatie
Pentru primul test, cele trei siruri posibile sunt: 1 2 1, 2 2 2 si 3 2 3. Pentru al doilea test, singurul sir posibil este format din elementul 3.
