3578 - Palind

Enunt

Ana a descoperit că are o adevărată pasiune pentru palindromuri. Un şir de numere este palindrom dacă se citeşte la fel de la stânga la dreapta şi de la dreapta la stânga (primul număr este egal cu ultimul, al doilea cu penultimul etc). Ea are un şir cu N numere naturale şi vrea ca orice subsecvenţă de lungime impară a şirului să fie palindrom. Pentru a-şi îndeplini dorinţa ea poate efectua asupra şirului mai multe operaţii. O operaţie constă în alegerea unui element din şir şi incrementarea sau decrementarea lui cu o unitate. Bineînţeles, Ana doreşte să utilizeze un număr minim de operaţii pentru ca şirul obţinut să respecte proprietatea amintită mai sus (orice subsecvenţă de lungime impară să fie palindrom).

Cerinţa

Determinaţi pentru Ana numărul minim de operaţii pe care trebuie să-l efectueze pentru ca orice subsecvenţă de lungime impară a şirului obţinut în urma efectuării operaţiilor să fie palindrom. De asemenea aflaţi şi numărul de şiruri finale distincte pe care le poate obţine efectuând acest numar minim de operaţii.

Date de intrare

Fişierul de intrare palind.in va conţine pe prima linie numărul T, reprezentând numărul de seturi de date de intrare care urmează. În continuare urmează seturile de date de intrare, fiecare pe câte două linii. Pe prima linie a unui set de date se află numărul N, având semnificaţia din enunţ. Pe următoarea linie se află elementele şirului iniţial, separate prin câte un spaţiu.

Date de ieșire

Fişierul de ieşire palind.out va conţine T linii, pe linia i aflându-se două numere, reprezentând raspunsul pentru al i-lea set de date de intrare. Primul numar este numarul minim de operaţii, iar al doilea numărul de şiruri distincte finale care se pot obţine efectuând numărul minim de operaţii.

Restricţii şi precizări

• 1 ≤ T ≤ 20
• 1 ≤ N ≤ 10.000
• Elementele şirului sunt numere naturale din intervalul [1, 7.000]
• subsecvenţă a unui şir este un subşir de numere care apar pe poziţii consecutive
• Toate testele folosite la corectare vor avea T = 20
• Pentru 20% din teste 1 ≤ N ≤ 100
• Pentru 20% din teste valoarea maximă din oricare şir este cel mult 500 şi N ≥ 101

Exemplu

palind.in

2
3
1 2 3
1
3

palind.out

2 3
0 1

Explicație

entru primul test, cele trei șiruri posibile sunt: 1 2 1, 2 2 2 și 3 2 3. Pentru al doilea test, singurul șir posibil este format din elementul 3.

Rezolvare

<syntaxhighlight lang="python" line> def min_operations_and_unique_sequences(N, sequence):

   min_operations = 0
   unique_sequences = set()

   for i in range(N // 2):
       diff = abs(sequence[i] - sequence[N - i - 1])
       min_operations += diff

       # Actualizăm numărul de șiruri unice posibile
       unique_sequences.add(sequence[i] + min_operations)
       unique_sequences.add(sequence[N - i - 1] + min_operations)

   if N % 2 == 1:
       # Dacă lungimea șirului este impară, trebuie să tratăm mijlocul separat
       middle_number = sequence[N // 2]
       unique_sequences.add(middle_number + min_operations)

   return min_operations, len(unique_sequences)

def main():

   with open("palind.in", "r") as fin:
       T = int(fin.readline())
       results = []

       for _ in range(T):
           N = int(fin.readline())
           sequence = list(map(int, fin.readline().split()))

           min_ops, unique_seqs = min_operations_and_unique_sequences(N, sequence)
           results.append((min_ops, unique_seqs))

   with open("palind.out", "w") as fout:
       for min_ops, unique_seqs in results:
           fout.write(f"{min_ops} {unique_seqs}\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>