Ramona Dragoș at 14:27, 6 January 2024

2024-01-06T14:27:25Z

← Older revision		Revision as of 14:27, 6 January 2024
Line 39:		Line 39:
	1 4 3		1 4 3
	1 4 4		1 4 4
			= Explicatie =
			*Prima felie primită de <code>XORin</code> va fi cea care are colțul din dreapta jos <code>(3,3)</code> și latura 3.
			*A doua felie va fi cea cu colțul din dreapta jos <code>(4,7)</code> și latura 3.
			*Următoarea felie va fi cea cu colțul din dreapta jos <code>(1,4)</code> și latură 1. ș.a.m.d.
	= Exemplu 2: =		= Exemplu 2: =
	<code>tortin.txt</code>		<code>tortin.txt</code>

Ramona Dragoș: /* Exemplu 2: */

2023-12-22T08:45:42Z

Exemplu 2:

← Older revision		Revision as of 08:45, 22 December 2023
Line 45:		Line 45:
	<code>tortout.txt</code>		<code>tortout.txt</code>
	Nu au fost respectate cerintele impuse		Nu au fost respectate cerintele impuse
			== Rezolvare ==
	<syntaxhighlight lang="python">		<syntaxhighlight lang="python">
			#1677 - Tort
	def read_input(file_name):		def read_input(file_name):
	try:		try:

Ramona Dragoș: Pagină nouă: Pentru că s-a calificat la Olimpiada Națională de Informatică de la Craiova, NN îi pregătește lui XORin un tort. Tortul este dreptunghiular, format din linii și coloane numerotate de la `1` la `N` pentru linii și de la `1` la `M` pentru coloane. Tortul este format din bucăți de dimensiune `1x1`, fiecare fiind acoperită cu un alt tip de glazură. În fiecare zi NN îi taie lui XORin câte o felie, alegând cel...

2023-12-22T08:44:31Z

Pagină nouă: Pentru că s-a calificat la Olimpiada Națională de Informatică de la Craiova, NN îi pregătește lui XORin un tort. Tortul este dreptunghiular, format din linii și coloane numerotate de la <code>1</code> la <code>N</code> pentru linii și de la <code>1</code> la <code>M</code> pentru coloane. Tortul este format din bucăți de dimensiune <code>1x1</code>, fiecare fiind acoperită cu un alt tip de glazură. În fiecare zi NN îi taie lui XORin câte o felie, alegând cel...

New page

Pentru că s-a calificat la Olimpiada Națională de Informatică de la Craiova, NN îi pregătește lui XORin un tort. Tortul este dreptunghiular, format din linii și coloane numerotate de la <code>1</code> la <code>N</code> pentru linii și de la <code>1</code> la <code>M</code> pentru coloane. Tortul este format din bucăți de dimensiune <code>1x1</code>, fiecare fiind acoperită cu un alt tip de glazură. În fiecare zi NN îi taie lui XORin câte o felie, alegând cel mai mare pătrat care conține bucăți acoperite cu același tip de glazură. În cazul în care există mai multe astfel de felii, NN o alege pe cea care are colțul din dreapta jos situat pe linia cu indicele cel mai mic. Dacă și în acest caz există mai multe posibilități, el o va alege pe cea cu colțul din dreapta jos situat în coloana cu indicele cel mai mic.

= Cerința =
Precizați latura și coordonatele colțului din dreapta jos pentru fiecare felie de tort primită, în ordinea specificată mai sus.

= Date de intrare =
Fișierul de intrare <code>tortin.txt</code> conține pe prima linie numerele naturale <code>N</code> și <code>M</code>, separate printr-un spațiu, reprezentând lungimea și lățimea tortului. Pe următoarele <code>N</code> linii se vor afla câte <code>M</code> caractere din mulțimea <code>{‘0’, ..., ‘9’}</code> reprezentând tipul de glazură cu care este acoperită bucata de pe linia <code>i</code> și coloana <code>j</code> a tortului. Liniile și coloanele sunt numerotate de la <code>1</code> la <code>N</code>, respectiv de la <code>1</code> la <code>M</code>. Pe linii nu există spațiu între oricare două caractere alăturate.

= Date de ieșire =
În fișierul de ieșire <code>tortout.txt</code> se vor afișa feliile de tort în ordinea în care XORin le va primi. Pentru fiecare felie se va afișa latura feliei, precum și coordonatele colțului din dreapta jos, valori separate prin câte un singur spațiu.

= Restricții și precizări =

* <code>1 ≤ N,M ≤ 500</code>
* Numerotarea liniilor și coloanelor nu se schimbă în urma operațiilor de eliminare.
* Pentru 30% din teste se garantează că <code>1 ≤ N,M ≤ 35</code>

= Exemplu 1: =
<code>tortin.txt</code>
4 7
1111111
1112333
1112333
4444333
<code>tortout.txt</code>
Datele de intrare sunt corecte

3 3 3
3 4 7
1 1 4
1 1 5
1 1 6
1 1 7
1 2 4
1 3 4
1 4 1
1 4 2
1 4 3
1 4 4

= Exemplu 2: =
<code>tortin.txt</code>
0 0
<code>tortout.txt</code>
Nu au fost respectate cerintele impuse
<syntaxhighlight lang="python">
def read_input(file_name):
try:
with open(file_name, 'r') as file:
N, M = map(int, file.readline().split())
tort = [list(map(int, line.strip())) for line in file]

if 1 <= N <= 500 and 1 <= M <= 500:
return N, M, tort
else:
raise ValueError("Numerele nu respecta restricțiile.")
except Exception as e:
print(f"Nu au fost respectate cerintele impuse: {str(e)}")
return None

def write_output(file_name, result):
with open(file_name, 'w') as file:
if result is not None:
for item in result:
file.write(" ".join(map(str, item)) + "\n")

def find_largest_square(N, M, tort, i, j):
size = 1

while i + size <= N and j + size <= M:
if all(tort[x][y] == tort[i][j] for x in range(i, i + size) for y in range(j, j + size)):
size += 1
else:
break
#1677 - Tort
return size - 1 # Return the side length of the largest square

def find_felii(N, M, tort):
felii = []

for i in range(N):
for j in range(M):
side_length = find_largest_square(N, M, tort, i, j)
if side_length > 0:
felii.append((side_length, i + side_length, j + side_length))

felii.sort(key=lambda x: (x[0], x[1], x[2]))
return felii

def main(input_file, output_file):
result = read_input(input_file)
if result is not None:
N, M, tort = result
felii = find_felii(N, M, tort)
write_output(output_file, felii)

if __name__ == "__main__":
main("tortin.txt", "tortout.txt")

</syntaxhighlight>

1677 - Tort - Revision history

Ramona Dragoș at 14:27, 6 January 2024

Ramona Dragoș: /* Exemplu 2: */