2553 - Josephus - Revision history

Cata at 14:33, 14 May 2023

2023-05-14T14:33:06Z

← Older revision		Revision as of 14:33, 14 May 2023
Line 1:		Line 1:
			==Cerința==
	Aceasta este o problemă foarte cunoscută atât în universul informatic, cât și în cel matematic!		Aceasta este o problemă foarte cunoscută atât în universul informatic, cât și în cel matematic!

	~~==Cerința==~~
	Legenda ne povestește că Josephus și alți n-1 soldați evrei se luptau cu trupele romane. Din nefericire pentru aceștia, au ajuns foarte curând încercuiți și doborâți numeric. Ei se hotărăsc rapid să nu se predea, dar nici să nu își ia de unii singuri viața și astfel le vine următoarea idee: se așează cu toții într-un cerc și își scriu pe rând pe frunte câte un număr, reprezentând indicativul fiecăruia (1, 2, …, n). Soldații decid ca soldatul cu numărul 1 să îl trimită în rai pe soldatul încă în viață din stânga sa (notat, în acest context, cu numărul 2), apoi următorul soldat în viață să repete aceeași acțiune până când nu va mai rămâne decât o singură persoană în viață.		Legenda ne povestește că Josephus și alți n-1 soldați evrei se luptau cu trupele romane. Din nefericire pentru aceștia, au ajuns foarte curând încercuiți și doborâți numeric. Ei se hotărăsc rapid să nu se predea, dar nici să nu își ia de unii singuri viața și astfel le vine următoarea idee: se așează cu toții într-un cerc și își scriu pe rând pe frunte câte un număr, reprezentând indicativul fiecăruia (1, 2, …, n). Soldații decid ca soldatul cu numărul 1 să îl trimită în rai pe soldatul încă în viață din stânga sa (notat, în acest context, cu numărul 2), apoi următorul soldat în viață să repete aceeași acțiune până când nu va mai rămâne decât o singură persoană în viață.

Cata: /* Exemplu */

2023-05-03T06:36:41Z

Exemplu

← Older revision		Revision as of 06:36, 3 May 2023
Line 19:		Line 19:
	: 41		: 41
	; Ieșire		; Ieșire
	: ~~Valid input~~		: Input valid
	: 19		: 19
	==Explicație==		==Explicație==

Cata at 06:30, 3 May 2023

2023-05-03T06:30:43Z

← Older revision		Revision as of 06:30, 3 May 2023
Line 1:		Line 1:
	Aceasta este o problemă foarte cunoscută atât în universul informatic, cât și în cel matematic!		Aceasta este o problemă foarte cunoscută atât în universul informatic, cât și în cel matematic!

			==Cerința==
	Legenda ne povestește că Josephus și alți n-1 soldați evrei se luptau cu trupele romane. Din nefericire pentru aceștia, au ajuns foarte curând încercuiți și doborâți numeric. Ei se hotărăsc rapid să nu se predea, dar nici să nu își ia de unii singuri viața și astfel le vine următoarea idee: se așează cu toții într-un cerc și își scriu pe rând pe frunte câte un număr, reprezentând indicativul fiecăruia (1, 2, …, n). Soldații decid ca soldatul cu numărul 1 să îl trimită în rai pe soldatul încă în viață din stânga sa (notat, în acest context, cu numărul 2), apoi următorul soldat în viață să repete aceeași acțiune până când nu va mai rămâne decât o singură persoană în viață.		Legenda ne povestește că Josephus și alți n-1 soldați evrei se luptau cu trupele romane. Din nefericire pentru aceștia, au ajuns foarte curând încercuiți și doborâți numeric. Ei se hotărăsc rapid să nu se predea, dar nici să nu își ia de unii singuri viața și astfel le vine următoarea idee: se așează cu toții într-un cerc și își scriu pe rând pe frunte câte un număr, reprezentând indicativul fiecăruia (1, 2, …, n). Soldații decid ca soldatul cu numărul 1 să îl trimită în rai pe soldatul încă în viață din stânga sa (notat, în acest context, cu numărul 2), apoi următorul soldat în viață să repete aceeași acțiune până când nu va mai rămâne decât o singură persoană în viață.

	~~==Cerința==~~
	Josephus ar fi preferat să se predea. Pe ce poziție ar fi trebuit să se afle soldatul pentru a putea realiza acest lucru?		Josephus ar fi preferat să se predea. Pe ce poziție ar fi trebuit să se afle soldatul pentru a putea realiza acest lucru?

Line 10:		Line 10:

	==Date de ieșire==		==Date de ieșire==
	Se va afișa un singur număr ce reprezintă poziția pe care Josephus trebuia să se afle pentru a rămâne în viață, alături de un mesaj de validare a datelor introduse.		Se va afișa un singur număr ce reprezintă poziția pe care Josephus trebuia să se afle pentru a rămâne în viață, alături de un mesaj de validare a datelor introduse ("Input valid"; se afișează "n trebuie să fie între i și 10^18" în caz contrar).

	==Restricții și precizări==		==Restricții și precizări==
Line 58:		Line 58:
	def validate_n(n):		def validate_n(n):
	if not 1 <= n <= 10**18:		if not 1 <= n <= 10**18:
	raise ValueError("n ~~should be between 1 and~~ 10^18 ~~inclusive~~")		raise ValueError("n trebuie să fie între i și 10^18")
	else:		else:
	print("~~Valid input~~")		print("Input valid")

	if __name__ == "__main__":		if __name__ == "__main__":

Cata at 07:36, 28 April 2023

2023-04-28T07:36:59Z

← Older revision		Revision as of 07:36, 28 April 2023
Line 10:		Line 10:

	==Date de ieșire==		==Date de ieșire==
	Se va afișa un singur număr ce reprezintă poziția pe care Josephus trebuia să se afle pentru a rămâne în viață.		Se va afișa un singur număr ce reprezintă poziția pe care Josephus trebuia să se afle pentru a rămâne în viață, alături de un mesaj de validare a datelor introduse.

	==Restricții și precizări==		==Restricții și precizări==
Line 16:		Line 16:
	* Se garantează că există o soluție pentru oricare n;		* Se garantează că există o soluție pentru oricare n;
	==Exemplu==		==Exemplu==
	Intrare		; Intrare
			: 41
	41		; Ieșire
	Ieșire		: Valid input
			: 19
	19
	==Explicație==		==Explicație==
	1 ⇒ 2 <br>		1 ⇒ 2 <br>
Line 60:		Line 59:
	if not 1 <= n <= 10**18:		if not 1 <= n <= 10**18:
	raise ValueError("n should be between 1 and 10^18 inclusive")		raise ValueError("n should be between 1 and 10^18 inclusive")
			else:
			print("Valid input")

	if __name__ == "__main__":		if __name__ == "__main__":

Cata: Pagină nouă: Aceasta este o problemă foarte cunoscută atât în universul informatic, cât și în cel matematic! Legenda ne povestește că Josephus și alți n-1 soldați evrei se luptau cu trupele romane. Din nefericire pentru aceștia, au ajuns foarte curând încercuiți și doborâți numeric. Ei se hotărăsc rapid să nu se predea, dar nici să nu își ia de unii singuri viața și astfel le vine următoarea idee: se așează cu toții într-un cerc și își scriu pe rând pe...

2023-04-20T16:01:49Z

Pagină nouă: Aceasta este o problemă foarte cunoscută atât în universul informatic, cât și în cel matematic! Legenda ne povestește că Josephus și alți n-1 soldați evrei se luptau cu trupele romane. Din nefericire pentru aceștia, au ajuns foarte curând încercuiți și doborâți numeric. Ei se hotărăsc rapid să nu se predea, dar nici să nu își ia de unii singuri viața și astfel le vine următoarea idee: se așează cu toții într-un cerc și își scriu pe rând pe...

New page

Aceasta este o problemă foarte cunoscută atât în universul informatic, cât și în cel matematic!

Legenda ne povestește că Josephus și alți n-1 soldați evrei se luptau cu trupele romane. Din nefericire pentru aceștia, au ajuns foarte curând încercuiți și doborâți numeric. Ei se hotărăsc rapid să nu se predea, dar nici să nu își ia de unii singuri viața și astfel le vine următoarea idee: se așează cu toții într-un cerc și își scriu pe rând pe frunte câte un număr, reprezentând indicativul fiecăruia (1, 2, …, n). Soldații decid ca soldatul cu numărul 1 să îl trimită în rai pe soldatul încă în viață din stânga sa (notat, în acest context, cu numărul 2), apoi următorul soldat în viață să repete aceeași acțiune până când nu va mai rămâne decât o singură persoană în viață.

==Cerința==
Josephus ar fi preferat să se predea. Pe ce poziție ar fi trebuit să se afle soldatul pentru a putea realiza acest lucru?

==Date de intrare==
Se va citi un singur număr natural nenul, n.

==Date de ieșire==
Se va afișa un singur număr ce reprezintă poziția pe care Josephus trebuia să se afle pentru a rămâne în viață.

==Restricții și precizări==
* 1 ≤ n ≤ 1018;
* Se garantează că există o soluție pentru oricare n;
==Exemplu==
Intrare

41
Ieșire

19
==Explicație==
1 ⇒ 2 
3 ⇒ 4 
… 
39 ⇒ 40 
41 ⇒ 1 
3 ⇒ 5 
… 
39 ⇒ 41 
3 ⇒ 7 
11 ⇒ 15 
……… 
19 ⇒ 35 

==Rezolvare==
<syntaxhighlight lang="python">
def calculate_exponent(n):
exponent = 0
save_n = n
while save_n != 1:
save_n //= 2
exponent += 1
return exponent

def is_power_of_two(n):
exponent = calculate_exponent(n)
return (1 << exponent) == n

def calculate_result(n):
exponent = calculate_exponent(n)
if is_power_of_two(n):
return 1
else:
return ((n - (1 << exponent)) << 1) + 1

def validate_n(n):
if not 1 <= n <= 10**18:
raise ValueError("n should be between 1 and 10^18 inclusive")

if __name__ == "__main__":
n = int(input())
validate_n(n)
print(calculate_result(n))

</syntaxhighlight>

==Explicație cod==
Acest program implementează trei funcții care lucrează împreună pentru a verifica dacă un număr întreg n este o putere a lui 2 și pentru a calcula un rezultat bazat pe n.

Funcția "calculate_exponent" primește un număr întreg n și calculează exponentul său în baza 2. Exponentul este calculat prin împărțirea repetată a lui n la 2 până când n ajunge la valoarea 1, numărul de împărțiri fiind exponentul.

Funcția "is_power_of_two" primește un număr întreg n și verifică dacă este o putere a lui 2, comparându-l cu 2 ridicat la exponentul calculat în funcția anterioară.

Funcția "calculate_result" primește un număr întreg n și calculează rezultatul bazat pe aceasta. Dacă n este o putere a lui 2, rezultatul va fi 1, altfel va fi calculat după o formulă dată.

Funcția "validate_n" primește un număr întreg n și verifică dacă se încadrează între 1 și 10^18 inclusiv. Dacă n nu se încadrează în această plajă, funcția va arunca o excepție "ValueError".

În metoda "main", se primește un număr întreg n de la utilizator, se validează și se calculează și se afișează rezultatul apelând funcția "calculate_result".