1225 - Sort 2 Dist - Revision history

Oros Ioana Diana at 17:10, 18 May 2024

2024-05-18T17:10:17Z

Oros Ioana Diana at 17:20, 8 January 2024

2024-01-08T17:20:10Z

← Older revision		Revision as of 17:20, 8 January 2024
Line 11:		Line 11:
	*pe următoarele N linii, N numere, reprezentând, în această ordine, identificatorii aflați în căsuțele tabletei (identificatorul de pe linia i se află în căsuța i-1).		*pe următoarele N linii, N numere, reprezentând, în această ordine, identificatorii aflați în căsuțele tabletei (identificatorul de pe linia i se află în căsuța i-1).
	== Date de ieșire ==		== Date de ieșire ==
	Fișierul de ieșire ~~sort2dist~~.~~out~~ va conține:		Fișierul de ieșire sort2distout.txt va conține:
	*pe prima linie un număr natural M, reprezentând numărul de interschimbări realizate de Robo (nu neapărat numărul minim de interschimbări necesare);		*pe prima linie un număr natural M, reprezentând numărul de interschimbări realizate de Robo (nu neapărat numărul minim de interschimbări necesare);
	*pe fiecare dintre următoarele M linii (doar dacă M este nenul), câte două numere naturale, separate prin câte un spațiu, reprezentând etichetele căsuțelor al căror conținut s-a interschimbat, în ordinea realizării acestor interschimbări.		*pe fiecare dintre următoarele M linii (doar dacă M este nenul), câte două numere naturale, separate prin câte un spațiu, reprezentând etichetele căsuțelor al căror conținut s-a interschimbat, în ordinea realizării acestor interschimbări.

Oros Ioana Diana at 17:19, 8 January 2024

2024-01-08T17:19:50Z

← Older revision		Revision as of 17:19, 8 January 2024
Line 4:		Line 4:

	El își poate fixa în orice moment distanța dintre brațe la 1 sau își poate dubla distanța curentă dintre brațe, de oricâte ori este necesar, fără a depăși valoarea N-1. Astfel, distanța dintre brațele sale poate fi 1, apoi, prin dublare, 2, apoi, prin dublare 4, apoi, prin dublare 8 etc. La începutul jocului, distanța dintre brațele lui Robo este 1. De fiecare dată când consideră convenabilă distanța dintre brațe, realizează o interschimbare.		El își poate fixa în orice moment distanța dintre brațe la 1 sau își poate dubla distanța curentă dintre brațe, de oricâte ori este necesar, fără a depăși valoarea N-1. Astfel, distanța dintre brațele sale poate fi 1, apoi, prin dublare, 2, apoi, prin dublare 4, apoi, prin dublare 8 etc. La începutul jocului, distanța dintre brațele lui Robo este 1. De fiecare dată când consideră convenabilă distanța dintre brațe, realizează o interschimbare.

	~~Cerința~~
	== Cerința ==		== Cerința ==
	Se cere ca Robo să așeze identificatorii în căsuțe în ordine crescătoare, prin maximum 12500 interschimbări de tipul celei precizate mai sus.		Se cere ca Robo să așeze identificatorii în căsuțe în ordine crescătoare, prin maximum 12500 interschimbări de tipul celei precizate mai sus.
	== Date de intrare ==		== Date de intrare ==
	Fișierul de intrare ~~sort2dist~~.in conține:		Fișierul de intrare sort2distin.txt conține:
	~~<br>~~		*pe prima linie numărul natural N, cu semnificația din enunț;
	~ pe prima linie numărul natural N, cu semnificația din enunț;		*pe următoarele N linii, N numere, reprezentând, în această ordine, identificatorii aflați în căsuțele tabletei (identificatorul de pe linia i se află în căsuța i-1).
	~~<br>~~
	~ pe următoarele N linii, N numere, reprezentând, în această ordine, identificatorii aflați în căsuțele tabletei (identificatorul de pe linia i se află în căsuța i-1).
	== Date de ieșire ==		== Date de ieșire ==
	Fișierul de ieșire sort2dist.out va conține:		Fișierul de ieșire sort2dist.out va conține:
	~~<br>~~		*pe prima linie un număr natural M, reprezentând numărul de interschimbări realizate de Robo (nu neapărat numărul minim de interschimbări necesare);
	~pe prima linie un număr natural M, reprezentând numărul de interschimbări realizate de Robo (nu neapărat numărul minim de interschimbări necesare);		*pe fiecare dintre următoarele M linii (doar dacă M este nenul), câte două numere naturale, separate prin câte un spațiu, reprezentând etichetele căsuțelor al căror conținut s-a interschimbat, în ordinea realizării acestor interschimbări.
	~~<br>~~
	~pe fiecare dintre următoarele M linii (doar dacă M este nenul), câte două numere naturale, separate prin câte un spațiu, reprezentând etichetele căsuțelor al căror conținut s-a interschimbat, în ordinea realizării acestor interschimbări.
	== Restricții și precizări ==		== Restricții și precizări ==
	~ 1 ≤ N ≤ 1000;\		*1 ≤ N ≤ 1000;\
	~~<br>~~		*identificatorii sunt numere naturale de maximum 30 de cifre;
	~ identificatorii sunt numere naturale de maximum 30 de cifre;		*pentru 25% din punctaj, fișierele de test conțin numere cu maximum 18 cifre;
	~~<br>~~		*pentru 25% din punctaj, N ≤ 100.
	~ pentru 25% din punctaj, fișierele de test conțin numere cu maximum 18 cifre;		== Exemplul 1 ==
	~~<br>~~		; sort2distin.txt
	~ pentru 25% din punctaj, N ≤ 100.
	== ~~Exemplu~~ 1 ==
	; ~~Intrare~~
	~~: sort2dist~~.in
	:4		:4
	:5		:5
Line 36:		Line 26:
	:6		:6
	:2		:2
	; ~~Ieșire~~		; sort2distout.txt
	~~: sort2dist~~.~~out~~
	:2		:2
	:2 4		:2 4
	:2 1		:2 1
	<br>		<br>
	== ~~Exemplu~~ 2 ==		== Exemplul 2 ==
	; ~~Intrare~~		; sort2distin.txt
	~~: sort2dist~~.in
	:2		:2
	:5		:5
Line 50:		Line 38:
	:3		:3
	:7		:7
	; ~~Ieșire~~		; sort2distout.txt
	~~: sort2dist~~.~~out~~
	:2 3		:2 3
	:4 2 2		:4 2 2
Line 71:		Line 58:

	return interschimbari		return interschimbari

			def verificare_restrictii(N): # funcția de verificare a datelor de intrare
			if 1 <= N <= 1000: # adăugăm restricția pentru n
			return True
			else:
			return False


	def main():		def main():
	with open("~~sort2dist~~.in", "r") as file_in:		with open("sort2distin.txt", "r") as file_in:
	N = int(file_in.readline())		N = int(file_in.readline())
	identificatori = [int(file_in.readline()) for _ in range(N)]		identificatori = [int(file_in.readline()) for _ in range(N)]
Line 79:		Line 73:
	interschimbari = sortare_distanta_minima(N, identificatori)		interschimbari = sortare_distanta_minima(N, identificatori)

	with open("~~sort2dist~~.~~out~~", "w") as file_out:		with open("sort2distout.txt", "w") as file_out:
	file_out.write(str(len(interschimbari)) + "\n")		file_out.write(str(len(interschimbari)) + "\n")
	for interschimbare in interschimbari:		for interschimbare in interschimbari:

Oros Ioana Diana at 17:15, 8 January 2024

2024-01-08T17:15:59Z

← Older revision		Revision as of 17:15, 8 January 2024
Line 1:		Line 1:
			Jocul pe care îl joaca Robo atunci când se plictisește este un joc inteligent pentru roboței. Pe ecranul tabletei lui roboțești, sunt N căsuțe de formă pătrată, cu latura egală cu 1. Căsuțele sunt așezate pe un rând, una lângă alta, fiind etichetate, în această ordine, cu numere de la 1 la N. Fiecare căsuță conține câte un număr natural, identificatorul câte unuia dintre prietenii săi, roboței, ca și el. Identificatorii se pot repeta.

			Robo poate interschimba conținutul a două căsuțe, numai dacă distanța dintre centrele acestora pe orizontală este egală cu distanța dintre brațele sale; distanța, pe orizontală, dintre centrele a două căsuțe etichetate cu i, respectiv cu j, este j-i (1≤i<j≤N).

			El își poate fixa în orice moment distanța dintre brațe la 1 sau își poate dubla distanța curentă dintre brațe, de oricâte ori este necesar, fără a depăși valoarea N-1. Astfel, distanța dintre brațele sale poate fi 1, apoi, prin dublare, 2, apoi, prin dublare 4, apoi, prin dublare 8 etc. La începutul jocului, distanța dintre brațele lui Robo este 1. De fiecare dată când consideră convenabilă distanța dintre brațe, realizează o interschimbare.

			Cerința
	== Cerința ==		== Cerința ==
	Se cere ca Robo să așeze identificatorii în căsuțe în ordine crescătoare, prin maximum 12500 interschimbări de tipul celei precizate mai sus.		Se cere ca Robo să așeze identificatorii în căsuțe în ordine crescătoare, prin maximum 12500 interschimbări de tipul celei precizate mai sus.

Oros Ioana Diana: Pagină nouă: == Cerința == Se cere ca Robo să așeze identificatorii în căsuțe în ordine crescătoare, prin maximum 12500 interschimbări de tipul celei precizate mai sus. == Date de intrare == Fișierul de intrare sort2dist.in conține:
~ pe prima linie numărul natural N, cu semnificația din enunț;
~ pe următoarele N linii, N numere, reprezentând, în această ordine, identificatorii aflați în căsuțele tabletei (identificatorul de pe linia i se află în căsuța...

2023-12-12T18:37:31Z

Pagină nouă: == Cerința == Se cere ca Robo să așeze identificatorii în căsuțe în ordine crescătoare, prin maximum 12500 interschimbări de tipul celei precizate mai sus. == Date de intrare == Fișierul de intrare sort2dist.in conține: ~ pe prima linie numărul natural N, cu semnificația din enunț; ~ pe următoarele N linii, N numere, reprezentând, în această ordine, identificatorii aflați în căsuțele tabletei (identificatorul de pe linia i se află în căsuța...

New page

== Cerința ==
Se cere ca Robo să așeze identificatorii în căsuțe în ordine crescătoare, prin maximum 12500 interschimbări de tipul celei precizate mai sus.
== Date de intrare ==
Fișierul de intrare sort2dist.in conține:
 
~ pe prima linie numărul natural N, cu semnificația din enunț;
 
~ pe următoarele N linii, N numere, reprezentând, în această ordine, identificatorii aflați în căsuțele tabletei (identificatorul de pe linia i se află în căsuța i-1).
== Date de ieșire ==
Fișierul de ieșire sort2dist.out va conține:
 
~pe prima linie un număr natural M, reprezentând numărul de interschimbări realizate de Robo (nu neapărat numărul minim de interschimbări necesare);
 
~pe fiecare dintre următoarele M linii (doar dacă M este nenul), câte două numere naturale, separate prin câte un spațiu, reprezentând etichetele căsuțelor al căror conținut s-a interschimbat, în ordinea realizării acestor interschimbări.
== Restricții și precizări ==
~ 1 ≤ N ≤ 1000;\
 
~ identificatorii sunt numere naturale de maximum 30 de cifre;
 
~ pentru 25% din punctaj, fișierele de test conțin numere cu maximum 18 cifre;
 
~ pentru 25% din punctaj, N ≤ 100.
== Exemplu 1 ==
; Intrare
: sort2dist.in
:4
:5
:7
:6
:2
; Ieșire
: sort2dist.out
:2
:2 4
:2 1
 
== Exemplu 2 ==
; Intrare
: sort2dist.in
:2
:5
:6
:3
:7
; Ieșire
: sort2dist.out
:2 3
:4 2 2
 
== Rezolvare ==
<syntaxhighlight lang="python" line>
#1225 - Sort 2 Dist
def sortare_distanta_minima(N, identificatori):
interschimbari = []

distanta_brate = 1
while distanta_brate <= N - 1:
for i in range(0, N - distanta_brate, distanta_brate * 2):
if identificatori[i] > identificatori[i + distanta_brate]:
interschimbari.append((i + 1, i + distanta_brate + 1))
identificatori[i], identificatori[i + distanta_brate] = identificatori[i + distanta_brate], identificatori[i]

distanta_brate *= 2

return interschimbari

def main():
with open("sort2dist.in", "r") as file_in:
N = int(file_in.readline())
identificatori = [int(file_in.readline()) for _ in range(N)]

interschimbari = sortare_distanta_minima(N, identificatori)

with open("sort2dist.out", "w") as file_out:
file_out.write(str(len(interschimbari)) + "\n")
for interschimbare in interschimbari:
file_out.write(f"{interschimbare[0]} {interschimbare[1]}\n")

if __name__ == "__main__":
main()
</syntaxhighlight>