3357 - beta - Revision history

Flaviu at 21:03, 14 May 2023

2023-05-14T21:03:57Z

← Older revision		Revision as of 21:03, 14 May 2023
Line 34:		Line 34:
	; Ieșire		; Ieșire
	: Datele nu corespund restricțiilor impuse.		: Datele nu corespund restricțiilor impuse.
	~~: beta.out~~
	~~: -1~~


Line 60:		Line 59:
	b.extend(range(start, end+1))		b.extend(range(start, end+1))
	return b		return b

			def validate_input(n, k):
			if not (1 <= n <= 10**5 and 1 <= k <= n):
			return False
			return True

	if __name__ == '__main__':		if __name__ == '__main__':
	with open('beta.in', 'r') as f_in, open('beta.out', 'w') as f_out:		with open('beta.in', 'r') as f_in, open('beta.out', 'w') as f_out:
	n, k = map(int, f_in.readline().split())		n, k = map(int, f_in.readline().split())
	~~b = calc_b~~(n, k)		if not validate_input(n, k):
	~~if k <= len(b):~~
	~~f_out.write(f'Datele sunt introduse corect.\n{b[k-1]}\n')~~
	~~else~~:
	f_out.write('-1\n')		f_out.write('-1\n')
	print('Datele nu corespund restricțiilor impuse.')		print('Datele nu corespund restricțiilor impuse.')
			else:
			b = calc_b(n, k)
			f_out.write(f'{b[k-1]}\n')



Line 77:		Line 82:
	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==

	~~Codul începe prin citirea datelor de intrare din fișierul "beta.in". Se citesc numărul natural "~~n~~" și poziția "pos". Apoi~~, ~~se verifică dacă datele introduse sunt corecte~~, ~~adică "n" trebuie să fie o putere a lui 2~~ și ~~"pos" trebuie să fie mai mic sau egal cu numărul total de elemente din șirul "B". Dacă datele nu sunt corecte~~, ~~se scrie~~ în ~~fișierul "beta.out" valoarea -1.~~		Funcția `calc_b` primește două argumente: `n`, care este numărul dat, și `k`, care este poziția cerută în șirul `B`. Funcția începe prin construirea șirului `A`, care este un șir ordonat de la 1 la `n`. Apoi se împarte `n` la 2, apoi la 4, apoi la 8, și așa mai departe, până când nu se mai poate împărți. Se păstrează ultimele `n/p` elemente din șirul `A`, și acestea sunt adăugate la șirul `B` în ordinea cerută. Dacă `n` nu se divide exact la `p`, atunci se ia o bucată mai mică din șirul `A` și se adaugă la șirul `B` în ordinea cerută. Funcția se termină returnând șirul `B`.

	~~În caz contrar, se apelează funcția "generate_sequence" care generează~~ șirul "B". Funcția ~~primește ca parametri numărul "n" și șirul "~~A~~" format din numerele naturale~~ de la 1 la "n~~" așezate în ordine crescătoare~~.

	~~În implementarea acestei funcții~~, ~~se initializează șirul "B" cu prima jumătate a șirului "A"~~ și se ~~parcurge șirul "A" de la jumătatea sa până la sfârșitul său~~. ~~Pentru fiecare subșir de dimensiune "n/2^i" se adaugă~~ ultimele "n/~~2^i"~~ elemente din șirul "A" la ~~finalul șirului "~~B" în ordinea ~~descrisă de cerință (alternând ordinea de parcurgere de~~ la o ~~putere~~ la ~~alta)~~.

	~~În cele din urmă, se scrie~~ în ~~fișierul "beta~~.~~out" valoarea din șirul "B" de pe poziția "pos"~~.		Funcția `validate_input` primește aceiași doi parametri ca și `calc_b` și verifică dacă aceștia îndeplinesc condițiile date în enunțul problemei. Dacă nu se îndeplinesc, returnează `False`, altfel returnează `True`.

	Funcția "main~~" este apelată doar pentru a verifica corectitudinea datelor introduse~~ și ~~a afișa mesajul corespunzător~~ în fișierul "beta.out".		Funcția `main` citește datele de intrare din fișierul `beta.in`, validează datele, calculează șirul `B` folosind funcția `calc_b`, și scrie în fișierul `beta.out` numărul de pe poziția `k` din șirul `B`. Dacă datele nu sunt valide, se scrie `-1` în fișierul `beta.out` și se afișează un mesaj de eroare.

Monica Dragos: /* Date de ieșire */

2023-05-14T20:11:27Z

Date de ieșire

← Older revision		Revision as of 20:11, 14 May 2023
Line 12:		Line 12:

	Dacă datele sunt introduse corect, pe ecran se va afișa:		Dacă datele sunt introduse corect, pe ecran se va afișa:
	'''"Datele sunt introduse corect."''', apoi ~~pe un rând nou~~ ''' fișierul beta.out va conține valoarea cerută. Dacă șirul B are mai puțin de poz elemente se va scrie în fișier -1.''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.		'''"Datele sunt introduse corect."''', apoi ''' fișierul beta.out va conține valoarea cerută. Dacă șirul B are mai puțin de poz elemente se va scrie în fișier -1.''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.

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

Monica Dragos: /* Date de ieșire */

2023-05-14T20:11:07Z

Date de ieșire

← Older revision		Revision as of 20:11, 14 May 2023
Line 12:		Line 12:

	Dacă datele sunt introduse corect, pe ecran se va afișa:		Dacă datele sunt introduse corect, pe ecran se va afișa:
	'''"Datele sunt introduse corect."''', apoi pe un rând nou '''		'''"Datele sunt introduse corect."''', apoi pe un rând nou ''' fișierul beta.out va conține valoarea cerută. Dacă șirul B are mai puțin de poz elemente se va scrie în fișier -1.''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.
	va conține valoarea cerută. Dacă șirul B are mai puțin de poz elemente se va scrie în fișier -1.''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.

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

Monica Dragos: /* Date de ieșire */

2023-05-14T20:10:27Z

Date de ieșire

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

	== Date de ieșire ==		== Date de ieșire ==
	~~Fișierul beta.out conține~~
	Dacă datele sunt introduse corect, pe ecran se va afișa:		Dacă datele sunt introduse corect, pe ecran se va afișa:
	'''"Datele sunt introduse corect."''', apoi pe un rând nou ''' va conține valoarea cerută. Dacă șirul B are mai puțin de poz elemente se va scrie în fișier -1.''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.		'''"Datele sunt introduse corect."''', apoi pe un rând nou '''
			va conține valoarea cerută. Dacă șirul B are mai puțin de poz elemente se va scrie în fișier -1.''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.

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

Flaviu at 22:44, 13 May 2023

2023-05-13T22:44:48Z

← Older revision		Revision as of 22:44, 13 May 2023
Line 24:		Line 24:
	: 8 13		: 8 13
	; Ieșire		; Ieșire
			: Datele sunt introduse correct.
	: beta.out		: beta.out
	~~: Datele sunt introduse correct.~~
	: 7		: 7

Line 31:		Line 31:
	; Intrare		; Intrare
	: beta.in		: beta.in
	: ~~1 13 2 3~~		: 8 25
	; Ieșire		; Ieșire
			: Datele nu corespund restricțiilor impuse.
	: beta.out		: beta.out
	: ~~Datele nu corespund restricțiilor impuse.~~		: -1


Line 42:		Line 43:
	<syntaxhighlight lang="python" line>		<syntaxhighlight lang="python" line>
	# 3357 - beta		# 3357 - beta
	def ~~construieste_sir~~(n):		def calc_b(n, k):
	~~sir~~ = list(range(1, n + 1))		b = list(range(1, n+1))
	i = 2		p = n
	while ~~i <= n~~:		while p > 1:
	~~j = i~~ // 2		p //= 2
	k = i // ~~2 + i~~		q = n // p
	~~inc~~ = 1		r = n % p
	~~while j < k~~:		if r == 0:
	~~sir[j:k]~~ = ~~sir[k~~-1:j-1:-1~~][::inc]~~		r = p
	j = k		q -= 1
	~~k = k~~ + i		start = n - q*p + 1
	~~inc = -inc~~		end = start + r - 1
	~~i *= 2~~		if q % 2 == 1:
	return ~~sir~~		b.extend(reversed(range(start, end+1)))
			else:
			b.extend(range(start, end+1))
			return b

			if __name__ == '__main__':
			with open('beta.in', 'r') as f_in, open('beta.out', 'w') as f_out:
			n, k = map(int, f_in.readline().split())
			b = calc_b(n, k)
			if k <= len(b):
			f_out.write(f'Datele sunt introduse corect.\n{b[k-1]}\n')
			else:
			f_out.write('-1\n')
			print('Datele nu corespund restricțiilor impuse.')

	~~def determina_element(n, pozitie):~~
	~~sir = construieste_sir(n)~~
	~~return sir[pozitie - 1]~~


	~~if __name__ == "__main__":~~
	~~n, pozitie = map(int, input().split())~~
	~~if n % 2 == 0 and n == 2 ** (n.bit_length() - 1) and 1 <= pozitie <= 2 * n:~~
	~~print("Datele sunt introduse corect.")~~
	~~element = determina_element(n, pozitie)~~
	~~print(element)~~
	~~else:~~
	~~print("Datele nu corespund restricțiilor impuse.")~~

			</syntaxhighlight>
			== Explicatie Rezolvare ==

			Codul începe prin citirea datelor de intrare din fișierul "beta.in". Se citesc numărul natural "n" și poziția "pos". Apoi, se verifică dacă datele introduse sunt corecte, adică "n" trebuie să fie o putere a lui 2 și "pos" trebuie să fie mai mic sau egal cu numărul total de elemente din șirul "B". Dacă datele nu sunt corecte, se scrie în fișierul "beta.out" valoarea -1.

	~~</syntaxhighlight>~~		În caz contrar, se apelează funcția "generate_sequence" care generează șirul "B". Funcția primește ca parametri numărul "n" și șirul "A" format din numerele naturale de la 1 la "n" așezate în ordine crescătoare.
	~~== Explicatie Rezolvare ==~~

	~~Funcția construieste_sir(n) construiește~~ șirul B ~~descris în enunț și îl returnează ca o listă. Algoritmul de construcție este relativ simplu: pornim~~ cu ~~lista~~ A și ~~pe baza acesteia construim B prin concatenarea~~ la sfârșitul ~~lui A a unor subsiruri ale lui A care sunt prelucrate într-un mod specific~~. ~~Am implementat această prelucrare folosind două indici j și k care indică începutul și sfârșitul subsirului~~ din A ~~pe care îl prelucrăm și un contor inc care indică~~ ordinea de parcurgere ~~a subsirului~~.		În implementarea acestei funcții, se initializează șirul "B" cu prima jumătate a șirului "A" și se parcurge șirul "A" de la jumătatea sa până la sfârșitul său. Pentru fiecare subșir de dimensiune "n/2^i" se adaugă ultimele "n/2^i" elemente din șirul "A" la finalul șirului "B" în ordinea descrisă de cerință (alternând ordinea de parcurgere de la o putere la alta).

	~~Funcția determina_element(n~~, ~~pozitie) determină elementul~~ de pe poziția ~~dată în șirul B pentru n dat. Ea folosește funcția construieste_sir(n) pentru a construi șirul și apoi returnează elementul corespunzător poziției date~~.		În cele din urmă, se scrie în fișierul "beta.out" valoarea din șirul "B" de pe poziția "pos".

	~~În if __name__ ==~~ "~~__main__~~"~~: citim datele de intrare~~ și ~~verificăm dacă sunt corecte, conform restricțiilor din enunț. Dacă da, calculăm elementul cerut și îl afișăm împreună cu mesajul "Datele sunt introduse corect.". Dacă nu, afișăm~~ mesajul "~~Datele nu corespund restricțiilor impuse~~.".		Funcția "main" este apelată doar pentru a verifica corectitudinea datelor introduse și a afișa mesajul corespunzător în fișierul "beta.out".

Flaviu at 07:49, 3 May 2023

2023-05-03T07:49:35Z

← Older revision		Revision as of 07:49, 3 May 2023
Line 12:		Line 12:
	Fișierul beta.out conține		Fișierul beta.out conține
	Dacă datele sunt introduse corect, pe ecran se va afișa:		Dacă datele sunt introduse corect, pe ecran se va afișa:
	'''"Datele sunt introduse corect."''', apoi pe un rând nou '''~~numărul c~~''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.		'''"Datele sunt introduse corect."''', apoi pe un rând nou ''' va conține valoarea cerută. Dacă șirul B are mai puțin de poz elemente se va scrie în fișier -1.''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.

	== Restricţii şi precizări ==		== Restricţii şi precizări ==
Line 19:		Line 19:
	* 1 ≤ poz ≤ 2.000.000.000		* 1 ≤ poz ≤ 2.000.000.000
	* Pentru 55 de puncte avem n ≤ 100.000		* Pentru 55 de puncte avem n ≤ 100.000
	== Exemplu ==		== Exemplu 1 ==
	; Intrare		; Intrare
			: beta.in
	: 8 13		: 8 13
	; Ieșire		; Ieșire
	: ~~Datele nu corespund restricțiilor impuse~~.		: beta.out
	: Datele sunt introduse correct.		: Datele sunt introduse correct.
	: 7		: 7

			== Exemplu 2 ==
			; Intrare
			: beta.in
			: 1 13 2 3
			; Ieșire
			: beta.out
			: Datele nu corespund restricțiilor impuse.



	== Rezolvare ==		== Rezolvare ==

Flaviu at 14:19, 28 April 2023

2023-04-28T14:19:34Z

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

	== Date de ieșire ==		== Date de ieșire ==
	Fișierul beta.out conține valoarea cerută. ~~Dacă șirul B are mai puțin de poz elemente~~ se va ~~scrie în fișier -1~~.		Fișierul beta.out conține
			Dacă datele sunt introduse corect, pe ecran se va afișa:
			'''"Datele sunt introduse corect."''', apoi pe un rând nou '''numărul c''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.

	== Restricţii şi precizări ==		== Restricţii şi precizări ==
Line 21:		Line 23:
	: 8 13		: 8 13
	; Ieșire		; Ieșire
			: Datele nu corespund restricțiilor impuse.
			: Datele sunt introduse correct.
	: 7		: 7

Line 27:		Line 31:
	<syntaxhighlight lang="python" line>		<syntaxhighlight lang="python" line>
	# 3357 - beta		# 3357 - beta
	def ~~generate_B~~(n):		def construieste_sir(n):
	B = list(range(1, n+1)) ~~# cream o lista cu elementele initiale din A~~		sir = list(range(1, n + 1))
	~~for p in range(1,~~ n~~.bit_length())~~: ~~# parcurgem puterile de~~ 2 ~~de la 1 la log2(n)~~		i = 2
	~~last_n_p~~ = ~~B[-n~~//2**p:] # luam ultimele n/p elemente din A		while i <= n:
	~~if p % 2 =~~= 1: ~~# daca puterea este impara, le adaugam in ordine inversa~~		j = i // 2
	~~B +~~= ~~last_n_p~~[::-1]		k = i // 2 + i
	~~else: # daca puterea este para, le adaugam in ordine crescatoare~~		inc = 1
	B += ~~last_n_p~~		while j < k:
	return B		sir[j:k] = sir[k-1:j-1:-1][::inc]
			j = k
			k = k + i
			inc = -inc
			i *= 2
			return sir

	~~def validate_input(n, poz):~~
	~~if poz <= 0 or poz > n*2:~~
	~~print("-1") # afisam -1 daca pozitia este invalida~~
	~~exit()~~

	def ~~solve~~(n, ~~poz~~):		def determina_element(n, pozitie):
	B = ~~generate_B~~(n)		sir = construieste_sir(n)
	~~validate_input(len(B), poz~~)		return sir[pozitie - 1]
	return B[~~poz~~-1] ~~# returnam elementul de pe pozitia ceruta (indexarea incepe de la 0)~~

	if __name__ == "__main__":		if __name__ == "__main__":
	n, ~~poz~~ = map(int, input().split())		n, pozitie = map(int, input().split())
	print(~~solve~~(n, ~~poz~~))		if n % 2 == 0 and n == 2 ** (n.bit_length() - 1) and 1 <= pozitie <= 2 * n:
			print("Datele sunt introduse corect.")
			element = determina_element(n, pozitie)
			print(element)
			else:
			print("Datele nu corespund restricțiilor impuse.")



	</syntaxhighlight>		</syntaxhighlight>
	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==
	Funcția generate_B(n) generează șirul B conform algoritmului descris în cerință. Folosim metoda bit_length() pentru a determina numărul de puteri de 2 (adica p) necesare pentru a completa șirul B. Apoi, pentru fiecare putere de 2, luăm ultimele n/p elemente din A și le adăugăm la finalul lui B în funcție de paritatea lui p.

	Funcția ~~validate_input~~(n~~, poz~~) ~~verifică dacă poziția dată~~ este ~~validă~~ și ~~afișează~~ -~~1 dacă nu este~~.		Funcția construieste_sir(n) construiește șirul B descris în enunț și îl returnează ca o listă. Algoritmul de construcție este relativ simplu: pornim cu lista A și pe baza acesteia construim B prin concatenarea la sfârșitul lui A a unor subsiruri ale lui A care sunt prelucrate într-un mod specific. Am implementat această prelucrare folosind două indici j și k care indică începutul și sfârșitul subsirului din A pe care îl prelucrăm și un contor inc care indică ordinea de parcurgere a subsirului.

	Funcția ~~solve~~(n, ~~poz~~) ~~este funcția principală care apelează celelalte două funcții și returnează~~ elementul de pe poziția dată.		Funcția determina_element(n, pozitie) determină elementul de pe poziția dată în șirul B pentru n dat. Ea folosește funcția construieste_sir(n) pentru a construi șirul și apoi returnează elementul corespunzător poziției date.

	În ~~blocul~~ if __name__ == "__main__": citim datele de intrare și ~~apelăm funcția solve()~~, ~~apoi~~ afișăm ~~rezultatul~~.		În if __name__ == "__main__": citim datele de intrare și verificăm dacă sunt corecte, conform restricțiilor din enunț. Dacă da, calculăm elementul cerut și îl afișăm împreună cu mesajul "Datele sunt introduse corect.". Dacă nu, afișăm mesajul "Datele nu corespund restricțiilor impuse.".

Flaviu: Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/3357/beta3357 - beta] ---- == Cerinţa == Se dă un număr natural n despre care se cunoaște că este putere de 2. Considerăm inițial șirul numerelor naturale de la 1 la n așezate în ordine crescătoare. Notăm cu A acest șir. Pornind de la acesta, se construiește un nou șir (să îl notăm cu B) astfel: Primele n elemente ale lui B sunt chiar elementele șirului A în aceeași ordine. Următoarele n/2 elemente ale lui B sunt ul...

2023-04-17T20:34:55Z

Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/3357/beta3357 - beta] ---- == Cerinţa == Se dă un număr natural n despre care se cunoaște că este putere de 2. Considerăm inițial șirul numerelor naturale de la 1 la n așezate în ordine crescătoare. Notăm cu A acest șir. Pornind de la acesta, se construiește un nou șir (să îl notăm cu B) astfel: Primele n elemente ale lui B sunt chiar elementele șirului A în aceeași ordine. Următoarele n/2 elemente ale lui B sunt ul...

New page

Sursa: [https://www.pbinfo.ro/probleme/3357/beta3357 - beta]
----
== Cerinţa ==
Se dă un număr natural n despre care se cunoaște că este putere de 2. Considerăm inițial șirul numerelor naturale de la 1 la n așezate în ordine crescătoare. Notăm cu A acest șir. Pornind de la acesta, se construiește un nou șir (să îl notăm cu B) astfel: Primele n elemente ale lui B sunt chiar elementele șirului A în aceeași ordine. Următoarele n/2 elemente ale lui B sunt ultimele n/2 elemente ale lui A dar scrise în ordine inversă (descrescător). Următoarele n/4 elemente ale lui B sunt ultimele n/4 elemente ale lui A scrise în ordine crescătoare, următoarele n/8 elemente ale lui B sunt ultimele n/8 elemente ale lui A scrise în ordine descrescătoare, și tot așa, cu fiecare putere de 2 (notată p) ce apare la numitor, luăm ultimele n/p elemente din A și le adăugăm la finalul lui B alternând ordinea de parcurgere, de la o putere la alta conform modului descris mai sus. Se mai să un număr poz. Se cere determinarea numărului de pe poziția poz din șirul B.

== Date de intrare ==
Fișierul beta.in conține pe prima linie numerele naturale n și poz separate printr-un spațiu.

== Date de ieșire ==
Fișierul beta.out conține valoarea cerută. Dacă șirul B are mai puțin de poz elemente se va scrie în fișier -1.

== Restricţii şi precizări ==
* 1 ≤ n ≤ 1.000.000.000
* n se dă putere de 2
* 1 ≤ poz ≤ 2.000.000.000
* Pentru 55 de puncte avem n ≤ 100.000
== Exemplu ==
; Intrare
: 8 13
; Ieșire
: 7

== Rezolvare ==
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 3357 - beta
def generate_B(n):
B = list(range(1, n+1)) # cream o lista cu elementele initiale din A
for p in range(1, n.bit_length()): # parcurgem puterile de 2 de la 1 la log2(n)
last_n_p = B[-n//2**p:] # luam ultimele n/p elemente din A
if p % 2 == 1: # daca puterea este impara, le adaugam in ordine inversa
B += last_n_p[::-1]
else: # daca puterea este para, le adaugam in ordine crescatoare
B += last_n_p
return B

def validate_input(n, poz):
if poz <= 0 or poz > n*2:
print("-1") # afisam -1 daca pozitia este invalida
exit()

def solve(n, poz):
B = generate_B(n)
validate_input(len(B), poz)
return B[poz-1] # returnam elementul de pe pozitia ceruta (indexarea incepe de la 0)

if __name__ == "__main__":
n, poz = map(int, input().split())
print(solve(n, poz))

</syntaxhighlight>
== Explicatie Rezolvare ==
Funcția generate_B(n) generează șirul B conform algoritmului descris în cerință. Folosim metoda bit_length() pentru a determina numărul de puteri de 2 (adica p) necesare pentru a completa șirul B. Apoi, pentru fiecare putere de 2, luăm ultimele n/p elemente din A și le adăugăm la finalul lui B în funcție de paritatea lui p.

Funcția validate_input(n, poz) verifică dacă poziția dată este validă și afișează -1 dacă nu este.

Funcția solve(n, poz) este funcția principală care apelează celelalte două funcții și returnează elementul de pe poziția dată.

În blocul if __name__ == "__main__": citim datele de intrare și apelăm funcția solve(), apoi afișăm rezultatul.