Fişierul intrare/ieşire:palind2.in, palind2.outSursăONI 2008, clasa a 9-a
AutorAdrian AirineiAdăugată degabitzish1Gabriel Bitis gabitzish1
Timp execuţie pe test0.15 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.inpalind2.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content