Bitnami MediaWiki - User contributions [en]

0400 - Pachete

2024-01-07T11:28:28Z

Rus Marius: Pagină nouă: = Cerinţa = Într-un depozit există un raft cu <code>n+1</code> spații de depozitare, numerotate de la <code>1</code> la <code>n+1</code>. Primele <code>n</code> spatii de depozitare sunt ocupate cu <code>n</code> pachete numerotate cu valori între <code>1</code> și <code>n</code>, iar spațiul de depozitare <code>n+1</code> este gol. Administratorul depozitului decide mutarea pachetelor, astfel încât pentru orice <code>i</code>, pachetul numerotat cu <code>i</code> s...

= Cerinţa =
Într-un depozit există un raft cu <code>n+1</code> spații de depozitare, numerotate de la <code>1</code> la <code>n+1</code>. Primele <code>n</code> spatii de depozitare sunt ocupate cu <code>n</code> pachete numerotate cu valori între <code>1</code> și <code>n</code>, iar spațiul de depozitare <code>n+1</code> este gol.

Administratorul depozitului decide mutarea pachetelor, astfel încât pentru orice <code>i</code>, pachetul numerotat cu <code>i</code> să se afle în spațiul de depozitare <code>i</code>. Pentru aceasta se va folosi spațiul de depozitare suplimentar, <code>n+1</code>, singura manevră validă fiind mutarea unui pachet dintr-un spațiu de depozitare în altul, cu condiția ca acesta să fie gol.

Determinați o succesiune de manevre prin care fiecare pachet să fie în spațiul corect.

= Date de intrare =
Fişierul de intrare <code>pacheteIN.txt</code> conţine pe prima linie numărul <code>n</code>, iar pe a doua linie <code>n</code> numere naturale separate prin spaţii. Al <code>i</code>-lea număr reprezintă numărul pachetului aflat în spațiul de depozitare <code>i</code>.

= Date de ieşire =
Fişierul de ieşire <code>pacheteOUT.txt</code> va conţine pe prima linie numărul <code>M</code>, reprezentând numărul de manevre efectuate. Pe fiecare dintre următoarele <code>M</code> linii se descrie o manevră, prin două numere <code>i j</code>, cu semnificația: se ia pachetul din spațiul <code>i</code> și se mută în spațiul <code>j</code>.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricţii şi precizări =

* <code>1 ≤ n ≤ 100</code>
* pentru fiecare manevră <code>i j</code> efectuată, <code>1 ≤ i,j ≤ n+1</code>, <code>i ≠ j</code>, iar spațiul <code>j</code> trebuie să fie gol
* numărul de manevre realizate nu trebuie să fie minim

= Exemplul 1: =
<code>pacheteIN.txt</code>
5
2 5 4 3 1
<code>pacheteOUT.txt</code>
7
1 6
5 1
2 5
6 2
3 6
4 3
6 4

= Explicație =
Pachetele se vor muta în felul urmator.
{| class="wikitable"
|2
|5
|4
|3
|1
|_
|-
|_
|5
|4
|3
|1
|2
|-
|1
|5
|4
|3
|_
|2
|-
|1
|_
|4
|3
|5
|2
|-
|1
|2
|4
|3
|5
|_
|-
|1
|2
|_
|3
|5
|4
|-
|1
|2
|3
|_
|5
|4
|-
|1
|2
|3
|4
|5
|_
|}

== Exemplul 2: ==
<code>pacheteIN.txt</code>
101
2 5 4 3 1
<code>pacheteOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
INFILE = "pacheteIN.txt"
OUTFILE = "pacheteOUT.txt"

NMAX = 1000 * 100 + 1

v = [0] * NMAX
p = [0] * NMAX
sol = [[0] * (NMAX * 2) for _ in range(2)]

def check_constraints(n):
if 1 <= n <= 100:
return True
else:
with open(OUTFILE, "w") as outfile:
outfile.write("Datele nu corespund restrictiilor impuse\n")
return False

def main():
global v, p, sol

with open(INFILE, "r") as infile:
n = int(infile.readline())

if not check_constraints(n):
return

v[1:n+1] = map(int, infile.readline().split())
p = [0] * (n+1)

p[0] = n + 1
nr = 0

for i in range(1, n+1):
p[v[i]] = i

for i in range(1, n+1):
if v[i] == i:
continue

if p[0] != i:
nr += 1
sol[0][nr] = i
sol[1][nr] = p[0]
v[p[0]] = v[i]
p[v[i]] = p[0]
v[i] = 0
p[0] = i

nr += 1
sol[0][nr] = p[i]
sol[1][nr] = i
v[i] = i
v[p[i]] = 0
p[0] = p[i]
p[i] = i

with open(OUTFILE, "w") as outfile:
outfile.write(f"{nr}\n")
for i in range(1, nr+1):
outfile.write(f"{sol[0][i]} {sol[1][i]}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

0341 - Bomboane

2024-01-07T11:24:20Z

Rus Marius: Pagină nouă: = Cerinţa = La magazinul din colț au fost aduse <code>n</code> cutii, numerotate de la <code>1</code> la <code>n</code>, fiecare conținând un anumit număr de bomboane. Administratorul magazinului hotărăște, pentru bunul mers al afacerilor, că bomboanele trebuie rearanjate în cutii, astfel încât fiecare cutie să conțină același număr de bomboane. Pentru aceasta, administratorul magazinului realizează în mod repetat următoarea operație: mută un număr oare...

= Cerinţa =
La magazinul din colț au fost aduse <code>n</code> cutii, numerotate de la <code>1</code> la <code>n</code>, fiecare conținând un anumit număr de bomboane. Administratorul magazinului hotărăște, pentru bunul mers al afacerilor, că bomboanele trebuie rearanjate în cutii, astfel încât fiecare cutie să conțină același număr de bomboane. Pentru aceasta, administratorul magazinului realizează în mod repetat următoarea operație: mută un număr oarecare de bomboane din cutia cu număr maxim de bomboane în cea cu număr minim de bomboane.

Determinați un șir cu număr minim de operații prin care toate cutiile conțin același număr de bomboane.

= Date de intrare =
Fişierul de intrare <code>bomboaneIN.txt</code> conţine pe prima linie numărul <code>n</code>, iar pe a doua linie <code>n</code> numere naturale separate prin spaţii, reprezentând numărul de bomboane din fiecare cutie.

= Date de ieşire =
Fişierul de ieşire <code>bomboaneOUT.txt</code> va conţine pe prima linie numărul <code>M</code>, reprezentând numărul total de mutări. Următoarele <code>M</code> linii descriu mutările. Fiecare linie va conține câte trei numere <code>S D B</code>, separate prin câte un spațiu, cu semnificația: din cutia <code>S</code> s-au mutat în cutia <code>D</code> un număr de <code>B</code> bomboane.

= Restricţii şi precizări =

* <code>1 ≤ n ≤ 1000</code>
* în fiecare cutie se află cel puțin una și cel mult <code>1000</code> de bomboane
* după efectuarea mutărilor numărul total de bomboane din cutii este același cu numărul total de bomboane de la început
* dacă nu este posibilă redistribuirea bomboanelor în condițiile date se va afișa pe prima linie a fișierului valoarea <code>-1</code>
* administratorul magazinului bănuiește că aceasta nu este cea mai eficientă metodă de lucru, dar se mulțumește cu aceasta.

= Exemplul 1: =
<code>bomboaneIN.txt</code>
5
4 2 1 7 1
<code>bomboaneOUT.txt</code>
3
4 3 2
4 5 2
1 2 1

= Explicație =
Se fac <code>3</code> operații:

* se mută <code>2</code> bomboane din cutia <code>4</code> în cutia <code>3</code>. Conținutul cutiilor va fi: <code>4 2 3 5 1</code>
* se mută <code>2</code> bomboane din cutia <code>4</code> în cutia <code>5</code>. Conținutul cutiilor va fi: <code>4 2 3 3 3</code>
* se mută o bomboană din cutia <code>1</code> în cutia <code>2</code>. Conținutul cutiilor va fi: <code>3 3 3 3 3</code>

== Exemplul 2: ==
<code>bomboaneIN.txt</code>
1001
4 2 1 7 1
<code>bomboaneOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
INFILE = "bomboaneIN.txt"
OUTFILE = "bomboaneOUT.txt"

NMAX = 1000 + 1
VALMAX = 1000 + 1

v = [0] * NMAX
p = [0] * NMAX
sol = [[0] * NMAX for _ in range(3)]

def check_constraints(n):
if 1 <= n <= 1000:
return True
else:
with open(OUTFILE, 'w') as outfile:
outfile.write("Datele nu corespund restrictiilor impuse")
return False

with open(INFILE, 'r') as infile:
n = int(infile.readline())

if not check_constraints(n):
exit()

v[1:n + 1] = map(int, infile.readline().split())
p[1:n + 1] = range(1, n + 1)
sum_val = sum(v[1:n + 1])

if sum_val % n != 0:
with open(OUTFILE, 'w') as outfile:
outfile.write("-1")
exit()

ma = sum_val // n
nr = 0

while n > 0:
min_val, max_val = VALMAX, 0
p1, p2 = 0, 0

for i in range(1, n + 1):
if v[i] < min_val:
min_val = v[i]
p1 = i
if v[i] > max_val:
max_val = v[i]
p2 = i

if max_val == ma:
break

v[p2] -= ma - v[p1]
nr += 1
sol[0][nr] = p[p2]
sol[1][nr] = p[p1]
sol[2][nr] = ma - v[p1]
v[p1] += ma - v[p1]

v[0] = 0
for i in range(1, n + 1):
if v[i] != ma:
v[0] += 1
v[v[0]] = v[i]
p[v[0]] = p[i]

n = v[0]

with open(OUTFILE, 'w') as outfile:
outfile.write(f"{nr}\n")
for i in range(1, nr + 1):
outfile.write(f"{sol[0][i]} {sol[1][i]} {sol[2][i]}\n")

</syntaxhighlight>

3919 - Back ME

2024-01-07T11:11:30Z

Rus Marius: Pagină nouă: = Cerința = Se citesc două numere naturale <code>n</code> și <code>m</code>. Afișați în ordine lexicografică toate cuvintele care sunt formate din <code>n</code> litere <code>E</code> și <code>m</code> litere <code>M</code> cu proprietatea că nu există mai mult de două litere <code>M</code> alăturate și nici mai mult de două litere <code>E</code> alăturate. = Date de intrare = Programul citește de la tastatură numerele <code>n</code> și <code>m</code>, sepa...

= Cerința =
Se citesc două numere naturale <code>n</code> și <code>m</code>. Afișați în ordine lexicografică toate cuvintele care sunt formate din <code>n</code> litere <code>E</code> și <code>m</code> litere <code>M</code> cu proprietatea că nu există mai mult de două litere <code>M</code> alăturate și nici mai mult de două litere <code>E</code> alăturate.

= Date de intrare =
Programul citește de la tastatură numerele <code>n</code> și <code>m</code>, separate prin spații.

= Date de ieșire =
Programul va afișa pe ecran pe linii separate cuvintele cerute.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>0 ≤ n ≤ 17</code>, <code>0 ≤ m ≤ 17</code>
* <code>0 ≤ n + m ≤ 28</code>
* Dacă nu există cuvinte care să respecte condițiile, atunci se va afișa <code>IMPOSIBIL</code>.

= Exemplul 1: =
Intrare
3 3
Ieșire
EEMEMM
EEMMEM
EMEEMM
EMEMEM
EMEMME
EMMEEM
EMMEME
MEEMEM
MEEMME
MEMEEM
MEMEME
MEMMEE
MMEEME
MMEMEE

= Exemplul 2: =
Intrare
18 29
Ieșire
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def afisare(v, st, e, m):
for i in range(1, e + m + 1):
print(v[st[i]], end='')
print()

def valid(v, st, k, e, m):
for i in range(1, k - 1):
if v[st[i]] == 'E' and v[st[i + 1]] == 'E' and v[st[i + 2]] == 'E':
return False
if v[st[i]] == 'M' and v[st[i + 1]] == 'M' and v[st[i + 2]] == 'M':
return False
if k == e + m:
E, M = 0, 0
for i in range(1, k + 1):
if v[st[i]] == 'E':
E += 1
else:
M += 1
if E != e or M != m:
return False
return True

def bck(v, st, k, e, m, g):
for i in range(2):
st[k] = i
if valid(v, st, k, e, m):
if k == e + m:
g[0] = 1
afisare(v, st, e, m)
else:
bck(v, st, k + 1, e, m, g)

def check_restrictions(n, m):
if 0 <= n <= 17 and 0 <= m <= 17 and 0 <= n + m <= 28:
return True
else:
print("Datele nu corespund restrictiilor impuse")
return False

def main():
e, m = map(int, input().split())

if not check_restrictions(e, m):
return

v = [''] * 109
st = [0] * 109
g = [0]
v[0], v[1] = 'E', 'M'
bck(v, st, 1, e, m, g)
if g[0] == 0:
print("IMPOSIBIL")

if __name__ == "__main__":
main()
</syntaxhighlight>

3918 - Back Cp

2024-01-07T11:07:58Z

Rus Marius: Pagină nouă: = Cerința = Se citesc două numere naturale <code>n</code> și <code>m</code>. Afișați în ordine lexicografică toate cuvintele care sunt formate din <code>n</code> litere <code>C</code> și <code>m</code> litere <code>P</code> cu proprietatea că nu există nicio literă <code>P</code> cuprinsă între două litere <code>C</code>. = Date de intrare = Programul citește de la tastatură numerele <code>n</code> și <code>m</code>, separate prin spații. = Date de ieșire...

= Cerința =
Se citesc două numere naturale <code>n</code> și <code>m</code>. Afișați în ordine lexicografică toate cuvintele care sunt formate din <code>n</code> litere <code>C</code> și <code>m</code> litere <code>P</code> cu proprietatea că nu există nicio literă <code>P</code> cuprinsă între două litere <code>C</code>.

= Date de intrare =
Programul citește de la tastatură numerele <code>n</code> și <code>m</code>, separate prin spații.

= Date de ieșire =
Programul va afișa pe ecran pe linii separate cuvintele cerute.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>0 ≤ n ≤ 13</code>, <code>0 ≤ m ≤ 13</code>

= Exemplul 1: =
Intrare
3 2
Ieșire
CCCPP
CCPPC
CPPCC
PCCCP
PPCCC

= Exemplul 2: =
Intrare
14 14
Ieșire
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def check_restrictions(n, m):
if 0 <= n <= 13 and 0 <= m <= 13:
return True
else:
print("Datele nu corespund restrictiilor impuse")
return False

def afisare(X, n, m):
result = ""
for i in range(1, n + m + 1):
if X[i] == 0:
result += 'C'
else:
result += 'P'
print(result)

def ok(X, k, n, m):
s = sum(X[1:k+1])
if s > m or k - s > n:
return False
if k > 2 and X[k-2] == 0 and X[k-1] == 1 and X[k] == 0:
return False
return True

def back(X, k, n, m):
for i in range(2):
X[k] = i
if ok(X, k, n, m):
if k == n + m:
afisare(X, n, m)
else:
back(X, k + 1, n, m)

def main():
n, m = map(int, input().split())

if not check_restrictions(n, m):
return

X = [0] * (n + m + 1)
back(X, 1, n, m)

if __name__ == "__main__":
main()

</syntaxhighlight>

3917 - Numere 1234

2024-01-07T11:05:04Z

Rus Marius: Pagină nouă: = Cerința = Se citește <code>n</code> număr natural nenul. Afișați în ordine crescătoare toate numerele care au o cifră egală cu <code>1</code>, două cifre de <code>2</code>, …, <code>n</code> cifre egale cu <code>n</code>. = Date de intrare = Programul citește de la tastatură numărul <code>n</code>. = Date de ieșire = Programul va afișa pe ecran pe linii separte numerele cerute.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Da...

= Cerința =
Se citește <code>n</code> număr natural nenul. Afișați în ordine crescătoare toate numerele care au o cifră egală cu <code>1</code>, două cifre de <code>2</code>, …, <code>n</code> cifre egale cu <code>n</code>.

= Date de intrare =
Programul citește de la tastatură numărul <code>n</code>.

= Date de ieșire =
Programul va afișa pe ecran pe linii separte numerele cerute.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 ≤ n ≤ 4</code>

= Exemplul 1: =
Intrare
2
Ieșire
122
212
221

= Exemplul 2: =
Intrare
5
Ieșire
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def afisare(x, m):
for i in range(1, m + 1):
print(x[i], end="")
print()

def valid(x, k, n):
vf = [0] * 5
for i in range(1, k + 1):
vf[x[i]] += 1
for i in range(1, n + 1):
if vf[i] > i:
return False
return True

def backtracking(x, k, n, m):
if k > m:
afisare(x, m)
else:
for i in range(1, n + 1):
x[k] = i
if valid(x, k, n):
backtracking(x, k + 1, n, m)

def check_restriction(n):
return 1 <= n <= 4

def main():
n = int(input())
if not check_restriction(n):
print("Datele nu corespund restrictiilor impuse")
return

m = n * (n + 1) // 2
x = [0] * 11
backtracking(x, 1, n, m)

if __name__ == "__main__":
main()

</syntaxhighlight>

3991 - Modifica Paranteze

2024-01-07T11:00:56Z

Rus Marius: Pagină nouă: = Cerința = Fie un șir de paranteze rotunde, deschise sau închise. Putem efectua de câte ori dorim operația de transformare a unei paranteze deschise într-una închisă sau invers. Să se determine numărul minim de operații necesare transformării secvenței inițiale într-una corect parantezată. Dacă acest lucru nu este posibil, se va afișa <code>-1</code>. = Date de intrare = Programul citește de la tastatură șirul de paranteze rotunde, fără spații. = Da...

= Cerința =
Fie un șir de paranteze rotunde, deschise sau închise. Putem efectua de câte ori dorim operația de transformare a unei paranteze deschise într-una închisă sau invers. Să se determine numărul minim de operații necesare transformării secvenței inițiale într-una corect parantezată. Dacă acest lucru nu este posibil, se va afișa <code>-1</code>.

= Date de intrare =
Programul citește de la tastatură șirul de paranteze rotunde, fără spații.

= Date de ieșire =
Programul va afișa pe ecran numărul minim de operații necesar pentru a transforma șirul într-o secvență corect parantezată. Dacă nu este posibilă parantezarea corectă, se va afișa <code>-1</code>.

= Restricții și precizări =

* <code>1 ≤ numărul de paranteze ≤ 1000</code>

= Exemplul 1: =
Intrare
((((
Ieșire
2

=== Explicație ===
O posibilitate este să modificăm ultimele două paranteze deschise în paranteze închise și să obținem <code>(())</code>.

== Exemplul 2: ==
Intrare
(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((
Ieșire
Datele nu corespund restrictiilor impuse.

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def check_restriction(s):
num_parentheses = s.count('(') + s.count(')')
return 1 <= num_parentheses <= 1000

def nr_min_op(s):
cnt = 0
nr_op = 0
n = len(s)

if not check_restriction(s):
print("Datele nu corespund restrictiilor impuse.")
return -1

if n % 2 == 1:
return -1

for i in range(n):
if s[i] == '(':
cnt += 1
else:
cnt -= 1

if cnt < 0:
nr_op += 1
cnt = 1

nr_op += cnt // 2
return nr_op

if __name__ == "__main__":
s = input("Introduceti un sir cu paranteze: ")

if check_restriction(s):
result = nr_min_op(s)
if result != -1:
print(result)
else:
print("Datele nu corespund restrictiilor impuse.")

</syntaxhighlight>

0205 - Shuffle

2024-01-07T10:21:07Z

Rus Marius: Pagină nouă: = Cerinţa = Se citeşte un număr natural nenul <code>n</code> şi o permutare a mulţimii <code>M={1,2,..,n}</code>. Să se afişeze, în ordine lexicografică, toate permutările mulţimii M care nu conţin elemente alăturate care au fost alăturate şi în permutarea dată. = Date de intrare = Fişierul de intrare <code>shuffleIN.txt</code> conţine pe prima linie numărul <code>n</code>, iar pe a doua linie <code>n</code> valori distincte cuprinse între <code>1</code>...

= Cerinţa =
Se citeşte un număr natural nenul <code>n</code> şi o permutare a mulţimii <code>M={1,2,..,n}</code>. Să se afişeze, în ordine lexicografică, toate permutările mulţimii M care nu conţin elemente alăturate care au fost alăturate şi în permutarea dată.

= Date de intrare =
Fişierul de intrare <code>shuffleIN.txt</code> conţine pe prima linie numărul <code>n</code>, iar pe a doua linie <code>n</code> valori distincte cuprinse între <code>1</code> și <code>n</code>, separate prin câte un spațiu, reprezentând permutarea dată.

= Date de ieşire =
Fişierul de ieşire <code>shuffleOUT.txt</code> va conţine pe fiecare linie elementele unei permutări, separate prin câte un spaţiu.

= Restricţii şi precizări =

* <code>0 < n < 9</code>
* dacă nu există soluţii se va afişa pe prima linie a fişierului de ieşire mesajul <code>nu exista</code>

= Exemplul 1: =
<code>shuffleIN.txt</code>
4
2 3 1 4
<code>shuffleOUT.txt</code>
1 2 4 3
3 4 2 1

= Exemplul 2: =
<code>shuffleIN.txt</code>
11
2 3 1 4
<code>shuffleOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def citire():
with open("shuffleIN.txt", "r") as input_file:
n = int(input_file.readline().strip())
v = [0] + list(map(int, input_file.readline().split()))
return n, v

def prim(num):
if num < 2:
return False
if num % 2 == 0 and num != 2:
return False
for i in range(3, int(num**0.5) + 1, 2):
if num % i == 0:
return False
return True

def sortare(n, v):
for i in range(1, n):
for j in range(i + 1, n + 1):
if not prim(v[i]) and not prim(v[j]) and v[i] > v[j]:
v[i], v[j] = v[j], v[i]

def puncte_fixe(n, v):
x = [0] * (n + 1)
for i in range(1, n + 1):
if prim(v[i]):
x[i] = i
return x

def afisare(n, v, x, output_file):
result = [v[x[i]] for i in range(1, n + 1) if x[i] != 0]
output_file.write(" ".join(map(str, result)) + "\n")

def valid(k, x):
for i in range(1, k):
if x[i] == x[k]:
return False
return True

def backtracking(k, n, v, x, output_file):
if k > n:
afisare(n, v, x, output_file)
else:
if prim(v[k]):
backtracking(k + 1, n, v, x, output_file)
else:
for i in range(1, n + 1):
if not prim(v[i]):
x[k] = i
if valid(k, x):
backtracking(k + 1, n, v, x, output_file)

def verifica_restrictii(n):
if 0 < n < 9:
return True
else:
with open("shuffleOUT.txt", "w") as output_file:
output_file.write("Datele nu corespund restrictiilor impuse\n")
return False

def main():
n, v = citire()

if verifica_restrictii(n):
sortare(n, v)
x = puncte_fixe(n, v)

with open("shuffleOUT.txt", "w") as output_file:
backtracking(1, n, v, x, output_file)

if __name__ == "__main__":
main()

</syntaxhighlight>

1327 - SirPIE

2024-01-07T10:04:37Z

Rus Marius: Pagină nouă: = Cerinţa = Se citeşte un număr natural nenul <code>n</code>, apoi <code>n</code> numere naturale distincte. Să se afişeze, în ordine lexicografică, șirurile din cele <code>n</code> valori cu proprietatea că oricare două valori învecinate sunt prime între ele. = Date de intrare = Fişierul de intrare <code>sirpieIN.txt</code>conţine pe prima linie numărul <code>n</code>, iar pe a doua linie <code>n</code> numere naturale. = Date de ieşire = Fişierul de ieşi...

= Cerinţa =
Se citeşte un număr natural nenul <code>n</code>, apoi <code>n</code> numere naturale distincte. Să se afişeze, în ordine lexicografică, șirurile din cele <code>n</code> valori cu proprietatea că oricare două valori învecinate sunt prime între ele.

= Date de intrare =
Fişierul de intrare <code>sirpieIN.txt</code>conţine pe prima linie numărul <code>n</code>, iar pe a doua linie <code>n</code> numere naturale.

= Date de ieşire =
Fişierul de ieşire <code>sirpieOUT.txt</code> va conţine pe fiecare linie elementele unei șir, separate prin câte un spaţiu.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricţii şi precizări =

* <code>1 ≤ n < 10</code>
* cele <code>n</code> numere de pe a doua linie a fişierului de intrare sunt mai mici decât <code>10000</code>

= Exemplul 1: =
<code>sirpieIN.txt</code>
4
8 6 7 9
<code>sirpieOUT.txt</code>
6 7 8 9
6 7 9 8
8 9 7 6
9 8 7 6

= Exemplul 2: =
<code>sirpieIN.txt</code>
11
8 6 7 9
<code>sirpieOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def check_constraints(n, v, fout):
if not (1 <= n < 10):
fout.write("Datele nu corespund restrictiilor impuse\n")
return False

for num in v:
if not (1 <= num < 10000):
fout.write("Datele nu corespund restrictiilor impuse\n")
return False

return True

def gcd(a, b):
while b:
a, b = b, a % b
return a

def afisare_sol(sol, fout):
fout.write(" ".join(map(str, sol)) + "\n")

def back(k, prev, fout):
if k == n:
afisare_sol(sol, fout)
else:
for i in range(n):
if not folosit[i] and gcd(v[i], prev) == 1:
sol[k] = v[i]
folosit[i] = True
back(k + 1, v[i], fout)
folosit[i] = False

if __name__ == "__main__":
with open("sirpieIN.txt", "r") as fin, open("sirpieOUT.txt", "w") as fout:
n = int(fin.readline().strip())
v = list(map(int, fin.readline().split()))

if not check_constraints(n, v, fout):
# Exit if constraints are not met
exit()

sol = [0] * n
folosit = [False] * n

# Sorting
v.sort()

back(0, 1, fout)

</syntaxhighlight>

1666 – Arbrush

2024-01-07T09:32:08Z

Rus Marius: Pagină nouă: == Enunț == Eșuând în a-și regăsi adevărata identitate, Brush se refugiază în magicul tărâm al arborilor. Arbotra o sună și îi dă următoarea problemă: se dă un arbore cu <code>N</code> noduri, o rădăcină fixată, și <code>M</code> întrebări de forma: câte perechi neordonate de noduri pot forma, luând noduri doar din subarborele nodului <code>X</code> (inclusiv pe <code>X</code>). = Cerința = Ajutați-o pe Brush să răspundă cât mai repede la int...

== Enunț ==
Eșuând în a-și regăsi adevărata identitate, Brush se refugiază în magicul tărâm al arborilor. Arbotra o sună și îi dă următoarea problemă: se dă un arbore cu <code>N</code> noduri, o rădăcină fixată, și <code>M</code> întrebări de forma: câte perechi neordonate de noduri pot forma, luând noduri doar din subarborele nodului <code>X</code> (inclusiv pe <code>X</code>).

= Cerința =
Ajutați-o pe Brush să răspundă cât mai repede la intrebările lui Arbotra.

= Date de intrare =
Fișierul de intrare <code>arbrushIN.txt</code> va conține pe prima linie trei numere naturale, numărul <code>N</code>, <code>M</code> și <code>Root</code>, separate de un spațiu. Următoarele <code>N-1</code> linii vor conține două numere naturale <code>a</code> și <code>b</code> (între <code>1</code> și <code>N</code>), separate de un spațiu, cu semnificația că există muchie între nodurile <code>a</code> și <code>b</code>. Ultima linie a fișierului de intrare (linia <code>N+1</code>) va conține <code>M</code> numere separate de căte un spațiu, acestea vor semnifica cele <code>M</code> întrebari cerute de Arbotra.

= Date de ieșire =
Fișierul de ieșire <code>arbrushOUT.txt</code> va conține <code>M</code> linii, aflându-se răspunsul la fiecare întrebare cerută (în ordinea cerută în fișierul de intrare).În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>2 ≤ N, M ≤ 27040</code>
* <code>1 ≤ Root ≤ N</code>
* Uituc de fel, Arbotra poate pune aceeași întrebare de mai multe ori.

= Exemplul 1: =
<code>arbrushIN.txt</code>
8 4 1
1 2
2 3
2 5
5 6
6 7
6 8
1 4
6 4 5 2
<code>arbrushOUT.txt</code>
3
0
6
15

=== Explicație ===
Pentru prima întrebare, răspunsul este <code>3</code>, deoarece în subarborele nodului <code>6</code> există <code>3</code> noduri: <code>6</code>, <code>7</code>, <code>8</code>, cu care pot forma perechile <code>{6, 7}</code>, <code>{7, 8}</code>, <code>{6, 8}</code>

Pentru a doua întrebare răspunsul este <code>0</code>, deoarece subarborele lui <code>4</code> are doar un nod, pe el înșusi și nu se pot forma perechi de câte două noduri.

Pentru a treia întrebare răspunsul este 6, deoarece în subarborele nodului <code>5</code> există <code>4</code> noduri: <code>5</code>, <code>6</code>, <code>7</code>, <code>8</code>, perechile formate sunt <code>{6, 8}</code>, <code>{5, 6}</code>, <code>{7, 8}</code>, <code>{5, 8}</code>, <code>{5, 7}</code>, <code>{6, 7}</code>

Pentru a patra întrebare răspunsul este <code>15</code>.

== Exemplul 2: ==
<code>arbrushIN.txt</code>
27041 4 1
1 2
2 3
2 5
5 6
6 7
6 8
1 4
6 4 5 2
<code>arbrushOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
Nmax = 27040 + 1
Mmax = 27040 + 1

def check_restrictions(N, M, Root):
if not (2 <= N <= 27040) or not (2 <= M <= 27040) or not (1 <= Root <= N):
with open("arbrushOUT.txt", "w") as file_out:
file_out.write("Datele nu corespund restrictiilor impuse\n")
return False
return True

def DFS(x):
global Viz, D, Tree
Viz[x] = True
D[x] = 1
for y in Tree[x]:
if not Viz[y]:
DFS(y)
D[x] += D[y]

def main():
global N, M, Root, D, Tree, Viz
with open("arbrushIN.txt", "r") as file_in:
N, M, Root = map(int, file_in.readline().split())
if not check_restrictions(N, M, Root):
return

Tree = [[] for _ in range(Nmax)]
D = [0] * Nmax
Viz = [False] * Nmax

for _ in range(N - 1):
a, b = map(int, file_in.readline().split())
Tree[a].append(b)
Tree[b].append(a)

DFS(Root)

questions = list(map(int, file_in.readline().split()))

with open("arbrushOUT.txt", "w") as file_out:
for x in questions:
file_out.write(str((D[x] * (D[x] - 1)) // 2) + '\n')

if __name__ == "__main__":
main()

</syntaxhighlight>

3944 - Turn 1

2024-01-07T09:19:35Z

Rus Marius: Pagină nouă: == Enunț == Se consideră <code>n</code> cuburi numerotate de la <code>1</code> la <code>n</code> pentru care se cunosc latura și culoarea. Să se genereze toate turnurile de înălțime <code>H</code> ce se pot forma cu cele <code>n</code> cuburi, astfel încât fiecare turn să respecte următoarele condiții: * orice cub se așează peste un altul ce are latura mai mare sau egală cu a lui; * să nu existe două cuburi consecutive de aceeași culoare; = Date de intrare...

== Enunț ==
Se consideră <code>n</code> cuburi numerotate de la <code>1</code> la <code>n</code> pentru care se cunosc latura și culoarea. Să se genereze toate turnurile de înălțime <code>H</code> ce se pot forma cu cele <code>n</code> cuburi, astfel încât fiecare turn să respecte următoarele condiții:

* orice cub se așează peste un altul ce are latura mai mare sau egală cu a lui;
* să nu existe două cuburi consecutive de aceeași culoare;

= Date de intrare =
Fișierul de intrare <code>turn_1IN.txt</code> conține pe prima linie două numere naturale <code>n</code> și <code>H</code>, iar pe următoarele <code>n</code> linii descrierea cuburilor. Linia <code>i+1</code> conține descrierea cubului <code>i</code> sub forma: ''latură culoare''.

= Date de ieșire =
Fișierul de ieșire <code>turn_1OUT.txt</code> va conține soluțiile generate în ordinea lexicografică a indicilor. O soluție este validă dacă conține descrierea indicilor cuburilor care alcătuiesc turnul de înălțime <code>H</code>.

= Restricții și precizări =

* <code>1 ≤ n < 15</code>
* <code>1 ≤ H ≤ 50</code>
* <code>1 ≤ latura ≤ 10</code>
* <code>culorile sunt șiruri de caractere cu cel mult 20 de litere și sunt scrise cu litere mici</code>
* nu există cuburi identice
* pentru datele de intrare există întotdeauna soluție

= Exemplu 1: =
<code>turn_1IN.txt</code>
5 5
1 alb
2 alb
1 roz
2 roz
3 alb
<code>turn_1OUT.txt</code>
2 4 1
4 2 3
5 3 1
5 4

=== Explicație ===
Primul turn este format din cuburile: <code>2 (2,alb), 4 (2,roz), 1 (1,alb)</code>.

Al doilea turn este format din cuburile: <code>4 (2,roz), 2 (2,alb), 3 (1,roz)</code>

etc.

== Exemplu 2: ==
<code>turn_1IN.txt</code>
16 5
1 alb
2 alb
1 roz
2 roz
3 alb
<code>turn_1OUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def afisare(b):
non_zero_values = [value for value in b if value != 0]
fout.write(" ".join(map(str, non_zero_values)) + '\n')

def verif(k):
if k > 1:
if col[b[k]] == col[b[k-1]]:
return False
if lat[b[k]] > lat[b[k-1]]:
return False
return True

def verifica_restrictii(n, h, lat, col):
if not (1 <= n < 15 and 1 <= h <= 50):
fout.write("Datele nu corespund restrictiilor impuse\n")
return False

for i in range(1, n + 1):
if not (1 <= lat[i] <= 10 and 1 <= len(col[i]) <= 20 and col[i].islower()):
fout.write("Datele nu corespund restrictiilor impuse\n")
return False

return True

def bkt(k, sp):
for i in range(1, n+1):
if viz[i] == 0:
b[k] = i
viz[i] = 1
sp += lat[b[k]]
if sp <= h and verif(k):
if sp == h:
afisare(b[:k+1])
else:
bkt(k+1, sp)
sp -= lat[b[k]]
viz[i] = 0

if __name__ == "__main__":
with open("turn_1IN.txt", 'r') as fin, open("turn_1OUT.txt", 'w') as fout:
n, h = map(int, fin.readline().split())
lat = [0] * 105
b = [0] * 105
sp = 0
viz = [0] * 105
col = [""] * 105

for i in range(1, n+1):
line = fin.readline().split()
if len(line) < 2:
fout.write("Datele nu corespund restrictiilor impuse\n")
exit()

lat_str, col[i] = line
lat[i] = int(lat_str)

if not verifica_restrictii(n, h, lat, col):
exit()

bkt(1, sp)

</syntaxhighlight>

2109 - Dineu

2024-01-07T09:06:18Z

Rus Marius: Pagină nouă: == Enunț == La un dineu participă reprezentanţii mai multor state. Fiecare reprezentant cunoaşte un număr de limbi străine. Doi reprezentanţi vor putea discuta direct dacă există cel puţin o limbă pe care o înţeleg amândoi. Organizatorii dineului doresc să existe cel puţin o masă la care să nu fie nevoie de translator, astfel oricare două persoane care stau la această masă să se înţeleagă direct. = Cerința = Cunoscând <code>N</code> – numărul de...

== Enunț ==
La un dineu participă reprezentanţii mai multor state. Fiecare reprezentant cunoaşte un număr de limbi străine. Doi reprezentanţi vor putea discuta direct dacă există cel puţin o limbă pe care o înţeleg amândoi. Organizatorii dineului doresc să existe cel puţin o masă la care să nu fie nevoie de translator, astfel oricare două persoane care stau la această masă să se înţeleagă direct.

= Cerința =
Cunoscând <code>N</code> – numărul de reprezentanţi, identificăm fiecare reprezentant cu un număr natural cuprins între <code>1</code> şi <code>N</code>, <code>L</code> – numărul limbilor străine care se vorbesc la dineu (acestea sunt codificate prin numerele naturale de la <code>1</code> la <code>L</code>), numărul de limbi vorbite de fiecare reprezentant şi codurile acestora să se determine numărul maxim de persoane care pot sta la o masa fără translator.

= Date de intrare =
Fişierul de intrare <code>dineuIN.txt</code> conţine, pe prima linie, numerele naturale <code>N</code> şi <code>L</code>, separate printr-un spaţiu, cu semnificaţia de mai sus. Pe fiecare dintre următoarele <code>N</code> linii se află informaţii despre câte un reprezentant, în ordinea numerelor de identificare a acestora. Astfel, pe linia corespunzătoare reprezentantului <code>i (1≤i≤N)</code>, se află un număr natural <code>nri</code>- numărul limbilor străine vorbite de acesta, urmat de <code>nri</code> numere naturale distincte <code>l1 l2 ... lnri</code>, reprezentând codurile acestora. Numerele de pe aceeaşi linie sunt separate prin câte un spaţiu.

= Date de ieșire =
Fişierul de ieşire <code>dineuOUT.txt</code> va conţine două linii. Pe prima linie se află numărul maxim de reprezentanţi care stau la aceeaşi masă. Pe a doua linie se află numerele de identificare ale acestora. Numerele de pe aceeaşi linie sunt separate prin câte un spaţiu.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =
• <code>1 <= N <= 20</code>

• <code>1 <= L <= 10</code>

• <code>1 <= nri, l1, l2, ..., lnri <= 10</code>

• Dacă există mai multe soluţii se va afişa cea mai mică din punct de vedere lexicografic

= Exemplul 1: =
<code>dineuIN.txt</code>
5 5
3 1 3 5
2 3 4
3 1 2 4
2 4 5
2 2 3
<code>dineuOUT.txt</code>
4
1 2 3 4

=== Explicație ===
1 cu 2 vorbesc în limba 3

1 cu 4 vorbesc în limba 5

1 cu 3 vorbesc în limba 1

2 cu 4 vorbesc în limba 4

2 cu 3 vorbesc în limba 4

3 cu 4 vorbesc în limba 4

există şi alte soluţii, de exemplu soluţia 1 2 3 5, dar este mai mare din punct de vedere lexicografic

== Exemplul 1: ==
<code>dineuIN.txt</code>
21 5
3 1 3 5
2 3 4
3 1 2 4
2 4 5
2 2 3
<code>dineuOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verificare_restrictii(n, l, limbi):
if not (1 <= n <= 20) or not (1 <= l <= 10):
return False

for i in range(1, n + 1):
k = sum(limbi[i])
if not (1 <= k <= 10):
return False

return True

def main():
nMAX = 20
lMAX = 10

# Deschide fișierele pentru citire și scriere
with open("dineuIN.txt", "r") as fin, open("dineuOUT.txt", "w") as fout:
try:
n, l = map(int, fin.readline().split())
except ValueError:
fout.write("Datele nu corespund restrictiilor impuse")
return

limbi = [[0] * (lMAX + 1) for _ in range(nMAX + 1)]

for i in range(1, n + 1):
try:
data = list(map(int, fin.readline().split()))

# Verifică dacă linia citită conține suficiente elemente
if len(data) < 2:
fout.write("Datele nu corespund restrictiilor impuse")
return

k = data[0]
for j in range(1, k + 1):
if j < len(data):
limbi[i][data[j]] = 1
else:
fout.write("Datele nu corespund restrictiilor impuse")
return
except ValueError:
fout.write("Datele nu corespund restrictiilor impuse")
return

# Verifică restricțiile
if not verificare_restrictii(n, l, limbi):
fout.write("Datele nu corespund restrictiilor impuse")
return

dp = [0] * (1 << nMAX)
solmax = []

dp[0] = 1
for mask in range(1, (1 << n)):
i = 0
while not (mask & 1 << i):
i += 1

oldmask = mask ^ 1 << i
if dp[oldmask]:
okkk = True
for j in range(n):
if oldmask & 1 << j:
ok = False
for k in range(1, l + 1):
if limbi[j + 1][k] and limbi[i + 1][k]:
ok = True
break

if not ok:
okkk = False
break

dp[mask] = okkk

if dp[mask]:
sz = bin(mask).count('1')

if sz == len(solmax):
ok = False
k = 0
for j in range(n):
if mask & 1 << j:
if ok:
solmax[k] = j + 1
else:
if j + 1 < solmax[k]:
solmax[k] = j + 1
ok = True
elif j + 1 > solmax[k]:
break
k += 1

elif sz > len(solmax):
solmax = [j + 1 for j in range(n) if mask & 1 << j]

# Scrie rezultatele în fișierul de ieșire
fout.write(f"{len(solmax)}\n")
fout.write(" ".join(map(str, solmax)))

if __name__ == "__main__":
main()

</syntaxhighlight>

1979 - Rb Tree

2024-01-07T08:45:53Z

Rus Marius: Pagină nouă: == Enunț == Gigel se joacă cu un graf orientat cu <code>N</code> noduri. Inițial toate nodurile grafului sunt transparente, dar lui Gigel îi place schimbarea. Fire ambițioasă, el colorează unele noduri în roșu, altele în negru, iar pe celelalte în alb (probabil din cauza crizei de vopsea colorată din 2017). Gigel recrutează o armată de furnici pe care o așează în nodul <code>1</code>, cu el în fruntea lor și se hotărăște să cucerească graful.În fieca...

== Enunț ==
Gigel se joacă cu un graf orientat cu <code>N</code> noduri. Inițial toate nodurile grafului sunt transparente, dar lui Gigel îi place schimbarea. Fire ambițioasă, el colorează unele noduri în roșu, altele în negru, iar pe celelalte în alb (probabil din cauza crizei de vopsea colorată din 2017).

Gigel recrutează o armată de furnici pe care o așează în nodul <code>1</code>, cu el în fruntea lor și se hotărăște să cucerească graful.În fiecare moment, Gigel poate trimite un număr de furnici din orice nod <code>X</code> (în care se află deja furnici) în vecinii lui <code>X</code>, cu condiția ca cel puțin o furnică să rămână în nodul <code>X</code>. Excepție de la această regulă face nodul <code>1</code>, cel în care se află Gigel, unde nu este obligatoriu să rămână furnici.

Dacă într-un nod se află Gigel sau cel puțin o furnică, atunci acel nod se numește ocupat. Graful este cucerit atunci când Gigel a ocupat cel puțin un nod roșu și cel puțin un nod negru.

= Cerința =
Sa se determine numărul minim de furnici pentru ca Gigel să cucerească graful.

= Date de intrare =
Fișierul de intrare <code>rbtreeIN.txt</code> conține pe prima linie trei numere naturale: <code>N</code> – reprezentând numărul de noduri ale grafului, <code>R</code> – reprezentând numărul nodurilor de culoare roșie și <code>B</code> – reprezentând numărul nodurilor de culoare neagră.

A doua linie conține <code>R</code> numere distincte <code>r1</code>, <code>r2</code>, …, <code>rR</code>, reprezentând nodurile roșii.

A treia linie conține <code>B</code> numere distincte <code>b1</code>, <code>b2</code>, …, <code>bB</code>, reprezentând nodurile negre.

Următoarele <code>N</code> linii descriu nodurile grafului împreună cu vecinii lor. Pe linia <code>i+3</code> se află vecinii nodului <code>i</code> și este formată din:

- un număr <code>P</code>, reprezentând numărul de vecini ai nodului <code>i</code>

- <code>P</code> numere distincte <code>n1</code>, <code>n2</code>, <code>…</code> , <code>nP</code> reprezentând vecinii nodului

= Date de ieșire =
Fișierul de ieșire <code>rbtreeOUT.txt</code> va conține o singură linie pe care se află numărul minim de furnici pentru ca Gigel să cucerească graful. În cazul în care graful nu poate fi cucerit, se va afișa mesajul <code>impossible</code>.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>2 ≤ N ≤ 100.000</code>
* <code>1 ≤ R < N</code>
* <code>1 ≤ B < N</code>
* <code>1 ≤ ri ≤ N</code>, pentru oricare <code>i</code>, <code>1 ≤ i ≤ R</code>
* <code>1 ≤ bi ≤ N</code>, pentru oricare <code>i</code>, <code>1 ≤ i ≤ B</code>
* <code>0 ≤ P ≤ 10</code>
* <code>1 ≤ ni ≤ N</code>, pentru oricare <code>1 ≤ i ≤ P</code>
* Se garantează că un nod are o singură culoare. Dacă un nod nu este roșu sau negru, atunci este alb.
* Gigel rămâne tot timpul în nodul <code>1</code>, deci nodul <code>1</code> este ocupat.

= Exemplul 1: =
<code>rbtreeIN.txt</code>
3 1 1
2
3
1 2
2 3 1
1 1
<code>rbtreeOUT.txt</code>
2

= Exemplul 2: =
<code>rbtreeIN.txt</code>
100001 1 1
2
3
1 2
2 3 1
1 1
<code>rbtreeOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
from collections import deque

INF = 99999999
NR = 100005

def check_restrictions(n, RED, BLACK, red_nodes, black_nodes, p_values):
if not (2 <= n <= 100000 and 1 <= RED < n and 1 <= BLACK < n):
return "Datele nu corespund restrictiilor impuse"

for x in red_nodes + black_nodes:
if not (1 <= x <= n):
return "Datele nu corespund restrictiilor impuse"

for ni in p_values:
if not (1 <= ni <= n):
return "Datele nu corespund restrictiilor impuse"

return None # All restrictions are satisfied

def BFS(q, dist, graph):
while q:
k = q.popleft()
for x in graph[k]:
if dist[x] > dist[k] + 1:
dist[x] = dist[k] + 1
q.append(x)

def process_input(filename):
try:
with open(filename, "r") as f:
n, RED, BLACK = map(int, f.readline().split())

restriction_result = check_restrictions(n, RED, BLACK, [], [], [])
if restriction_result:
return restriction_result

redQueue = deque()
blackQueue = deque()
rootQueue = deque()
v = [[] for _ in range(NR)]
vt = [[] for _ in range(NR)]

redDist = [INF] * NR
blackDist = [INF] * NR
rootDist = [INF] * NR

line = list(map(int, f.readline().split()))
for i in range(RED):
x = line[i]
redDist[x] = 0
redQueue.append(x)

line = list(map(int, f.readline().split()))
for i in range(BLACK):
x = line[i]
blackDist[x] = 0
blackQueue.append(x)

for i in range(1, n + 1):
line = list(map(int, f.readline().split()[1:]))
for x in line:
v[i].append(x)
vt[x].append(i)

rootDist[1] = 0
rootQueue.append(1)

BFS(redQueue, redDist, vt)
BFS(blackQueue, blackDist, vt)
BFS(rootQueue, rootDist, v)

minn = INF
for i in range(1, n + 1):
minn = min(minn, redDist[i] + blackDist[i] + rootDist[i])

if minn == INF:
return "impossible\n"
else:
return str(minn) + "\n"

except Exception as e:
return str(e)

def main():
input_filename = "rbtreeIN.txt"
output_filename = "rbtreeOUT.txt"

result = process_input(input_filename)

with open(output_filename, "w") as g:
g.write(result)

if __name__ == "__main__":
main()

</syntaxhighlight>

1497 - Nunta

2024-01-07T08:31:31Z

Rus Marius: Pagină nouă: == Enunț == La o nuntă sunt invitate <code>n</code> persoane, numerotate de la <code>1</code> la <code>n</code>. Se știe că o parte din ele se cunosc două câte două, fie că sunt rude, fie de la serviciu, fie sunt prieteni sau vecini. Astfel se vor forma un număr <code>K</code> minim de grupuri astfel încât în fiecare grup, fiecare persoană să aibă cel puţin un cunoscut. Pentru fiecare grup de cel puțin două persoane se stabileşte un lider – persoana cu nu...

== Enunț ==
La o nuntă sunt invitate <code>n</code> persoane, numerotate de la <code>1</code> la <code>n</code>. Se știe că o parte din ele se cunosc două câte două, fie că sunt rude, fie de la serviciu, fie sunt prieteni sau vecini. Astfel se vor forma un număr <code>K</code> minim de grupuri astfel încât în fiecare grup, fiecare persoană să aibă cel puţin un cunoscut. Pentru fiecare grup de cel puțin două persoane se stabileşte un lider – persoana cu numărul de ordine minim. Aceste grupuri vor fi numerotate de la <code>1</code> la <code>K</code> în ordinea crescătoare a numerelor de ordine ale liderilor. Ca sa se ivească cât mai puține situații stânjenitoare, organizatorul nunții ar dori să aranjeze o masă principală cu cel puţin <code>n/2+1</code> invitaţi, la care să fie aşezate unul sau mai multe astfel de grupuri întregi numerotate cu valori consecutive.

= Cerința =
Fiind date <code>n</code>, numărul de persoane, <code>m</code>, numărul de perechi de invitaţi care se cunosc între ei și cele <code>m</code> perechi, să se determine numărul <code>K</code> minim de grupuri formate din cel puțin doi invitați astfel încât, în fiecare grup, fiecare persoană să aibă cel puţin un cunoscut, precum şi numărul variantelor distincte în care se poate organiza masa cu cel puţin <code>n/2+1</code> invitaţi din grupurile formate.

= Date de intrare =
Fișierul de intrare <code>nuntaIN.txt</code> conține pe prima linie două numere naturale separate prin spațiu <code>n</code> și <code>m</code>, <code>n</code> reprezentând numărul de invitaţi, respectiv <code>m</code> numărul de perechi de invitaţi care se cunosc între ei. Pe fiecare din următoarele <code>m</code> linii se află câte două numere naturale <code>x</code> și <code>y</code>, <code>1≤x</code>, <code>y≤n</code>, separate printr-un spațiu, cu semnificația că invitaţii <code>x</code> și <code>y</code> se cunosc între ei.

= Date de ieșire =
Fișierul de ieșire <code>nuntaOUT.txt</code> va conține pe prima linie un număr natural <code>g</code> reprezentând numărul minim de grupuri formate din cel puțin doi invitați astfel încât, în fiecare grup, fiecare persoană să aibă cel puţin un cunoscut. Pe cea de a doua linie va fi scris un număr natural <code>v</code> reprezentând numărul variantelor distincte în care se poate organiza masa cu cel puţin <code>n/2+1</code> invitaţi din grupurile formate.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>0 < n <= 20000</code>
* <code>0 < m <= 100000</code>

= Exemplul 1: =
<code>nuntaIN.txt</code>
31 6
5 7
2 3
10 14
14 6
9 15
7 30
<code>nuntaOUT.txt</code>
4
0

=== Explicație ===
Grupurile formate din cel puțin doi invitați sunt : <code>(2,3)</code>, <code>(5,7,30)</code>, <code>(6,10,14)</code>, <code>(9,15)</code>, deci <code>K=4</code>. Ele nu sunt suficiente pentru a forma o masă cu cel puţin <code>16</code> invitaţi, deci sunt <code>0</code> variante de aranjare.

== Exemplul 1: ==
<code>nuntaIN.txt</code>
20001 6
5 7
2 3
10 14
14 6
9 15
7 30
<code>nuntaOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
from collections import namedtuple

nMAX = 20000

class Component:
def __init__(self):
self.min = float('inf')
self.cnt = 0

components = [Component() for _ in range(nMAX + 1)]
gf = [[] for _ in range(nMAX + 1)]
viz = [0] * (nMAX + 1)

def check_constraints(n, m):
if not (0 < n <= 20000) or not (0 < m <= 100000):
with open("nuntaOUT.txt", "w") as fout:
fout.write("Datele nu corespund restrictiilor impuse")
return False
return True

def dfs(nod, fil):
viz[nod] = fil
for nex in gf[nod]:
if not viz[nex]:
dfs(nex, fil)

def main():
global nMAX
global gf
global viz
global components

with open("nuntaIN.txt", "r") as fin:
n, m = map(int, fin.readline().split())

if not check_constraints(n, m):
return

with open("nuntaOUT.txt", "w") as fout:
for _ in range(m):
a, b = map(int, fin.readline().split())
gf[a].append(b)
gf[b].append(a)

fil = 0
for i in range(1, n + 1):
if not viz[i]:
fil += 1
dfs(i, fil)

for i in range(1, n + 1):
components[i].min = float('inf')

for i in range(1, n + 1):
components[viz[i]].min = min(components[viz[i]].min, i)
components[viz[i]].cnt += 1

components = sorted(components[1:fil + 1], key=lambda x: (x.cnt == 1, x.min))

while components[fil - 1].cnt == 1:
fil -= 1

fout.write(str(fil) + '\n')

dr = 0
s = 0
ne = 0
for st in range(1, fil + 1):
while dr + 1 <= fil and s + components[dr].cnt < n // 2 + 1:
s += components[dr].cnt
dr += 1

if s + components[dr].cnt < n // 2 + 1:
break

ne += fil - dr
s -= components[st - 1].cnt

fout.write(str(ne))

if __name__ == "__main__":
main()

</syntaxhighlight>

2261 - Turn

2024-01-06T22:12:06Z

== Enunț ==
Se consideră <code>n</code> cuburi numerotate de la <code>1</code> la <code>n</code> pentru care se cunosc latura și culoarea. Să se genereze toate turnurile de înălțime <code>H</code> ce se pot forma cu cele <code>n</code> cuburi, astfel încât fiecare turn să respecte următoarele condiții:

* orice cub se așează peste un altul ce are latura mai mare sau egală cu a lui;
* să nu existe două cuburi consecutive de aceeași culoare;

= Date de intrare =
Fișierul de intrare <code>turnIN.txt</code> conține pe prima linie două numere naturale <code>n</code> și <code>H</code>, iar pe următoarele <code>n</code> linii descrierea cuburilor. Linia <code>i+1</code> conține descrierea cubului <code>i</code> sub forma: ''latură culoare''.

= Date de ieșire =
Fișierul de ieșire <code>turnOUT.txt</code> va conține soluțiile generate în ordinea lexicografică a indicilor. O soluție este validă dacă conține descrierea indicilor cuburilor care alcătuiesc turnul de înălțime <code>H</code>.

= Restricții și precizări =

* <code>1 ≤ n < 15</code>
* <code>1 ≤ H ≤ 50</code>
* <code>1 ≤ latura ≤ 10</code>
* <code>1 ≤ culoare ≤ 5</code>
* nu există cuburi identice
* pentru datele de intrare există întotdeauna soluție

= Exemplul 1: =
<code>turnIN.txt</code>
5 5
1 1
2 1
1 2
2 2
3 1
<code>turnOUT.txt</code>
2 4 1
4 2 3
5 3 1
5 4

=== Explicație ===
Primul turn este format din cuburile: <code>2 (2,1), 4 (2,2), 1 (1,1)</code>.

Al doilea turn este format din cuburile: <code>4 (2,2), 2 (2,1), 3 (1,2)</code>

etc.

== Exemplul 1: ==
<code>turnIN.txt</code>
16 5
1 1
2 1
1 2
2 2
3 1
<code>turnOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def afis(k, st, out):
out.write(" ".join(map(str, st[1:k + 1])) + '\n')

def vef(k, st, v):
if v[st[k]]['y'] == v[st[k - 1]]['y']:
return False
if v[st[k]]['x'] > v[st[k - 1]]['x']:
return False
return True

def back(k, suma, st, uz, v, h, out):
for i in range(1, len(v) + 1):
if not uz[i]:
uz[i] = 1
st[k] = i
suma += v[st[k]]['x']
if k == 1 or (vef(k, st, v) and suma <= h):
if suma == h:
afis(k, st, out)
else:
back(k + 1, suma, st, uz, v, h, out)
uz[i] = 0
suma -= v[st[k]]['x']

def check_constraints(n, h, v):
if not (1 <= n < 15 and 1 <= h <= 50):
return False

for i in range(1, n + 1):
if not (1 <= v[i]['x'] <= 10 and 1 <= v[i]['y'] <= 5):
return False

return True

def main():
with open("turnIN.txt", "r") as f_in, open("turnOUT.txt", "w") as f_out:
n, h = map(int, f_in.readline().split())
v = {}
for i in range(1, n + 1):
line = f_in.readline().split()
if len(line) < 2:
f_out.write("Datele nu corespund restrictiilor impuse\n")
return
x, y = map(int, line)
v[i] = {'x': x, 'y': y}

if not check_constraints(n, h, v):
f_out.write("Datele nu corespund restrictiilor impuse\n")
else:
st = [0] * 1010
uz = [0] * 101
back(1, 0, st, uz, v, h, f_out)

if __name__ == "__main__":
main()

</syntaxhighlight>

1136 - Dragoni

2024-01-06T22:05:33Z

Rus Marius: Pagină nouă: == Enunț == Supărați că lansarea părții a treia a filmului lor preferat s-a amânat până în iunie 2018, Henry și Hetty s-au gândit la propriul scenariu pentru finalul trilogiei: Într-o lume în care vikingii pot zbura cu dragonii există <code>N</code> insule. Hiccup, șeful tribului de vikingi aflat pe insula <code>1</code>, știe <code>M</code> rute directe de zbor bidirecționale între insule. Pentru fiecare <code>j</code> intre <code>1</code> si <code>M</cod...

== Enunț ==
Supărați că lansarea părții a treia a filmului lor preferat s-a amânat până în iunie 2018, Henry și Hetty s-au gândit la propriul scenariu pentru finalul trilogiei:

Într-o lume în care vikingii pot zbura cu dragonii există <code>N</code> insule. Hiccup, șeful tribului de vikingi aflat pe insula <code>1</code>, știe <code>M</code> rute directe de zbor bidirecționale între insule. Pentru fiecare <code>j</code> intre <code>1</code> si <code>M</code>, ruta <code>j</code> unește insulele <code>Aj</code> și <code>Bj</code> și are lungime <code>Dj</code>.

Pe fiecare insulă <code>i</code>, (<code>1 ≤ i ≤ n</code>) există dragoni din specia <code>i</code> care pot zbura fără a se opri pentru odihnă o distanță maximă <code>Dmaxi</code>. Cu alte cuvinte, dragonii de pe insula <code>i</code> vor putea parcurge orice rută <code>j</code>, (<code>1 ≤ j ≤ m</code>) pentru care <code>Dj ≤ Dmaxi</code>, indiferent de ce alte drumuri au făcut anterior.

Hiccup dorește să ajungă de pe insula <code>1</code> pe insula <code>N</code> pentru a-l salva pe Toothless, dragonul lui. Pentru a ajunge acolo, el va lua inițial un dragon din specia <code>1</code> (de pe insula <code>1</code>). Apoi, dacă la un moment dat Hiccup se află pe o insula <code>i</code>, (<code>1 ≤ i ≤ n</code>) având cu el un dragon din specia <code>t</code>, el poate:

# Să zboare de pe insula <code>i</code> pe o altă insulă <code>x</code> cu dragonul pe care îl are, folosind o rută directă <code>j</code> între insulele <code>i</code> si <code>x</code>, bineînțeles doar dacă <code>Dj ≤ Dmaxt</code>.
# Să schimbe dragonul din specia <code>t</code> pe care îl are cu un dragon din specia <code>i</code> aflat pe insula respectivă.

= Cerințe =
a. Să se determine distanța maxima <code>Dmaxi</code> caracteristică unui dragon la care Hiccup poate ajunge fără a schimba dragonul pe care l-a luat inițial de pe insula <code>1</code>.

b. Să se determine distanța minimă pe care Hiccup trebuie să o parcurgă pentru a ajunge de pe insula <code>1</code> pe insula <code>N</code>.

= Date de intrare =
Fișierul de intrare <code>dragoniIN.txt</code> conține pe prima linie numărul <code>p</code>. Pentru toate testele de intrare, numărul <code>p</code> poate avea doar valoarea <code>1</code> sau valoarea <code>2</code>. Pe a doua linie se găsesc două numere naturale <code>N</code> și <code>M</code> reprezentând numărul de insule, respectiv numărul de rute directe între insule. Pe a treia linie se găsesc <code>N</code> numere naturale, al <code>i</code>-lea dintre acestea reprezentând distanta maximă <code>Dmaxi</code> pe care o poate zbura un dragon de pe insula <code>i</code>. Pe următoarele <code>M</code> linii sunt descrise cele <code>M</code> rute directe. Pe fiecare dintre aceste linii se găsesc câte trei numere naturale <code>A</code>, <code>B</code> și <code>D</code> cu semnificația că există rută bidirecțională de lungime <code>D</code> între insulele <code>A</code> și <code>B</code>.

= Date de ieșire =
n fișierul de ieșire <code>dragoniOUt.txt</code> se va afișa un singur număr natural.

Dacă valoarea lui <code>p</code> este <code>1</code>, se rezolvă numai cerința a.

În acest caz numărul afișat va reprezenta distanța maximă <code>Dmaxi</code> a unui dragon <code>i</code> la care Hiccup poate ajunge fără a schimba dragonul pe care l-a luat inițial de pe insula <code>1</code>.

Daca valoarea lui <code>p</code> este <code>2</code>, se va rezolva numai cerința b,

În acest caz numărul afișat va reprezenta distanța minima pe care Hiccup trebuie să o parcurgă pentru a ajunge de pe insula <code>1</code> pe insula <code>N</code>.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 ≤ N ≤ 800</code>
* <code>1 ≤ M ≤ 6000</code>
* <code>1 ≤ Dmaxi ≤ 50 000</code>, pentru orice <code>1 ≤ i ≤ N</code>.
* <code>1 ≤ Aj, Bj ≤ N</code>, pentru orice <code>1 ≤ j ≤ M</code>.
* <code>1 ≤ Dj ≤ 50 000</code>, pentru orice <code>1 ≤ j ≤ M</code>.
* Se garantează că Hiccup poate ajunge pe insula <code>N</code>.
* Se garantează că răspunsul oricărei cerințe este un număr natural mai mic decât <code>109</code>.
* Pentru rezolvarea corectă a primei cerințe se acordă 20% din punctajul testului respectiv.
* Pentru rezolvarea corectă a celei de-a doua cerințe se acordă 80% din punctajul testului respectiv.

= Exemplul 1: =
<code>dragoniIN.txt</code>
1
5 6
6 3 13 20 26
1 2 5
1 3 7
1 5 10
2 3 6
3 4 5
3 5 14
<code>dragoniOUt.txt</code>
20

= Explicație =
<code>p = 1</code> deci se va rezolva cerința a).

Există <code>N = 5</code> insule si <code>M = 6</code> rute între ele. Hiccup pornește de pe insula <code>1</code> având un dragon care poate zbura o distanță de maxim <code>6</code>. Cu acest dragon poate ajunge doar pe insulele <code>1</code>, <code>2</code>, <code>3</code> si <code>4</code>, întrucât pentru a ajunge pe insula <code>5</code> el ar fi obligat sa parcurgă o ruta de lungime mai mare decât <code>6</code>.

Distanta maxima pe care o poate zbura un dragon aflat pe insulele <code>1</code>, <code>2</code>, <code>3</code> sau <code>4</code> este deci <code>20</code> (dragonul de pe insula <code>4</code>). Se observă că dragonul care poate zbura o distanță de <code>26</code> se afla pe insula 5 și este inaccesibil.

== Exemplul 2: ==
<code>dragoniIN.txt</code>
1
801 6
6 3 13 20 26
1 2 5
1 3 7
1 5 10
2 3 6
3 4 5
3 5 14
<code>dragoniOUt.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
import heapq

class Dij:
def __init__(self, nod, cost):
self.nod = nod
self.cost = cost

def __lt__(self, other):
return self.cost > other.cost

def validate_restrictions(n, m, dmax):
if not (1 <= n <= 800 and 1 <= m <= 6000):
return False

for i in range(1, n + 1):
if not (1 <= dmax[i] <= 50000):
return False

return True

with open("dragoniIN.txt", "r") as fin, open("dragoniOUT.txt", "w") as fout:
p = int(fin.readline())

if p == 1:
n, m = map(int, fin.readline().split())
dmax = [0] + list(map(int, fin.readline().split()))

if not validate_restrictions(n, m, dmax):
fout.write("Datele nu corespund restrictiilor impuse\n")
exit()

gf = [[] for _ in range(n + 1)]

for _ in range(m):
a, b, c = map(int, fin.readline().split())
if not (1 <= a <= n and 1 <= b <= n and 1 <= c <= 50000):
fout.write("Datele nu corespund restrictiilor impuse\n")
exit()
gf[a].append((b, c))
gf[b].append((a, c))

q = []
max_val = dmax[1]
viz = [False] * (n + 1)
viz[1] = True
q.append(1)

while q:
nod = q.pop(0)

for nex in gf[nod]:
if nex[1] <= dmax[1] and not viz[nex[0]]:
viz[nex[0]] = True
max_val = max(max_val, dmax[nex[0]])
q.append(nex[0])

fout.write(str(max_val) + "\n")

elif p == 2:
n, m = map(int, fin.readline().split())
dmax = [0] + list(map(int, fin.readline().split()))

if not validate_restrictions(n, m, dmax):
fout.write("Datele nu corespund restrictiilor impuse\n")
exit()

cost = [[float('inf')] * (n + 1) for _ in range(n + 1)]
costmin = [[float('inf')] * (n + 1) for _ in range(n + 1)]
gf = [[] for _ in range(n + 1)]

for _ in range(m):
a, b, c = map(int, fin.readline().split())
if not (1 <= a <= n and 1 <= b <= n and 1 <= c <= 50000):
fout.write("Datele nu corespund restrictiilor impuse\n")
exit()
gf[a].append((b, c))
gf[b].append((a, c))

for i in range(1, n + 1):
pq = []
heapq.heappush(pq, Dij(i, 0))
cost[i][i] = 0

while pq:
cur = heapq.heappop(pq)
nod, costc = cur.nod, cur.cost

if costc < cost[i][nod]:
continue

for nex in gf[nod]:
if nex[1] <= dmax[i] and costc + nex[1] < cost[i][nex[0]]:
cost[i][nex[0]] = costc + nex[1]
heapq.heappush(pq, Dij(nex[0], cost[i][nex[0]]))

class Stare:
def __init__(self, nod, cost, dragon):
self.nod = nod
self.cost = cost
self.dragon = dragon

q = []
q.append(Stare(1, 0, 1))
costfinalmin = float('inf')
costmin[1][1] = 0

while q:
cur = q.pop(0)
nod, costc, dragon = cur.nod, cur.cost, cur.dragon

if costc > costmin[dragon][nod]:
continue

for nex in gf[nod]:
if nex[1] <= dmax[dragon]:
nexcost = costc + nex[1]
nexdrag = dragon
if dmax[nex[0]] > dmax[dragon]:
nexdrag = nex[0]
elif dmax[nex[0]] == dmax[dragon]:
nexdrag = min(dragon, nex[0])

if nexcost >= costmin[nexdrag][nex[0]]:
continue

costmin[nexdrag][nex[0]] = nexcost
q.append(Stare(nex[0], nexcost, nexdrag))

costfinalmin = min(costfinalmin, costmin[nexdrag][nex[0]] + cost[nexdrag][nex[0]])

fout.write(str(costfinalmin) + "\n")

</syntaxhighlight>

2165 - Graf 1

2024-01-06T21:39:45Z

Rus Marius: Pagină nouă: == Enunț == Se știe că într-un graf neorientat conex, între oricare două vârfuri există cel putin un lanț iar lungimea unui lanț este egală cu numărul muchiilor care-l compun. Definim noțiunea lanț optim între două vârfuri <code>X</code> și <code>Y</code> ca fiind un lanț de lungime minimă care are ca extremități vârfurile <code>X</code> și <code>Y</code>. Este evident că între oricare două vârfuri ale unui graf conex vom avea unul sau mai multe la...

== Enunț ==
Se știe că într-un graf neorientat conex, între oricare două vârfuri există cel putin un lanț iar lungimea unui lanț este egală cu numărul muchiilor care-l compun. Definim noțiunea lanț optim între două vârfuri <code>X</code> și <code>Y</code> ca fiind un lanț de lungime minimă care are ca extremități vârfurile <code>X</code> și <code>Y</code>. Este evident că între oricare două vârfuri ale unui graf conex vom avea unul sau mai multe lanțuri optime, depinzând de configurația grafului.

= Cerința =
Fiind dat un graf neorientat conex cu <code>N</code> vârfuri etichetate cu numerele de ordine <code>1</code>, <code>2</code>, …, <code>N</code> și două vârfuri ale sale notate <code>X</code> și <code>Y</code> (<code>1 ≤ X, Y ≤ N</code>, <code>X≠Y</code> ), se cere să scrieți un program care determină vârfurile care aparțin tuturor lanțurilor optime dintre <code>X</code> și <code>Y</code>.

= Date de intrare =
Fișierul de intrare <code>graf1.in</code> conține pe prima linie patru numere naturale reprezentând: <code>N</code> (numărul de vârfuri ale grafului), <code>M</code> (numărul de muchii), <code>X</code> și <code>Y</code> (cu semnificația din enunț). Pe următoarele <code>M</code> linii câte două numere naturale nenule <code>A[i], B[i]</code> (<code>1 ≤ A[i], B[i] ≤ N</code>, <code>A[i] ≠ B[i]</code>, pentru <code>1 ≤ i ≤ M</code> ) fiecare dintre aceste perechi de numere reprezentând câte o muchie din graf.

= Date de ieșire =
Fișierul de ieșire <code>graf1.out</code> va conține pe prima linie, numărul de vârfuri comune tuturor lanțurilor optime dintre <code>X</code> și <code>Y</code>; pe a doua linie, numerele corespunzătoare etichetelor acestor vârfuri, dispuse în ordine crescătoare; între două numere consecutive de pe această linie se va afla câte un spațiu.

= Restricții și precizări =

* <code>2 ≤ N ≤ 7500</code>
* <code>1 ≤ M ≤ 14000</code>

= Exemplul 1: =
<code>graf1.in</code>
6 7 1 4
1 2
1 3
1 6
2 5
3 5
5 6
5 4
<code>graf1.out</code>
3
1 4 5

= Exemplul 2: =
<code>graf1.in</code>
7501 7 1 4
1 2
1 3
1 6
2 5
3 5
5 6
5 4
<code>graf1.out</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
from collections import deque

def check_constraints(n, m):
return 2 <= n <= 7500 and 1 <= m <= 14000

def bfs(start, dist, E):
for i in range(1, n + 1):
dist[i] = float('inf')

q = deque([start])
dist[start] = 0

while q:
nn = q.popleft()
for i in E[nn]:
if dist[i] == float('inf'):
dist[i] = dist[nn] + 1
q.append(i)

if __name__ == "__main__":
with open("graf1IN.txt", "r") as f:
n, m, x, y = map(int, f.readline().split())

if not check_constraints(n, m):
with open("graf1OUT.txt", "w") as g:
g.write("Datele nu corespund restrictiilor impuse")
exit()

E = [[] for _ in range(n + 1)]

for _ in range(m):
a, b = map(int, f.readline().split())
E[a].append(b)
E[b].append(a)

dist1 = [0] * (n + 1)
dist2 = [0] * (n + 1)
fr = [0] * (n + 1)
rez = []

bfs(x, dist1, E)
bfs(y, dist2, E)

for i in range(1, n + 1):
if dist1[i] + dist2[i] == dist1[y]:
fr[dist1[i]] += 1

for i in range(1, n + 1):
if dist1[i] != float('inf') and dist2[i] != float('inf') and dist1[y] != float('inf'):
if dist1[i] + dist2[i] == dist1[y] and fr[dist1[i]] == 1:
rez.append(i)

with open("graf1OUT.txt", "w") as g:
if rez:
g.write(str(len(rez)) + '\n')
g.write(" ".join(map(str, rez)))
else:
g.write("Nu exista noduri care sa corespunda conditiilor.")

</syntaxhighlight>

1118 - Clepsidra

2024-01-06T21:26:53Z

Rus Marius: Pagină nouă: Un graf conex cu <code>N</code> noduri și <code>M</code> muchii poate fi privit ca o clepsidră cu centrul în nodul <code>X</code>, <code>1 ≤ X ≤ N</code>, dacă putem împărți toate nodurile, mai puțin nodul <code>X</code>, în două submulțimi nevide astfel încât orice drum de la un nod dintr-o mulțime la un nod din cealaltă mulțime trece prin nodul <code>X</code>. Voi trebuie să determinați numărul de moduri distincte în care putem privi graful ca o cle...

Un graf conex cu <code>N</code> noduri și <code>M</code> muchii poate fi privit ca o clepsidră cu centrul în nodul <code>X</code>, <code>1 ≤ X ≤ N</code>, dacă putem împărți toate nodurile, mai puțin nodul <code>X</code>, în două submulțimi nevide astfel încât orice drum de la un nod dintr-o mulțime la un nod din cealaltă mulțime trece prin nodul <code>X</code>. Voi trebuie să determinați numărul de moduri distincte în care putem privi graful ca o clepsidră pentru fiecare din cele <code>N</code> noduri alese drept centru, modulo <code>666013</code>. Două moduri se consideră distincte dacă cele două submulțimi aferente sunt diferite. Ordinea submulțimilor într-un mod este relevantă, dar ordinea nodurilor în cadrul unei mulțimi nu este. Spre exemplu, soluțiile <code>({1,2,3}, {4,5})</code> şi <code>({4,5}, {1,2,3})</code> sunt distincte, dar soluţiile <code>({4,5}, {1,2,3})</code> şi <code>({4,5}, {1,3,2})</code> nu sunt distincte.

= Date de intrare =
Fișierul de intrare <code>clepsidra.in</code> conține pe prima linie două numere naturale, <code>N</code> și <code>M</code>, reprezentând numărul de noduri, respectiv numărul de muchii din graf. Pe următoarele <code>M</code> linii se vor afla câte două numere naturale separate prin câte un spaţiu, reprezentând câte o muchie.

= Date de ieșire =
Fișierul de ieșire <code>clepsidra.out</code> va conține <code>N</code> linii. A <code>i</code>-a linie, <code>1 ≤ i ≤ N</code>, va conține numărul de moduri în care putem privi graful ca o clepsidră cu centrul în nodul <code>i</code>, modulo <code>666013</code>.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>2 ≤ N ≤ 200 002</code>
* <code>1 ≤ M ≤ 250 002</code>
* Pentru 40% din teste avem restricţiile <code>2 ≤ N ≤ 1002</code> și <code>1 ≤ M ≤ 1502</code>.
* Atentie! Graful este conex.

= Exemplul 1: =
<code>clepsidra.in</code>
6 7
4 3
1 3
5 4
4 1
3 2
1 5
5 6
<code>clepsidra.out</code>
0
0
2
0
2
0

= Explicație =
Pentru nodul cu indicele <code>3</code>, soluţiile sunt: <code>({2}, {1,4,5,6})</code> și <code>({1,4,5,6}, {2})</code>

Pentru nodul cu indicele <code>5</code>, soluţiile sunt: <code>({6}, {1,2,3,4})</code> și <code>({1,2,3,4},{6})</code>

== Exemplul 2: ==
<code>clepsidra.in</code>
200200 213
4 3
1 3
5 4
4 1
3 2
1 5
5 6
<code>clepsidra.out</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
MOD = 666013

def power(x, y):
rez = 1
while y > 0:
if y % 2 == 1:
rez = (rez * x) % MOD
x = (x * x) % MOD
y = y // 2
return rez % MOD

def check_constraints(n, m):
if 2 <= n <= 200002 and 1 <= m <= 250002:
return True
else:
with open("clepsidraOUT.txt", 'w') as out:
out.write("Datele nu corespund restrictiilor impuse\n")
return False

def dfs(nc):
global niv, nmin, nrfii, tati, viz, a, r

viz[nc] = 1
niv[nc] = niv[tati[nc]] + 1
nmin[nc] = niv[nc]
for nv in a[nc]:
if viz[nv] == 0:
tati[nv] = nc
dfs(nv)
nmin[nc] = min(nmin[nc], nmin[nv])
if nc != r and nmin[nv] >= niv[nc]:
nrfii[nc] += 1

elif tati[nc] != nv:
nmin[nc] = min(nmin[nc], niv[nv])

def main():
global niv, nmin, nrfii, tati, viz, a, r

with open("clepsidraIN.txt", 'r') as f:
n, m = map(int, f.readline().split())

if not check_constraints(n, m):
return

a = [[] for _ in range(n + 1)]
for _ in range(m):
x, y = map(int, f.readline().split())
a[x].append(y)
a[y].append(x)

r = 1
niv = [0] * (n + 1)
nmin = [0] * (n + 1)
nrfii = [0] * (n + 1)
tati = [0] * (n + 1)
viz = [0] * (n + 1)

dfs(r)

with open("clepsidraOUT.txt", 'w') as out:
if nrfii[r] > 1:
out.write(str((power(2, nrfii[r]) + MOD - 2) % MOD) + "\n")
else:
out.write("0\n")

for i in range(2, n + 1):
if nrfii[i] == 0:
out.write("0\n")
else:
out.write(str((power(2, nrfii[i] + 1) + MOD - 2) % MOD) + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

3364 - Unire

2024-01-06T21:10:54Z

Rus Marius: Pagină nouă: = Cerința = Gigel are un graf cu <code>n</code> noduri și <code>m</code> muchii, care nu este conex. El dorește să afle răspunsul la două întrebări: 1) Care este numărul minim de muchii ce trebuie ađugate astfel încât graful să devină conex? 2) Dacă costul adăugării unei muchii între nodurile <code>a</code> și <code>b</code> este <code>a + b</code>, care este costul total minim al muchiilor care trebuie adăugate astfel încât graful să devină conex?...

= Cerința =
Gigel are un graf cu <code>n</code> noduri și <code>m</code> muchii, care nu este conex. El dorește să afle răspunsul la două întrebări:

1) Care este numărul minim de muchii ce trebuie ađugate astfel încât graful să devină conex?

2) Dacă costul adăugării unei muchii între nodurile <code>a</code> și <code>b</code> este <code>a + b</code>, care este costul total minim al muchiilor care trebuie adăugate astfel încât graful să devină conex?

= Date de intrare =
Fișierul de intrare <code>unireIN.txt</code> conține pe prima linie numerele <code>n</code> și <code>m</code>, pe a doua linie conține numărul <code>c</code>, reprezentând numărul cerinței <code>1 ≤ c ≤ 2</code>, iar pe următoarele <code>m</code> linii se află muchiile grafului <code>a b</code>, <code>1 ≤ a, b ≤ n</code>, <code>a ≠ b</code>.

= Date de ieșire =
Fișierul de ieșire <code>unireOUT.txt</code> va conține pe prima linie numărul <code>S</code>, reprezentând răspunsul cerut de Gigel.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 ≤ n ≤ 100000</code>, <code>0 ≤ m < n-1</code>
* Pentru teste în valoare de <code>30</code> de puncte, cerința va fi <code>1</code>.
* Pentru teste în valoare de <code>40</code> de puncte, <code>1 ≤ n ≤ 1000</code>.

= Exemplul 1: =
<code>unireIN.txt</code>
6 3
1
1 2
3 4
5 6
<code>unireOUT.txt</code>
2

= Exemplul 2: =
<code>unireIN.txt</code>
1000001 3
1
1 2
3 4
5 6
<code>unireOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def check_restrictions(n, m):
return not (1 <= n <= 100000 and 0 <= m < n - 1)

def dfs(v, c, C, G):
C[v] = c
for i in G[v]:
if not C[i]:
dfs(i, c, C, G)

def main():
with open("unireIN.txt", "r") as input_file, open("unireOUT.txt", "w") as output_file:
n, m = map(int, input_file.readline().split())

if check_restrictions(n, m):
output_file.write("Datele nu corespund restrictiilor impuse\n")
return

c = int(input_file.readline().strip())

G = [[] for _ in range(100001)]
C = [0] * 100001
nc = 0
f = [0] * 100001
s = 0

for _ in range(m):
x, y = map(int, input_file.readline().split())
G[x].append(y)
G[y].append(x)

for i in range(1, n + 1):
if not C[i]:
nc += 1
dfs(i, i, C, G)

if c == 1:
output_file.write(str(nc - 1) + "\n")
else:
C.sort()
for i in range(2, n + 1):
if C[1] != C[i] and f[C[i]] == 0:
s += (C[1] + C[i])
f[C[i]] += 1

output_file.write(str(s) + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

1691 - Arbore 1

2024-01-06T20:55:00Z

Rus Marius: Pagină nouă: = Cerința = Se dă un arbore (graf conex aciclic) cu <code>N</code> noduri. Vrem să eliminăm noduri (împreună cu muchiile adiacente) din arborele dat, astfel încât numărul de componente conexe ale grafului rămas să fie maxim. Aflați care este numărul maxim de componente conexe pe care le putem obține și câte submulțimi distincte de noduri se pot elimina din arbore astfel încât să rămână la final acest număr maxim de componente conexe. = Date de intrare...

= Cerința =
Se dă un arbore (graf conex aciclic) cu <code>N</code> noduri. Vrem să eliminăm noduri (împreună cu muchiile adiacente) din arborele dat, astfel încât numărul de componente conexe ale grafului rămas să fie maxim. Aflați care este numărul maxim de componente conexe pe care le putem obține și câte submulțimi distincte de noduri se pot elimina din arbore astfel încât să rămână la final acest număr maxim de componente conexe.

= Date de intrare =
Fișierul de intrare <code>arbore1IN.txt</code> conține pe prima linie numărul natural <code>N</code>, reprezentând numărul de noduri ale arborelui. Pe următoarele <code>N-1</code> linii se vor afla câte două numere <code>X</code> și <code>Y</code>, cu semnificația că există o muchie între nodurile <code>X</code> și <code>Y</code>.

= Date de ieșire =
Fișierul de ieșire <code>arbore1OUT.txt</code> va conține pe prima linie două numere naturale reprezentând numărul maxim de componente conexe pe care îl putem obține, respectiv numărul de moduri în care putem obține acest număr de componente conexe modulo <code>10^9+7</code> (adică restul împărțirii acestui număr la <code>1000000007</code>).În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 ≤ N ≤ 100 000</code>
* Se acordă 40% din punctajul unui test dacă numărul maxim de componente conexe este corect.
* Se acordă 60% din punctajul unui test dacă numărul de moduri este corect.
* Pentru 20% din teste <code>N ≤ 20</code>
* Pentru alte 30% din teste <code>N ≤ 1000</code>

= Exemplul 1: =
<code>arbore1IN.txt</code>
6
1 2
1 3
1 4
4 5
4 6
<code>arbore1OUT.txt</code>
4 1

=== Explicație ===
Se șterg nodurile <code>1</code> și <code>4</code>. Nicio altă submulțime de noduri șterse nu produce <code>4</code> sau mai multe componente conexe.

== Exemplul 2 ==
<code>arbore1IN.txt</code>
100001
1 2
1 3
1 4
4 5
4 6
<code>arbore1OUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
from collections import defaultdict

N = 100100
mod = 1000000007

v = defaultdict(list)
D = [[0] * N for _ in range(3)]
W = [[1] * N for _ in range(3)]

def check_constraints(n):
if not (1 <= n <= 100000):
with open("arbore1OUT.txt", "w") as output_file:
output_file.write("Datele nu corespund restrictiilor impuse")
exit()

def dfs(x, p):
D[1][x] = 1
D[0][x] = 0
D[2][x] = 1
W[1][x] = 1
W[0][x] = 1
W[2][x] = 1

for it in v[x]:
if it != p:
dfs(it, x)

# Cazul 1. Stergem nodul
for it in v[x]:
if it != p:
D[0][x] += D[2][it]
W[0][x] *= W[2][it]
W[0][x] %= mod

# Cazul 2. Nu stergem nodul
for it in v[x]:
if it != p:
if D[0][it] + 1 == D[1][it]:
W[1][x] *= (W[0][it] + W[1][it]) % mod
W[1][x] %= mod
D[1][x] += D[0][it]
elif D[0][it] + 1 < D[1][it]:
W[1][x] *= W[1][it]
W[1][x] %= mod
D[1][x] += D[1][it] - 1
else:
W[1][x] *= W[0][it]
W[1][x] %= mod
D[1][x] += D[0][it]

# Calculam solutia pentru acest subarbore stiind cele 2 cazuri
D[2][x] = max(D[1][x], D[0][x])
if D[1][x] == D[0][x]:
W[2][x] = (W[1][x] + W[0][x]) % mod
elif D[1][x] > D[0][x]:
W[2][x] = W[1][x]
else:
W[2][x] = W[0][x]

def main():
with open("arbore1IN.txt", "r") as input_file:
n = int(input_file.readline().strip())
check_constraints(n)

for _ in range(n-1):
x, y = map(int, input_file.readline().strip().split())
v[x].append(y)
v[y].append(x)

dfs(1, 0)

with open("arbore1OUT.txt", "w") as output_file:
output_file.write(f"{D[2][1]} {W[2][1]}")

if __name__ == "__main__":
main()

</syntaxhighlight>

1825 - Zoomba

2024-01-06T20:37:24Z

Rus Marius: Pagină nouă: = Enunț = În țara Zoomba trăiesc <code>K</code> prieteni, fiecare în localități diferite. În această țară se găsesc <code>N</code> orașe, oricare două fiind legate prin cel mult o șosea bidirecțională. Deoarece nu s-au mai întâlnit de mult, cei <code>K</code> prieteni s-au hotărât să se reîntâlnească într-un oraș. Fiecare are câte o mașină cu număr nelimitat de locuri. Pentru a trece de la un oraș la altul, o mașină consumă <code>1</code> li...

= Enunț =
În țara Zoomba trăiesc <code>K</code> prieteni, fiecare în localități diferite. În această țară se găsesc <code>N</code> orașe, oricare două fiind legate prin cel mult o șosea bidirecțională. Deoarece nu s-au mai întâlnit de mult, cei <code>K</code> prieteni s-au hotărât să se reîntâlnească într-un oraș. Fiecare are câte o mașină cu număr nelimitat de locuri. Pentru a trece de la un oraș la altul, o mașină consumă <code>1</code> litru de benzină.

= Cerința =
Știind că odată ce au ajuns în același oraș <code>2</code> sau mai mulți prieteni, aceștia iși pot continua drumul cu o singură mașină, să se determine consumul minim de benzină pentru ca aceștia să ajungă în orașul <code>Z</code>.

= Date de intrare =
Fișierul de intrare <code>zoombaIN.txt</code> conține pe prima linie numerele <code>N</code>, <code>M</code>(numărul de șosele), <code>K</code> și <code>Z</code>. Pe următoarea linie se află <code>K</code> numere, reprezentând pozițiile inițiale ale celor <code>K</code> prieteni. Pe următoarele <code>M</code> linii se află câte o pereche <code>i j</code>, cu semnificația că există șosea de la orașul <code>i</code> la orașul <code>j</code>.

= Date de ieșire =
Fișierul de ieșire <code>zoombaOUt.txt</code> va conține pe prima linie numărul <code>C</code>, ce va fi egal cu consumul minim de combustibil necesar ca cei <code>K</code> prieteni să se întâlnească în orașul <code>Z</code>, sau <code>-1</code> în cazul în care aceștia nu pot ajunge în el.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 ≤ Z ≤ N ≤ 200</code>
* <code>1 ≤ K ≤ min(N,10)</code>

= Exemplul 1: =
<code>zoombaIN.txt</code>
5 4 3 5
1 2 3
1 4
2 4
3 4
4 5
<code>zoombaOUt.txt</code>
4

= Exemplul 2: =
<code>zoombaIN.txt</code>
201 4 3 5
1 2 3
1 4
2 4
3 4
4 5
<code>zoombaOUt.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
from collections import deque
import sys

def check_constraints(n, k, z):
if not (1 <= z <= n <= 200 and 1 <= k <= min(n, 10)):
with open('zoombaOUT.txt', 'w') as fout:
fout.write("Datele nu corespund restrictiilor impuse\n")
sys.exit()

def main():
kmax = 10
nmax = 203
inf = int(1e9)

def lee(v):
while coada:
k = coada.popleft()
for i in range(len(g[k])):
if dp[g[k][i]][v] > dp[k][v] + 1:
dp[g[k][i]][v] = dp[k][v] + 1
coada.append(g[k][i])

def construct(l):
ret = 0
i = 0
while l:
ret ^= (1 << i)
i += 1
l -= 1
return ret

def nbiti(x):
k = 0
while x:
k += (x & 1)
x >>= 1
return k

# Redirect input and output to files
sys.stdin = open('zoombaIN.txt', 'r')
sys.stdout = open('zoombaOUT.txt', 'w')

n, m, k, z = map(int, input().split())

# Check constraints and exit if not met
check_constraints(n, k, z)

a = list(map(int, input().split()))
g = [[] for _ in range(nmax)]
dp = [[inf] * (1 << (kmax + 1)) for _ in range(nmax)]
coada = deque()

for _ in range(m):
i, j = map(int, input().split())
g[i].append(j)
g[j].append(i)

for i in range(k):
dp[a[i]][1 << i] = 0
coada.append(a[i])
lee(1 << i)

for l in range(2, k + 1):
for j in range(construct(l), (1 << k)):
if nbiti(j) == l:
for i in range(1, n + 1):
for c in range(1, j):
if (j | c) == j:
dp[i][j] = min(dp[i][j], dp[i][c] + dp[i][j ^ c])
coada.append(i)
lee(j)

result = dp[z][(1 << k) - 1] if dp[z][(1 << k) - 1] != inf else -1
print(result)

# Close the files
sys.stdin.close()
sys.stdout.close()

if __name__ == "__main__":
main()

</syntaxhighlight>

2041 - Camelot

2024-01-06T20:32:36Z

Rus Marius: Pagină nouă: = Cerința = Regele Arthur – Inimă de Leu, vrea să adune la castel toţi cavalerii ''Mesei Rotunde'' pentru a hotărî împreună soarta regatului. Dar cavalerii nu se află toţi în ''Camelot'' şi durează un timp până vor ajunge la castel din pădurea care înconjoară castelul. Harta pădurii are forma unei matrici, cu <code>m</code> linii şi <code>n</code> coloane. Pentru fiecare cavaler care nu este în ''Camelot'' se cunosc coordonatele <code>x y</code>, repre...

= Cerința =
Regele Arthur – Inimă de Leu, vrea să adune la castel toţi cavalerii ''Mesei Rotunde'' pentru a hotărî împreună soarta regatului. Dar cavalerii nu se află toţi în ''Camelot'' şi durează un timp până vor ajunge la castel din pădurea care înconjoară castelul.

Harta pădurii are forma unei matrici, cu <code>m</code> linii şi <code>n</code> coloane. Pentru fiecare cavaler care nu este în ''Camelot'' se cunosc coordonatele <code>x y</code>, reprezentând linia şi coloana din matrice în care se află iniţial cavalerul. Toţi cavalerii pornesc simultan spre castel, iar fiecare cavaler se deplasează după regula de deplasare a calului de la jocul de şah.

Cunoscând dimensiunile <code>mxn</code> ale matricei, coordonatele castelului şi cele ale cavalerilor, se cere să se determine:

1. numărul minim de mutări după care va ajunge la castel unul dintre cavaleri

2. numărul minim de mutări după care toţi cavalerii se vor afla la castel.

De exemplu, în imaginea de mai sus este reprezentată harta sub forma unei matrici de tip <code>8x8</code>, iar castelul are coordonatele <code>4 5</code> (linia <code>4</code> şi coloana <code>5</code>), primul cavaler se află iniţial în punctul de coordonate <code>1 2</code> iar cel de al doilea în punctul <code>8 1</code>. Primul cavaler va ajunge la castel din minim <code>2</code> deplasări, iar al doilea după minim <code>4</code> mutări Pentru prima întrebare răspunsul este <code>2</code>, iar pentru a doua întrebare răspunsul este <code>4</code>.

= Date de intrare =
Fișierul de intrare <code>camelotIN.txt</code> conține pe prima linie numărul <code>p</code>, pentru toate testele de intrare numărul <code>p</code> putând avea doar valoarea <code>1</code> sau valoarea <code>2</code>.

Pe cea de a doua linie sunt scrise numerele naturale <code>m n k</code>, separate prin câte un spaţiu, iar pe a treia linie se află coordonatele <code>xc yc</code> ale castelului. Pe următoarele <code>k</code> linii se află <code>k</code> perechi de numere întregi <code>x[i] y[i]</code> (<code>1 ≤ i ≤ k</code>), separate prin câte un spaţiu, reprezentând coordonatele cavalerilor.

= Date de ieșire =
Fișierul de ieșire <code>camelotOUT.txt</code> va conține pe prima linie:

* pentru <code>p=1</code>, pe prima linie se va scrie numărul minim de mutări după care va ajunge unul din cavaleri
* pentru <code>p=2</code>, pe prima linie se va scrie numărul minim de mutări după care vor ajunge toţi cavalerii. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>5 ≤ m,n ≤ 1000</code>
* <code>1 ≤ k ≤ 1000</code>
* <code>1 ≤ x[i]</code>, <code>xc ≤ m</code>, <code>1 ≤ y[i]</code>, <code>yc ≤ n</code>, pentru orice <code>1 ≤ i ≤ k</code>
* Eventualele intersecţii ale drumurilor cavalerilor nu influenţează rezultatele
* Pentru datele de test se garantează existenţa unei soluţii

= Exemplul 1: =
<code>camelotIN.txt</code>
1
8 8 2
4 5
1 2
8 1
<code>camelotOUT.txt</code>
2

= Exemplul 2: =
<code>camelotIN.txt</code>
1
1001 8 2
4 5
1 2
8 1
<code>camelotOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
from collections import deque

dx = [-2, -2, -1, -1, 1, 1, 2, 2]
dy = [1, -1, -2, 2, -2, 2, -1, 1]

def inmat(i, j, n, m):
return 1 <= i <= n and 1 <= j <= m

def check_restrictions(n, m, k, c1, c2, positions):
if not (5 <= n <= 1000 and 5 <= m <= 1000):
return "Datele nu corespund restrictiilor impuse"
if not (1 <= k <= 1000):
return "Datele nu corespund restrictiilor impuse"
if not (1 <= c1 <= m and 1 <= c2 <= n):
return "Datele nu corespund restrictiilor impuse"
for x, y in positions:
if not (1 <= x <= m and 1 <= y <= n):
return "Datele nu corespund restrictiilor impuse"
return None

def lee(ir, jr, n, m, b, q):
b[ir][jr] = 1
q.append((ir, jr))

while q:
x, y = q.popleft()
for d in range(8):
ii, jj = x + dx[d], y + dy[d]
if inmat(ii, jj, n, m) and b[ii][jj] == 0:
b[ii][jj] = b[x][y] + 1
q.append((ii, jj))

if __name__ == "__main__":
with open("camelotIN.txt", "r") as fin, open("camelotOUT.txt", "w") as fout:
op = int(fin.readline().strip())
n, m, k = map(int, fin.readline().strip().split())
c1, c2 = map(int, fin.readline().strip().split())

positions = [tuple(map(int, fin.readline().strip().split())) for _ in range(k)]

restriction_error = check_restrictions(n, m, k, c1, c2, positions)
if restriction_error:
fout.write(restriction_error)
else:
a = [[0] * 1001 for _ in range(1001)]
b = [[0] * 1001 for _ in range(1001)]
q = deque()

lee(c1, c2, n, m, b, q)

mini = float('inf')
maxi = 0

for x, y in positions:
if b[x][y] < mini:
mini = b[x][y]
if b[x][y] > maxi:
maxi = b[x][y]

if op == 1:
fout.write(str(mini - 1))
else:
fout.write(str(maxi - 1))

</syntaxhighlight>

4013 - CMGB

2024-01-06T20:22:14Z

Rus Marius: Pagină nouă: == Enunț == Cunoscutul programator Văndămel are la dispoziție o matrice binară cu <code>n</code> linii (numerotate de la <code>1</code> la <code>n</code>) și <code>m</code> coloane (numerotate de la <code>1</code> la <code>m</code>). Văndămel poate efectua, de câte ori e posibil, următoarea operație: alege două poziții vecine pe linie sau pe coloană și care conțin ambele valoarea <code>1</code> și le transformă în <code>0</code>. De exemplu, în matricea:...

== Enunț ==
Cunoscutul programator Văndămel are la dispoziție o matrice binară cu <code>n</code> linii (numerotate de la <code>1</code> la <code>n</code>) și <code>m</code> coloane (numerotate de la <code>1</code> la <code>m</code>). Văndămel poate efectua, de câte ori e posibil, următoarea operație: alege două poziții vecine pe linie sau pe coloană și care conțin ambele valoarea <code>1</code> și le transformă în <code>0</code>. De exemplu, în matricea:

<code>0 1 1 0</code>

<code>1 1 0 0</code>

<code>1 0 0 0</code>

<code>0 1 1 0</code>

el poate alege valorile de <code>1</code> de la pozițiile vecine <code>(1,2)</code> și <code>(2,2)</code>, le transformă în <code>0</code> și obține matricea:

<code>0 0 1 0</code>

<code>1 0 0 0</code>

<code>1 0 0 0</code>

<code>0 1 1 0</code>

= Cerința =
Văndămel știe să rezolve orice problemă, dar vrea să vadă dacă știți și voi să aflați numărul maxim posibil de operații care se pot efectua pe matricea dată.

= Date de intrare =
Programul citește de la tastatură numerele <code>n</code> și <code>m</code> și de pe următoarele <code>n</code> linii câte <code>m</code> numere binare reprezentând valorile din matrice.

= Date de ieșire =
Programul va afișa pe ecran un singur număr natural reprezentând numărul maxim posibil de operații care se pot aplica asupra matricei.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 ≤ n, m ≤ 100</code>

= Exemplul 1: =
Intrare
4 4
0 1 1 0
1 1 0 0
1 0 0 0
0 1 1 0
Ieșire
3

=== Explicație ===
Se efectuează operațiile la <code>(2,1)</code> și <code>(3,1)</code>, la <code>(1,2)</code> și <code>(2,2)</code> și la <code>(4,2)</code> și <code>(4,3)</code>. După efectuarea celor <code>3</code> operații matricea arată astfel:

== Exemplul 2: ==
Intrare
101 101
Ieșire
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
Nmax = 100001

oo = 1 << 28
VI = list[int]

n, m, p, v, im = 0, 0, 0, 0, 0
M = [[0]*202 for _ in range(202)]
A = [[0]*202 for _ in range(202)]
U = [0]*10001
D = [0]*10001
Vis = [False] * Nmax
V = [[] for _ in range(Nmax)]

def check_constraints(n, m):
if not (1 <= n <= 100) or not (1 <= m <= 100):
print("Datele nu corespund restrictiilor impuse")
return False
return True

def cupleaza(v):
if Vis[v]:
return 0

Vis[v] = 1

for x in V[v]:
if not D[x]:
U[v] = x
D[x] = v
return True

for x in V[v]:
if cupleaza(D[x]):
U[v] = x
D[x] = v
return True

return False

def main():
global n, m, p, v, im, M, A, U, D, Vis, V

n, m = map(int, input().split())

if not check_constraints(n, m):
return

for i in range(1, n + 1):
row = list(map(int, input().split()))
for j in range(1, m + 1):
M[i][j] = row[j - 1]

if M[i][j] == 1:
if (i + j) % 2 == 0:
p += 1
A[i][j] = p
else:
im += 1
A[i][j] = im

for i in range(1, n + 1):
for j in range(1, m + 1):
if M[i][j] == 1 and (i + j) % 2 == 0:
if M[i + 1][j]: V[A[i][j]].append(A[i + 1][j])
if M[i][j + 1]: V[A[i][j]].append(A[i][j + 1])
if M[i - 1][j]: V[A[i][j]].append(A[i - 1][j])
if M[i][j - 1]: V[A[i][j]].append(A[i][j - 1])

done = 0
ans = 0

while not done:
done = 1

for i in range(p + 1):
Vis[i] = 0

for i in range(1, p + 1):
if U[i] == 0 and cupleaza(i):
ans += 1
done = 0

print(ans)

if __name__ == "__main__":
main()

</syntaxhighlight>

1601 - Ascensiune

2024-01-06T20:07:10Z

Rus Marius: Pagină nouă: = Cerința = Înainte de a participa la Olimpiada Naționala de Informatică, Zoli s-a decis să se plimbe prin oraș. Orașul în care locuiește Zoli are forma unui arbore, fiecare nod reprezentând o locuință iar deplasarea între acestea se efectuează prin intermediul muchiilor. Zoli dorește să determine lungimea maximă dintre oricare două locuințe din orașul său. = Date de intrare = Fișierul de intrare <code>ascensiuneIN.txt</code> conține pe prima linie nu...

= Cerința =
Înainte de a participa la Olimpiada Naționala de Informatică, Zoli s-a decis să se plimbe prin oraș. Orașul în care locuiește Zoli are forma unui arbore, fiecare nod reprezentând o locuință iar deplasarea între acestea se efectuează prin intermediul muchiilor.

Zoli dorește să determine lungimea maximă dintre oricare două locuințe din orașul său.

= Date de intrare =
Fișierul de intrare <code>ascensiuneIN.txt</code> conține pe prima linie numărul <code>n</code>, numărul de locuințe, iar pe următoarele <code>n-1</code> linii câte două numere naturale <code>a</code>, <code>b</code> separate prin spații, reprezentând posibilitatea de deplasare bidirecțională între două locuințe.

= Date de ieșire =
Fișierul de ieșire <code>ascensiuneOUT.txt</code> va conține pe prima linie un număr natural, reprezentând lungimea dintre cele mai îndepărtate locuințe din oraș.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 ≤ n ≤ 100000</code>
* Pentru 40% dintre teste, <code>1 ≤ n ≤ 1000</code>
* Distanța dintre două locuințe reprezintă numărul minim de locuințe intermediare prin care se poate ajunge de la una la cealaltă, inclusiv locuințele inițiale.

= Exemplul 1: =
<code>ascensiuneIN.txt</code>
8
1 2
1 3
2 4
2 5
3 6
3 7
5 8
<code>ascensiuneOUT.txt</code>
6

=== Explicație ===
Cele mai îndepărtate două locuințe sunt cele cu numărul de ordine 8, respectiv 6 sau 7. Distanța dintre acestea este de 6 locuințe.

== Exemplul 2: ==
<code>ascensiuneIN.txt</code>
1000001
1 2
1 3
2 4
2 5
3 6
3 7
5 8
<code>ascensiuneOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
class TreeDiameter:
def __init__(self, n):
self.n = n
self.G = [[] for _ in range(n + 1)]
self.dist = [0] * (n + 1)
self.viz = [False] * (n + 1)
self.nod_max = 0
self.dmax = 0

def dfs(self, i):
self.viz[i] = True
for p in self.G[i]:
if not self.viz[p]:
self.dist[p] = self.dist[i] + 1
if self.dist[p] > self.dmax:
self.dmax = self.dist[p]
self.nod_max = p
self.dfs(p)

def find_diameter(self):
for i in range(1, self.n):
x, y = map(int, input_file.readline().split())
self.G[x].append(y)
self.G[y].append(x)

self.dist[1] = 1
self.dfs(1)

for i in range(1, self.n + 1):
self.dist[i] = 0
self.viz[i] = False

self.dist[self.nod_max] = 1
self.dmax = 0

self.dfs(self.nod_max)

return self.dmax

def check_constraints(n):
if 1 <= n <= 100000:
return True
else:
with open("ascensiuneOUT.txt", "w") as os:
os.write("Datele nu corespund restrictiilor impuse")
return False

if __name__ == "__main__":
with open("ascensiuneIN.txt", "r") as input_file:
n = int(input_file.readline())

if not check_constraints(n):
# Exit if constraints are not met
exit()

tree_diameter = TreeDiameter(n)
result = tree_diameter.find_diameter()

with open("ascensiuneOUT.txt", "w") as os:
os.write(str(result))

</syntaxhighlight>

2888 - Spanning Tree

2024-01-06T19:55:04Z

Rus Marius: /* Date de ieșire */

== Enunț ==
Se consideră un graf neorientat conex cu <code>n</code> noduri și <code>n</code> muchii.

= Cerința =
Să se determine numărul arborilor parțiali ai grafului.

= Date de intrare =
Programul citește de la tastatură numărul <code>n</code>, iar apoi <code>n</code> perechi de numere naturale <code>x y</code> reprezentând cele <code>n</code> muchii.

= Date de ieșire =
Programul va afișa pe ecran numărul arborilor parțiali ai grafului.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 ≤ n ≤ 30.000</code>
* cele <code>n</code> muchii sunt distincte două câte două

= Exemplul 1: =
Intrare
7
1 4
1 5
2 3
2 4
4 5
4 6
4 7
Ieșire
3

= Exemplul 2: =
Intrare
30001
Ieșire
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
from collections import deque

def check_restriction_n(value):
if not (1 <= value <= 30000):
print("Datele nu corespund restrictiilor impuse")
exit()

def main():
n = int(input())
check_restriction_n(n)

v = [[] for _ in range(30001)]
t = [0] * 30001
cnt = 0
q = deque()

for _ in range(n):
x, y = map(int, input().split())
v[x].append(y)
v[y].append(x)
t[x] += 1
t[y] += 1

for i in range(1, n + 1):
if t[i] == 1:
q.append(i)

while q:
x = q.popleft()
for y in v[x]:
if t[y]:
t[y] -= 1
if t[y] == 1:
q.append(y)
t[x] = 0

for i in range(1, n + 1):
if t[i] == 2:
cnt += 1

print(cnt)

if __name__ == "__main__":
main()

</syntaxhighlight>

2888 - Spanning Tree

2024-01-06T19:54:54Z

Rus Marius: Pagină nouă: == Enunț == Se consideră un graf neorientat conex cu <code>n</code> noduri și <code>n</code> muchii. = Cerința = Să se determine numărul arborilor parțiali ai grafului. = Date de intrare = Programul citește de la tastatură numărul <code>n</code>, iar apoi <code>n</code> perechi de numere naturale <code>x y</code> reprezentând cele <code>n</code> muchii. = Date de ieșire = Programul va afișa pe ecran numărul arborilor parțiali ai grafului. = Restricții și...

== Enunț ==
Se consideră un graf neorientat conex cu <code>n</code> noduri și <code>n</code> muchii.

= Cerința =
Să se determine numărul arborilor parțiali ai grafului.

= Date de intrare =
Programul citește de la tastatură numărul <code>n</code>, iar apoi <code>n</code> perechi de numere naturale <code>x y</code> reprezentând cele <code>n</code> muchii.

= Date de ieșire =
Programul va afișa pe ecran numărul arborilor parțiali ai grafului.

= Restricții și precizări =

* <code>1 ≤ n ≤ 30.000</code>
* cele <code>n</code> muchii sunt distincte două câte două

= Exemplul 1: =
Intrare
7
1 4
1 5
2 3
2 4
4 5
4 6
4 7
Ieșire
3

= Exemplul 2: =
Intrare
30001
Ieșire
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
from collections import deque

def check_restriction_n(value):
if not (1 <= value <= 30000):
print("Datele nu corespund restrictiilor impuse")
exit()

def main():
n = int(input())
check_restriction_n(n)

v = [[] for _ in range(30001)]
t = [0] * 30001
cnt = 0
q = deque()

for _ in range(n):
x, y = map(int, input().split())
v[x].append(y)
v[y].append(x)
t[x] += 1
t[y] += 1

for i in range(1, n + 1):
if t[i] == 1:
q.append(i)

while q:
x = q.popleft()
for y in v[x]:
if t[y]:
t[y] -= 1
if t[y] == 1:
q.append(y)
t[x] = 0

for i in range(1, n + 1):
if t[i] == 2:
cnt += 1

print(cnt)

if __name__ == "__main__":
main()

</syntaxhighlight>

4078 - Distanta

2024-01-06T19:49:40Z

Rus Marius: Pagină nouă: = Cerința = Matei, care locuiește in orașul <code>p</code>, vrea să ajungă in orașul <code>q</code> să il viziteze. El are o hartă pe care se află <code>n</code> orașe și <code>m</code> drumuri prin care poate să treacă pentru a ajunge la destinație. Pe hartă apare și durata de timp <code>td</code> pentru fiecare drum, care reprezintă numărul de minute în care este parcurs drumul și <code>to</code> pentru traversarea orașelor (unele orașe sunt mai aglome...

= Cerința =
Matei, care locuiește in orașul <code>p</code>, vrea să ajungă in orașul <code>q</code> să il viziteze. El are o hartă pe care se află <code>n</code> orașe și <code>m</code> drumuri prin care poate să treacă pentru a ajunge la destinație. Pe hartă apare și durata de timp <code>td</code> pentru fiecare drum, care reprezintă numărul de minute în care este parcurs drumul și <code>to</code> pentru traversarea orașelor (unele orașe sunt mai aglomerate, iar altele nu). Matei vrea să ajungă cat mai rapid la destinație, dar dacă există mai multe trasee de timp minim, il va alege pe acela care trece prin mai multe orașe. Nu vor exista trasee de timp minim cu același număr de orașe. Ajutati-l pe Matei să gasească drumul cerut.

= Date de intrare =
Fișierul de intrare <code>distantaIN.txt</code> conține pe prima linie numărul <code>n</code>, iar pe următoarele <code>n</code> linii se citesc <code>nume oraș</code> și <code>to</code> al acestuia. Se citește <code>m</code>, iar pe următoarele <code>m</code> linii <code>i</code>, <code>j</code>, <code>td</code> unde <code>i</code> și <code>j</code> reprezintă orașele care sunt legate prin drumul care se parcurge în <code>td</code>. Pe ultima linie se citesc <code>p</code> și <code>q</code>.

= Date de ieșire =
Fișierul de ieșire <code>distantaOUT.txt</code> va conține pe prima linie numărul <code>S</code>, reprezentând durata de timp în care se parcurge traseul cerut, iar pe următoarele linii se afișează traseul. Dacă nu există nici un traseu se va afișa <code>NU EXISTA TRASEU</code>.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 < n < 21</code>
* <code>0 ≤ m ≤ 190</code>
* <code>0 < numele orașelor (număr caractere) < 21</code>
* <code>0 ≤ numărul de drumuri dintre oricare 2 orașe ≤ 1</code>
* <code>0 ≤ S ≤ 2.000.000.001</code>
* Nu există drum de la un oraș la el însuși
* Dacă nu există nici un traseu se va afișa <code>NU EXISTA TRASEU</code>.

= Exemplul 1: =
<code>distantaIN.txt</code>
7
Bistrita 14
Oradea 80
Beius 7
Galatii-Bistritei 1
Reghin 3
Sibiu 15
Cluj-Napoca 30
10
Bistrita Oradea 223
Cluj-Napoca Sibiu 119
Bistrita Cluj-Napoca 100
Beius Oradea 50
Bistrita Galatii-Bistritei 15
Reghin Galatii-Bistritei 35
Oradea Cluj-Napoca 100
Sibiu Reghin 154
Beius Sibiu 130
Reghin Cluj-Napoca 133
Bistrita Beius
<code>distantaOUT.txt</code>
374
Bistrita
Galatii-Bistritei
Reghin
Sibiu
Beius

= Exemplul 2: =
<code>distantaIN.txt</code>
22
Bistrita 14
Oradea 80
Beius 7
Galatii-Bistritei 1
Reghin 3
Sibiu 15
Cluj-Napoca 30
10
Bistrita Oradea 223
Cluj-Napoca Sibiu 119
Bistrita Cluj-Napoca 100
Beius Oradea 50
Bistrita Galatii-Bistritei 15
Reghin Galatii-Bistritei 35
Oradea Cluj-Napoca 100
Sibiu Reghin 154
Beius Sibiu 130
Reghin Cluj-Napoca 133
Bistrita Beius
<code>distantaOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
from queue import Queue

Inf = 0x3f3f3f3f

def check_restrictions(n, m, codif):
if not (1 < n < 21) or not (0 <= m <= 190):
return False

for _, _, s in codif:
if not (0 < len(s) < 21):
return False

return True
if __name__ == "__main__":
with open("distantaIN.txt", "r") as infile, open("distantaOUT.txt", "w") as outfile:
n = int(infile.readline().strip())
codif = []
G = [[] for _ in range(51)]
t = [0] * 51
timp = [0] * 51

if not (1 < n < 21):
outfile.write("Datele nu corespund restrictiilor impuse")
else:
for i in range(1, n + 1):
line = infile.readline().split()
if len(line) != 2:
outfile.write("Datele nu corespund restrictiilor impuse")
break

s, cost = line
cost = int(cost)
codif.append((i, cost, s))

m = int(infile.readline().strip())

if not (0 <= m <= 190):
outfile.write("Datele nu corespund restrictiilor impuse")
else:
for i in range(1, m + 1):
line = infile.readline().split()
if len(line) != 3:
outfile.write("Datele nu corespund restrictiilor impuse")
break

unu, doi, cost = line
cost = int(cost)
x = next(item[0] for item in codif if item[2] == unu)
y = next(item[0] for item in codif if item[2] == doi)
G[x].append((y, cost))
G[y].append((x, cost))

unu, doi = infile.readline().split()
start_node = next(item[0] for item in codif if item[2] == doi)

def decodif(oras):
for x, y, s in codif:
if s == oras:
return x

def costnod(nod):
for x, y, s in codif:
if nod == x:
return y

def afisare(nod):
for x, y, s in codif:
if nod == x:
return s

def bfs(nod):
t[nod] = nod
timp[nod] = costnod(nod)
q = Queue()
q.put(nod)

while not q.empty():
x = q.get()

for i, c in G[x]:
costnou = timp[x] + c + costnod(i)

if not timp[i] or costnou <= timp[i]:
timp[i] = costnou
t[i] = x
q.put(i)

bfs(start_node)

if timp[decodif(unu)] != 0:
outfile.write(str(timp[decodif(unu)]) + '\n')

plec = decodif(unu)
while plec != t[plec]:
outfile.write(afisare(plec) + '\n')
plec = t[plec]

outfile.write(afisare(decodif(doi)))
else:
outfile.write("NU EXISTA TRASEU")

</syntaxhighlight>

4304 - FF

2024-01-06T19:40:44Z

Rus Marius: Pagină nouă: = Cerința = Se dă un graf neorientat. Să se determine un subgraf al său, cu număr cât mai mare de noduri și în care fiecare nod are gradul cel puțin <code>2</code>. = Date de intrare = Fișierul de intrare <code>ffIN.txt</code> conține pe prima linie numerele <code>n</code> și <code>m</code> reprezentând numărul de noduri și numărul de muchii pentru graful dat. Fiecare din următoarele <code>m</code> linii conține două numere, <code>x</code> și <code>y</cod...

= Cerința =
Se dă un graf neorientat. Să se determine un subgraf al său, cu număr cât mai mare de noduri și în care fiecare nod are gradul cel puțin <code>2</code>.

= Date de intrare =
Fișierul de intrare <code>ffIN.txt</code> conține pe prima linie numerele <code>n</code> și <code>m</code> reprezentând numărul de noduri și numărul de muchii pentru graful dat. Fiecare din următoarele <code>m</code> linii conține două numere, <code>x</code> și <code>y</code>, semnificând existența în graful dat a unei muchii între nodurile <code>x</code> și <code>y</code>.

= Date de ieșire =
Fișierul de ieșire <code>ffOUT.txt</code> va conține valoarea ce reprezintă numărul maxim de noduri pe care le poate avea subgraful determinat.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 ≤ n ≤ 100.000</code>
* <code>1 ≤ m ≤ 200.000</code>
* Se garantează existența unui astfel de subgraf.

= Exemplul 1: =
<code>ffIN.txt</code>
4 4
1 2
4 1
2 3
1 3
<code>ffOUT.txt</code>
3

= Exemplul 2: =
<code>ffIN.txt</code>
123921321 4
1 2
4 1
2 3
1 3
<code>ffOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
from collections import deque

Inf = 0x3f3f3f3f

def check_restrictions(n, m):
if not (1 <= n <= 100000 and 1 <= m <= 200000):
with open("ffOUT.txt", "w") as outfile:
outfile.write("Datele nu corespund restrictiilor impuse")
return True
return False

def main():
with open("ffIN.txt", "r") as infile, open("ffOUT.txt", "w") as outfile:
n, m = map(int, infile.readline().split())

if check_restrictions(n, m):
return

G = [[] for _ in range(n + 1)]
g = [0] * (n + 1)
f = [0] * (n + 1)
scad = 0

for _ in range(m):
x, y = map(int, infile.readline().split())
G[x].append(y)
G[y].append(x)
g[x] += 1
g[y] += 1

q = deque()
for i in range(1, n + 1):
if g[i] == 1:
q.append(i)
g[i] = 0
f[i] = 1
elif g[i] == 0:
scad += 1

while q:
x = q.popleft()
scad += 1
for i in G[x]:
g[i] -= 1

if g[i] < 2 and f[i] == 0:
q.append(i)
f[i] = 1

outfile.write(str(n - scad))

if __name__ == "__main__":
main()

</syntaxhighlight>

0544 - Partial

2024-01-06T19:34:55Z

Rus Marius: /* Date de ieșire */

= Cerința =
Se dă un graf neorientat conex cu <code>n</code> vârfuri și număr par de muchii. Să se determine un graf parțial al celui dat care să fie conex și să fie obținut prin eliminarea a jumătate din numărul de muchii.

= Date de intrare =
Fișierul de intrare <code>partialIN.txt</code> conține pe prima linie numărul <code>n</code>, iar pe a următoarele linii perechi de numere <code>i j</code>, cu semnificația că există muchie de la <code>i</code> la <code>j</code>.

= Date de ieșire =
Fișierul de ieșire <code>partialOUT.txt</code> va conține matricea de adiacență a grafului parțial obținut, câte o linie a matricei pe o linie a fișierului, elementele fiecărei linii fiind separate prin exact un spațiu.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 ≤ n ≤ 200</code>
* <code>1 ≤ i,j ≤ n</code>
* se garantează existența unui graf parțial cu proprietatea cerută

= Exemplul 1: =
<code>partialIN.txt</code>
6
1 2
1 3
1 4
1 5
1 6
2 4
2 5
3 4
3 5
4 5
4 6
5 6
<code>partialOUT.txt</code>
0 1 0 0 0 0
1 0 0 1 0 0
0 0 0 1 1 0
0 1 1 0 0 1
0 0 1 0 0 1
0 0 0 1 1 0

= Observații =

* 2016, iunie 02: am adăugat un test cu o situație care nu era cuprinsă în testele anterioare.

== Exemplul 2: ==
<code>partialIN.txt</code>
201
1 2
1 3
1 4
1 5
1 6
2 4
2 5
3 4
3 5
4 5
4 6
5 6
<code>partialOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
nMAX = 200

def check_constraints(n, i, j):
if not (1 <= n <= nMAX) or not (1 <= i <= n) or not (1 <= j <= n):
with open("partialOUT.txt", "w") as fout:
fout.write("Datele nu corespund restrictiilor impuse")
return False
return True

def dfs(n, gf, viz, viznod):
def dfs_util(nod):
viznod[nod] = True
for j in range(1, n + 1):
if gf[nod][j] and not viznod[j]:
viz[nod][j] = viz[j][nod] = True
dfs_util(j)

dfs_util(1)

def process_input():
n, m = 0, 0
gf = [[False] * (nMAX + 1) for _ in range(nMAX + 1)]
viz = [[False] * (nMAX + 1) for _ in range(nMAX + 1)]
viznod = [False] * (nMAX + 1)

with open("partialIN.txt", "r") as fin:
n = int(fin.readline().strip())
if not check_constraints(n, 1, 1):
return

for line in fin:
a, b = map(int, line.split())
if not check_constraints(n, a, b):
return

gf[a][b] = gf[b][a] = True
m += 1

dfs(n, gf, viz, viznod)

mfol = 0
for i in range(1, n + 1):
for j in range(i + 1, n + 1):
if mfol != m // 2 and gf[i][j] and not viz[i][j]:
gf[i][j] = gf[j][i] = False
mfol += 1

with open("partialOUT.txt", "w") as fout:
if check_constraints(n, 1, 1):
for i in range(1, n + 1):
fout.write(' '.join(map(str, [int(x) for x in gf[i][1:n + 1]])) + '\n')

if __name__ == "__main__":
process_input()

</syntaxhighlight>

0544 - Partial

2024-01-06T19:34:43Z

Rus Marius: Pagină nouă: = Cerința = Se dă un graf neorientat conex cu <code>n</code> vârfuri și număr par de muchii. Să se determine un graf parțial al celui dat care să fie conex și să fie obținut prin eliminarea a jumătate din numărul de muchii. = Date de intrare = Fișierul de intrare <code>partialIN.txt</code> conține pe prima linie numărul <code>n</code>, iar pe a următoarele linii perechi de numere <code>i j</code>, cu semnificația că există muchie de la <code>i</code> la <...

= Cerința =
Se dă un graf neorientat conex cu <code>n</code> vârfuri și număr par de muchii. Să se determine un graf parțial al celui dat care să fie conex și să fie obținut prin eliminarea a jumătate din numărul de muchii.

= Date de intrare =
Fișierul de intrare <code>partialIN.txt</code> conține pe prima linie numărul <code>n</code>, iar pe a următoarele linii perechi de numere <code>i j</code>, cu semnificația că există muchie de la <code>i</code> la <code>j</code>.

= Date de ieșire =
Fișierul de ieșire <code>partialOUT.txt</code> va conține matricea de adiacență a grafului parțial obținut, câte o linie a matricei pe o linie a fișierului, elementele fiecărei linii fiind separate prin exact un spațiu.

= Restricții și precizări =

* <code>1 ≤ n ≤ 200</code>
* <code>1 ≤ i,j ≤ n</code>
* se garantează existența unui graf parțial cu proprietatea cerută

= Exemplul 1: =
<code>partialIN.txt</code>
6
1 2
1 3
1 4
1 5
1 6
2 4
2 5
3 4
3 5
4 5
4 6
5 6
<code>partialOUT.txt</code>
0 1 0 0 0 0
1 0 0 1 0 0
0 0 0 1 1 0
0 1 1 0 0 1
0 0 1 0 0 1
0 0 0 1 1 0

= Observații =

* 2016, iunie 02: am adăugat un test cu o situație care nu era cuprinsă în testele anterioare.

== Exemplul 2: ==
<code>partialIN.txt</code>
201
1 2
1 3
1 4
1 5
1 6
2 4
2 5
3 4
3 5
4 5
4 6
5 6
<code>partialOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
nMAX = 200

def check_constraints(n, i, j):
if not (1 <= n <= nMAX) or not (1 <= i <= n) or not (1 <= j <= n):
with open("partialOUT.txt", "w") as fout:
fout.write("Datele nu corespund restrictiilor impuse")
return False
return True

def dfs(n, gf, viz, viznod):
def dfs_util(nod):
viznod[nod] = True
for j in range(1, n + 1):
if gf[nod][j] and not viznod[j]:
viz[nod][j] = viz[j][nod] = True
dfs_util(j)

dfs_util(1)

def process_input():
n, m = 0, 0
gf = [[False] * (nMAX + 1) for _ in range(nMAX + 1)]
viz = [[False] * (nMAX + 1) for _ in range(nMAX + 1)]
viznod = [False] * (nMAX + 1)

with open("partialIN.txt", "r") as fin:
n = int(fin.readline().strip())
if not check_constraints(n, 1, 1):
return

for line in fin:
a, b = map(int, line.split())
if not check_constraints(n, a, b):
return

gf[a][b] = gf[b][a] = True
m += 1

dfs(n, gf, viz, viznod)

mfol = 0
for i in range(1, n + 1):
for j in range(i + 1, n + 1):
if mfol != m // 2 and gf[i][j] and not viz[i][j]:
gf[i][j] = gf[j][i] = False
mfol += 1

with open("partialOUT.txt", "w") as fout:
if check_constraints(n, 1, 1):
for i in range(1, n + 1):
fout.write(' '.join(map(str, [int(x) for x in gf[i][1:n + 1]])) + '\n')

if __name__ == "__main__":
process_input()

</syntaxhighlight>

4064 - Ghiocel

2024-01-06T19:27:07Z

Rus Marius: Pagină nouă: = Cerința = Într-un oraș sunt <code>n</code> case numerotate de la <code>1</code> la <code>n</code>. Între anumite case sunt străzi bidirecționale. În casa cu numărul <code>g</code> locuiește Ghiocel. El are <code>k</code> colege ale căror numere de casă îi sunt cunoscute și Ghiocel dorește să le ducă ghiocei la inceputul lunii martie. Pentru că este leneș, Ghiocel se decide să ducă ghiocei colegei sau colegelor care stă (stau) la o casă până la care G...

= Cerința =
Într-un oraș sunt <code>n</code> case numerotate de la <code>1</code> la <code>n</code>. Între anumite case sunt străzi bidirecționale. În casa cu numărul <code>g</code> locuiește Ghiocel. El are <code>k</code> colege ale căror numere de casă îi sunt cunoscute și Ghiocel dorește să le ducă ghiocei la inceputul lunii martie. Pentru că este leneș, Ghiocel se decide să ducă ghiocei colegei sau colegelor care stă (stau) la o casă până la care Ghiocel are de parcurs un număr minim de străzi. Ajutați-l pe Ghiocel să determine numerele acestor case.

= Date de intrare =
Fișierul de intrare <code>ghiocelIN.txt</code> conține pe prima linie numerele <code>n m g</code>, reprezentând numărul de case, numărul de străzi și numărul casei în care locuiește Ghiocel. Urmează <code>m</code> linii cu câte două numere <code>i j</code>, cu semnificația: casele <code>i</code> și <code>j</code> sunt legate printr-o stradă bidirecțională. Pe următoarea linie se află numărul <code>k</code> a colegelor lui Ghiocel, iar pe ultima linie se află <code>k</code> numere distincte cuprinse între <code>1</code> și <code>n</code>, reprezentând numerele caselor unde locuiesc colegele lui Ghiocel.

= Date de ieșire =
Fișierul de ieșire <code>ghiocelOUT.txt</code> va conține pe prima linie numerele caselor unde locuiesc colege de-ale lui Ghicel până la care acesta are de parcurs un număr minim de străzi. Numerele se vor afișa în ordine crescătoare și separate prin câte un spațiu.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

= Restricții și precizări =

* <code>1 ≤ n ≤ 100</code>
* <code>1 ≤ m ≤ n * (n - 1) / 2</code>
* <code>1 ≤ i, j ≤ n</code>
* <code>1 ≤ k ≤ n</code>

= Exemplul 1: =
<code>ghiocelIN.txt</code>
10 12 6
1 2
1 7
1 10
2 4
2 5
2 6
3 4
4 5
5 6
7 8
8 10
9 10
4
1 4 8 10
<code>ghiocelOUT.txt</code>
1 4

= Explicație =
Ghiocel locuiește în casa cu numărul <code>6</code>. Colegele lui stau în casele <code>1 4 8 10</code>. Până la casele <code>1</code> și <code>4</code> ajunge mergând pe un număr minim de străzi.

== Exemplul 2: ==
<code>ghiocelIN.txt</code>
101 12 6
1 2
1 7
1 10
2 4
2 5
2 6
3 4
4 5
5 6
7 8
8 10
9 10
4
1 4 8 10
<code>ghiocelOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
from collections import deque

def check_constraints(n, m, edges):
if not (1 <= n <= 100) or not (1 <= m <= n * (n - 1) / 2):
return False

for a, b in edges:
if not (1 <= a <= n) or not (1 <= b <= n):
return False

return True

def BFS(start):
q = deque([start])

while q:
current = q.popleft()

for neighbor in vecini[current]:
if not gasit[neighbor]:
gasit[neighbor] = True
q.append(neighbor)
distanta[neighbor] = distanta[current] + 1

def main():
global vecini, gasit, distanta
with open("ghiocelIN.txt", "r") as file_in:
n, m, start = map(int, file_in.readline().split())

edges = [tuple(map(int, file_in.readline().split())) for _ in range(m)]

if not check_constraints(n, m, edges):
with open("ghiocelOUT.txt", "w") as file_out:
file_out.write("Datele nu corespund restrictiilor impuse")
return

vecini = {i: set() for i in range(1, n + 1)}
gasit = [False] * (n + 1)
distanta = [0] * (n + 1)

for a, b in edges:
vecini[a].add(b)
vecini[b].add(a)

BFS(start)

fete = int(file_in.readline()) # Read the number of girls from the file
colege = set(map(int, file_in.readline().split()))

with open("ghiocelOUT.txt", "w") as file_out:
mini = float('inf')
for i in colege:
mini = min(mini, distanta[i])

result = [i for i in colege if distanta[i] == mini]
file_out.write(" ".join(map(str, result)))

if __name__ == "__main__":
main()

</syntaxhighlight>

3235 - Entries

2024-01-06T19:18:10Z

Rus Marius: /* Date de ieșire */

== Enunț ==
Se consideră un graf care inițial este format din <code>P</code> noduri izolate, etichetate de la <code>1</code> la <code>P</code>. Se mai consideră <code>N</code> intrări, unde intrare poate însemna:

* comandă – o comandă are forma <code>I + J</code>, cu semnificația că în graf se adaugă muchia care unește nodurile <code>I</code> și <code>J</code> (dacă <code>I</code> și <code>J</code> erau deja unite în acel moment, nu se întreprinde nici o acțiune);
* întrebare – o întrebare este de forma <code>I ? J</code>, adică se întreabă dacă în acel moment <code>I</code> și <code>J</code> sunt în aceeași componentă conexă.

Se pleacă deci de la un graf inițial format din noduri izolate, care pe parcurs se “unifică”. Tot pe parcurs sunteți întrebat dacă anumite perechi de noduri sunt sau nu în aceeași componentă conexă.

= Cerința =
Scrieți un program care să răspundă la întrebările din fișierul de intrare.

= Date de intrare =
Din fișierul <code>entriesIN.txt</code> veți citi de pe prima linie numărul <code>N</code> de intrări. Pe următoarele <code>N</code> linii se găsesc intrările, câte una pe linie. O intrare este codificată prin trei numere separate prin câte un blanc. Primele două numere reprezintă nodurile <code>I</code> și <code>J</code> (numere întregi, cuprinse între <code>1</code> și <code>P</code>), iar al treilea este <code>1</code> dacă intrarea este o comandă, respectiv <code>2</code> dacă intrarea este o întrebare.

= Date de ieșire =
Fișierul de ieșire <code>entriesOUT.txt</code> va conține răspunsurile la întrebări, câte un răspuns pe o linie, în ordinea din fișierul de intrare. Răspunsul va fi numărul <code>1</code> dacă nodurile despre care ați fost întrebat sunt în acel moment în aceeași componentă conexă, respectiv numărul <code>0</code> în caz contrar.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

= Restricții și precizări =

* <code>1 ≤ N ≤ 5 000</code>
* <code>1 ≤ P ≤ 10.000.000</code>

= Exemplul 1: =
<code>entriesIN.txt</code>
9
1 2 2
1 2 1
3 7 2
2 3 1
1 3 2
2 4 2
1 4 1
3 4 2
1 7 2
<code>entriesOUT.txt</code>
0
0
1
0
1
0

= Exemplul 2: =
<code>entriesIN.txt</code>
5001
1 2 2
1 2 1
3 7 2
2 3 1
1 3 2
2 4 2
1 4 1
3 4 2
1 7 2
<code>entriesOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verifica_restrictiile(n, p):
if not (1 <= n <= 5000):
raise ValueError("")
if not (1 <= p <= 10000000):
raise ValueError("")

def main():
fin = open("entriesIN.txt", "r")
fout = open("entriesOUT.txt", "w")

M = {}
t = [0] * 10005
n = 0

def find(x):
z, y = x, x
while t[x] != 0:
x = t[x]

while t[y] != 0:
z = t[y]
t[y] = x
y = z

return x

def union(x, y):
t[y] = x

T = int(fin.readline().strip())
try:
verifica_restrictiile(T, T) # Check restrictions for n (number of test cases)
except ValueError as e:
fout.write(f"Datele nu corespund restrictiilor impuse {str(e)}")
fin.close()
fout.close()
return

for _ in range(T):
x, y, op = map(int, fin.readline().strip().split())
k = 0
if x not in M:
k = 1
n += 1
M[x] = n
if y not in M:
k = 1
n += 1
M[y] = n

x = M[x]
y = M[y]
x = find(x)
y = find(y)

if op == 1:
if x != y:
union(x, y)
else:
if k == 1:
fout.write("0\n")
elif x == y:
fout.write("1\n")
else:
fout.write("0\n")

fin.close()
fout.close()

if __name__ == "__main__":
main()

</syntaxhighlight>

3235 - Entries

2024-01-06T19:17:55Z

Rus Marius: Pagină nouă: == Enunț == Se consideră un graf care inițial este format din <code>P</code> noduri izolate, etichetate de la <code>1</code> la <code>P</code>. Se mai consideră <code>N</code> intrări, unde intrare poate însemna: * comandă – o comandă are forma <code>I + J</code>, cu semnificația că în graf se adaugă muchia care unește nodurile <code>I</code> și <code>J</code> (dacă <code>I</code> și <code>J</code> erau deja unite în acel moment, nu se întreprinde nici o...

== Enunț ==
Se consideră un graf care inițial este format din <code>P</code> noduri izolate, etichetate de la <code>1</code> la <code>P</code>. Se mai consideră <code>N</code> intrări, unde intrare poate însemna:

* comandă – o comandă are forma <code>I + J</code>, cu semnificația că în graf se adaugă muchia care unește nodurile <code>I</code> și <code>J</code> (dacă <code>I</code> și <code>J</code> erau deja unite în acel moment, nu se întreprinde nici o acțiune);
* întrebare – o întrebare este de forma <code>I ? J</code>, adică se întreabă dacă în acel moment <code>I</code> și <code>J</code> sunt în aceeași componentă conexă.

Se pleacă deci de la un graf inițial format din noduri izolate, care pe parcurs se “unifică”. Tot pe parcurs sunteți întrebat dacă anumite perechi de noduri sunt sau nu în aceeași componentă conexă.

= Cerința =
Scrieți un program care să răspundă la întrebările din fișierul de intrare.

= Date de intrare =
Din fișierul <code>entriesIN.txt</code> veți citi de pe prima linie numărul <code>N</code> de intrări. Pe următoarele <code>N</code> linii se găsesc intrările, câte una pe linie. O intrare este codificată prin trei numere separate prin câte un blanc. Primele două numere reprezintă nodurile <code>I</code> și <code>J</code> (numere întregi, cuprinse între <code>1</code> și <code>P</code>), iar al treilea este <code>1</code> dacă intrarea este o comandă, respectiv <code>2</code> dacă intrarea este o întrebare.

= Date de ieșire =
Fișierul de ieșire <code>entriesOUT.txt</code> va conține răspunsurile la întrebări, câte un răspuns pe o linie, în ordinea din fișierul de intrare. Răspunsul va fi numărul <code>1</code> dacă nodurile despre care ați fost întrebat sunt în acel moment în aceeași componentă conexă, respectiv numărul <code>0</code> în caz contrar.

= Restricții și precizări =

* <code>1 ≤ N ≤ 5 000</code>
* <code>1 ≤ P ≤ 10.000.000</code>

= Exemplul 1: =
<code>entriesIN.txt</code>
9
1 2 2
1 2 1
3 7 2
2 3 1
1 3 2
2 4 2
1 4 1
3 4 2
1 7 2
<code>entriesOUT.txt</code>
0
0
1
0
1
0

= Exemplul 2: =
<code>entriesIN.txt</code>
5001
1 2 2
1 2 1
3 7 2
2 3 1
1 3 2
2 4 2
1 4 1
3 4 2
1 7 2
<code>entriesOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verifica_restrictiile(n, p):
if not (1 <= n <= 5000):
raise ValueError("")
if not (1 <= p <= 10000000):
raise ValueError("")

def main():
fin = open("entriesIN.txt", "r")
fout = open("entriesOUT.txt", "w")

M = {}
t = [0] * 10005
n = 0

def find(x):
z, y = x, x
while t[x] != 0:
x = t[x]

while t[y] != 0:
z = t[y]
t[y] = x
y = z

return x

def union(x, y):
t[y] = x

T = int(fin.readline().strip())
try:
verifica_restrictiile(T, T) # Check restrictions for n (number of test cases)
except ValueError as e:
fout.write(f"Datele nu corespund restrictiilor impuse {str(e)}")
fin.close()
fout.close()
return

for _ in range(T):
x, y, op = map(int, fin.readline().strip().split())
k = 0
if x not in M:
k = 1
n += 1
M[x] = n
if y not in M:
k = 1
n += 1
M[y] = n

x = M[x]
y = M[y]
x = find(x)
y = find(y)

if op == 1:
if x != y:
union(x, y)
else:
if k == 1:
fout.write("0\n")
elif x == y:
fout.write("1\n")
else:
fout.write("0\n")

fin.close()
fout.close()

if __name__ == "__main__":
main()

</syntaxhighlight>

1942 - Ciclu Hamiltonian

2024-01-06T18:59:19Z

Rus Marius: Pagină nouă: = Cerința = Dându-se un număr natural <code>N</code>, aflaţi numărul de cicluri Hamiltoniene dintr-un graf complet cu <code>N</code> noduri. = Date de intrare = Programul citește de la tastatură numărul <code>N</code>. = Date de ieșire = Programul va afișa pe ecran numărul cerut. = Restricții și precizări = * <code>3 ≤ N ≤ 100</code> * două cicluri diferă dacă au cel puțin o muchie diferită = Exemplul 1: = Intrare 3 Ieșire 1 === Explicație ===...

= Cerința =
Dându-se un număr natural <code>N</code>, aflaţi numărul de cicluri Hamiltoniene dintr-un graf complet cu <code>N</code> noduri.

= Date de intrare =
Programul citește de la tastatură numărul <code>N</code>.

= Date de ieșire =
Programul va afișa pe ecran numărul cerut.

= Restricții și precizări =

* <code>3 ≤ N ≤ 100</code>
* două cicluri diferă dacă au cel puțin o muchie diferită

= Exemplul 1: =
Intrare
3
Ieșire
1

=== Explicație ===
Un graf complet cu <code>3</code> noduri are un ciclu Hamiltonian.

== Exemplul 2: ==
Intrare
2
Ieșire
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def check_restrictions(n):
if n < 3 or n >= 100:
print("Datele nu corespund restrictiilor impuse")
return False
return True

def inmultire(x, k):
t = 0
for i in range(1, x[0] + 1):
c = x[i] * k + t
x[i] = c % 10
t = c // 10
while t:
x[0] += 1
x[x[0]] = t % 10
t //= 10

def calculate_factorial(n):
if not check_restrictions(n):
return

x = [0] * 1001
x[0], x[1] = 1, 1

for i in range(3, n):
inmultire(x, i)

for i in range(x[0], 0, -1):
print(x[i], end='')

def main():
n = int(input(""))
calculate_factorial(n)

if __name__ == "__main__":
main()

</syntaxhighlight>

4071 - Ciclu L

2024-01-06T18:49:54Z

Rus Marius: Pagină nouă: = Cerinţa = Se dă lista muchiilor unui graf neorientat cu <code>n</code> noduri și un număr <code>L</code>. Să se determine un ciclu elementar de lungime <code>L</code>. = Date de intrare = Fişierul de intrare <code>ciclulIN.txt</code> conţine pe prima linie numerele <code>n</code> și <code>m</code>, reprezentând numărul de noduri ale grafului și numărul de muchii date în continuare. Fiecare dintre următoarele <code>m</code> linii conține câte o pereche de nu...

= Cerinţa =
Se dă lista muchiilor unui graf neorientat cu <code>n</code> noduri și un număr <code>L</code>. Să se determine un ciclu elementar de lungime <code>L</code>.

= Date de intrare =
Fişierul de intrare <code>ciclulIN.txt</code> conţine pe prima linie numerele <code>n</code> și <code>m</code>, reprezentând numărul de noduri ale grafului și numărul de muchii date în continuare. Fiecare dintre următoarele <code>m</code> linii conține câte o pereche de numere <code>i j</code>, cu semnificația că există muchie între <code>i</code> și <code>j</code>.

Următoarea linie conține numărul <code>L</code>.

= Date de ieşire =
Fişierul de ieşire <code>ciclulOUT.txt</code> va conține un singur ciclu elementar de lungime <code>L</code>. Acesta va începe și se va termina cu același nod.

= Restricţii şi precizări =

* <code>1 ≤ n ≤ 20</code>
* <code>1 ≤ i , j ≤ n</code>
* <code>1 ≤ L ≤ n</code>
* pentru toate datele de test, va exista cel puțin un ciclu de lungime <code>L</code>
* lungimea unui ciclu este egală cu numărul de muchii.

= Exemplul 1: =
<code>ciclulIN.txt</code>
6 7
1 2
2 3
2 5
3 6
4 6
5 4
3 5
4
<code>ciclulOUT.txt</code>
3 5 4 6 3

= Exemplul 2: =
<code>ciclulIN.txt</code>
21 7
1 2
2 3
2 5
3 6
4 6
5 4
3 5
4
<code>ciclulOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
N = 235

def check_constraints(n, m, k):
if not (1 <= n <= 20) or not (1 <= m <= n*(n-1)//2) or not (1 <= k <= n):
fout.write("Datele nu corespund restrictiilor impuse\n")
exit(0)

def cond(j):
if j > 1 and a[X[j-1]][X[j]] == 0:
return 0
if j == k and a[X[j]][X[1]] == 0:
return 0
return 1

def afis():
for i in range(1, k+1):
fout.write(str(X[i]) + " ")
fout.write(str(X[1]) + '\n')
exit(0)

def back(j):
for i in range(1, n+1):
if not p[i]:
X[j] = i
p[i] = 1
if cond(j):
if j == k:
afis()
else:
back(j + 1)
p[i] = 0

if __name__ == "__main__":
fin = open("ciclulIN.txt", "r")
fout = open("ciclulOUT.txt", "w")

a = [[0] * 50 for _ in range(50)]
n, m = map(int, fin.readline().split())

check_constraints(n, m, n) # Assuming k is the same as n

for _ in range(m):
x, y = map(int, fin.readline().split())
a[x][y] = a[y][x] = 1

k = int(fin.readline())
check_constraints(n, m, k)

X = [0] * 50
p = [0] * 50

back(1)

fin.close()
fout.close()

</syntaxhighlight>

0478 - Ciclu

2024-01-06T18:45:09Z

Rus Marius: Pagină nouă: = Cerinţa = Se dă lista muchiilor unui graf neorientat cu <code>n</code> vârfuri și un vârf <code>p</code>. Să se determine un ciclu elementar care conține vârful <code>p</code>. = Date de intrare = Fişierul de intrare <code>cicluIN.txt</code> conţine pe prima linie numerele <code>n</code> și <code>m</code>, reprezentând numărul de vârfuri ale grafului și numărul de muchii date în continuare. Fiecare dintre următoarele <code>m</code> linii conține câte o...

= Cerinţa =
Se dă lista muchiilor unui graf neorientat cu <code>n</code> vârfuri și un vârf <code>p</code>. Să se determine un ciclu elementar care conține vârful <code>p</code>.

= Date de intrare =
Fişierul de intrare <code>cicluIN.txt</code> conţine pe prima linie numerele <code>n</code> și <code>m</code>, reprezentând numărul de vârfuri ale grafului și numărul de muchii date în continuare. Fiecare dintre următoarele <code>m</code> linii conține câte o pereche de numere <code>i j</code>, cu semnificația că există muchie între <code>i</code> și <code>j</code>.

Următoarea linie conține numărul <code>p</code>.

= Date de ieşire =
Fişierul de ieşire <code>cicluOUT.txt</code> va conține un singur ciclu elementar care conține vârful <code>p</code>. Acesta va începe și se va termina cu vârful <code>p</code>.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

= Restricţii şi precizări =

* <code>1 ≤ n ≤ 20</code>
* <code>1 ≤ i , j ≤n</code>
* muchiile se pot repeta în fișierul de intrare
* <code>1 ≤ p ≤ n</code>
* pentru toate datele de test, va exista cel puțin un ciclu care conține vârful <code>p</code>

= Exemplul 1: =
<code>cicluIN.txt</code>
5 8
1 4
1 3
3 5
4 5
2 4
1 2
4 2
3 4
2
<code>cicluOUT.txt</code>
2 1 3 4 2

= Exemplul 2: =
<code>cicluIN.txt</code>
21 8
1 4
1 3
3 5
4 5
2 4
1 2
4 2
3 4
2
<code>cicluOUT.txt</code>
"Datele nu corespund restrictiilor impuse"

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def check_restrictions(n, m, edges, p):
# Check constraints
if not (1 <= n <= 20):
return False
for i, j in edges:
if not (1 <= i <= n) or not (1 <= j <= n):
return False
if not (1 <= p <= n):
return False

return True

def afis(k):
global gasit
for i in range(1, k + 1):
fout.write(str(x[i]) + " ")
fout.write(str(p) + " ")
gasit = 1

def OK(k):
if a[x[k - 1]][x[k]] != 1:
return 0
for i in range(1, k):
if x[k] == x[i]:
return 0
return 1

def back(k):
global gasit
for i in range(1, n + 1):
x[k] = i
if not gasit and OK(k):
if a[x[k]][p] == 1 and k > 2:
afis(k)
back(k + 1)

if __name__ == "__main__":
fin = open("cicluIN.txt", "r")
fout = open("cicluOUT.txt", "w")

n, m = map(int, fin.readline().split())
edges = [tuple(map(int, fin.readline().split())) for _ in range(m)]

# Read the line and strip any leading or trailing whitespace
p_line = fin.readline().strip()

# Check if the line is not empty before converting to an integer
if p_line:
p = int(p_line)
else:
fout.write("Datele nu corespund restrictiilor impuse")
fin.close()
fout.close()
exit()

# Check restrictions
if not check_restrictions(n, m, edges, p):
fout.write("Datele nu corespund restrictiilor impuse")
else:
a = [[0] * (n + 1) for _ in range(n + 1)]

for i, j in edges:
a[i][j] = a[j][i] = 1

x = [0] * 205
gasit = 0

x[1] = p
back(2)

fin.close()
fout.close()
</syntaxhighlight>

3147 - Fete Graf

2024-01-06T18:24:09Z

Rus Marius: /* Exemplul 1: */

= Cerința =
Se dă lista de muchii ale unui graf neorientat, conex, planar. Determinați numărul de fețe ale acestuia dacă este desenat astfel încât 2 muchii nu se intersectează.

O față este o regiune înconjurată de muchii.

= Date de intrare =
Se vor citi repetat de la tastatură muchiile grafului.

= Date de ieșire =
Programul va afișa pe ecran numărul de fețe ale grafului.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

= Restricții și precizări =

* Ca și față, este considerată și regiunea exterioară, infinit de mare, a grafului.
* Numărul de muchii va fi mai mic decât <code>1.000.000</code>.
*
=Exemplul 1:=
Intrare
1 2
2 3
3 4
4 1
Ieșire
2

=== Explicație ===
Graful se poate desena sub forma unui pătrat. Are doar o față, la care se adaugă și regiunea exterioară.

== Exemplul 2: ==
Intrare
10000000
1000000000000000
Ieșire
Nu corespunde restricțiilor impuse.

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verificare_restricții(numar_varfuri, numar_muchii):
return 0 < numar_varfuri < 1000000 and 0 < numar_muchii < 1000000

def numar_fețe(numar_varfuri, numar_muchii):
# Folosim formula lui Euler pentru grafuri planare: V - E + F = 2
# Deoarece graful este conex, V = E + 2, deci substituim în formulă.
# Obținem E + 2 - E + F = 2, și astfel F = 2.
return 2

def main():
try:
numar_varfuri = int(input("Introduceți numărul de vârfuri ale grafului: "))
numar_muchii = int(input("Introduceți numărul de muchii ale grafului: "))

if not verificare_restricții(numar_varfuri, numar_muchii):
print("Nu corespunde restricțiilor impuse.")
return

numar_muchii_introduse = 0
while numar_muchii_introduse < numar_muchii:
input_muchie = input(f"Introduceți o muchie sub forma x y (muchiile introduse: {numar_muchii_introduse}/{numar_muchii}): ")

if ' ' in input_muchie:
v1, v2 = map(int, input_muchie.split())

if 0 < v1 <= numar_varfuri and 0 < v2 <= numar_varfuri:
numar_muchii_introduse += 1
else:
print(f"Vârfurile muchiei trebuie să fie între 1 și {numar_varfuri} inclusiv.")
else:
print("Introduceți o pereche validă de vârfuri sub forma x y.")

rezultat = numar_fețe(numar_varfuri, numar_muchii)
print(f"Numărul de fețe al grafului este: {rezultat}")

except ValueError:
print("Introduceți numere valide pentru numărul de vârfuri și muchii.")

if __name__ == "__main__":
main()

</syntaxhighlight>

0479 - Lant Maxim

2024-01-06T18:18:19Z

Rus Marius: /* Rezolvare */

= Cerinţa =
Se dă lista muchiilor unui graf neorientat cu <code>n</code> vârfuri și două vârfuri <code>p q</code>. Să se determine cel mai lung lanț elementar cu extremitățile <code>p</code> și <code>q</code>.

= Date de intrare =
Fişierul de intrare <code>lantmaximIN.txt</code> conţine pe prima linie numerele <code>n</code> și <code>m</code>, reprezentând numărul de vârfuri ale grafului și numărul de muchii date în continuare. Fiecare dintre următoarele <code>m</code> linii conține câte o pereche de numere <code>i j</code>, cu semnificația că există muchie între <code>i</code> și <code>j</code>.

Următoarea linie conține două numere <code>p q</code>.

= Date de ieşire =
Fişierul de ieşire <code>lantmaximOUT.txt</code> va conține cel mai lung lanț elementar cu extremitățile <code>p</code> și <code>q</code>, vârfurile sale fiind separate prin exact un spațiu. Dacă sunt mai multe lanțuri de lungime maximă, se va afișa primul în ordine lexicografică.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

= Restricţii şi precizări =

* <code>1 ≤ n ≤ 20</code>
* <code>1 ≤ i , j ≤n</code>
* muchiile se pot repeta în fișierul de intrare
* <code>1 ≤ p , q ≤ n</code>
* pentru toate datele de test, va exista cel puțin un lanț cu extremitățile <code>p q</code>

= Exemplul 1: =
<code>lantmaximIN.txt</code>
5 7
1 4
1 3
3 5
4 5
1 2
4 2
3 4
2 5
<code>lantmaximOUT.txt</code>
2 1 3 4 5

= Exemplul 2: =
<code>lantmaximIN.txt</code>
100 100
1 4
1 3
3 5
4 5
1 2
4 2
3 4
2 5
<code>lantmaximOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def citeste_graf(filename):
try:
with open(filename, 'r') as file:
n, m = map(int, file.readline().split())
graf = {}
muchii = []
for _ in range(m):
i, j = map(int, file.readline().split())
muchii.append((i, j))
graf.setdefault(i, []).append(j)
graf.setdefault(j, []).append(i)
p, q = map(int, file.readline().split())
return n, m, muchii, graf, p, q
except ValueError:
return None, None, None, None, None, None
except FileNotFoundError:
print(f"Fisierul {filename} nu a fost gasit.")
return None, None, None, None, None, None
except Exception as e:
print(f"A aparut o eroare la citirea fisierului {filename}: {e}")
return None, None, None, None, None, None

def verifica_restrictii(n, m, muchii, p, q):
if not (1 <= n <= 20):
return False
for i, j in muchii:
if not (1 <= i <= n) or not (1 <= j <= n):
return False
if not (1 <= p <= n) or not (1 <= q <= n):
return False
return True

def dfs(graf, start, end, path, visited, results):
visited[start] = True
path.append(start)

if start == end:
results.append(path.copy())

for neighbor in graf[start]:
if not visited[neighbor]:
dfs(graf, neighbor, end, path, visited, results)

path.pop()
visited[start] = False

def lanț_maxim(filename_in, filename_out):
n, m, muchii, graf, p, q = citeste_graf(filename_in)

if n is None:
with open(filename_out, 'w') as file:
file.write("Datele nu corespund restrictiilor impuse")
return

if not verifica_restrictii(n, m, muchii, p, q):
with open(filename_out, 'w') as file:
file.write("Datele nu corespund restrictiilor impuse")
return

visited = {v: False for v in graf}
results = []

dfs(graf, p, q, [], visited, results)

if results:
results.sort()
result = results[0]

with open(filename_out, 'w') as file:
file.write(' '.join(map(str, result)))
else:
with open(filename_out, 'w') as file:
file.write("Nu există lanț între vârfurile date")

def main():
try:
# Get input and output filenames from the user
input_filename = input("Introduceți numele fișierului de intrare: ")
output_filename = input("Introduceți numele fișierului de ieșire: ")

# Call the lanț_maxim function with the provided filenames
lanț_maxim(input_filename, output_filename)

print(f"Rezultatele au fost scrise în {output_filename}")
except Exception as e:
print(f"A apărut o eroare: {e}")

if __name__ == "__main__":
main()

</syntaxhighlight>

1462 - Gasti

2024-01-06T18:14:24Z

Rus Marius: Pagină nouă: == Enunț == În orașul Nicăieri există <code>N</code> băieți răi. Se știe că între ei există <code>M</code> relații de prietenie. De-a lungul timpului, aceste prietenii au dus la apariția unor “''găști''”. Dacă doi băieți nu sunt prieteni dar au cel puțin un prieten comun spunem că “''se cunosc''”. Dacă doi băieți au cel puțin o cunoștință comună, atunci și ei se cunosc. O gașcă este un grup de băieți cu proprietatea că oricare ar fi...

== Enunț ==
În orașul Nicăieri există <code>N</code> băieți răi. Se știe că între ei există <code>M</code> relații de prietenie. De-a lungul timpului, aceste prietenii au dus la apariția unor “''găști''”. Dacă doi băieți nu sunt prieteni dar au cel puțin un prieten comun spunem că “''se cunosc''”. Dacă doi băieți au cel puțin o cunoștință comună, atunci și ei se cunosc. O gașcă este un grup de băieți cu proprietatea că oricare ar fi doi băieți <code>x</code> și <code>y</code> din grup, aceștia “se cunosc”.

= Cerința =
Arpsod, știe exact cine este prieten cu cine și, fiind singurul băiat bun din oraș, și-a pus următoarele întrebări:

1. Câte găști există în oraș.

2. Dacă ar mai exista O SINGURĂ relație de prietenie pe lângă cele date, în câte moduri ar putea apărea aceasta, astfel încât să se obțină o gașcă cu număr maxim de membri. Pentru că numărul de moduri poate fi foarte mare, Arpsod se mulțumește cu restul împărțirii rezultatului la <code>666013</code>.

Pentru că e prea ocupat să se baricadeze în casă de frica băieților răi, Arpsod vă roagă pe voi să aflați cele două răspunsuri

= Date de intrare =
Pe prima linie a fișierului <code>gastiIN.txt</code> se vor afla două numere naturale <code>N</code> și <code>M</code> reprezentând numărul de băieți răi, respectiv numărul de relații de prietenie. Următoarele <code>M</code> linii vor conține câte două numere naturale <code>x</code> și <code>y</code> cu semnificația că există o relație de prietenie între băiatul <code>x</code> și băiatul <code>y</code>.

= Date de ieșire =
Pe singura linie a fișierului <code>gastiOUT.txt</code> se vor afișa două numere separate prin spațiu, primul reprezentând răspunsul pentru prima cerința iar cel de-al doilea pentru a doua cerință.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

= Restricții și precizări =

* <code>1 ≤ N ≤ 100.000</code>
* <code>0 ≤ M ≤ 300.000</code>
* Dacă <code>x</code> este prieten cu <code>y</code> atunci și <code>y</code> este prieten cu <code>x</code>
* Toate relațiile de prietenie sunt unice
* La numărarea modurilor de adaugare a unei prietenii, prietenia <code>x y</code> si prietenia <code>y x</code> coincid
* Se garanteaza ca pentru <code>30%</code> din teste <code>1 ≤ N ≤ 1000</code>
* Pentru rezolvarea corectă a primei cerințe se acordă <code>40%</code> din punctajul pe testul respectiv iar pentru rezolvarea corectă a celei de-a doua cerințe se acordă <code>60%</code> din punctajul pe testul respectiv
* Fișierul de ieșire TREBUIE să conțină DOUĂ valori chiar dacă doriți să rezolvați o singură cerință din cele două
* Arpsod înțelege cel mai bine hit-ul lui Bob Marley: “Bad Boys”

= Exemplul 1: =
<code>gastiIN.txt</code>
5 3
1 2
2 3
3 1
<code>gastiOUT.txt</code>
3 6

=== Explicație ===
Există <code>3</code> găști în oraș, formate:

Gașca <code>1</code>: <code>1</code>, <code>2</code>, <code>3</code>

Gașca <code>2</code>: <code>4</code>

Gașca <code>3</code>: <code>5</code>

Sunt <code>6</code> moduri de a face o relație de prietenie astfel încât gașca obținută să aibă număr maxim de membri

<code>4</code> cu <code>1</code>, <code>4</code> cu <code>2</code>, <code>4</code> cu <code>3</code>, <code>5</code> cu <code>1</code>, <code>5</code> cu <code>2</code>, <code>5</code> cu <code>3</code>

== Exemplul 2: ==
<code>gastiIN.txt</code>
1000001 23
1 2
2 3
3 1
<code>gastiOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def DFS(node, gasca):
global cnt
cnt += 1
Gasca[node] = gasca

for neighbor in G[node]:
if Gasca[neighbor] == 0:
DFS(neighbor, gasca)

def verifica_restrictii(N, M, G):
if not (1 <= N <= 100000 and 0 <= M <= 300000):
return "Datele nu corespund restrictiilor impuse"

for i in range(1, N + 1):
if not (0 <= len(G[i]) <= 100000):
return "Datele nu corespund restrictiilor impuse"

return None

Nmax = 100002
Mod = 666013

G = [[] for _ in range(Nmax)]
Gasca = [0] * Nmax
Members = [0] * Nmax
Cate = [0] * Nmax

cnt = 0

with open("gastiIN.txt", "r") as fin:
N, M = map(int, fin.readline().split())

restrictii_msg = verifica_restrictii(N, M, G)
if restrictii_msg is not None:
with open("gastiOUT.txt", "w") as fout:
fout.write(restrictii_msg)
exit()

for _ in range(M):
x, y = map(int, fin.readline().split())
if y not in G[x]:
G[x].append(y)
if x not in G[y]:
G[y].append(x)

gasti = 0
max1, max2 = -1, -1

for i in range(1, N + 1):
if Gasca[i] == 0:
cnt = 0
gasti += 1
DFS(i, gasti)
Members[gasti] = cnt
Cate[Members[gasti]] += 1

if Members[gasti] > max1:
max2 = max1
max1 = Members[gasti]
elif Members[gasti] > max2:
max2 = Members[gasti]

if max1 != max2:
x = (Cate[max1] * max1) % Mod
y = (Cate[max2] * max2) % Mod
else:
x = (max1 * max1) % Mod
y = (Cate[max1] * (Cate[max1] - 1) // 2) % Mod

rez = (x * y) % Mod

with open("gastiOUT.txt", "w") as fout:
fout.write(f"{gasti} {rez}")

</syntaxhighlight>

2710 - Cuv

2024-01-04T14:32:32Z

Rus Marius:

== Enunț ==
Se dau <code>n</code> cuvinte formate doar din litere mici. Trebuie construit un nou cuvânt <code>C</code> de <code>n</code> litere format astfel: prima literă a lui <code>C</code> este din primul cuvânt, a doua literă este din al doilea cuvânt, …, a <code>n</code>-a literă este din cel de-al <code>n</code>-lea cuvânt. În plus, literele cuvântului <code>C</code> trebuie să fie distincte.

= Cerința =
Să se determine cuvântul <code>C</code> minim lexicografic ce se poate forma utilizând litere distincte extrase din cuvintele inițiale.

= Date de intrare =
Programul citește de la tastatură numărul <code>n</code>, iar apoi cele <code>n</code> cuvinte separate prin spațiu.

= Date de ieșire =
Programul va afișa pe ecran cuvântul <code>C</code> minim lexicografic care se poate obține din litere distincte.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

= Restricții și precizări =

* <code>1 ≤ n ≤ 9</code>
* Cele <code>n</code> cuvinte au cel puțin o literă și cel mult <code>6</code> litere
* Este garantat că <code>C</code> se poate forma din cuvintele inițiale

= Exemplul 1: =
Intrare
3
gem de caise
Ieșire
eda

= Exemplul 2: =
Intrare
10
Ieșire
"Datele nu corespund restrictiilor impuse"

== Rezolvare: ==
<syntaxhighlight lang="python3" line="1">
def backtracking_permutations(words, current_permutation, used_letters, result):
if len(current_permutation) == len(words):
result.append(current_permutation)
return

current_word = words[len(current_permutation)]
for letter in current_word:
if letter not in used_letters:
backtracking_permutations(
words,
current_permutation + letter,
used_letters + letter,
result
)

def find_min_lexicographic_permutation(words):
result = []
backtracking_permutations(words, "", "", result)
return min(result)

def check_restrictions(n, words):
if n < 1 or n > 9:
return False

for word in words:
if len(word) < 1 or len(word) > 6:
return False

return True

def main():
try:
n = int(input("Introduceti numarul de cuvinte: "))

if n > 9:
print("Datele nu corespund restrictiilor impuse.")
return

words = input("Introduceti cele %d cuvinte separate prin spațiu: " % n).split()

if not check_restrictions(n, words):
print("Datele nu corespund restrictiilor impuse.")
return

result = find_min_lexicographic_permutation(words)

print("Cuvântul C minim lexicografic este:", result)
except ValueError:
print("Datele nu corespund restrictiilor impuse.")

if __name__ == "__main__":
main()

</syntaxhighlight>

2710 - Cuv

2024-01-04T14:32:18Z

Rus Marius: Pagină nouă: == Enunț == Se dau <code>n</code> cuvinte formate doar din litere mici. Trebuie construit un nou cuvânt <code>C</code> de <code>n</code> litere format astfel: prima literă a lui <code>C</code> este din primul cuvânt, a doua literă este din al doilea cuvânt, …, a <code>n</code>-a literă este din cel de-al <code>n</code>-lea cuvânt. În plus, literele cuvântului <code>C</code> trebuie să fie distincte. = Cerința = Să se determine cuvântul <code>C</code> minim le...

== Enunț ==
Se dau <code>n</code> cuvinte formate doar din litere mici. Trebuie construit un nou cuvânt <code>C</code> de <code>n</code> litere format astfel: prima literă a lui <code>C</code> este din primul cuvânt, a doua literă este din al doilea cuvânt, …, a <code>n</code>-a literă este din cel de-al <code>n</code>-lea cuvânt. În plus, literele cuvântului <code>C</code> trebuie să fie distincte.

= Cerința =
Să se determine cuvântul <code>C</code> minim lexicografic ce se poate forma utilizând litere distincte extrase din cuvintele inițiale.

= Date de intrare =
Programul citește de la tastatură numărul <code>n</code>, iar apoi cele <code>n</code> cuvinte separate prin spațiu.

= Date de ieșire =
Programul va afișa pe ecran cuvântul <code>C</code> minim lexicografic care se poate obține din litere distincte.

= Restricții și precizări =

* <code>1 ≤ n ≤ 9</code>
* Cele <code>n</code> cuvinte au cel puțin o literă și cel mult <code>6</code> litere
* Este garantat că <code>C</code> se poate forma din cuvintele inițiale

= Exemplul 1: =
Intrare
3
gem de caise
Ieșire
eda

= Exemplul 2: =
Intrare
10
Ieșire
"Datele nu corespund restrictiilor impuse"

== Rezolvare: ==
<syntaxhighlight lang="python3" line="1">
def backtracking_permutations(words, current_permutation, used_letters, result):
if len(current_permutation) == len(words):
result.append(current_permutation)
return

current_word = words[len(current_permutation)]
for letter in current_word:
if letter not in used_letters:
backtracking_permutations(
words,
current_permutation + letter,
used_letters + letter,
result
)

def find_min_lexicographic_permutation(words):
result = []
backtracking_permutations(words, "", "", result)
return min(result)

def check_restrictions(n, words):
if n < 1 or n > 9:
return False

for word in words:
if len(word) < 1 or len(word) > 6:
return False

return True

def main():
try:
n = int(input("Introduceti numarul de cuvinte: "))

if n > 9:
print("Datele nu corespund restrictiilor impuse.")
return

words = input("Introduceti cele %d cuvinte separate prin spațiu: " % n).split()

if not check_restrictions(n, words):
print("Datele nu corespund restrictiilor impuse.")
return

result = find_min_lexicographic_permutation(words)

print("Cuvântul C minim lexicografic este:", result)
except ValueError:
print("Datele nu corespund restrictiilor impuse.")

if __name__ == "__main__":
main()

</syntaxhighlight>

1810 - Cifre Gen 5

2024-01-04T14:06:19Z

Rus Marius: Pagină nouă: = Cerința = Scrieți un program care citeşte o valoare naturală nenulă impară pentru <code>n</code> şi apoi generează şi afişează în ordine crescătoare lexicografic toate combinaţiile formate din <code>n</code> cifre care îndeplinesc următoarele proprietăţi: - încep şi se termină cu <code>0</code>; - modulul diferenţei între oricare două cifre alăturate dintr-o combinaţie este <code>1</code>. Astfel, pentru <code>n=5</code>, combinaţiile afişate...

= Cerința =
Scrieți un program care citeşte o valoare naturală nenulă impară pentru <code>n</code> şi apoi generează şi afişează în ordine crescătoare lexicografic toate combinaţiile formate din <code>n</code> cifre care îndeplinesc următoarele proprietăţi:

- încep şi se termină cu <code>0</code>;

- modulul diferenţei între oricare două cifre alăturate dintr-o combinaţie este <code>1</code>.

Astfel, pentru <code>n=5</code>, combinaţiile afişate sunt, în ordine, următoarele: <code>01010, 01210</code>.

= Date de intrare =
Programul citește de la tastatură numărul <code>n</code>, impar.

= Date de ieșire =
Programul va afișa pe ecran, pe rânduri separate, soluțiile generate.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

= Restricții și precizări =

* <code>3 ≤ n ≤ 19</code>

= Exemplul 1: =
Intrare
5
Ieșire
01010
01210

= Exemplul 2: =
Intrare
40
Ieșire
Datele introduse nu corespund restricțiilor impuse.
<syntaxhighlight lang="python3" line="1">
def check_restrictions(n):
if 3 <= n <= 19 and n % 2 == 1:
return True
else:
print("Datele introduse nu corespund restricțiilor impuse.")
return False

def generate_combinations(n, current_combination):
if len(current_combination) == n:
if current_combination[0] == 0 and current_combination[-1] == 0:
print("".join(map(str, current_combination)))
else:
for digit in range(0, 10):
if not current_combination or abs(digit - current_combination[-1]) == 1:
current_combination.append(digit)
generate_combinations(n, current_combination)
current_combination.pop()

# Funcția principală
def main():
# Citirea valorii pentru n
n = int(input("Introduceți un număr natural nenul impar n: "))

# Verificarea restricțiilor
if not check_restrictions(n):
return

# Inițializarea listei cu prima cifră (0)
current_combination = []

# Generarea și afișarea combinațiilor
generate_combinations(n, current_combination)

if __name__ == "__main__":
main()

</syntaxhighlight>

0320 - Partitii Numar

2024-01-04T13:19:51Z

Rus Marius: Pagină nouă: = Cerinţa = Se dă un număr natural <code>n</code>. Determinaţi, în ordine lexicografică, toate modalităţile de a-l scrie pe <code>n</code> ca sumă de numere naturale. = Date de intrare = Fişierul de intrare <code>partitiinumarIN.txt</code> conţine pe prima linie numărul <code>n</code>. = Date de ieşire = Fişierul de ieşire <code>partitiinumarOUT.txt</code> va conţine pe fiecare linie câte un şir de numere naturale ordonate crescător, separate prin câte u...

= Cerinţa =
Se dă un număr natural <code>n</code>. Determinaţi, în ordine lexicografică, toate modalităţile de a-l scrie pe <code>n</code> ca sumă de numere naturale.

= Date de intrare =
Fişierul de intrare <code>partitiinumarIN.txt</code> conţine pe prima linie numărul <code>n</code>.

= Date de ieşire =
Fişierul de ieşire <code>partitiinumarOUT.txt</code> va conţine pe fiecare linie câte un şir de numere naturale ordonate crescător, separate prin câte un spaţiu. Suma numerelor din fiecare şir este <code>n</code>. Şirurile vor fi afişate în ordine lexicografică.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

= Restricţii şi precizări =

* <code>1 ≤ n ≤ 40</code>

= Exemplul 1: =
<code>partitiinumarIN.txt</code>
5
<code>partitiinumarOUT.txt</code>
1 1 1 1 1
1 1 1 2
1 1 3
1 2 2
1 4
2 3
5

= Exemplul 2: =
<code>partitiinumarIN.txt</code>
41
<code>partitiinumarOUT.txt</code>
"Datele nu corespund restrictiilor impuse"

== Rezolvare: ==
<syntaxhighlight lang="python3" line="1">
def check_restrictions(n):
return 1 <= n <= 40

def generate_partitions(n, current_partition, all_partitions):
if n == 0:
all_partitions.append(list(current_partition))
return
for i in range(1, n + 1):
if not current_partition or i >= current_partition[-1]:
current_partition.append(i)
generate_partitions(n - i, current_partition, all_partitions)
current_partition.pop()

def write_partitions_to_file(partitions, output_file):
with open(output_file, 'w') as file:
for partition in partitions:
partition_str = ' '.join(map(str, partition))
file.write(partition_str + '\n')

def process_input(input_file, output_file):
with open(input_file, 'r') as file:
n = int(file.readline().strip())

if not check_restrictions(n):
with open(output_file, 'w') as file:
file.write("Datele nu corespund restrictiilor impuse\n")
else:
all_partitions = []
generate_partitions(n, [], all_partitions)
all_partitions.sort()
write_partitions_to_file(all_partitions, output_file)

if __name__ == "__main__":
input_file = "partitiinumarIN.txt"
output_file = "partitiinumarOUT.txt"

process_input(input_file, output_file)

</syntaxhighlight>

3147 - Fete Graf

2023-12-30T14:49:24Z

Rus Marius: Pagină nouă: = Cerința = Se dă lista de muchii ale unui graf neorientat, conex, planar. Determinați numărul de fețe ale acestuia dacă este desenat astfel încât 2 muchii nu se intersectează. O față este o regiune înconjurată de muchii. = Date de intrare = Se vor citi repetat de la tastatură muchiile grafului. = Date de ieșire = Programul va afișa pe ecran numărul de fețe ale grafului.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu coresp...

= Cerința =
Se dă lista de muchii ale unui graf neorientat, conex, planar. Determinați numărul de fețe ale acestuia dacă este desenat astfel încât 2 muchii nu se intersectează.

O față este o regiune înconjurată de muchii.

= Date de intrare =
Se vor citi repetat de la tastatură muchiile grafului.

= Date de ieșire =
Programul va afișa pe ecran numărul de fețe ale grafului.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

= Restricții și precizări =

* Ca și față, este considerată și regiunea exterioară, infinit de mare, a grafului.
* Numărul de muchii va fi mai mic decât <code>1.000.000</code>.

= Exemplul 1: =
Intrare
4

4

1 2

2 3

3 4

4 1

Ieșire
2

=== Explicație ===
Graful se poate desena sub forma unui pătrat. Are doar o față, la care se adaugă și regiunea exterioară.

== Exemplul 2: ==
Intrare
10000000
1000000000000000
Ieșire
Nu corespunde restricțiilor impuse.

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verificare_restricții(numar_varfuri, numar_muchii):
return 0 < numar_varfuri < 1000000 and 0 < numar_muchii < 1000000

def numar_fețe(numar_varfuri, numar_muchii):
# Folosim formula lui Euler pentru grafuri planare: V - E + F = 2
# Deoarece graful este conex, V = E + 2, deci substituim în formulă.
# Obținem E + 2 - E + F = 2, și astfel F = 2.
return 2

def main():
try:
numar_varfuri = int(input("Introduceți numărul de vârfuri ale grafului: "))
numar_muchii = int(input("Introduceți numărul de muchii ale grafului: "))

if not verificare_restricții(numar_varfuri, numar_muchii):
print("Nu corespunde restricțiilor impuse.")
return

numar_muchii_introduse = 0
while numar_muchii_introduse < numar_muchii:
input_muchie = input(f"Introduceți o muchie sub forma x y (muchiile introduse: {numar_muchii_introduse}/{numar_muchii}): ")

if ' ' in input_muchie:
v1, v2 = map(int, input_muchie.split())

if 0 < v1 <= numar_varfuri and 0 < v2 <= numar_varfuri:
numar_muchii_introduse += 1
else:
print(f"Vârfurile muchiei trebuie să fie între 1 și {numar_varfuri} inclusiv.")
else:
print("Introduceți o pereche validă de vârfuri sub forma x y.")

rezultat = numar_fețe(numar_varfuri, numar_muchii)
print(f"Numărul de fețe al grafului este: {rezultat}")

except ValueError:
print("Introduceți numere valide pentru numărul de vârfuri și muchii.")

if __name__ == "__main__":
main()

</syntaxhighlight>

0477 - Lanturi 1

2023-12-30T13:33:10Z

Rus Marius: Pagină nouă: = Cerinţa = Se dă lista muchiilor unui graf neorientat cu <code>n</code> vârfuri și trei vârfuri <code>p q r</code>. Să se determine toate lanțurile elementare cu extremitățile în <code>p</code> și <code>q</code> care nu conțin vârful <code>r</code>. = Date de intrare = Fişierul de intrare <code>lanturi1IN.txt</code> conţine pe prima linie numerele <code>n</code> și <code>m</code>, reprezentând numărul de vârfuri ale grafului și numărul de muchii date î...

= Cerinţa =
Se dă lista muchiilor unui graf neorientat cu <code>n</code> vârfuri și trei vârfuri <code>p q r</code>. Să se determine toate lanțurile elementare cu extremitățile în <code>p</code> și <code>q</code> care nu conțin vârful <code>r</code>.

= Date de intrare =
Fişierul de intrare <code>lanturi1IN.txt</code> conţine pe prima linie numerele <code>n</code> și <code>m</code>, reprezentând numărul de vârfuri ale grafului și numărul de muchii date în continuare. Fiecare dintre următoarele <code>m</code> linii conține câte o pereche de numere <code>i j</code>, cu semnificația că există muchie între <code>i</code> și <code>j</code>.

Următoarea linie conține trei numere <code>p q r</code>, cu semnificația precizată.

= Date de ieşire =
Fişierul de ieşire <code>lanturi1OUT.txt</code> va conține, în ordine lexicografică, toate lanțurile elementare cu extremitățile în <code>p</code>, respectiv <code>q</code>, care nu conțin vârful <code>r</code> , fiecare lanț fiind afișat pe câte o linie a fișierului, vârfurile dintr-un lanț fiind separate prin exact un spațiu.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

= Restricţii şi precizări =

* <code>1 ≤ n ≤ 20</code>
* <code>1 ≤ i , j ≤n</code>
* muchiile se pot repeta în fișierul de intrare
* <code>1 ≤ p , q , r ≤ n</code>
* <code>p</code>, <code>q</code> și <code>r</code> sunt diferite

= Exemplul 1: =
<code>lanturi1IN.txt</code>
5 8
1 4
1 3
3 5
4 5
2 4
1 2
4 2
3 4
2 5 3
<code>lanturi1OUT.txt</code>
2 1 4 5
2 4 5

= Exemplul 2: =
<code>lanturi1IN.txt</code>
100 100
1 4
1 3
3 5
4 5
2 4
1 2
4 2
3 4
2 5 3
<code>lanturi1OUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def is_valid_edge(u, v, path, r, visited):
return v != r and v not in path and not visited[v]

def generate_paths(graph, p, q, r, n):
def backtrack(current, path, visited):
visited[current] = True

if current == q:
result.append(path[:])
visited[current] = False
return

for neighbor in graph[current]:
if is_valid_edge(current, neighbor, path, r, visited):
path.append(neighbor)
backtrack(neighbor, path, visited)
path.pop()

visited[current] = False

result = []
visited = {i: False for i in range(1, n + 1)}
backtrack(p, [p], visited)
return result

def check_restrictions(n, m, edges, p, q, r):
if not (1 <= n <= 20 and 1 <= p <= n and 1 <= q <= n and 1 <= r <= n and p != q != r):
with open('lanturi1OUT.txt', 'w') as output_file:
output_file.write("Datele nu corespund restrictiilor impuse\n")
return False

for edge in edges:
u, v = edge
if not (1 <= u <= n and 1 <= v <= n):
with open('lanturi1OUT.txt', 'w') as output_file:
output_file.write("Datele nu corespund restrictiilor impuse\n")
return False

return True

def main():
with open('lanturi1IN.txt', 'r') as input_file:
n, m = map(int, input_file.readline().split())
edges = [tuple(map(int, input_file.readline().split())) for _ in range(m)]

line = input_file.readline().split()
if len(line) < 3:
with open('lanturi1OUT.txt', 'w') as output_file:
output_file.write("Datele nu corespund restrictiilor impuse\n")
return

p, q, r = map(int, line)

if not check_restrictions(n, m, edges, p, q, r):
return

graph = {i: [] for i in range(1, n + 1)}
for edge in edges:
u, v = edge
graph[u].append(v)
graph[v].append(u)

paths = generate_paths(graph, p, q, r, n)
unique_paths = [list(item) for item in set(tuple(path) for path in paths)]
unique_paths.sort()

with open('lanturi1OUT.txt', 'w') as output_file:
for path in unique_paths:
output_file.write(" ".join(map(str, path)) + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

0476 - Lanturi

2023-12-30T13:23:44Z

Rus Marius: Pagină nouă: = Cerinţa = Se dă lista muchiilor unui graf neorientat cu <code>n</code> vârfuri și trei vârfuri <code>p q r</code>. Să se determine toate lanțurile elementare cu extremitățile în <code>p</code> și <code>q</code> care conțin vârful <code>r</code>. = Date de intrare = Fişierul de intrare <code>lanturiIN.txt</code> conţine pe prima linie numerele <code>n</code> și <code>m</code>, reprezentând numărul de vârfuri ale grafului și numărul de muchii date în co...

= Cerinţa =
Se dă lista muchiilor unui graf neorientat cu <code>n</code> vârfuri și trei vârfuri <code>p q r</code>. Să se determine toate lanțurile elementare cu extremitățile în <code>p</code> și <code>q</code> care conțin vârful <code>r</code>.

= Date de intrare =
Fişierul de intrare <code>lanturiIN.txt</code> conţine pe prima linie numerele <code>n</code> și <code>m</code>, reprezentând numărul de vârfuri ale grafului și numărul de muchii date în continuare. Fiecare dintre următoarele <code>m</code> linii conține câte o pereche de numere <code>i j</code>, cu semnificația că există muchie între <code>i</code> și <code>j</code>.

Următoarea linie conține trei numere <code>p q r</code>, cu semnificația precizată.

= Date de ieşire =
Fişierul de ieşire <code>lanturiOUT.txt</code> va conține, în ordine lexicografică, toate lanțurile elementare cu extremitățile în <code>p</code>, respectiv <code>q</code>, care conțin vârful <code>r</code>, fiecare lanț fiind afișat pe câte o linie a fișierului, vârfurile dintr-un lanț fiind separate prin exact un spațiu.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

= Restricţii şi precizări =

* <code>1 ≤ n ≤ 20</code>
* <code>1 ≤ i , j ≤n</code>
* muchiile se pot repeta în fișierul de intrare
* <code>1 ≤ p , q , r ≤ n</code>
* <code>p</code>, <code>q</code> și <code>r</code> sunt diferite

= Exemplul 1: =
<code>lanturiIN.txt</code>
5 8
1 4
1 3
3 5
4 5
2 4
1 2
4 2
3 4
2 5 3
<code>lanturiOUT.txt</code>
2 1 3 4 5
2 1 3 5
2 1 4 3 5
2 4 1 3 5
2 4 3 5

= Exemplul 2: =
<code>lanturiIN.txt</code>
100 100
1 4
1 3
3 5
4 5
2 4
1 2
4 2
3 4
2 5 3
<code>lanturiOUT.txt</code>
Nu corespunde restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def gaseste_lanturi_elementare(graph, p, q, r):
def dfs(curent, cale):
nonlocal rezultat
vizitat[curent] = True
cale.append(curent)

if curent == q:
if r in cale:
rezultat.add(tuple(cale))
else:
for vecin in graph[curent]:
if not vizitat[vecin]:
dfs(vecin, cale)

vizitat[curent] = False
cale.pop()

rezultat = set()
vizitat = [False] * (n + 1)
dfs(p, [])

return rezultat

def verifica_restrictii(n, p, q, r):
if not (1 <= n <= 20) or not (1 <= p <= n) or not (1 <= q <= n) or not (1 <= r <= n) or p == q or p == r or q == r:
return False
return True

def citeste_intrare(nume_fisier):
with open(nume_fisier, 'r') as fisier:
try:
n, m = map(int, fisier.readline().split())
graf = {i: [] for i in range(1, n + 1)}

for _ in range(m):
linie = fisier.readline().split()
if len(linie) != 2:
raise ValueError("Nu corespunde restrictiilor impuse")
i, j = map(int, linie)
graf[i].append(j)
graf[j].append(i)

linie = fisier.readline().split()
if len(linie) != 3:
raise ValueError("Nu corespunde restrictiilor impuse")

p, q, r = map(int, linie)

if not (1 <= p <= n) or not (1 <= q <= n) or not (1 <= r <= n) or p == q or p == r or q == r:
raise ValueError("Nu corespunde restrictiilor impuse")

except ValueError as e:
with open('lanturiOUT.txt', 'w') as fisier_iesire:
fisier_iesire.write(f"Nu corespunde restrictiilor impuse")
exit()

return n, graf, p, q, r

def scrie_iesire(nume_fisier, lanturi):
with open(nume_fisier, 'w') as fisier:
if lanturi == "Nu corespunde restricțiilor impuse":
fisier.write(lanturi)
else:
for lant in lanturi:
fisier.write(' '.join(map(str, lant)) + '\n')

if __name__ == '__main__':
fisier_intrare = 'lanturiIN.txt'
fisier_iesire = 'lanturiOUT.txt'

n, graf, p, q, r = citeste_intrare(fisier_intrare)

if not verifica_restrictii(n, p, q, r):
scrie_iesire(fisier_iesire, "Nu corespunde restrictiilor impuse")
else:
lanturi = gaseste_lanturi_elementare(graf, p, q, r)
lanturi = [list(lant) for lant in lanturi]
lanturi.sort()

scrie_iesire(fisier_iesire, lanturi)

</syntaxhighlight>

0479 - Lant Maxim

2023-12-30T13:00:53Z

Rus Marius: Pagină nouă: = Cerinţa = Se dă lista muchiilor unui graf neorientat cu <code>n</code> vârfuri și două vârfuri <code>p q</code>. Să se determine cel mai lung lanț elementar cu extremitățile <code>p</code> și <code>q</code>. = Date de intrare = Fişierul de intrare <code>lantmaximIN.txt</code> conţine pe prima linie numerele <code>n</code> și <code>m</code>, reprezentând numărul de vârfuri ale grafului și numărul de muchii date în continuare. Fiecare dintre următoarele...

= Cerinţa =
Se dă lista muchiilor unui graf neorientat cu <code>n</code> vârfuri și două vârfuri <code>p q</code>. Să se determine cel mai lung lanț elementar cu extremitățile <code>p</code> și <code>q</code>.

= Date de intrare =
Fişierul de intrare <code>lantmaximIN.txt</code> conţine pe prima linie numerele <code>n</code> și <code>m</code>, reprezentând numărul de vârfuri ale grafului și numărul de muchii date în continuare. Fiecare dintre următoarele <code>m</code> linii conține câte o pereche de numere <code>i j</code>, cu semnificația că există muchie între <code>i</code> și <code>j</code>.

Următoarea linie conține două numere <code>p q</code>.

= Date de ieşire =
Fişierul de ieşire <code>lantmaximOUT.txt</code> va conține cel mai lung lanț elementar cu extremitățile <code>p</code> și <code>q</code>, vârfurile sale fiind separate prin exact un spațiu. Dacă sunt mai multe lanțuri de lungime maximă, se va afișa primul în ordine lexicografică.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

= Restricţii şi precizări =

* <code>1 ≤ n ≤ 20</code>
* <code>1 ≤ i , j ≤n</code>
* muchiile se pot repeta în fișierul de intrare
* <code>1 ≤ p , q ≤ n</code>
* pentru toate datele de test, va exista cel puțin un lanț cu extremitățile <code>p q</code>

= Exemplul 1: =
<code>lantmaximIN.txt</code>
5 7
1 4
1 3
3 5
4 5
1 2
4 2
3 4
2 5
<code>lantmaximOUT.txt</code>
2 1 3 4 5

= Exemplul 2: =
<code>lantmaximIN.txt</code>
100 100
1 4
1 3
3 5
4 5
1 2
4 2
3 4
2 5
<code>lantmaximOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def citeste_graf(filename):
with open(filename, 'r') as file:
try:
n, m = map(int, file.readline().split())
graf = {}
muchii = []
for _ in range(m):
i, j = map(int, file.readline().split())
muchii.append((i, j))
if i not in graf:
graf[i] = []
if j not in graf:
graf[j] = []
graf[i].append(j)
graf[j].append(i)
p, q = map(int, file.readline().split())
except ValueError:
return None, None, None, None, None, None

return n, m, muchii, graf, p, q

def verifica_restrictii(n, m, muchii, p, q):
if not (1 <= n <= 20):
return False
for i, j in muchii:
if not (1 <= i <= n) or not (1 <= j <= n):
return False
if not (1 <= p <= n) or not (1 <= q <= n):
return False
return True

def dfs(graf, start, end, path, visited, results):
visited[start] = True
path.append(start)

if start == end:
results.append(path.copy())

for neighbor in graf[start]:
if not visited[neighbor]:
dfs(graf, neighbor, end, path, visited, results)

path.pop()
visited[start] = False

def lanț_maxim(filename_in, filename_out):
n, m, muchii, graf, p, q = citeste_graf(filename_in)

if n is None:
with open(filename_out, 'w') as file:
file.write("Datele nu corespund restrictiilor impuse")
return

if not verifica_restrictii(n, m, muchii, p, q):
with open(filename_out, 'w') as file:
file.write("Datele nu corespund restrictiilor impuse")
return

visited = {v: False for v in graf}
results = []

dfs(graf, p, q, [], visited, results)

if results:
results.sort()
result = results[0]

with open(filename_out, 'w') as file:
file.write(' '.join(map(str, result)))
else:
with open(filename_out, 'w') as file:
file.write("Nu există lanț între vârfurile date")

# Apelul funcției pentru datele din fișierul de intrare lantmaximIN.txt și scrierea rezultatului în lantmaximOUT.txt
lanț_maxim("lantmaximIN.txt", "lantmaximOUT.txt")

</syntaxhighlight>

4152 - Lant Maxim 1

2023-12-30T12:50:44Z

Rus Marius: Pagină nouă: = Cerinţa = Se dă lista muchiilor unui graf neorientat cu <code>n</code> vârfuri și un vârf <code>q</code>. Să se determine cel mai lung lanț elementar cu extremitatea finală în <code>q</code>. = Date de intrare = Fişierul de intrare <code>lantmaxim1IN.txt</code> conţine pe prima linie numerele <code>n</code> și <code>m</code>, reprezentând numărul de vârfuri ale grafului și numărul de muchii date în continuare. Fiecare dintre următoarele <code>m</code> li...

= Cerinţa =
Se dă lista muchiilor unui graf neorientat cu <code>n</code> vârfuri și un vârf <code>q</code>. Să se determine cel mai lung lanț elementar cu extremitatea finală în <code>q</code>.

= Date de intrare =
Fişierul de intrare <code>lantmaxim1IN.txt</code> conţine pe prima linie numerele <code>n</code> și <code>m</code>, reprezentând numărul de vârfuri ale grafului și numărul de muchii date în continuare. Fiecare dintre următoarele <code>m</code> linii conține câte o pereche de numere <code>i j</code>, cu semnificația că există muchie între <code>i</code> și <code>j</code>.

Următoarea linie conține numărul <code>q</code>.

= Date de ieşire =
Fişierul de ieşire <code>lantmaxim1OUT.txt</code> va conține cel mai lung lanț elementar cu extremitățile <code>p</code> și <code>q</code>, vârfurile sale fiind separate prin exact un spațiu. Dacă sunt mai multe lanțuri de lungime maximă, se va afișa primul în ordine lexicografică.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

= Restricţii şi precizări =

* <code>1 ≤ n ≤ 20</code>
* <code>1 ≤ i , j ≤ n</code>
* <code>1 ≤ q ≤ n</code>

= Exemplul 1: =
<code>lantmaxim1IN.txt</code>
5 6
1 4
1 3
3 5
4 5
1 2
3 4
5
<code>lantmaxim1OUT.txt</code>
2 1 3 4 5

= Exemplul 2: =
<code>lantmaxim1IN.txt</code>
21 21
1 4
1 3
3 5
4 5
1 2
3 4
5
<code>lantmaxim1OUT.txt</code>
Nu corespunde restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verifica_restrictii(n, muchii, q):
if not (1 <= n <= 20):
return False
for u, v in muchii:
if not (1 <= u <= n) or not (1 <= v <= n):
return False
if not (1 <= q <= n):
return False
return True

def gestionare_restrictii(file_path_out):
with open(file_path_out, 'w') as file_out:
file_out.write("Nu corespunde restrictiilor impuse")
exit()

def citeste_graf(file_path):
with open(file_path, 'r') as file:
n, m = map(int, file.readline().split())
muchii = [tuple(map(int, file.readline().split())) for _ in range(m)]

try:
q = int(file.readline())
except ValueError:
gestionare_restrictii("lantmaxim1OUT.txt")

if not verifica_restrictii(n, muchii, q):
gestionare_restrictii("lantmaxim1OUT.txt")

return n, muchii, q

def dfs_lant_maxim(q, graf, vizitat, path, lant_maxim):
vizitat[q] = True
path.append(q)

for vecin in graf[q]:
if not vizitat[vecin]:
dfs_lant_maxim(vecin, graf, vizitat, path, lant_maxim)

if len(path) >= len(lant_maxim):
lant_maxim.clear()
lant_maxim.extend(path)

path.pop()
vizitat[q] = False

def lungime_lant(q, graf, vizitat):
lant_maxim = []
dfs_lant_maxim(q, graf, vizitat, [], lant_maxim)
return len(lant_maxim), lant_maxim

def gaseste_lant_maxim(n, muchii, q):
graf = {i: [] for i in range(1, n + 1)}
for u, v in muchii:
graf[u].append(v)
graf[v].append(u)

vizitat = {i: False for i in range(1, n + 1)}

lungime_maxima = 0
lant_maxim = []

for v in range(1, n + 1):
if not vizitat[v]:
lungime, lant = lungime_lant(v, graf, vizitat)
if lungime > lungime_maxima:
lungime_maxima = lungime
lant_maxim = lant

return lant_maxim

def scrie_lant_maxim(file_path, lant_maxim):
with open(file_path, 'w') as file:
file.write(' '.join(map(str, lant_maxim)) + '\n')

if __name__ == "__main__":
file_in = "lantmaxim1IN.txt"
file_out = "lantmaxim1OUT.txt"

n, muchii, q = citeste_graf(file_in)
lant_maxim = gaseste_lant_maxim(n, muchii, q)

if lant_maxim:
scrie_lant_maxim(file_out, lant_maxim)
else:
with open(file_out, 'w') as file_out:
file_out.write("Nu corespunde restrictiilor impuse")

</syntaxhighlight>

0475 - Lant

2023-12-30T12:45:22Z

Rus Marius: Pagină nouă: = Cerinţa = Se dă lista muchiilor unui graf neorientat cu <code>n</code> vârfuri și două vârfuri <code>p q</code>. Să se determine toate lanțurile elementare cu extremitățile <code>p</code> și <code>q</code>. = Date de intrare = Fişierul de intrare <code>lantIN.txt</code> conţine pe prima linie numerele <code>n</code> și <code>m</code>, reprezentând numărul de vârfuri ale grafului și numărul de muchii date în continuare. Fiecare dintre următoarele <code>...

= Cerinţa =
Se dă lista muchiilor unui graf neorientat cu <code>n</code> vârfuri și două vârfuri <code>p q</code>. Să se determine toate lanțurile elementare cu extremitățile <code>p</code> și <code>q</code>.

= Date de intrare =
Fişierul de intrare <code>lantIN.txt</code> conţine pe prima linie numerele <code>n</code> și <code>m</code>, reprezentând numărul de vârfuri ale grafului și numărul de muchii date în continuare. Fiecare dintre următoarele <code>m</code> linii conține câte o pereche de numere <code>i j</code>, cu semnificația că există muchie între <code>i</code> și <code>j</code>.

Următoarea linie conține două numere <code>p q</code>.

= Date de ieşire =
Fişierul de ieşire <code>lantOUT.txt</code> va conține, în ordine lexicografică, toate lanțurile elementare cu extremitățile în <code>p</code>, respectiv <code>q</code>, fiecare lanț fiind afișat pe câte o linie a fișierului, vârfurile dintr-un lanț fiind separate prin exact un spațiu.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

= Restricţii şi precizări =

* <code>1 ≤ n ≤ 20</code>
* <code>1 ≤ i , j ≤n</code>
* muchiile se pot repeta în fișierul de intrare
* <code>1 ≤ p , q ≤ n</code>

= Exemplul 1: =
<code>lantIN.txt</code>
5 8
1 4
1 3
3 5
4 5
2 4
1 2
4 2
3 4
2 5
<code>lantOUT.txt</code>
2 1 3 4 5
2 1 3 5
2 1 4 3 5
2 1 4 5
2 4 1 3 5
2 4 3 5
2 4 5

= Exemplul 2: =
<code>lantIN.txt</code>
1000 100
1 4
1 3
3 5
4 5
2 4
1 2
4 2
3 4
2 5
<code>lantOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verifica_restrictii(n, muchii, p, q):
if not (1 <= n <= 20):
return False
for u, v in muchii:
if not (1 <= u <= n) or not (1 <= v <= n):
return False
if not (1 <= p <= n) or not (1 <= q <= n):
return False
return True

def citeste_graf(file_path):
with open(file_path, 'r') as file:
n, m = map(int, file.readline().split())
muchii = [tuple(map(int, file.readline().split())) for _ in range(m)]

try:
p, q = map(int, file.readline().split())
except ValueError:
with open("lantOUT.txt", 'w') as file_out:
file_out.write("Datele nu corespund restrictiilor impuse")
exit()

if not verifica_restrictii(n, muchii, p, q):
with open("lantOUT.txt", 'w') as file_out:
file_out.write("Datele nu corespund restrictiilor impuse")
exit()

return n, muchii, p, q

def dfs(v, tinta, graf, vizitat, path, rezultat):
vizitat[v] = True
path.append(v)

if v == tinta:
rezultat.append(path.copy())
else:
for vecin in graf[v]:
if not vizitat[vecin]:
dfs(vecin, tinta, graf, vizitat, path, rezultat)

path.pop()
vizitat[v] = False

def gaseste_lanturi(n, muchii, p, q):
graf = {i: [] for i in range(1, n + 1)}
for u, v in muchii:
graf[u].append(v)
graf[v].append(u)

vizitat = {i: False for i in range(1, n + 1)}
rezultat = []

dfs(p, q, graf, vizitat, [], rezultat)

rezultat = list(set(tuple(lant) for lant in rezultat))
rezultat.sort()

return rezultat

def scrie_lanturi(file_path, lanturi):
with open(file_path, 'w') as file:
for lant in lanturi:
file.write(' '.join(map(str, lant)) + '\n')

if __name__ == "__main__":
file_in = "lantIN.txt"
file_out = "lantOUT.txt"

n, muchii, p, q = citeste_graf(file_in)
rezultat = gaseste_lanturi(n, muchii, p, q)
scrie_lanturi(file_out, rezultat)

</syntaxhighlight>

0474 - Verif Lant

2023-12-30T12:37:10Z

Rus Marius: Pagină nouă: = Cerinţa = Se dă lista muchiilor unui graf neorientat cu <code>n</code> vârfuri și mai multe șiruri de vârfuri din graf. Să se verifice despre fiecare șir dacă reprezintă un lanț. În caz afirmativ, să se precizeze dacă este elementar. = Date de intrare = Fişierul de intrare <code>veriflantIN.txt</code> conţine pe prima linie numerele <code>n</code> și <code>m</code>, reprezentând numărul de vârfuri ale grafului și numărul de muchii date în continuare....

= Cerinţa =
Se dă lista muchiilor unui graf neorientat cu <code>n</code> vârfuri și mai multe șiruri de vârfuri din graf. Să se verifice despre fiecare șir dacă reprezintă un lanț. În caz afirmativ, să se precizeze dacă este elementar.

= Date de intrare =
Fişierul de intrare <code>veriflantIN.txt</code> conţine pe prima linie numerele <code>n</code> și <code>m</code>, reprezentând numărul de vârfuri ale grafului și numărul de muchii date în continuare. Fiecare dintre următoarele <code>m</code> linii conține câte o pereche de numere <code>i j</code>, cu semnificația că există muchie între <code>i</code> și <code>j</code>.

Urmează numărul de șiruri <code>k</code>. Pentru fiecare șir se dă numărul de vârfuri și apoi vârfurile.

= Date de ieşire =
Fişierul de ieşire <code>veriflantOUT.txt</code> va conține <code>k</code> linii. Fiecare linie va contine unul dintre cuvintele <code>NU</code>, <code>ELEMENTAR</code>, <code>NEELEMENTAR</code>, după cum șirul de vârfuri corespunzător nu formează lanț, formează lanț elementar, respectiv formează lanț neelementar.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

= Restricţii şi precizări =

* <code>1 ≤ n ≤ 100</code>
* <code>1 ≤ i , j ≤ n</code>
* muchiile se pot repeta în fișierul de intrare
* <code>1 ≤ k ≤ 100</code>
* lungimea fiecărui șir dat este mai mică decât <code>200</code>

= Exemplul 1: =
<code>veriflantIN.txt</code>
5 8
1 4
1 3
3 5
4 5
2 4
1 2
4 2
3 4
3
5 1 2 3 4 5
4 2 4 5 3
5 2 4 3 4 5
<code>veriflantOUT.txt</code>
NU
ELEMENTAR
NEELEMENTAR

= Exemplul 2: =
<code>veriflantIN.txt</code>
1001 100
1 4
1 3
3 5
4 5
2 4
1 2
4 2
3 4
3
5 1 2 3 4 5
4 2 4 5 3
5 2 4 3 4 5
<code>veriflantOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def citire_graf(muchii):
graf = {}
for i, j in muchii:
if i not in graf:
graf[i] = []
if j not in graf:
graf[j] = []
graf[i].append(j)
graf[j].append(i)
return graf

def este_lant(graf, sir):
for i in range(len(sir) - 1):
if sir[i + 1] not in graf[sir[i]]:
return False
return True

def este_elementar(sir):
return len(set(sir)) == len(sir)

def verifica_restrictii(n, muchii, k, vrf_siruri):
if not (1 <= n <= 100):
return False
for i, j in muchii:
if not (1 <= i <= n and 1 <= j <= n):
return False
if not (1 <= k <= 100):
return False
for sir in vrf_siruri:
if not (len(sir) < 200):
return False
return True

# Deschideți fișierele de intrare și ieșire
with open("veriflantIN.txt", "r") as input_file, open("veriflantOUT.txt", "w") as output_file:
n, m = map(int, input_file.readline().split())
muchii = [tuple(map(int, input_file.readline().split())) for _ in range(m)]

try:
k = int(input_file.readline())
except ValueError:
output_file.write("Datele nu corespund restrictiilor impuse\n")
exit()

vrf_siruri = [list(map(int, input_file.readline().split()[1:])) for _ in range(k)]

if verifica_restrictii(n, muchii, k, vrf_siruri):
graf = citire_graf(muchii)
for vrf_sir in vrf_siruri:
if este_lant(graf, vrf_sir):
if este_elementar(vrf_sir):
output_file.write("ELEMENTAR\n")
else:
output_file.write("NEELEMENTAR\n")
else:
output_file.write("NU\n")
else:
output_file.write("Datele nu corespund restrictiilor impuse\n")

</syntaxhighlight>

0598 - Gears

2023-12-27T20:53:27Z

Rus Marius: Pagină nouă: = Cerința = Considerăm un ansamblu format din <code>n</code> roți dințate, numerotate de la <code>1</code> la <code>n</code>, ca în imaginea alăturată. Fiecare roată se poate roti spre dreapta sau spre stânga. Dacă o roată se rotește spre dreapta, toate roțile pe care le angrenează se vor roti spre stânga, și invers. Una dintre roți este conectată la un motor și se va roti spre dreapta, iar toate roțile din ansamblu se vor roti în mod corespunzător. Ans...

= Cerința =
Considerăm un ansamblu format din <code>n</code> roți dințate, numerotate de la <code>1</code> la <code>n</code>, ca în imaginea alăturată. Fiecare roată se poate roti spre dreapta sau spre stânga. Dacă o roată se rotește spre dreapta, toate roțile pe care le angrenează se vor roti spre stânga, și invers.

Una dintre roți este conectată la un motor și se va roti spre dreapta, iar toate roțile din ansamblu se vor roti în mod corespunzător. Ansamblul este construit astfel încât toate roțile vor fi angrenate și fiecare roată va fi angrenată de o unică altă roată.

Dându-se numărul de roți <code>n</code>, numărul de ordine <code>x</code> al roții conectate la motor și perechile de roți conectate între ele, să se determine sensul de rotație al fiecărei roți.

= Date de intrare =
Fișierul de intrare <code>gearsIN.txt</code> conține pe prima linie numerele <code>n x</code>. Următoarele <code>n-1</code> linii vor conține perechi de numere <code>i j</code> reprezentând perechi de roți conectate.

= Date de ieșire =
Fișierul de ieșire <code>gearsOUT.txt</code> va conține pe prima linie un șir de <code>n</code> caractere: <code>S</code> sau <code>D</code>, după cum roata corespunzătoare se rotește spre stânga, respectiv dreapta. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

= Restricții și precizări =

* <code>1 ≤ n ≤ 100</code>

= Exemplul 1: =
<code>gearsIN.txt</code>
7 4
1 2
1 3
1 4
1 5
3 6
3 7
<code>gearsOUT.txt</code>
SDDDDSS

= Exemplul 2: =
<code>gearsIN.txt</code>
1001 23
1 2
1 3
1 4
1 5
3 6
3 7
<code>gearsOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verifica_restrictii(n):
if 1 <= n <= 100:
return True
else:
return False

def citeste_intrare(nume_fisier):
with open(nume_fisier, 'r') as fisier:
n, x = map(int, fisier.readline().split())
conexiuni = [tuple(map(int, linie.split())) for linie in fisier.readlines()]
return n, x, conexiuni

def scrie_iesire(nume_fisier, rezultat):
with open(nume_fisier, 'w') as fisier:
fisier.write(rezultat)

def directii_rotire(n, x, conexiuni):
graf = {i: {'directie': 'S'} for i in range(1, n+1)}
graf[x]['directie'] = 'D'

for conexiune in conexiuni:
i, j = conexiune
if graf[i]['directie'] == 'S':
graf[j]['directie'] = 'D'
else:
graf[j]['directie'] = 'S'

return ''.join(graf[i]['directie'] for i in range(1, n+1))

if __name__ == "__main__":
fisier_intrare = "gearsIN.txt"
fisier_iesire = "gearsOUT.txt"

n, x, conexiuni = citeste_intrare(fisier_intrare)

if verifica_restrictii(n):
rezultat = directii_rotire(n, x, conexiuni)
scrie_iesire(fisier_iesire, rezultat)
else:
scrie_iesire(fisier_iesire, "Datele nu corespund restrictiilor impuse")

</syntaxhighlight>