Andrada378 at 20:58, 3 January 2024

2024-01-03T20:58:10Z

← Older revision		Revision as of 20:58, 3 January 2024
Line 1:		Line 1:
			== Enunț ==
	Oleg ține un istoric al vieții sale. O zi rea este notata cu 0, iar una bună este notată cu 1. Oleg numește un subșir zebră, un subșir care începe și se termină cu o zi rea și nu conține două zile de același fel pe poziții alăturate. De exemplu 0101, 001 și 0110 nu sunt subșiruri zebra, dar 010, 0 și 01010 sunt subșiruri zebră.		Oleg ține un istoric al vieții sale. O zi rea este notata cu 0, iar una bună este notată cu 1. Oleg numește un subșir zebră, un subșir care începe și se termină cu o zi rea și nu conține două zile de același fel pe poziții alăturate. De exemplu 0101, 001 și 0110 nu sunt subșiruri zebra, dar 010, 0 și 01010 sunt subșiruri zebră.

	~~'''''~~Cerința~~'''''~~		== Cerința ==

	Să se determine o împărțire a unui șir în subșiruri zebră.		Să se determine o împărțire a unui șir în subșiruri zebră.

	~~'''''~~Date de intrare~~'''''~~		== Date de intrare ==

	Programul citește de la tastatură un șir de caractere format din 0 și 1.		Programul citește de la tastatură un șir de caractere format din 0 și 1.

	~~'''''~~Date de ieșire~~'''''~~		== Date de ieșire ==

	Programul va afișa pe ecran S, numărul de subșiruri, iar apoi, pe următoarele S linii numărul de zile componente ale fiecărui subșir și pozițiile din șirul inițial la care se află acestea. Dacă șirul nu se poate împărții în subșiruri zebră, atunci se va afișa -1.		Programul va afișa pe ecran S, numărul de subșiruri, iar apoi, pe următoarele S linii numărul de zile componente ale fiecărui subșir și pozițiile din șirul inițial la care se află acestea. Dacă șirul nu se poate împărții în subșiruri zebră, atunci se va afișa -1.

	~~'''''~~Restricții și precizări~~'''''~~		== Restricții și precizări ==

	Inputul conține cel mult 200.000 de caractere.		* Inputul conține cel mult 200.000 de caractere.
			* Orice împărțire în subșiruri zebră este acceptată.

	~~Orice împărțire în subșiruri zebră este acceptată.~~		== Exemplu 1: ==
			'''Intrare'''
	~~'''''~~Exemplu 1:'''''

	~~Intrare~~

	0010100		0010100

	Ieșire		'''Ieșire'''

	3		3
Line 35:		Line 31:
	1 7		1 7

	Exemplu 2:		== Exemplu 2: ==

	Intrare		Intrare

Line 45:		Line 40:
	-1		-1

	~~'''''~~Rezolvare~~'''''~~<syntaxhighlight lang="python">		== Rezolvare ==
			<syntaxhighlight lang="python">
			def validate_input(sir):
			if len(sir) > 200000:
			print("Inputul depășește limita de 200.000 de caractere.")
			return False
			return True
	def gaseste_subsiruri_zebra(sir):		def gaseste_subsiruri_zebra(sir):
	n = len(sir)		n = len(sir)
Line 91:		Line 92:
	for subSir in rezultat:		for subSir in rezultat:
	print(*subSir)		print(*subSir)

	</syntaxhighlight>		</syntaxhighlight>

Andrada378: Pagină nouă: Oleg ține un istoric al vieții sale. O zi rea este notata cu 0, iar una bună este notată cu 1. Oleg numește un subșir zebră, un subșir care începe și se termină cu o zi rea și nu conține două zile de același fel pe poziții alăturate. De exemplu 0101, 001 și 0110 nu sunt subșiruri zebra, dar 010, 0 și 01010 sunt subșiruri zebră. '''''Cerința''''' Să se determine o împărțire a unui șir în subșiruri zebră. '''''Date de intrare''''' Programul ci...

2023-12-28T15:09:07Z

Pagină nouă: Oleg ține un istoric al vieții sale. O zi rea este notata cu 0, iar una bună este notată cu 1. Oleg numește un subșir zebră, un subșir care începe și se termină cu o zi rea și nu conține două zile de același fel pe poziții alăturate. De exemplu 0101, 001 și 0110 nu sunt subșiruri zebra, dar 010, 0 și 01010 sunt subșiruri zebră. '''''Cerința''''' Să se determine o împărțire a unui șir în subșiruri zebră. '''''Date de intrare''''' Programul ci...

New page

Oleg ține un istoric al vieții sale. O zi rea este notata cu 0, iar una bună este notată cu 1. Oleg numește un subșir zebră, un subșir care începe și se termină cu o zi rea și nu conține două zile de același fel pe poziții alăturate. De exemplu 0101, 001 și 0110 nu sunt subșiruri zebra, dar 010, 0 și 01010 sunt subșiruri zebră.

'''''Cerința'''''

Să se determine o împărțire a unui șir în subșiruri zebră.

'''''Date de intrare'''''

Programul citește de la tastatură un șir de caractere format din 0 și 1.

'''''Date de ieșire'''''

Programul va afișa pe ecran S, numărul de subșiruri, iar apoi, pe următoarele S linii numărul de zile componente ale fiecărui subșir și pozițiile din șirul inițial la care se află acestea. Dacă șirul nu se poate împărții în subșiruri zebră, atunci se va afișa -1.

'''''Restricții și precizări'''''

Inputul conține cel mult 200.000 de caractere.

Orice împărțire în subșiruri zebră este acceptată.

'''''Exemplu 1:'''''

Intrare

0010100

Ieșire

3

3 1 3 4

3 2 5 6

1 7

Exemplu 2:

Intrare

111

Ieșire

-1

'''''Rezolvare'''''<syntaxhighlight lang="python">
def gaseste_subsiruri_zebra(sir):
n = len(sir)
subSiruri = []

i = 0
while i < n:
# Găsirea primei zi rele
while i < n and sir[i] == '1':
i += 1

if i == n:
break # Am ajuns la finalul șirului, nu mai avem subșiruri zebră

start = i
ziua_curenta = 0
while i < n and sir[i] == '0':
ziua_curenta += 1
i += 1

if i == n:
break # Am ajuns la finalul șirului, ultima zi a fost bună

# Verificăm dacă următoarea zi este rea
if i < n and sir[i] == '1':
subSiruri.append((ziua_curenta, start + 1, i))

if not subSiruri:
return -1

return subSiruri

# Citirea datelor de intrare
sir = input().strip()

# Găsirea subșirurilor zebră
rezultat = gaseste_subsiruri_zebra(sir)

# Afișarea rezultatelor
if rezultat == -1:
print(-1)
else:
print(len(rezultat))
for subSir in rezultat:
print(*subSir)

</syntaxhighlight>

2430 - zebra - Revision history

Andrada378 at 20:58, 3 January 2024