3196 - Instabook - Revision history

Dragos1234: /* Explicatie rezolvare */

2023-04-14T15:00:38Z

Explicatie rezolvare

← Older revision		Revision as of 15:00, 14 April 2023
Line 107:		Line 107:

	== 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 citeste date de intrare dintr-un fisier '''instabook.in''' si apoi le valideaza prin intermediul functiei validate_input, care verifica daca n si m respecta limitele impuse de cerinta. Daca datele de intrare sunt invalide, se afiseaza un mesaj corespunzator si programul se opreste prin intermediul functiei '''exit()'''. Daca datele sunt valide, se afiseaza un mesaj corespunzator si programul continua executia.

	~~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~~.		In continuare, programul aloca cate o lista pentru a, p, ma si mi de dimensiune '''NMAX'''. Lista a retine ordinea initiala a elementelor, lista p retine pozitia curenta a fiecarui element, lista ma retine pozitia maxima pe care a fost gasit fiecare element si lista mi retine pozitia minima pe care a fost gasit fiecare element.

	~~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~~.		Urmeaza citirea efectiva a elementelor si executia operatiilor de interschimbare. Daca elementul citit nu se afla deja pe pozitia 1 (adica nu este primul element), se efectueaza interschimbarea elementelor aflate pe pozitiile p[x]-1 si p[x]. Dupa aceasta, pozitia fiecarui element modificat este actualizata in lista p, iar pozitia maxima si minima pe care a fost gasit fiecare element sunt actualizate in listele ma si mi.

			In final, programul scrie datele de iesire in fisierul '''instabook.out''' utilizand functia '''write_output'''. Aceasta parcurge toate elementele si scrie, pentru fiecare dintre ele, valorile minime si maxime ale pozitiei acestora in listele mi si ma.

Dragos1234: /* Exemplul 2 */

2023-04-14T14:59:49Z

Exemplul 2

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

Dragos1234: /* Exemplul 1 */

2023-04-14T14:59:01Z

Exemplul 1

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

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

2023-04-14T14:57:54Z

Restricţii şi precizări

← Older revision		Revision as of 14:57, 14 April 2023
Line 18:		Line 18:

	== Restricţii şi precizări ==		== Restricţii şi precizări ==
	* 1 &les; '''n''' &les; ~~1000~~		* 1 &les; '''n''' &les; 100.000
	* 1 &les; '''k''' &les; ~~n•(n-1)/2~~		* 1 &les; '''m''' &les; 200.000

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

Dragos1234: /* Date de ieșire */

2023-04-14T14:57:24Z

Date de ieșire

← Older revision		Revision as of 14:57, 14 April 2023
Line 15:		Line 15:

	== Date de ieșire ==		== 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."		Fișierul '''instabook.out''' va conține n linii: pe linia i se vor afișa separate printr-un spațiu cel mai slab loc si cel mai bun loc din clasament al pozei i, (1 ≤ i ≤ n), iar în consolă se va afișa mesajul "Datele introduse corespund cerintelor." În caz contrar programul va afisa "Datele introduse nu corespund cerintelor."

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

Dragos1234: /* Date de intrare */

2023-04-14T14:56:09Z

Date de intrare

← Older revision		Revision as of 14:56, 14 April 2023
Line 8:		Line 8:

	== Date de intrare ==		== 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~~.		Fișierul instabook.in va conține:

			* pe prima linie se află n – numărul de poze și m – numărul de like-uri.

			* pe a doua linie se află m numere naturale (1 ≤ număr ≤ n), fiecare reprezentând numărul de ordine al pozei care a primit like de la prietenul j, (1 ≤ j ≤ m).

	== Date de ieșire ==		== Date de ieșire ==

Dragos1234: /* Cerinţa */

2023-04-14T14:55:47Z

Cerinţa

← Older revision		Revision as of 14:55, 14 April 2023
Line 1:		Line 1:
	Sursa: [https://www.pbinfo.ro/probleme/3196/instabook]		Sursa: [https://www.pbinfo.ro/probleme/3196/instabook]
	== Cerinţa ==		== 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~~.		Gigel și-a făcut un nou cont pe Instabook. Imediat, a postat n poze, numerotate de la 1 la n, cu care s-a făcut un clasament în care poza 1 ocupă locul 1, poza 2 ocupă locul 2, …, poza n ocupă locul n. Fiecare dintre cei m prieteni ai lui Gigel dau like la o singură poză (prietenul i dă like la poza a[i], 1 ≤ i ≤ m).

			Clasamentul pozelor de pe Instabook funcționează în felul următor: la un like dat unei poze, aceasta urcă în clasament cu un loc, cu excepția cazului în care este deja pe primul loc.

			Gigel vrea să știe cel mai bun loc și cel mai slab loc din clasament pe care le-a ocupat fiecare poză.

	== Date de intrare ==		== Date de intrare ==

Dragos1234: /* Rezolvare */

2023-04-14T14:54:43Z

Rezolvare

@@ Line 35: / Line 35: @@
 == Rezolvare ==
 <syntaxhighlight lang="python" line>
-import math
+#3196
-def read_input_file(nume):
+def validate_input(n, m):
-     with open(nume + '.in', 'r') as fin:
+     if not (1 <= n <= 100000):
-        n, k = map(int, fin.readline().split())
+         print("Datele introduse nu corespund cerintelor.")
-         v = list(map(int, fin.readline().split()))
+         exit()
-         return n, k, v
+     if not (1 <= m <= 200000):
+        print("Datele introduse nu corespund cerintelor.")
+         exit()
-def write_output_file(nume, v):
+    print("Datele introduse corespund cerintelor.")
-     with open(nume + '.out', 'w') as fout:
-     else:
+def write_output(filename, n, ma, mi):
-         print("Datele introduse corespund cerintelor.")
+     with open(filename, "w") as fout:
-if __name__ == '__main__':
+if __name__ == "__main__":
-    nume = "gama"
+     n, ma, mi = read_input("instabook.in")
-     n, k, v = read_input_file(nume)
+     write_output("instabook.out", n, ma, mi)
 </syntaxhighlight>

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

2023-04-14T14:28:20Z

Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/3196/instabook] == 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ți...

New page

Sursa: [https://www.pbinfo.ro/probleme/3196/instabook]
== 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 &les; '''n''' &les; 1000
* 1 &les; '''k''' &les; n•(n-1)/2

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

== Exemplul 2 ==
; Intrare
: ''gama.in''
: 4 2
: 3 2 1 4
; Ieșire
: Datele introduse corespund cerintelor.
: ''gama.out''
: 1 3 2 4
<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 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ț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 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.