1675 - Calc - Revision history

Cata at 07:12, 3 May 2023

2023-05-03T07:12:34Z

← Older revision		Revision as of 07:12, 3 May 2023
Line 1:		Line 1:
			==Cerința==
	La un concurs de informatică participă 2∙N elevi împărțiți în N echipe de câte 2. Echipa poate lucra în comun la problemele propuse doar dacă au calculatoarele în rețea. Laboratorul de informatică este unul special: are 2∙N calculatoare, distribuite pe două rânduri la distanță de un metru între ele (vertical și orizontal) și N cabluri de rețea de lungime un metru. Concursul se desfășoară pe mai multe zile și nu există două zile de concurs cu aceeași configurație a rețelei.		La un concurs de informatică participă 2∙N elevi împărțiți în N echipe de câte 2. Echipa poate lucra în comun la problemele propuse doar dacă au calculatoarele în rețea. Laboratorul de informatică este unul special: are 2∙N calculatoare, distribuite pe două rânduri la distanță de un metru între ele (vertical și orizontal) și N cabluri de rețea de lungime un metru. Concursul se desfășoară pe mai multe zile și nu există două zile de concurs cu aceeași configurație a rețelei.

	Exemplu: pentru N=3, cei 6 elevi au fost împărțiți în 3 echipe, iar aranjarea rețelei în cele 3 zile de concurs este cea din figura de mai jos.		Exemplu: pentru N=3, cei 6 elevi au fost împărțiți în 3 echipe, iar aranjarea rețelei în cele 3 zile de concurs este cea din figura de mai jos.

			Administratorul laboratorului vrea să memoreze în ordine lexicografică toate configurațiile folosite în zilele de concurs. Cablul orizontal se notează prin 0, iar cel vertical prin 1. Lucrând ordonat și eficient, pentru cele trei zile el își va nota valorile: 001, 100, respectiv 111. Se observă că o reprezentare de genul 000, 010, 011, 101 nu poate fi realizată.


	Administratorul laboratorului vrea să memoreze în ordine lexicografică toate configurațiile folosite în zilele de concurs. Cablul orizontal se notează prin 0, iar cel vertical prin 1. Lucrând ordonat și eficient, pentru cele trei zile el își va nota valorile: 001, 100, respectiv 111. Se observă că o reprezentare de genul 000, 010, 011, 101 nu poate fi realizată.

	~~==Cerința==~~
	Cunoscând N, să se determine:		Cunoscând N, să se determine:

Line 26:		Line 25:
	În acest caz, fişierul de ieşire calc.out va conține două linii. Pe prima linie se vor scrie N cifre binare, fără spații între ele, reprezentând configurația rețelei din ziua precedentă, iar pe a doua linie N cifre binare, fără spații între ele, reprezentând configurația din ziua următoare. Dacă în ziua precedentă nu există o configurație conform cerințelor problemei, se va scrie pe prima linie valoarea -1. Dacă în ziua următoare nu există o configurație conform cerințelor problemei, se va scrie pe a doua linie valoarea -1.		În acest caz, fişierul de ieşire calc.out va conține două linii. Pe prima linie se vor scrie N cifre binare, fără spații între ele, reprezentând configurația rețelei din ziua precedentă, iar pe a doua linie N cifre binare, fără spații între ele, reprezentând configurația din ziua următoare. Dacă în ziua precedentă nu există o configurație conform cerințelor problemei, se va scrie pe prima linie valoarea -1. Dacă în ziua următoare nu există o configurație conform cerințelor problemei, se va scrie pe a doua linie valoarea -1.

			Consola va afișa "Input valid" sau instrucțiuni de introducere a datelor.
	==Restricții și precizări==		==Restricții și precizări==
	* 1 &les; N &les; 100000		* 1 &les; N &les; 100000
Line 132:		Line 132:
	return True		return True

	~~def main()~~:		if __name__ == "__main__":
	tip, n, s = read_input()		tip, n, s = read_input()
	if not validate_input(tip, n, s):		if not validate_input(tip, n, s):
Line 149:		Line 149:
	write_output(prev, next)		write_output(prev, next)


	~~if __name__ == "__main__":~~
	~~main()~~

	</syntaxhighlight>		</syntaxhighlight>

	==Explicație cod==		==Explicație cod==
	~~Programul~~ citește ~~datele de intrare~~ din fișierul "calc.in", ~~validează datele de~~ intrare, ~~apoi își dă seama dacă tipul problemei este~~ 1 ~~sau 2~~.		MODULO = 1000 * 1000 * 1000 + 7: definește valoarea modulo care va fi utilizată în funcția compute_fibonacci.

			def read_input(): definește o funcție care citește intrarea din fișierul "calc.in". Prima linie a fișierului reprezintă tipul de operație de efectuat (tip), a doua linie reprezintă lungimea șirului (n), iar a treia linie reprezintă șirul (s). Funcția returnează valorile tipul, n și s.

			def write_output(prev, next): definește o funcție care scrie ieșirea în fișierul "calc.out". Ieșirea constă din două linii: prev și next. Funcția primește două argumente: prev și next.

			def compute_prev(s): definește o funcție care primește un șir s ca intrare și returnează șirul anterior în ordinea lexicografică. Dacă șirul anterior nu există, funcția returnează -1.

			def compute_next(s): definește o funcție care primește un șir s ca intrare și returnează următorul șir în ordinea lexicografică. Dacă următorul șir nu există, funcția returnează -1.

	~~Dacă tipul problemei este 1, programul~~ calculează ~~numărul~~ Fibonacci de ~~ordine~~ n și scrie rezultatul în fișierul "calc.out". Dacă tipul problemei este 2, programul calculează valorile anterioară și următoare a unui șir de biți și scrie cele două rezultate în fișierul "calc.out".		def compute_fibonacci(n): definește o funcție care calculează al n-lea număr Fibonacci folosind o abordare iterativă. Funcția returnează valoarea celui de-al n-lea număr Fibonacci.

	~~Pentru a calcula valorile anterioară~~ și ~~următoare, programul apelează funcțiile~~ "~~compute_prev(s)~~" și "~~compute_next(s)~~" ~~care primesc ca parametru un șir de biți și întorc valoarea anterioară și următoarea valoare~~, ~~respectiv~~.		def validate_input(tip: int, N: int, S: str) -> bool: definește o funcție care validează intrarea. Verifică dacă valoarea tipului este 1 sau 2, dacă valoarea n se află între 1 și 100000 și dacă șirul s conține doar caracterele "0" și "1". Dacă intrarea este validă, funcția returnează True; în caz contrar, returnează False.

	~~Pentru a verifica dacă datele~~ de intrare ~~sunt valide~~, ~~programul utilizează~~ funcția "validate_input(tip~~: int~~, ~~N: int, S: str)~~ -~~> bool~~". Dacă ~~datele~~ de ~~intrare nu sunt valide~~, ~~programul afișează un mesaj de eroare~~ și se ~~termină~~.		if name == "main": este punctul de intrare principal al programului. Mai întâi, se citește intrarea folosind funcția read_input și se validează utilizând funcția validate_input. Dacă intrarea nu este validă, programul se încheie cu o eroare. Dacă tipul de operație (tip) este 1, se calculează al n-lea număr Fibonacci folosind funcția compute_fibonacci și se scrie ieșirea în fișierul "calc.out". Dacă tipul de operație este 2, se calculează șirurile anterioare și următoare în ordinea lexicografică folosind funcțiile compute_prev și compute_next, respectiv, și se scrie ieșirea în fișierul "calc.out".

Cata at 08:04, 28 April 2023

2023-04-28T08:04:16Z

← Older revision		Revision as of 08:04, 28 April 2023
Line 30:		Line 30:
	* Pentru rezolvarea corectă a primei cerinţe se acordă 20 de puncte, iar pentru cerința a doua se acordă 80 de puncte.		* Pentru rezolvarea corectă a primei cerinţe se acordă 20 de puncte, iar pentru cerința a doua se acordă 80 de puncte.
	==Exemplul 1==		==Exemplul 1==
	calc.in		; calc.in

	1		: 1
	3		: 3
	001		: 001
	calc.out		; calc.out

	3		: 3
			; Consola
			: Input valid
	==Exemplul 2==		==Exemplul 2==
	calc.in		; calc.in

	2		: 2
	3		: 3
	001		: 001
	calc.out		; calc.out

	-1
	~~100~~

			: -1
			: 100
			; Consola
			: Input valid
	==Rezolvare==		==Rezolvare==
	<syntaxhighlight lang="python">		<syntaxhighlight lang="python">
	~~# Adrian Budau - 100 de puncte - Complexitate O(N)~~
	MODULO = 1000 * 1000 * 1000 + 7		MODULO = 1000 * 1000 * 1000 + 7

Line 127:		Line 129:
	print("S trebuie sa fie un sir de N caractere '0' sau '1'")		print("S trebuie sa fie un sir de N caractere '0' sau '1'")
	return False		return False
			print("Input valid")
	return True		return True

Cata: Pagină nouă: La un concurs de informatică participă 2∙N elevi împărțiți în N echipe de câte 2. Echipa poate lucra în comun la problemele propuse doar dacă au calculatoarele în rețea. Laboratorul de informatică este unul special: are 2∙N calculatoare, distribuite pe două rânduri la distanță de un metru între ele (vertical și orizontal) și N cabluri de rețea de lungime un metru. Concursul se desfășoară pe mai multe zile și nu există două zile de concurs cu ace...

2023-04-20T19:46:18Z

Pagină nouă: La un concurs de informatică participă 2∙N elevi împărțiți în N echipe de câte 2. Echipa poate lucra în comun la problemele propuse doar dacă au calculatoarele în rețea. Laboratorul de informatică este unul special: are 2∙N calculatoare, distribuite pe două rânduri la distanță de un metru între ele (vertical și orizontal) și N cabluri de rețea de lungime un metru. Concursul se desfășoară pe mai multe zile și nu există două zile de concurs cu ace...

New page

La un concurs de informatică participă 2∙N elevi împărțiți în N echipe de câte 2. Echipa poate lucra în comun la problemele propuse doar dacă au calculatoarele în rețea. Laboratorul de informatică este unul special: are 2∙N calculatoare, distribuite pe două rânduri la distanță de un metru între ele (vertical și orizontal) și N cabluri de rețea de lungime un metru. Concursul se desfășoară pe mai multe zile și nu există două zile de concurs cu aceeași configurație a rețelei.

Exemplu: pentru N=3, cei 6 elevi au fost împărțiți în 3 echipe, iar aranjarea rețelei în cele 3 zile de concurs este cea din figura de mai jos.

Administratorul laboratorului vrea să memoreze în ordine lexicografică toate configurațiile folosite în zilele de concurs. Cablul orizontal se notează prin 0, iar cel vertical prin 1. Lucrând ordonat și eficient, pentru cele trei zile el își va nota valorile: 001, 100, respectiv 111. Se observă că o reprezentare de genul 000, 010, 011, 101 nu poate fi realizată.

==Cerința==
Cunoscând N, să se determine:

Numărul de zile modulo 1000000007 în care se desfășoară concursul.
Configurațiile laboratorului în ziua X-1 și ziua X+1, cunoscând configurația zilei X.
==Date de intrare==
Fişierul de intrare calc.in conţine pe prima linie un număr natural p. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2.

Pe linia a doua vom avea numărul natural N.

Pe linia a treia se va găsi un șir de N cifre binare, fără spații între ele, reprezentând configurația corectă realizată de administrator în ziua X.

==Date de ieșire==
Dacă valoarea lui p este 1, se va rezolva numai punctul 1) din cerință.
În acest caz, în fişierul de ieşire calc.out se va scrie un singur număr natural Z reprezentând numărul de zile în care se desfășoară concursul pentru cele N echipe.

Dacă valoarea lui p este 2, se va rezolva numai punctul 2) din cerință.
În acest caz, fişierul de ieşire calc.out va conține două linii. Pe prima linie se vor scrie N cifre binare, fără spații între ele, reprezentând configurația rețelei din ziua precedentă, iar pe a doua linie N cifre binare, fără spații între ele, reprezentând configurația din ziua următoare. Dacă în ziua precedentă nu există o configurație conform cerințelor problemei, se va scrie pe prima linie valoarea -1. Dacă în ziua următoare nu există o configurație conform cerințelor problemei, se va scrie pe a doua linie valoarea -1.

==Restricții și precizări==
* 1 &les; N &les; 100000
* Pentru rezolvarea corectă a primei cerinţe se acordă 20 de puncte, iar pentru cerința a doua se acordă 80 de puncte.
==Exemplul 1==
calc.in

1
3
001
calc.out

3
==Exemplul 2==
calc.in

2
3
001
calc.out

-1
100

==Rezolvare==
<syntaxhighlight lang="python">
# Adrian Budau - 100 de puncte - Complexitate O(N)
MODULO = 1000 * 1000 * 1000 + 7

def read_input():
with open("calc.in", "r") as f:
tip = int(f.readline().strip())
n = int(f.readline().strip())
s = f.readline().strip()
return tip, n, s

def write_output(prev, next):
with open("calc.out", "w") as f:
f.write(f"{prev}\n{next}\n")

def compute_prev(s):
n = len(s)
prev = list(s)
if s[n - 1] == "1" and s[n - 2] == "1":
prev[n - 1] = prev[n - 2] = "0"
else:
i = n - 2
while i >= 0 and s[i] == "0":
i -= 1
if i < 0:
prev = "-1"
else:
prev[i] = "0"
for j in range(i + 2, n):
prev[j] = "1"
return "".join(prev)

def compute_next(s):
n = len(s)
next = list(s)
if s[n - 1] == "0" and s[n - 2] == "0":
next[n - 1] = next[n - 2] = "1"
else:
i = n - 1
while i >= 0 and s[i] == "1":
i -= 1
if i < 0:
next = "-1"
else:
next[i - 1] = "1"
next[i] = "0"
oldi = i
for j in range(i + 1, n):
next[j] = "0"
if (n - 1 - oldi) % 2 == 0:
next[n - 1] = "1"
return "".join(next)

def compute_fibonacci(n):
if n <= 1:
return 1
a, b = 1, 1
for i in range(2, n + 1):
c = (a + b) % MODULO
a, b = b, c
return b

def validate_input(tip: int, N: int, S: str) -> bool:
if tip not in (1, 2):
print("tip trebuie sa fie 1 sau 2")
return False
if not (1 <= N <= 100000):
print("N trebuie sa fie intre 1 si 100000")
return False
if len(S) != N or not set(S).issubset({'0', '1'}):
print("S trebuie sa fie un sir de N caractere '0' sau '1'")
return False
return True

def main():
tip, n, s = read_input()
if not validate_input(tip, n, s):
exit(1)
if tip == 1:
result = compute_fibonacci(n)
write_output(result, result)
return

if n == 1:
write_output("-1", "-1")
return

prev = compute_prev(s)
next = compute_next(s)
write_output(prev, next)

if __name__ == "__main__":
main()

</syntaxhighlight>

==Explicație cod==
Programul citește datele de intrare din fișierul "calc.in", validează datele de intrare, apoi își dă seama dacă tipul problemei este 1 sau 2.

Dacă tipul problemei este 1, programul calculează numărul Fibonacci de ordine n și scrie rezultatul în fișierul "calc.out". Dacă tipul problemei este 2, programul calculează valorile anterioară și următoare a unui șir de biți și scrie cele două rezultate în fișierul "calc.out".

Pentru a calcula valorile anterioară și următoare, programul apelează funcțiile "compute_prev(s)" și "compute_next(s)" care primesc ca parametru un șir de biți și întorc valoarea anterioară și următoarea valoare, respectiv.

Pentru a verifica dacă datele de intrare sunt valide, programul utilizează funcția "validate_input(tip: int, N: int, S: str) -> bool". Dacă datele de intrare nu sunt valide, programul afișează un mesaj de eroare și se termină.