3358 - gama - Revision history

Dragos1234: /* Explicatie rezolvare */

2023-04-14T17:03:10Z

Explicatie rezolvare

← Older revision		Revision as of 17:03, 14 April 2023
Line 96:		Line 96:
	Acest program sortează primele k elemente ale unui vector de dimensiune n.		Acest program sortează primele k elemente ale unui vector de dimensiune n.

	Funcția read_input_file(nume) citește datele de intrare din fișierul cu numele nume.in. Prima linie din fișier conține două numere întregi separate prin spațiu, n și k. A doua linie conține n numere întregi separate prin spațiu, care reprezintă elementele vectorului. Funcția returnează dimensiunea vectorului n, numărul k și vectorul v.		Funcția '''read_input_file(nume)''' citește datele de intrare din fișierul cu numele nume.in. Prima linie din fișier conține două numere întregi separate prin spațiu, n și k. A doua linie conține n numere întregi separate prin spațiu, care reprezintă elementele vectorului. Funcția returnează dimensiunea vectorului n, numărul k și vectorul v.

	Funcția '''write_output_file(nume, v)''' scrie vectorul sortat în fișierul cu numele nume.out.		Funcția '''write_output_file(nume, v)''' scrie vectorul sortat în fișierul cu numele nume.out.

	Funcția min_element_index(v, start, end) primește un vector v și intervalul de indexi start și end și returnează indexul elementului minim din acest interval.		Funcția '''min_element_index(v, start, end)''' primește un vector v și intervalul de indexi start și end și returnează indexul elementului minim din acest interval.

	Funcția sort_k_elements(n, k, v) sortează primele k elemente ale vectorului v de dimensiune n. Sortarea se face prin găsirea elementului minim dintr-un interval și interschimbarea acestuia cu primul element din interval, apoi cu următorul element și tot așa, până când primele k elemente sunt sortate.		Funcția '''sort_k_elements(n, k, v)''' sortează primele k elemente ale vectorului v de dimensiune n. Sortarea se face prin găsirea elementului minim dintr-un interval și interschimbarea acestuia cu primul element din interval, apoi cu următorul element și tot așa, până când primele k elemente sunt sortate.

	Funcția validate_input(n, k) verifică dacă dimensiunile vectorului și numărul k sunt în limitele cerute. Dacă nu sunt, afișează un mesaj de eroare și oprește programul.		Funcția '''validate_input(n, k)''' verifică dacă dimensiunile vectorului și numărul k sunt în limitele cerute. Dacă nu sunt, afișează un mesaj de eroare și oprește programul.

	În funcția principală __main__, se specifică numele fișierului de intrare, se citește intrarea, se validează datele de intrare, se sortează primele k elemente și se scrie rezultatul în fișierul de ieșire.		În funcția principală''' __main__''', se specifică numele fișierului de intrare, se citește intrarea, se validează datele de intrare, se sortează primele k elemente și se scrie rezultatul în fișierul de ieșire.

Dragos1234: /* Explicatie rezolvare */

2023-04-14T17:02:34Z

Explicatie rezolvare

← Older revision		Revision as of 17:02, 14 April 2023
Line 94:		Line 94:

	== Explicatie rezolvare ==		== Explicatie rezolvare ==
	Acest program ~~primește ca date de intrare un număr întreg n, un număr întreg k și o listă v de n numere întregi și~~ sortează ~~primii~~ k elemente ~~ai listei v în ordine crescătoare, folosind o implementare a algoritmului~~ de ~~sortare prin selecție~~.		Acest program sortează primele k elemente ale unui vector de dimensiune n.

	~~Funcțiile '''~~read_input_file~~''' și '''write_output_file''' se ocupă de citirea datelor~~ de intrare din fișierul cu ~~extensia "~~.in" și ~~scrierea datelor de ieșire în fișierul cu extensia "~~.~~out"~~. Funcția ~~min_element_index~~ returnează ~~indexul elementului minim dintr-un interval specificat~~, ~~iar funcția '''sort_k_elements''' sortează primii~~ k ~~elemente ai listei~~ v.		Funcția read_input_file(nume) citește datele de intrare din fișierul cu numele nume.in. Prima linie din fișier conține două numere întregi separate prin spațiu, n și k. A doua linie conține n numere întregi separate prin spațiu, care reprezintă elementele vectorului. Funcția returnează dimensiunea vectorului n, numărul k și vectorul v.

	Funcția ~~validate_input verifică dacă datele~~ de ~~intrare corespund cerințelor~~. ~~Dacă valorile~~ n și k ~~nu sunt între 1~~ și ~~1000~~, ~~respectiv 1~~ și n(n-1)/2, ~~funcția~~ afișează un mesaj ~~corespunzător~~ și programul ~~se încheie~~. În ~~caz contrar~~, ~~funcția afișează un mesaj corespunzător~~ și ~~programul continuă cu sortarea listei v~~.		Funcția '''write_output_file(nume, v)''' scrie vectorul sortat în fișierul cu numele nume.out.

			Funcția min_element_index(v, start, end) primește un vector v și intervalul de indexi start și end și returnează indexul elementului minim din acest interval.

			Funcția sort_k_elements(n, k, v) sortează primele k elemente ale vectorului v de dimensiune n. Sortarea se face prin găsirea elementului minim dintr-un interval și interschimbarea acestuia cu primul element din interval, apoi cu următorul element și tot așa, până când primele k elemente sunt sortate.

			Funcția validate_input(n, k) verifică dacă dimensiunile vectorului și numărul k sunt în limitele cerute. Dacă nu sunt, afișează un mesaj de eroare și oprește programul.

			În funcția principală __main__, se specifică numele fișierului de intrare, se citește intrarea, se validează datele de intrare, se sortează primele k elemente și se scrie rezultatul în fișierul de ieșire.

Dragos1234: /* Explicatie rezolvare */

2023-04-14T14:23:45Z

Explicatie rezolvare

← Older revision		Revision as of 14:23, 14 April 2023
Line 94:		Line 94:

	== Explicatie rezolvare ==		== 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~~.		Acest program primește ca date de intrare un număr întreg n, un număr întreg k și o listă v de n numere întregi și sortează primii k elemente ai listei v în ordine crescătoare, folosind o implementare a algoritmului de sortare prin selecție.

	~~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țiile '''read_input_file''' și '''write_output_file''' se ocupă de citirea datelor de intrare din fișierul cu extensia ".in" și scrierea datelor de ieșire în fișierul cu extensia ".out". Funcția min_element_index returnează indexul elementului minim dintr-un interval specificat, iar funcția '''sort_k_elements''' sortează primii k elemente ai listei v.

	Funcția ~~'''primaCif''' este folosită pentru a returna prima cifră a unui număr dat x.~~		Funcția validate_input verifică dacă datele de intrare corespund cerințelor. Dacă valorile n și k nu sunt între 1 și 1000, respectiv 1 și n(n-1)/2, funcția afișează un mesaj corespunzător și programul se încheie. În caz contrar, funcția afișează un mesaj corespunzător și programul continuă cu sortarea listei v.

	~~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~~.

Dragos1234: /* Date de ieșire */

2023-04-14T14:21:52Z

Date de ieșire

← Older revision		Revision as of 14:21, 14 April 2023
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 ==

Dragos1234: /* Restricţii şi precizări */

2023-04-14T14:20:11Z

Restricţii şi precizări

← Older revision		Revision as of 14:20, 14 April 2023
Line 10:		Line 10:

	== Restricţii şi precizări ==		== Restricţii şi precizări ==
	* 1 &les; '''X''' &les; ~~999~~		* 1 &les; '''n''' &les; 1000
	* 1 &les; '''K''' &les; 1~~.000.000.000~~		* 1 &les; '''k''' &les; n•(n-1)/2
	* Pentru teste în valoare de 29 de puncte, C = 1.
	* Pentru teste în valoare de 71 de puncte, C = 2.

	== Exemplul 1 ==		== Exemplul 1 ==

Dragos1234: /* Exemplul 2 */

2023-04-14T14:19:03Z

Exemplul 2

← Older revision		Revision as of 14:19, 14 April 2023
Line 26:		Line 26:
	== Exemplul 2 ==		== Exemplul 2 ==
	; Intrare		; Intrare
	: ''~~rotire25~~.in''		: ''gama.in''
	: ~~0 0 0~~		: 4 2
			: 3 2 1 4
	; Ieșire		; Ieșire
	: Datele introduse nu corespund cerintelor.		: Datele introduse corespund cerintelor.
			: ''gama.out''
			: 1 3 2 4
	<br>		<br>

Dragos1234: /* Exemplul 1 */

2023-04-14T14:17:39Z

Exemplul 1

← Older revision		Revision as of 14:17, 14 April 2023
Line 17:		Line 17:
	== Exemplul 1 ==		== Exemplul 1 ==
	; Intrare		; Intrare
	: ''~~rotire25~~.in''		: ''gama.in''
	: ~~1 27 3~~		: 0 0
			: 0 0 0 0
	; Ieșire		; Ieșire
	: Datele introduse corespund cerintelor.		: Datele introduse nu corespund cerintelor.
	~~: ''rotire25.out''~~
	~~: 6~~
	<br>		<br>

Dragos1234: Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/3358/gama] == 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...

2023-04-14T14:16:41Z

Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/3358/gama] == 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...

New page

Sursa: [https://www.pbinfo.ro/probleme/3358/gama]
== 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 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."

== Restricţii şi precizări ==
* 1 &les; '''X''' &les; 999
* 1 &les; '''K''' &les; 1.000.000.000
* Pentru teste în valoare de 29 de puncte, C = 1.
* Pentru teste în valoare de 71 de puncte, C = 2.

== Exemplul 1 ==
; Intrare
: ''rotire25.in''
: 1 27 3
; Ieșire
: Datele introduse corespund cerintelor.
: ''rotire25.out''
: 6
<br>

== Exemplul 2 ==
; Intrare
: ''rotire25.in''
: 0 0 0
; Ieșire
: Datele introduse nu corespund cerintelor.
<br>

== 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.