4021 - Tablou 1: Diferență între versiuni
De la Universitas MediaWiki
Linia 42: | Linia 42: | ||
== Rezolvare == | == Rezolvare == | ||
<syntaxhighlight lang="python3" line="1"> | <syntaxhighlight lang="python3" line="1"> | ||
def is_valid(tablou): | |||
# Verificare pe linii | |||
for linie in tablou: | |||
if len(set(linie)) != len(linie): | |||
return False | |||
# Verificare pe coloane | |||
for coloana in zip(*tablou): | |||
if len(set(coloana)) != len(coloana): | |||
return False | |||
return True | |||
def generate_tablou(N, S): | def generate_tablou(N, S): | ||
if N == 1: | if N == 1: | ||
Linia 60: | Linia 73: | ||
tablou[0][N - 1] = S - (N - 1) | tablou[0][N - 1] = S - (N - 1) | ||
return tablou | return tablou if is_valid(tablou) else None | ||
# Citire date de intrare | # Citire date de intrare | ||
Linia 69: | Linia 82: | ||
tablou = generate_tablou(N, S) | tablou = generate_tablou(N, S) | ||
# Scriere rezultat | # Scriere rezultat în fișierul de ieșire | ||
with open("tablouout.txt", "w") as file: | with open("tablouout.txt", "w") as file: | ||
if tablou: | if tablou: | ||
Linia 76: | Linia 89: | ||
else: | else: | ||
file.write("0\n") | file.write("0\n") | ||
</syntaxhighlight> | </syntaxhighlight> |
Versiunea curentă din 29 decembrie 2023 11:36
Cerinta
Generaţi un tablou bidimensional cu proprietăţile:
- conţine N linii şi N coloane;
- elementele sale sunt numere naturale nenule;
- suma elementelor este egală cu numărul natural nenul S;
- pe nici o linie şi pe nici o coloană nu există două elemente identice;
- diferenţa dintre cel mai mare şi cel mai mic element ale tabloului este minimă.
Date de intrare
Fișierul de intrare tablouin.txt conţine pe prima linie două numere naturale nenule N S, separate printr-un spaţiu, reprezentând numărul de linii şi de coloane ale tabloului, respectiv valoarea sumei tuturor elementelor din tablou.
Date de iesire
Fișierul de ieșire tablouout.txt va conţine N linii pe care se vor scrie elementele tabloului, câte o linie din tablou pe o linie din fişier; elementele de pe aceeaşi linie se vor separa prin câte un spaţiu.
Restrictii si precizari
- 1 < N ⩽ 100
- '0 < S < 2^31
- Dacă problema nu are soluţie, în fişierul de ieşire se va scrie cifra 0.
- Dacă problema are mai multe soluţii, în fişier se va scrie una singură.
Exemplul 1
- tablouin.txt
- 3 51
- tablouout.txt
- Datele introduse corespund restrictiilor impuse
- 4 6 7
- 7 4 6
- 6 7 4
Exemplul 2
- tablouin.txt
- 0 -10
- Datele introduse nu corespund restrictiilor impuse
Rezolvare
def is_valid(tablou):
# Verificare pe linii
for linie in tablou:
if len(set(linie)) != len(linie):
return False
# Verificare pe coloane
for coloana in zip(*tablou):
if len(set(coloana)) != len(coloana):
return False
return True
def generate_tablou(N, S):
if N == 1:
if S == 1:
return [[1]]
else:
return [[0]]
# Initializare tablou
tablou = [[0] * N for _ in range(N)]
# Alegem coltul din stanga sus si coltul din dreapta jos
tablou[0][0] = 1
tablou[N - 1][N - 1] = S - (N - 1)
# Alegem coltul din stanga jos si coltul din dreapta sus
tablou[N - 1][0] = 1
tablou[0][N - 1] = S - (N - 1)
return tablou if is_valid(tablou) else None
# Citire date de intrare
with open("tablouin.txt", "r") as file:
N, S = map(int, file.readline().split())
# Generare tablou
tablou = generate_tablou(N, S)
# Scriere rezultat în fișierul de ieșire
with open("tablouout.txt", "w") as file:
if tablou:
for linie in tablou:
file.write(' '.join(map(str, linie)) + '\n')
else:
file.write("0\n")