3358 - gama: Difference between revisions

From Bitnami MediaWiki
Dragos1234 (talk | contribs)
Dragos1234 (talk | contribs)
Line 7: Line 7:


== Date de ieșire ==  
== Date de ieșire ==  
Fișierul de ieșire '''rotire25.out''' va conține un singur număr. Dacă C = 1, acest număr reprezintă rezultatul pentru prima cerinţă și se va afișa in consolă mesajul "Datele introduse corespund cerintelor.", iar dacă C = 2, acest număr reprezintă rezultatul pentru a doua cerință și se va afișa din nou in consolă mesajul "Datele introduse corespund cerintelor." În cazul în care datele de intrare nu respecta aceste condiții programul va afișa în consolă mesajul "Datele introduse nu corespund cerintelor."
Fișierul '''gama.out''' conține pe primul rând n numere naturale, distincte de la 1 la n, separate prin câte un spațiu, reprezentând permutarea obținută, iar in consolă se va afișa mesajul "Datele introduse corespund cerintelor." În cazul în care datele de intrare sunt invalide programul va afișa în consolă mesajul "Datele introduse nu corespund cerintelor."


== Restricţii şi precizări ==
== Restricţii şi precizări ==

Revision as of 14:21, 14 April 2023

Sursa: [1]

Cerinţa

Se dă o permutare a mulțimii {1, 2, ..., n} adică un șir cu n numere distincte cuprinse între 1 și n. Se mai dă și o valoare k. Fiind permise maximum k interschimbări de elemente aflate pe poziții consecutive, se cere determinarea permutării minime din punct de vedere lexicografic.

Date de intrare

Fișierul gama.in conține pe prima linie numerele naturale n și k separate printr-un spațiu. Pe linia a doua se află elementele șirului dat, separate printr-un spațiu.

Date de ieșire

Fișierul gama.out conține pe primul rând n numere naturale, distincte de la 1 la n, separate prin câte un spațiu, reprezentând permutarea obținută, iar in consolă se va afișa mesajul "Datele introduse corespund cerintelor." În cazul în care datele de intrare sunt invalide programul va afișa în consolă mesajul "Datele introduse nu corespund cerintelor."

Restricţii şi precizări

  • 1 ⩽ n ⩽ 1000
  • 1 ⩽ k ⩽ n•(n-1)/2

Exemplul 1

Intrare
gama.in
0 0
0 0 0 0
Ieșire
Datele introduse nu corespund cerintelor.


Exemplul 2

Intrare
gama.in
4 2
3 2 1 4
Ieșire
Datele introduse corespund cerintelor.
gama.out
1 3 2 4


Rezolvare

<syntaxhighlight lang="python" line> import math


def read_input_file(nume):

   with open(nume + '.in', 'r') as fin:
       n, k = map(int, fin.readline().split())
       v = list(map(int, fin.readline().split()))
       return n, k, v


def write_output_file(nume, v):

   with open(nume + '.out', 'w') as fout:
       fout.write(' '.join(str(x) for x in v))


def min_element_index(v, start, end):

   minn = math.inf
   pozMin = start
   for i in range(start, end + 1):
       if v[i] < minn:
           minn = v[i]
           pozMin = i
   return pozMin


def sort_k_elements(n, k, v):

   for i in range(0, n):
       if k == 0:
           break
       pozMin = min_element_index(v, i, min(i + k, n))
       for j in range(pozMin, i, -1):
           v[j], v[j - 1] = v[j - 1], v[j]
           k -= 1


def validate_input(n, k):

   max_k = int(n * (n - 1) / 2)
   if not (1 <= n <= 1000 and 1 <= k <= max_k):
       print("Datele introduse nu corespund cerintelor.")
       exit()
   else:
       print("Datele introduse corespund cerintelor.")


if __name__ == '__main__':

   nume = "gama"
   n, k, v = read_input_file(nume)
   try:
       validate_input(n, k)
   except ValueError as e:
       print(e)
       exit(1)
   sort_k_elements(n, k, v)
   write_output_file(nume, v)

</syntaxhighlight>

Explicatie rezolvare

Acest program primește trei numere de la fișierul de intrare rotire25.in: c, x și k. C este o variabilă care indică care dintre cele două operații trebuie efectuată pe numărul x: dacă c este 1, programul trebuie să calculeze ultima cifră a lui x la puterea k, înmulțită cu prima cifră a lui x. Dacă c este 2, programul trebuie să efectueze operațiile descrise mai jos pe numărul x.

Funcția ultCifPutere este folosită pentru a calcula ultima cifră a lui x la puterea k, folosind proprietatea că ultima cifră a unui număr la puterea k este aceeași ca ultima cifră a numărului ridicat la puterea k modulo 10. Dacă ultima cifră a lui x este 0, 1, 5 sau 6, funcția întoarce acea cifră, altfel calculează ultima cifră a lui x ridicat la puterea k modulo 10.

Funcția primaCif este folosită pentru a returna prima cifră a unui număr dat x.

Funcția validate_input este folosită pentru a verifica dacă numerele date ca și input sunt valide. Verifică dacă x se află în intervalul [1, 999], dacă k se află în intervalul [1, 1000000000] și dacă c este 1 sau 2.

Funcția operatie este folosită pentru a efectua operațiile descrise în cazul în care c este 2. Înmulțește x cu inm și elimină zerourile din numărul rezultat, apoi întoarce numărul rezultat cu cifrele în ordine inversă.

La final, programul scrie rezultatul în fișierul de ieșire rotire25.out. Dacă datele de intrare sunt invalide, se scrie un mesaj de eroare în fișierul de ieșire și se afișează un mesaj corespunzător pe ecran. Dacă datele de intrare sunt valide, se scrie rezultatul în fișierul de ieșire și se afișează un mesaj corespunzător pe ecran.