Bitnami MediaWiki - User contributions [en]

0591 - Firma

2024-05-18T20:24:46Z

Oros Ioana Diana: Pagină nouă: = Cerința = Într-o țară sunt <code>n</code> orașe, numerotate de la <code>1</code> la <code>n</code>, unite între ele prin <code>m</code> șosele bidirecționale de lungimi cunoscute, între oricare două orașe existând drum, fie șosea directă, fie prin alte orașe. O firmă dorește să-și stabilească sediul în unul dintre orașe, astfel încât suma lungimilor drumurilor minime de la orașul în care se află sediul la toate celelaltele orașe să fie minimă....

= Cerința =
Într-o țară sunt <code>n</code> orașe, numerotate de la <code>1</code> la <code>n</code>, unite între ele prin <code>m</code> șosele bidirecționale de lungimi cunoscute, între oricare două orașe existând drum, fie șosea directă, fie prin alte orașe. O firmă dorește să-și stabilească sediul în unul dintre orașe, astfel încât suma lungimilor drumurilor minime de la orașul în care se află sediul la toate celelaltele orașe să fie minimă. Determinați orașul care va fi ales pentru sediul firmei. Dacă sunt mai multe orașe care pot fi alese, se va alege cel cu numărul de ordine mai mic.

= Date de intrare =
Fișierul de intrare <code>firmaIN.txt</code> conține pe prima linie numerele <code>n m</code>, iar următoarele <code>m</code> linii câte trei numere <code>i j L</code>, cu semnificatia: între orașele <code>i</code> și <code>j</code> există o șosea directă de lungime <code>L</code>.

= Date de ieșire =
Fișierul de ieșire <code>firmaOUT.txt</code> va conține pe prima linie numărul <code>X</code>, reprezentând numărul de ordine al orașului care va ales ca sediu pentru firmă.

= Restricții și precizări =

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

= Exemplu: =
<code>firmaIN.txt</code>
6 9
1 3 5
1 4 5
1 5 4
2 3 5
2 4 1
2 5 2
3 6 2
4 6 4
5 6 4
<code>firmaOUT.txt</code>
2

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

def check_restrictions(n, m):
if not (1 <= n <= 100):
with open("firmaOUT.txt", "w") as fout:
fout.write("Datele nu corespund restrictiilor impuse")
return False
return True

def dijkstra(nod, n, G):
D = [float('inf')] * (n + 1)
D[nod] = 0
Q = [(0, nod)]
while Q:
x, y = heapq.heappop(Q)
if x > D[y]:
continue
for nodnou, costnou in G[y]:
if D[nodnou] > D[y] + costnou:
D[nodnou] = D[y] + costnou
heapq.heappush(Q, (D[nodnou], nodnou))
return D

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

if not check_restrictions(n, m):
return

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

minim = float('inf')
mini = -1
for i in range(1, n + 1):
s = 0
D = dijkstra(i, n, G)
for j in range(1, n + 1):
if D[j] != float('inf'):
s += D[j]

if s < minim:
minim = s
mini = i

with open("firmaOUT.txt", "w") as fout:
fout.write(str(mini))

if __name__ == "__main__":
main()

</syntaxhighlight>

0589 - Roy-Floyd

2024-05-18T20:15:58Z

Oros Ioana Diana: Pagină nouă: = Cerința = Se dă un graf orientat ponderat cu <code>n</code> noduri și <code>m</code> arce – în care fiecare arc are asociat un cost, număr natural strict pozitiv. Folosind algoritmul Roy-Floyd, construiți matricea costurilor minime, <code>a[i][j]</code> fiind costul minim al unui drum de la <code>i</code> la <code>j</code>, dacă există un asemenea drum, sau <code>-1</code> în caz contrar. = Date de intrare = Fișierul de intrare <code>roy-floydIN.txt</code> con...

= Cerința =
Se dă un graf orientat ponderat cu <code>n</code> noduri și <code>m</code> arce – în care fiecare arc are asociat un cost, număr natural strict pozitiv. Folosind algoritmul Roy-Floyd, construiți matricea costurilor minime, <code>a[i][j]</code> fiind costul minim al unui drum de la <code>i</code> la <code>j</code>, dacă există un asemenea drum, sau <code>-1</code> în caz contrar.

= Date de intrare =
Fișierul de intrare <code>roy-floydIN.txt</code> conține pe prima linie numerele <code>n m</code>, iar următoarele linii câte un triplet <code>i j c</code>, cu semnificația: există arcul <code>(i j)</code> și are costul <code>c</code>.

= Date de ieșire =
Fișierul de ieșire <code>roy-floydOUT.txt</code> va conține matricea construită, câte o linie a matricei pe o linie a fișierului, elementele de pe fiecare linie fiind separate prin exact un spațiu.

= Restricții și precizări =

* <code>1 ≤ n ≤ 100</code>
* costul unui arc va fi mai mic decât <code>1000</code>
* costul unui drum este egal cu suma costurilor arcelor care îl compun

= Exemplu: =
<code>roy-floydIN.txt</code>
5 6
1 3 1
2 1 2
4 2 1
4 3 8
5 3 5
5 4 2
<code>roy-floydOUT.txt</code>
0 -1 1 -1 -1
2 0 3 -1 -1
-1 -1 0 -1 -1
3 1 4 0 -1
5 3 5 2 0

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
INFINIT = 1000000000

def verifica_restrictii(n, m, costuri):
if not (1 <= n <= 100):
return False
if any(c >= 1000 for _, _, c in costuri):
return False
return True

def roy_floyd():
try:
with open("roy-floydIN.txt", "r") as fin:
linie = fin.readline().strip()
if not linie:
raise ValueError("Linia de intrare este goala.")
n, m = map(int, linie.split())
costuri = [tuple(map(int, fin.readline().split())) for _ in range(m)]
except ValueError as e:
with open("roy-floydOUT.txt", "w") as fout:
fout.write(f"Datele nu corespund restrictiilor impuse: {e}")
return

if not verifica_restrictii(n, m, costuri):
with open("roy-floydOUT.txt", "w") as fout:
fout.write("Datele nu corespund restrictiilor impuse")
return

a = [[INFINIT] * (n + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
a[i][i] = 0

for i, j, c in costuri:
a[i][j] = c

for k in range(1, n + 1):
for i in range(1, n + 1):
for j in range(1, n + 1):
if a[i][j] > a[i][k] + a[k][j]:
a[i][j] = a[i][k] + a[k][j]

with open("roy-floydOUT.txt", "w") as fout:
for i in range(1, n + 1):
for j in range(1, n + 1):
fout.write(f"{-1 if a[i][j] == INFINIT else a[i][j]} ")
fout.write("\n")

if __name__ == "__main__":
roy_floyd()

</syntaxhighlight>

0593 - Parc

2024-05-18T20:00:13Z

Oros Ioana Diana: Pagină nouă: = Cerința = Parcul orașului este alcătuit din <code>n</code> intersecții, numerotate de la <code>1</code> la <code>n</code>, unite între ele prin <code>m</code> alei bidirecționale, fiecare având o anumita lungime. Într-o intersecție precizată <code>C</code> se organizează un concert; de asemenea, unele intersecții, precizate și ele, reprezintă porți de intrare în parc, accesul fiind posibil doar prin aceste porți. Gigel poate ajunge cu mașina la oricare di...

= Cerința =
Parcul orașului este alcătuit din <code>n</code> intersecții, numerotate de la <code>1</code> la <code>n</code>, unite între ele prin <code>m</code> alei bidirecționale, fiecare având o anumita lungime. Într-o intersecție precizată <code>C</code> se organizează un concert; de asemenea, unele intersecții, precizate și ele, reprezintă porți de intrare în parc, accesul fiind posibil doar prin aceste porți.

Gigel poate ajunge cu mașina la oricare dintre aceste porți, dar vă roagă să alegeți pentru el acea poartă pentru care distanța până la intersecția <code>C</code> este minimă. Dacă există mai multe porți cu această proprietate se va determina poarta cu numărul de ordine mai mic.

= Date de intrare =
Fișierul de intrare <code>parcIN.txt</code> conține pe prima linie numerele <code>n m C</code>; următoarele <code>m</code> linii câte un triplet <code>i j L</code>, cu semnificația: există alee între intersecția <code>i</code> și intersecția <code>j</code> și are lungimea <code>L</code>. Următoarea linie conține numărul de porți <code>P</code>; ultima linie conține <code>P</code> numere diferite, reprezentând porțile.

= Date de ieșire =
Fișierul de ieșire <code>parcOUT.txt</code> va conține pe prima linie numărul de ordine al porții alese.

= Restricții și precizări =

* <code>1 ≤ n ≤ 100</code>
* lungimea unei alei va fi mai mică decât <code>1000</code>
* între oricare două intersecții există drum, direct sau prin intermediul altor intersecții În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Exemplul 1: =
<code>parcIN.txt</code>
7 8 2
1 2 4
1 5 1
1 7 2
2 3 9
2 4 2
2 6 2
2 7 1
5 6 7
2
3 5
<code>parcOUt.txt</code>
5

= Exemplul 2: =
<code>parcIN.txt</code>
0 8 2
1 2 4
1 5 1
1 7 2
2 3 9
2 4 2
2 6 2
2 7 1
5 6 7
2
3 5
<code>parcOUt.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
import heapq
import sys

MAX = 100

def citire_date():
with open('parcIN.txt', 'r') as fin:
n, m, C = map(int, fin.readline().strip().split())
muchii = [dict() for _ in range(MAX + 1)]
lungimi = [dict() for _ in range(MAX + 1)]
for _ in range(m):
i, j, L = map(int, fin.readline().strip().split())
muchii[i][j] = muchii[j][i] = True
lungimi[i][j] = lungimi[j][i] = L
P = int(fin.readline().strip())
p_list = list(map(int, fin.readline().strip().split()))
return n, m, C, muchii, lungimi, P, p_list

def validare_restrictii(n, m, lungimi):
if not (1 <= n <= 100):
return False
for nod in range(1, n+1):
for lungime in lungimi[nod].values():
if lungime >= 1000:
return False
return True

def dijkstra(n, muchii, lungimi, start):
lenMin = [float('inf')] * (n + 1)
lenMin[start] = 0
heap = [(0, start)]
while heap:
current_len, node = heapq.heappop(heap)
if current_len > lenMin[node]:
continue
for neighbor in muchii[node]:
length = current_len + lungimi[node][neighbor]
if length < lenMin[neighbor]:
lenMin[neighbor] = length
heapq.heappush(heap, (length, neighbor))
return lenMin

def main():
n, m, C, muchii, lungimi, P, p_list = citire_date()
if not validare_restrictii(n, m, lungimi):
with open('parcOUT.txt', 'w') as fout:
fout.write("Datele nu corespund restrictiilor impuse")
return

lenMinP = float('inf')
pMin = -1
for p in p_list:
lenMin = dijkstra(n, muchii, lungimi, p)
if lenMin[C] < lenMinP:
lenMinP = lenMin[C]
pMin = p

with open('parcOUT.txt', 'w') as fout:
fout.write(str(pMin))

if __name__ == "__main__":
main()

</syntaxhighlight>

0592 - Kruskal

2024-05-18T19:55:47Z

Oros Ioana Diana: Pagină nouă: = Cerința = Se dă un graf neorientat ponderat conex cu <code>n</code> vârfuri și <code>m</code> muchii – în care fiecare muchie are asociat un cost, număr natural strict pozitiv. Folosind algoritmul lui Kruskal, determinați un arbore parțial de cost minim. = Date de intrare = Fișierul de intrare <code>kruskalIN.txt</code> conține pe prima linie numerele <code>n m</code>, iar următoarele linii câte un triplet <code>i j c</code>, cu semnificația: există muchia...

= Cerința =
Se dă un graf neorientat ponderat conex cu <code>n</code> vârfuri și <code>m</code> muchii – în care fiecare muchie are asociat un cost, număr natural strict pozitiv. Folosind algoritmul lui Kruskal, determinați un arbore parțial de cost minim.

= Date de intrare =
Fișierul de intrare <code>kruskalIN.txt</code> conține pe prima linie numerele <code>n m</code>, iar următoarele linii câte un triplet <code>i j c</code>, cu semnificația: există muchia <code>(i j)</code> și are costul <code>c</code>.

= Date de ieșire =
Fișierul de ieșire <code>kruskalOUT.txt</code> va conține pe prima linie costul arborelui de cost minim determinat, iar pe următoarele <code>n-1</code> linii câte o pereche de numere <code>i j</code>, cu semnificația că muchia <code>(i j)</code> aparține arborelui parțial de cost minim 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</code>
* costul unei muchii va fi mai mic decât <code>1000</code>

= Exemplul 1: =
<code>kruskalIN.txt</code>
7 11
1 2 2
1 7 4
2 3 3
2 5 2
2 6 3
2 7 3
3 4 1
3 5 2
4 5 1
5 6 3
6 7 5
<code>kruskalOUT.txt</code>
12
3 4
4 5
1 2
2 5
2 6
2 7

== Exemplul 2: ==
<code>kruskalIN.txt</code>
101 11
1 2 2
1 7 4
2 3 3
2 5 2
2 6 3
2 7 3
3 4 1
3 5 2
4 5 1
5 6 3
6 7 5
<code>kruskalOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
import sys

class Position:
def __init__(self, i, j, c):
self.i = i
self.j = j
self.c = c

def union(parent, a, b):
parent[a] = parent[b]

def find(parent, a):
if a == parent[a]:
return a
else:
parent[a] = find(parent, parent[a])
return parent[a]

def kruskal(n, m, graph, fout):
parent = [i for i in range(n + 1)]
result = 0
cnt = 0
A = []

for edge in graph:
r1 = find(parent, edge.i)
r2 = find(parent, edge.j)
if r1 != r2:
result += edge.c
A.append(edge)
cnt += 1
union(parent, r1, r2)

fout.write(f"{result}\n")
for edge in A:
fout.write(f"{edge.i} {edge.j}\n")

def check_restrictions(n, m, graph):
if not (1 <= n <= 100):
return False
for edge in graph:
if not (edge.c < 1000):
return False
return True

def main():
fin = open("kruskalIN.txt", "r")
fout = open("kruskalOUT.txt", "w")

n, m = map(int, fin.readline().split())

graph = []
for _ in range(m):
x, y, w = map(int, fin.readline().split())
graph.append(Position(x, y, w))

graph.sort(key=lambda edge: edge.c)

if not check_restrictions(n, m, graph):
fout.write("Datele nu corespund restrictiilor impuse\n")
else:
kruskal(n, m, graph, fout)

fin.close()
fout.close()

if __name__ == "__main__":
main()

</syntaxhighlight>

0590 - Prim

2024-05-18T19:50:44Z

Oros Ioana Diana: Pagină nouă: = Cerința = Se dă un graf neorientat ponderat conex cu <code>n</code> vârfuri și <code>m</code> muchii – în care fiecare muchie are asociat un cost, număr natural strict pozitiv. Folosind algoritmul lui Prim, determinați un arbore parțial de cost minim, cu rădăcina în vârful <code>1</code>. = Date de intrare = Fișierul de intrare <code>primIN.txt</code> conține pe prima linie numerele <code>n m</code>, iar următoarele linii câte un triplet <code>i j c</code...

= Cerința =
Se dă un graf neorientat ponderat conex cu <code>n</code> vârfuri și <code>m</code> muchii – în care fiecare muchie are asociat un cost, număr natural strict pozitiv. Folosind algoritmul lui Prim, determinați un arbore parțial de cost minim, cu rădăcina în vârful <code>1</code>.

= Date de intrare =
Fișierul de intrare <code>primIN.txt</code> conține pe prima linie numerele <code>n m</code>, iar următoarele linii câte un triplet <code>i j c</code>, cu semnificația: există muchia <code>(i j)</code> și are costul <code>c</code>.

= Date de ieșire =
Fișierul de ieșire <code>primOUT.txt</code> va conține pe prima linie costul arborelui de cost minim determinat, iar pe a doua linie vectorul de tați al arborelui, cu elementele 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 ≤ 100</code>
* costul unei muchii va fi mai mic decât <code>1000</code>

= Exemplul 1: =
<code>primIN.txt</code>
7 11
1 2 2
1 7 4
2 3 3
2 5 2
2 6 3
2 7 3
3 4 1
3 5 2
4 5 1
5 6 3
6 7 5
<code>primOUT.txt</code>
12
0 1 4 5 2 2 2

= Exemplul 2: =
<code>primIN.txt</code>
0 11
1 2 2
1 7 4
2 3 3
2 5 2
2 6 3
2 7 3
3 4 1
3 5 2
4 5 1
5 6 3
6 7 5
<code>primOUT.txt</code>
Datele nu corespund restrictiilor impuse

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

def check_restrictions(n, edges):
if not (1 <= n <= 100):
return False
for x, y, c in edges:
if c >= 1000:
return False
return True

def main():
with open("primIN.txt", "r") as infile:
n, m = map(int, infile.readline().strip().split())
edges = []
for _ in range(m):
x, y, c = map(int, infile.readline().strip().split())
edges.append((x, y, c))

if not check_restrictions(n, edges):
with open("primOUT.txt", "w") as outfile:
outfile.write("Datele nu corespund restrictiilor impuse")
return

G = [[] for _ in range(n + 1)]
for x, y, c in edges:
G[x].append((c, y))
G[y].append((c, x))

V = [False] * (n + 1)
T = [-1] * (n + 1)
D = [float('inf')] * (n + 1)

Q = []
V[1] = True
T[1] = 0
D[1] = 0

for c, y in G[1]:
T[y] = 1
D[y] = c
heapq.heappush(Q, (c, y))

S = 0
for k in range(1, n):
while V[Q[0][1]]:
heapq.heappop(Q)
c, u = heapq.heappop(Q)
V[u] = True
S += c
for cost, v in G[u]:
if not V[v] and D[v] > cost:
T[v] = u
D[v] = cost
heapq.heappush(Q, (cost, v))

with open("primOUT.txt", "w") as outfile:
outfile.write(f"{S}\n")
outfile.write(" ".join(map(str, T[1:])))

if __name__ == "__main__":
main()

</syntaxhighlight>

1330 - ParitiiMultime

2024-05-18T19:44:29Z

Oros Ioana Diana: Pagină nouă: = Cerința = Fie <code>n</code> un număr natural nenul și mulțimea <code>A={1,2,3,...,n}</code>. Să se determine toate partițiile disjuncte ale mulțimii <code>A</code>. O partiție a mulțimii <code>A</code> este formată din <code>m</code> (<code>1 ≤ m ≤ n</code>) submulțimi disjuncte ale lui <code>A</code>: <code>A1</code>, <code>A2</code>, …, <code>Am</code> cu proprietatea că <code>A=A1U A2</code> <code>U...U Am</code>. = Date de intrare = Fișierul de int...

= Cerința =
Fie <code>n</code> un număr natural nenul și mulțimea <code>A={1,2,3,...,n}</code>. Să se determine toate partițiile disjuncte ale mulțimii <code>A</code>.

O partiție a mulțimii <code>A</code> este formată din <code>m</code> (<code>1 ≤ m ≤ n</code>) submulțimi disjuncte ale lui <code>A</code>: <code>A1</code>, <code>A2</code>, …, <code>Am</code> cu proprietatea că <code>A=A1U A2</code> <code>U...U Am</code>.

= Date de intrare =
Fișierul de intrare <code>partitiimultimeIN.txt</code> conține pe prima linie numărul <code>n</code>.

= Date de ieșire =
Fișierul de ieșire <code>partitiimultimeOUT.txt</code> va conține câte o linie pentru fiecare partiție determinată. Submulțimile vor fi separate în fiecare linie cu ajutorul caracterului <code>*</code>, iar elementele fiecărei submulțimi se vor scrie fără spațiere, ca în exemplul de mai jos.

= Restricții și precizări =

* <code>1 ≤ n ≤ 9</code>
* Partițiile determinate se vor afișa în ordine lexicografică

= Exemplul 1: =
<code>partitiimultimeIN.txt</code>
3
<code>partitiimultimeOUT.txt</code>
123*
12*3*
13*2*
1*23*
1*2*3*

=== Explicație ===
Sunt determinate <code>5</code> partiții distincte ale mulțimii <code>A</code>.

# <code>{1,2,3}</code>
# <code>{1,2} U {3}</code>
# <code>{1,3} U {2}</code>
# <code>{1} U {2,3}</code>
# <code>{1} U {2} U {3}</code>

== Exemplul 2: ==
<code>partitiimultimeIN.txt</code>
10
<code>partitiimultimeOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
def maxim(k, x):
z = 0
for i in range(1, k):
z = max(x[i], z)
return z

def scrie(x, n, g):
z = maxim(n + 1, x)
for i in range(1, z + 1):
for j in range(1, n + 1):
if x[j] == i:
g.write(str(j))
g.write("*")
g.write("\n")

def back(k, n, x, g):
if k == n + 1:
scrie(x, n, g)
else:
for i in range(1, maxim(k, x) + 2):
x[k] = i
back(k + 1, n, x, g)

def verifica_restrictii(n, g):
if not (1 <= n <= 9):
g.write("Datele nu corespund restrictiilor impuse\n")
return False
return True

def main():
with open("partitiimultimeIN.txt", "r") as f:
n = int(f.readline().strip())

with open("partitiimultimeOUT.txt", "w") as g:
if verifica_restrictii(n, g):
x = [0] * (n + 1)
x[1] = 1
back(2, n, x, g)

if __name__ == "__main__":
main()

</syntaxhighlight>

3153 - eliminaren

2024-05-18T19:34:49Z

Oros Ioana Diana: Pagină nouă: = Cerința = Se citesc de la tastatură un cuvânt <code>s</code> format din litere mici distincte și un număr natural <code>n</code>. Să se afișeze pe ecran toate cuvintele care se pot obține din <code>s</code> eliminând exact <code>n</code> litere. Eliminarea se face începând cu literele de la sfârșitul cuvântului, iar ordinea din cuvânt a literelor nu se schimbă (vezi explicația din exemplu). = Date de intrare = Programul citește de la tastatură cuvântul...

= Cerința =
Se citesc de la tastatură un cuvânt <code>s</code> format din litere mici distincte și un număr natural <code>n</code>. Să se afișeze pe ecran toate cuvintele care se pot obține din <code>s</code> eliminând exact <code>n</code> litere.

Eliminarea se face începând cu literele de la sfârșitul cuvântului, iar ordinea din cuvânt a literelor nu se schimbă (vezi explicația din exemplu).

= Date de intrare =
Programul citește de la tastatură cuvântul <code>s</code> și numărul <code>n</code>.

= Date de ieșire =
Programul va afișa pe ecran pe rânduri separate cuvintele care se pot obține din <code>s</code> eliminând exact <code>n</code> litere.

= Restricții și precizări =

* Cuvântul <code>s</code> are cel mult <code>20</code> de litere
* Cuvântul <code>s</code> este format din litere mici distincte
* <code>1 <= n <</code> numărul de litere ale lui <code>s</code>

= Exemplu: =
Intrare
dorel 2
Ieșire
dor
doe
dol
dre
drl
del
ore
orl
oel
rel

=== Explicație ===
Din cele <code>5</code> litere se elimina două, astfel:

<code>dor</code> – se elimina a <code>4</code>-a si a <code>5</code>-a litera

<code>doe</code> – se elimina a <code>3</code>-a si a <code>5</code>-a litera

<code>dol</code> – se elimina a <code>3</code>-a si a <code>4</code>-a litera

<code>dre</code>

<code>drl</code>

<code>del</code>

<code>ore</code>

<code>orl</code>

<code>oel</code> – se elimina prima si a <code>3</code>-a litera

<code>rel</code> – se elimina prima si a <code>2</code>-a litera

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
def afisare(s, x, n, c):
rezultat = ''.join(s[x[i] - 1] for i in range(1, n - c + 1))
print(rezultat)

def bectreching(k, s, x, n, c):
for i in range(x[k - 1] + 1, n + 1):
x[k] = i
if k < n - c:
bectreching(k + 1, s, x, n, c)
else:
afisare(s, x, n, c)

def verifica_restrictii(s, c):
if len(s) > 20 or not s.islower() or len(s) != len(set(s)) or not (1 <= c < len(s)):
return False
return True

def main():
intrare = input().strip().split()
s = intrare[0]
c = int(intrare[1])
if not verifica_restrictii(s, c):
print("Datele nu corespund restrictiilor impuse")
return

n = len(s)
x = [0] * (n + 1)
bectreching(1, s, x, n, c)

if __name__ == "__main__":
main()

</syntaxhighlight>

3347 - Fibonacci3

2024-05-18T19:29:20Z

Oros Ioana Diana: Pagină nouă: = Cerința = Se dă un şir format din <code>n</code> numere naturale. Se calculează suma elementelor oricărui subşir al şirului dat. Să se afle câte din sumele obţinute sunt termeni ai şirului lui Fibonacci. = Date de intrare = Fișierul de intrare <code>fibonacci3IN.txt</code> conține pe prima linie numărul <code>n</code>, iar pe următoarea linie <code>n</code> numere naturale. = Date de ieșire = Fișierul de ieșire <code>fibonacci3OUT.txt</code> va conține...

= Cerința =
Se dă un şir format din <code>n</code> numere naturale. Se calculează suma elementelor oricărui subşir al şirului dat. Să se afle câte din sumele obţinute sunt termeni ai şirului lui Fibonacci.

= Date de intrare =
Fișierul de intrare <code>fibonacci3IN.txt</code> conține pe prima linie numărul <code>n</code>, iar pe următoarea linie <code>n</code> numere naturale.

= Date de ieșire =
Fișierul de ieșire <code>fibonacci3OUT.txt</code> va conține numărul sumelor care sunt termeni ai şirului lui Fibonacci. Î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 ≤ 25</code>
* numerele date sunt cel mult egale cu <code>1017</code>

= Exemplul 1: =
<code>fibonacci3IN.txt</code>
2
3 18
<code>fibonacci3OUT.txt</code>
2

=== Explicație ===
Sumele obţinute sunt <code>3</code>, <code>18</code> şi <code>21</code>, dintre care <code>3</code> şi <code>21</code> sunt termeni ai [[Fibonacci number|şirului lui Fibonacci]].

== Exemplul 2: ==
<code>fibonacci3IN.txt</code>
1
3 18
<code>fibonacci3OUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
import sys

NMAX = 2500000000000000225

def gen_fibo():
fibonacci = [0, 1]
x, y = 1, 1
while x + y < NMAX:
z = x + y
fibonacci.append(z)
y = x
x = z
return fibonacci

def cauta(fibonacci, valoare):
st, dr = 0, len(fibonacci) - 1
while st <= dr:
mij = (st + dr) // 2
if fibonacci[mij] == valoare:
return True
if valoare < fibonacci[mij]:
dr = mij - 1
else:
st = mij + 1
return False

def bkt(k, s, n, v, fibonacci):
global nr
if cauta(fibonacci, s):
nr += 1
if k < n:
for i in range(k + 1, n + 1):
bkt(i, s + v[i - 1], n, v, fibonacci)

def verifica_restrictii(n, v):
if not (2 <= n <= 25):
return False
if any(x > 10**17 for x in v):
return False
return True

def main():
global nr
nr = 0

with open("fibonacci3IN.txt", "r") as fin:
n = int(fin.readline().strip())
v = list(map(int, fin.readline().strip().split()))

with open("fibonacci3OUT.txt", "w") as fout:
if not verifica_restrictii(n, v):
fout.write("Datele nu corespund restrictiilor impuse")
return

fibonacci = gen_fibo()
for i in range(1, n + 1):
bkt(i, v[i - 1], n, v, fibonacci)
fout.write(str(nr))

if __name__ == "__main__":
main()

</syntaxhighlight>

1278 - ProdusCartezian2

2024-05-18T19:25:33Z

Oros Ioana Diana: Pagină nouă: = Cerinţa = Se dau <code>n</code> mulțimi: * A1={1,2,...,v1} * A2={1,2,...,v2} * .. * An={1,2,...,vn} Să se genereze în ordine lexicografică elementele produsului cartezian . = Date de intrare = Fișierul de intrare <code>produscartezian2IN.txt</code> conține pe prima linie numărul <code>n</code>, iar pe a doua linie <code>n</code> numere naturale nenule <code>v[1] v[2] ... v[n]</code>. = Date de ieşire = Fișierul de ieșire <code>produscartezian2OUt.txt</code> v...

= Cerinţa =
Se dau <code>n</code> mulțimi:

* A1={1,2,...,v1}
* A2={1,2,...,v2}
* ..
* An={1,2,...,vn}

Să se genereze în ordine lexicografică elementele produsului cartezian .

= Date de intrare =
Fișierul de intrare <code>produscartezian2IN.txt</code> conține pe prima linie numărul <code>n</code>, iar pe a doua linie <code>n</code> numere naturale nenule <code>v[1] v[2] ... v[n]</code>.

= Date de ieşire =
Fișierul de ieșire <code>produscartezian2OUt.txt</code> va conține elementele produsului cartezian, fiecare pe o linie. Valorile de pe fiecare linie vor fi 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 ≤ 7</code>
* <code>1 ≤ v[i] ≤ 7</code>

= Exemplul 1: =
<code>produscartezian2IN.txt</code>
3
2 1 3
<code>produscartezian2OUT.txt</code>
1 1 1
1 1 2
1 1 3
2 1 1
2 1 2
2 1 3

= Exemplul 2: =
<code>produscartezian2IN.txt</code>
10
2 1 3
<code>produscartezian2OUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
def citire():
with open("produscartezian2IN.txt", "r") as fin:
n = int(fin.readline().strip())
v = list(map(int, fin.readline().strip().split()))
return n, v

def afisare(x, fout):
fout.write(" ".join(map(str, x)) + '\n')

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

def verifica_restrictii(n, v):
if 1 <= n <= 7 and all(1 <= vi <= 7 for vi in v):
return True
return False

def main():
n, v = citire()
with open("produscartezian2OUT.txt", "w") as fout:
if verifica_restrictii(n, v):
x = [0] * n
backtracking(1, n, v, x, fout)
else:
fout.write("Datele nu corespund restrictiilor impuse\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

1277 - ProdusCartezian1

2024-05-18T19:18:57Z

Oros Ioana Diana: Pagină nouă: = Cerinţa = Se dau două numere naturale nenule <code>n</code> și <code>m</code>. Considerăm mulțimea <code>A={1,2,..,n}</code>. Să se genereze în ordine lexicografică elementele produsului cartezian . = Date de intrare = Fișierul de intrare <code>produscartezian1IN.txt</code> conține pe prima linie numerele <code>n</code> și <code>m</code>, separate printr-un spațiu. = Date de ieşire = Fișierul de ieșire <code>produscartezian1OUT.txt</code> va conține elemen...

= Cerinţa =
Se dau două numere naturale nenule <code>n</code> și <code>m</code>. Considerăm mulțimea <code>A={1,2,..,n}</code>. Să se genereze în ordine lexicografică elementele produsului cartezian .

= Date de intrare =
Fișierul de intrare <code>produscartezian1IN.txt</code> conține pe prima linie numerele <code>n</code> și <code>m</code>, separate printr-un spațiu.

= Date de ieşire =
Fișierul de ieșire <code>produscartezian1OUT.txt</code> va conține elementele produsului cartezian, fiecare pe o linie. Valorile de pe fiecare linie vor fi 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 ≤ 7</code>
* <code>1 ≤ m ≤ 6</code>

= Exemplul 1: =
<code>produscartezian1IN.txt</code>
2 3
<code>produscartezian1OUT.txt</code>
1 1 1
1 1 2
1 2 1
1 2 2
2 1 1
2 1 2
2 2 1
2 2 2

= Exemplul 2: =
<code>produscartezian1IN.txt</code>
2 8
<code>produscartezian1OUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
def afisare(x, m, out_file):
with open(out_file, 'a') as f:
for i in range(1, m + 1):
f.write(f"{x[i]} ")
f.write("\n")

def bectreching(k, n, m, x, out_file):
for i in range(1, n + 1):
x[k] = i
if k < m:
bectreching(k + 1, n, m, x, out_file)
else:
afisare(x, m, out_file)

def verifica_restrictii(n, m):
if 1 <= n <= 7 and 1 <= m <= 6:
return True
else:
return False

def main():
with open("produscartezian1IN.txt", 'r') as infile:
n, m = map(int, infile.readline().strip().split())

if verifica_restrictii(n, m):
x = [0] * (m + 1)
out_file = "produscartezian1OUT.txt"
with open(out_file, 'w'): # Clear the output file
pass
bectreching(1, n, m, x, out_file)
else:
with open("produscartezian1OUT.txt", 'w') as outfile:
outfile.write("Datele nu corespund restrictiilor impuse\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

1354 - varf

2024-05-18T19:11:57Z

Oros Ioana Diana: Pagină nouă: = Enunț = Se consideră un şir <code>a</code> cu <code>n</code> numere naturale distincte: <code>a1, a2,..., an</code>. Eliminând <code>n-k</code> numere din șirul a vom obține un subșir de lungime <code>k</code> al șirului <code>a</code>. Definim subșir <code>vârf</code> de lungime <code>k</code> al șirului <code>a</code> un subșir <code>x</code> cu proprietatea că acesta conține un număr <code>xi</code> (<code>1<i<k</code>) astfel încât: <code>x1</code> <...

= Enunț =
Se consideră un şir <code>a</code> cu <code>n</code> numere naturale distincte: <code>a1, a2,..., an</code>.

Eliminând <code>n-k</code> numere din șirul a vom obține un subșir de lungime <code>k</code> al șirului <code>a</code>.

Definim subșir <code>vârf</code> de lungime <code>k</code> al șirului <code>a</code> un subșir <code>x</code> cu proprietatea că acesta conține un număr <code>xi</code> (<code>1<i<k</code>) astfel încât:

<code>x1</code> <code>< x2</code> <code>< … < xi-1</code> <code>< xi</code> <code>> xi+1</code> <code>> … > xk</code>.

= Cerința =
Să se genereze toate subşirurile <code>vârf</code> ale şirului <code>a</code>, de lungime minim <code>3</code>.

= Date de intrare =
Fișierul de intrare <code>varfIN.txt</code> conține pe prima linie numărul <code>n</code>, iar pe a doua linie <code>n</code> numere naturale distincte separate prin câte un spațiu, reprezentând numerele din șirul <code>a</code>.

= Date de ieșire =
Fișierul de ieșire <code>varfOUT.txt</code> va conține pe fiecare linie câte un subșir <code>vârf</code>, în ordinea lexicografică a pozițiilor ocupate în șirul <code>a</code> de termenii subșirului. Numerele din fiecare linie vor fi 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>4 ≤ n ≤ 11</code>
* numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât <code>20</code>
* subșirurile <code>vârf</code> vor fi scrise în fișier în ordinea lexicografică a pozițiilor ocupate în șirul <code>a</code> de termenii fiecărui subșir.
* dacă nu există niciun subșir <code>vârf</code> atunci fișierul de ieșire <code>varf.out</code> va conține pe prima linie valoarea <code>0</code>.

= Exemplul 1: =
<code>varfIN.txt</code>
4
2 1 4 3
<code>varfOUT.txt</code>
2 4 3
1 4 3

=== Explicație ===
Se pot construi doar două subșiruri <code>vârf</code>: <code>(2,4,3)</code> și <code>(1,4,3)</code>.

== Exemplul 2: ==
<code>varfIN.txt</code>
3
2 1 4 3
<code>varfOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
def afisare(k, fout, x, b):
for i in range(1, k + 1):
fout.write(str(x[b[i]]) + " ")
fout.write('\n')

def solutie(k, x, b):
if k >= 3:
st, dr = 1, k
while x[b[st]] < x[b[st + 1]]:
st += 1
while x[b[dr]] < x[b[dr - 1]]:
dr -= 1
if st != dr:
return False
if st == 1 or dr == k or st == k or dr == 1:
return False
else:
return False
return True

def bkt(k, n, x, b, fout, ok):
for i in range(b[k - 1] + 1, n + 1):
b[k] = i
if k >= 3 and solutie(k, x, b):
afisare(k, fout, x, b)
ok[0] = 1
bkt(k + 1, n, x, b, fout, ok)

def main():
with open("varfIN.txt", "r") as fin:
n = int(fin.readline().strip())
x = [0] + list(map(int, fin.readline().strip().split()))

if not (4 <= n <= 11) or any(num >= 20 for num in x[1:]):
with open("varfOUT.txt", "w") as fout:
fout.write("Datele nu corespund restrictiilor impuse")
return

b = [0] * 30
ok = [0]
with open("varfOUT.txt", "w") as fout:
bkt(1, n, x, b, fout, ok)
if ok[0] == 0:
fout.write("0")

if __name__ == "__main__":
main()

</syntaxhighlight>

2676 - Afise

2024-05-18T17:19:08Z

Oros Ioana Diana:

Campania electorală s-a terminat de mult, dar zidul din parcul central al oraşului în care au fost puse afişele este încă într-o formă dezolantă. Ploile şi vântul au acţionat şi au urâţit şi mai mult această zonă pe care altă dată erau afişe frumos colorate. Primăria a decis să se ocupe de această problemă. A format o comisie şi a decis realizarea unor panouri reclamă care să ascundă porţiunile deteriorate. Deoarece fondurile sunt mici s-a decis să fie alocate doar un anumit număr de panouri publicitare care trebuie să ocupe o suprafaţă cât mai mică posibil. Comisia a primit datele din teren sub forma: lungime zid, câte unităţi sunt ocupate cu afişe ce trebuie acoperite şi care este numărul de panouri pe care le poate folosi. De asemenea se primesc ca date şi care sunt unităţile de zid ocupate cu afişe deja deteriorate.

= Cerința =
Fiind date lungimea zidului, câte unităţi sunt deteriorate, care este numărul maxim de panouri ce pot fi folosite şi care sunt unităţile de zid deteriorate, se cere să se determine lungimea minimă totală a panourilor care sunt folosite pentru a acoperi zona şi câte panouri se folosesc. Lungimea minimă o definim ca numărul total de unităţi de zid acoperite astfel încât să fie mascate zonele problemă. Pentru acoperirea unităţilor de zid deteriorate, nu este neapărat necesar să se folosească toate panourile. Numărul de panouri folosite fiind limitat există posibilitatea să fie acoperite şi zone din zid care sunt curate.

= Date de intrare =
Fișierul de intrare <code>afiseIN.txt</code> conţine pe prima linie trei valori separate prin câte un spaţiu <code>L n k</code>, cu semnificația: <code>L</code> lungimea totală a zidului, <code>n</code> numărul de unităţi ce urmează a fi acoperite şi <code>k</code> numărul maxim de panouri ce pot fi folosite. Pe a doua linie separate prin câte un spațiu sunt <code>n</code> valori <code>x1</code>, <code>x2</code>, … , <code>xn</code>, unde <code>xi</code> reprezintă unitatea din zid care este acoperită de un afiș vechi. Valorile <code>x1</code>, <code>x2</code>, … , <code>xn</code> apar într-o ordine aleatoare.

= Date de ieșire =
Fișierul de ieșire <code>afiseOUT.txt</code> va conține o singură linie cu două valori <code>val Nk</code>, ce reprezintă lungimea minimă totală folosită și numărul de panouri folosite astfel încât toate zonele deteriorate să fie acoperite. Î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 < L ≤ 1000</code>
* <code>0 < n ≤ L</code>
* <code>0 < k ≤ L / 2</code>

= Exemplul 1: =
<code>afiseIN.txt</code>
25 8 3
3 11 6 4 19 15 20 12
<code>afiseOUT.txt</code>
11 3

=== Explicație ===
Zidul are lungimea egală cu <code>25</code> de unități, iar <code>8</code> dintre ele conțin afișe care trebuiesc acoperite cu maximum <code>3</code> panouri. Se vor folosi toate cele <code>3</code> panouri care vor totaliza <code>11</code> unități, acoperind zonele <code>3-6</code>, <code>11-15</code> și <code>19-20</code>.

Caracterul <code>*</code> reprezintă unitățile de zid acoperite de afișe vechi

= Exemplul 2: =
<code>afiseIN.txt</code>
10 4 5
7 3 8 1
<code>afiseOUT.txt</code>
4 3

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
def verifica_restrictii(l, n, k):
if not (0 < l <= 1000):
return False
if not (0 < n <= l):
return False
if not (0 < k <= l / 2):
return False
return True

def main():
with open("afiseIN.txt", "r") as infile:
l, n, k = map(int, infile.readline().split())
x_values = list(map(int, infile.readline().split()))

if not verifica_restrictii(l, n, k):
with open("afiseOUT.txt", "w") as outfile:
outfile.write("Datele nu corespund restrictiilor impuse")
return

v = [0] * (l + 1)
for x in x_values:
v[x] = 1

val = 0
n1 = 0
n2 = 0
v1 = [0] * 1010
v2 = [0] * 1010

i = 1
while i <= l:
if not v[i] and not n1:
i += 1
else:
if not v[i]:
n2 += 1
while i <= l and not v[i]:
v2[n2] += 1
i += 1
else:
n1 += 1
while i <= l and v[i] == 1:
v1[n1] += 1
i += 1
val += 1

if not v[l]:
n2 -= 1

v2 = sorted(v2[1:n2 + 1])

if n1 > k:
nk = k
for i in range(n1 - k):
val += v2[i]
else:
nk = n1

with open("afiseOUT.txt", "w") as outfile:
outfile.write(f"{val} {nk}")

if __name__ == "__main__":
main()

</syntaxhighlight>

1225 - Sort 2 Dist

2024-05-18T17:10:17Z

Oros Ioana Diana:

Jocul pe care îl joaca Robo atunci când se plictisește este un joc inteligent pentru roboței. Pe ecranul tabletei lui roboțești, sunt <code>N</code> căsuțe de formă pătrată, cu latura egală cu <code>1</code>. Căsuțele sunt așezate pe un rând, una lângă alta, fiind etichetate, în această ordine, cu numere de la <code>1</code> la <code>N</code>. Fiecare căsuță conține câte un număr natural, identificatorul câte unuia dintre prietenii săi, roboței, ca și el. Identificatorii se pot repeta.

Robo poate interschimba conținutul a două căsuțe, numai dacă distanța dintre centrele acestora pe orizontală este egală cu distanța dintre brațele sale; distanța, pe orizontală, dintre centrele a două căsuțe etichetate cu <code>i</code>, respectiv cu <code>j</code>, este <code>j-i</code> (<code>1≤i<j≤N</code>).

El își poate fixa în orice moment distanța dintre brațe la <code>1</code> sau își poate dubla distanța curentă dintre brațe, de oricâte ori este necesar, fără a depăși valoarea <code>N-1</code>. Astfel, distanța dintre brațele sale poate fi <code>1</code>, apoi, prin dublare, <code>2</code>, apoi, prin dublare <code>4</code>, apoi, prin dublare <code>8</code> etc. La începutul jocului, distanța dintre brațele lui Robo este <code>1</code>. De fiecare dată când consideră convenabilă distanța dintre brațe, realizează o interschimbare.

= Cerința =
Se cere ca Robo să așeze identificatorii în căsuțe în ordine crescătoare, prin maximum <code>12500</code> interschimbări de tipul celei precizate mai sus.

= Date de intrare =
Fișierul de intrare <code>sort2distIN.txt</code> conține:

* pe prima linie numărul natural <code>N</code>, cu semnificația din enunț;
* pe următoarele <code>N</code> linii, <code>N</code> numere, reprezentând, în această ordine, identificatorii aflați în căsuțele tabletei (identificatorul de pe linia <code>i</code> se află în căsuța <code>i-1</code>).

= Date de ieșire =
Fișierul de ieșire <code>sort2distOUT.txt</code> va conține:

* pe prima linie un număr natural <code>M</code>, reprezentând numărul de interschimbări realizate de Robo (nu neapărat numărul minim de interschimbări necesare);
* pe fiecare dintre următoarele <code>M</code> linii (doar dacă <code>M</code> este nenul), câte două numere naturale, separate prin câte un spațiu, reprezentând etichetele căsuțelor al căror conținut s-a interschimbat, în ordinea realizării acestor interschimbări. Î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 ≤ 1000</code>;
* identificatorii sunt numere naturale de maximum <code>30</code> de cifre;
* pentru 25% din punctaj, fișierele de test conțin numere cu maximum <code>18</code> cifre;
* pentru 25% din punctaj, <code>N ≤ 100</code>.

= Exemplul 1 : =
<code>sort2distIN.txt</code>
4
5
7
6
2
<code>sort2distOUT.txt</code>
2
2 4
2 1

=== Explicație ===
Tableta are <code>4</code> căsuțe, conținând, în această ordine, identificatorii <code>(5,7,6,2)</code>.

Pentru ordonarea crescătoare s-au realizat <code>2</code> interschimbări:

* s-a interschimbat conținutul căsuțelor <code>2</code> și <code>4</code> (distanța dintre centrele lor fiind <code>2</code>), identificatorii din căsuțe fiind acum <code>(5, 2, 6, 7)</code>;
* s-a interschimbat conținutul căsuțelor <code>1</code> și <code>2</code> (distanța dintre centrele lor fiind <code>1</code>), identificatorii din căsuțe fiind acum <code>(2, 5, 6, 7)</code>, ordonați crescător.

== Exemplul 2 : ==
<code>sort2distIN.txt</code>
1001
5
7
6
2
<code>sort2distOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
import os

DIM = 1010

sol = []
v = [0] * DIM
s = [""] * DIM
aux = ""
w = [""] * DIM

def myStrcmp(s1, s2):
if len(s1) == len(s2):
return (s1 > s2) - (s1 < s2)
else:
return -1 if len(s1) < len(s2) else 1

def schimba(x, y):
sol.append((x, y))
aux = v[x]
v[x] = v[y]
v[y] = aux

def verify_restrictions(n, strings):
if not (1 <= n <= 1000):
return False
for string in strings:
if not (1 <= len(string) <= 30):
return False
return True

def main():
with open("sort2distIN.txt", "r") as fin:
n = int(fin.readline().strip())
for i in range(1, n + 1):
s[i] = fin.readline().strip()
w[i] = s[i]

if not verify_restrictions(n, s[1:n+1]):
with open("sort2distOUT.txt", "w") as fout:
fout.write("Datele nu corespund restrictiilor impuse")
return

for i in range(1, n):
for j in range(i + 1, n + 1):
if myStrcmp(w[i], w[j]) > 0:
w[i], w[j] = w[j], w[i]

k = 1
for i in range(2, n + 1):
if myStrcmp(w[i], w[k]) != 0:
k += 1
w[k] = w[i]

for i in range(1, n + 1):
st = 1
dr = k
while st <= dr:
mid = (st + dr) // 2
if myStrcmp(s[i], w[mid]) == 0:
v[i] = mid
break
if myStrcmp(s[i], w[mid]) < 0:
dr = mid - 1
else:
st = mid + 1

for i in range(n, 1, -1):
m = v[1]
p = 1
for j in range(2, i + 1):
if v[j] > m:
m = v[j]
p = j
if p != i:
d = i - p

putere = 1
last = p
while d != 0:
if d % 2 == 1:
schimba(last + putere, last)
last += putere
d = d // 2
putere *= 2

with open("sort2distOUT.txt", "w") as fout:
fout.write(f"{len(sol)}\n")
for x, y in sol:
fout.write(f"{x} {y}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

3344 - Fibonacci2

2024-05-18T17:05:06Z

Oros Ioana Diana:

== Cerința ==
Șirul lui Fibonacci este definit astfel:

Fn={1Fn−1+Fn−2dacă n=1 sau n=2,dacă n>2.
Se dă un număr natural n. Determinați al n-lea termen al șirului, modulo 666013.

= 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 <code>F</code>, reprezentând al <code>n</code>-lea termen al șirului, modulo <code>666013</code>.

= Restricții și precizări =

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

= Exemplu: =
Intrare
6
Ieșire
8

=== Explicație ===
Termenii sunt: <code>1 1 2 3 5 8 13 21 34 55 89 ...</code>
:

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

class Mat:
def __init__(self, mat):
self.mat = mat

nullMat = Mat([[1, 0], [0, 1]])
initMat = Mat([[1, 1], [1, 0]])

def prod(a, b):
ret = Mat([[0, 0], [0, 0]])
ret.mat[0][0] = (a.mat[0][0] * b.mat[0][0] + a.mat[0][1] * b.mat[1][0]) % MOD
ret.mat[0][1] = (a.mat[0][0] * b.mat[0][1] + a.mat[0][1] * b.mat[1][1]) % MOD
ret.mat[1][0] = (a.mat[1][0] * b.mat[0][0] + a.mat[1][1] * b.mat[1][0]) % MOD
ret.mat[1][1] = (a.mat[1][0] * b.mat[0][1] + a.mat[1][1] * b.mat[1][1]) % MOD
return ret

def pwr(mat, n):
if n == 0:
return nullMat
if n % 2 == 1:
return prod(mat, pwr(prod(mat, mat), n // 2))
return pwr(prod(mat, mat), n // 2)

def verifica_restrictii(n):
if 1 <= n <= 2000000000:
return True
else:
print("Datele nu corespund restrictiilor impuse")
return False

def main():
n = int(input())
if verifica_restrictii(n):
result = pwr(initMat, n)
print(result.mat[0][1])

if __name__ == "__main__":
main()

</syntaxhighlight>

3785 - AI

2024-05-18T17:02:09Z

Oros Ioana Diana:

Al Bundy a plecat la serviciu, lăsându-i soţiei lui, Peg, cardul de cumpărături. PIN-ul este valoarea expresiei E(n)=∑nk=1(2⋅(a2+b2)k2⋅cos(k⋅α)),
unde α=arctg(ab) , iar n, a, b sunt numere naturale nenule.

= Cerința =
Să se afle valoarea expresiei , modulo <code>1.000.000.007</code>.

= Date de intrare =
Fișierul de intrare <code>alIN.txt</code> conține pe prima linie numerele <code>n, a, b</code>, separate prin spațiu.

= Date de ieșire =
Fișierul de ieșire <code>alOUT.txt</code> va conține pe prima linie valoarea expresiei , modulo <code>1.000.000.007</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 ≤ 1012</code>
* <code>1 ≤ a , b ≤ 20</code>

= Exemplul 1: =
<code>alIN.txt</code>
3 5 12
<code>alOUT.txt</code>
1918

== Explicatie ==
Dacă α=arctg(5/12), atunci sin(α)=5/13 şi cos(α)=12/13.
Avem E(3)=2⋅13⋅cos(α)+2⋅13*2⋅cos(2α)+2⋅13*3⋅cos(3α)=2⋅13⋅12/13+2⋅13*2⋅(2⋅cos2(α)−1)+2⋅13*3⋅(4⋅cos*3(α)−3⋅cos(α))=24+238+1656=1918.

== Exemplul 2: ==
<code>alIN.txt</code>
3 21 12
<code>alOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
MOD = 1000000007

def gcd(a, b):
if b == 0:
return (1, 0)
else:
x, y = gcd(b, a % b)
return (y, x - y * (a // b))

def prod(x, y):
ret = [[0, 0], [0, 0]]
ret[0][0] = (x[0][0] * y[0][0] + x[0][1] * y[1][0]) % MOD
ret[0][1] = (x[0][0] * y[0][1] + x[0][1] * y[1][1]) % MOD
ret[1][0] = (x[1][0] * y[0][0] + x[1][1] * y[1][0]) % MOD
ret[1][1] = (x[1][0] * y[0][1] + x[1][1] * y[1][1]) % MOD
return ret

def pwr(mat, n):
nullMat = [[1, 0], [0, 1]]
if n == 0:
return nullMat
if n % 2:
return prod(mat, pwr(prod(mat, mat), n // 2))
return pwr(prod(mat, mat), n // 2)

def verify_restrictions(n, a, b):
if 1 <= n <= 1012 and 1 <= a <= 20 and 1 <= b <= 20:
return True
return False

def main():
try:
with open("alIN.txt", "r") as fin:
line = fin.readline().strip()
if not line:
raise ValueError("File is empty or invalid format.")
n, a, b = map(int, line.split())

if not verify_restrictions(n, a, b):
with open("alOUT.txt", "w") as fout:
fout.write("Datele nu corespund restrictiilor impuse")
return

if n == 1:
E = ((a * a + b * b) * (2 * b - 2) - 2 * (b * b - a * a) + 2 * b) // (a * a + b * b - 2 * b + 1)
with open("alOUT.txt", "w") as fout:
fout.write(str(E))
return

numi = (b - 1) ** 2 + a * a
pat = a * a + b * b
invm, ins = gcd(numi, MOD)

initMat = [[2 * b, -pat], [1, 0]]
Alt = [[2 * (b * b - a * a), 0], [2 * b, 0]]
C = pwr(initMat, n - 1)
sol = prod(C, Alt)
En = -2 * pat + 2 * b
E = (pat * sol[1][0] - sol[0][0] + En) % MOD
E = (E * invm) % MOD
if E < 0:
E = (MOD + E) % MOD

with open("alOUT.txt", "w") as fout:
fout.write(str(E))

except Exception as e:
with open("alOUT.txt", "w") as fout:
fout.write(str(e))

if __name__ == "__main__":
main()

</syntaxhighlight>

3785 - AI

2024-05-18T17:01:57Z

Oros Ioana Diana:

Al Bundy a plecat la serviciu, lăsându-i soţiei lui, Peg, cardul de cumpărături. PIN-ul este valoarea expresiei E(n)=∑nk=1(2⋅(a2+b2)k2⋅cos(k⋅α)),
unde α=arctg(ab) , iar n, a, b sunt numere naturale nenule.

= Cerința =
Să se afle valoarea expresiei , modulo <code>1.000.000.007</code>.

= Date de intrare =
Fișierul de intrare <code>alIN.txt</code> conține pe prima linie numerele <code>n, a, b</code>, separate prin spațiu.

= Date de ieșire =
Fișierul de ieșire <code>alOUT.txt</code> va conține pe prima linie valoarea expresiei , modulo <code>1.000.000.007</code>.

= Restricții și precizări =

* <code>1 ≤ n ≤ 1012</code>
* <code>1 ≤ a , b ≤ 20</code>

= Exemplul 1: =
<code>alIN.txt</code>
3 5 12
<code>alOUT.txt</code>
1918

== Explicatie ==
Dacă α=arctg(5/12), atunci sin(α)=5/13 şi cos(α)=12/13.
Avem E(3)=2⋅13⋅cos(α)+2⋅13*2⋅cos(2α)+2⋅13*3⋅cos(3α)=2⋅13⋅12/13+2⋅13*2⋅(2⋅cos2(α)−1)+2⋅13*3⋅(4⋅cos*3(α)−3⋅cos(α))=24+238+1656=1918.

== Exemplul 2: ==
<code>alIN.txt</code>
3 21 12
<code>alOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
MOD = 1000000007

def gcd(a, b):
if b == 0:
return (1, 0)
else:
x, y = gcd(b, a % b)
return (y, x - y * (a // b))

def prod(x, y):
ret = [[0, 0], [0, 0]]
ret[0][0] = (x[0][0] * y[0][0] + x[0][1] * y[1][0]) % MOD
ret[0][1] = (x[0][0] * y[0][1] + x[0][1] * y[1][1]) % MOD
ret[1][0] = (x[1][0] * y[0][0] + x[1][1] * y[1][0]) % MOD
ret[1][1] = (x[1][0] * y[0][1] + x[1][1] * y[1][1]) % MOD
return ret

def pwr(mat, n):
nullMat = [[1, 0], [0, 1]]
if n == 0:
return nullMat
if n % 2:
return prod(mat, pwr(prod(mat, mat), n // 2))
return pwr(prod(mat, mat), n // 2)

def verify_restrictions(n, a, b):
if 1 <= n <= 1012 and 1 <= a <= 20 and 1 <= b <= 20:
return True
return False

def main():
try:
with open("alIN.txt", "r") as fin:
line = fin.readline().strip()
if not line:
raise ValueError("File is empty or invalid format.")
n, a, b = map(int, line.split())

if not verify_restrictions(n, a, b):
with open("alOUT.txt", "w") as fout:
fout.write("Datele nu corespund restrictiilor impuse")
return

if n == 1:
E = ((a * a + b * b) * (2 * b - 2) - 2 * (b * b - a * a) + 2 * b) // (a * a + b * b - 2 * b + 1)
with open("alOUT.txt", "w") as fout:
fout.write(str(E))
return

numi = (b - 1) ** 2 + a * a
pat = a * a + b * b
invm, ins = gcd(numi, MOD)

initMat = [[2 * b, -pat], [1, 0]]
Alt = [[2 * (b * b - a * a), 0], [2 * b, 0]]
C = pwr(initMat, n - 1)
sol = prod(C, Alt)
En = -2 * pat + 2 * b
E = (pat * sol[1][0] - sol[0][0] + En) % MOD
E = (E * invm) % MOD
if E < 0:
E = (MOD + E) % MOD

with open("alOUT.txt", "w") as fout:
fout.write(str(E))

except Exception as e:
with open("alOUT.txt", "w") as fout:
fout.write(str(e))

if __name__ == "__main__":
main()

</syntaxhighlight>

3123 - summy

2024-05-18T16:52:32Z

Oros Ioana Diana:

== Cerința ==
Se dau n şi k numere naturale. Calculați suma ∑ni=1ik.
== Date de intrare ==
Se dau n şi k numere naturale. Calculați suma ∑ni=1ik.
== Date de ieșire ==
Programul va afișa pe ecran valoarea sumei ∑ni=1ik, modulo 1.000.000.007.
== Restricții și precizări ==
*1 ≤ n ≤ 100.000 şi 1 ≤ k ≤ 1.000.000.000 pentru 70% din teste
*1 ≤ n ≤ 1.000.000.000 şi 1 ≤ k ≤ 100.000 pentru 30% din teste

= Exemplul 1: =
Intrare
5 3
Ieșire
225

= Exemplul 2: =
Intrare
5 3
Ieșire
7 8
7907396

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
MOD = 1000000007

def gcd(a, b):
if b == 0:
return (1, 0)
else:
x, y = gcd(b, a % b)
return (y, x - y * (a // b))

def invers(x):
inv, _ = gcd(x, MOD)
if inv <= 0:
inv = MOD + inv % MOD
return inv

def pu(b, e):
if e == 0:
return 1
elif e % 2 == 0:
x = pu(b, e // 2)
return (x * x) % MOD
else:
return (b * pu(b, e - 1)) % MOD

def calculate_for_small_n(n, k):
sol = 0
for i in range(1, n + 1):
sol = (sol + pu(i, k)) % MOD
return sol

def verifica_restrictii(n, k):
return 1 <= n <= 100000 and 1 <= k <= 1000000000

def main():
n, k = map(int, input().split())
if verifica_restrictii(n, k):
if n <= 100000:
print(calculate_for_small_n(n, k))
else:
suma = 1
numarator = 1
numitor = 1
for i in range(2, k + 3):
numarator = (numarator * (n - i)) % MOD
numitor = (numitor * (1 - i)) % MOD
if numitor < 0:
numitor += MOD
sol = (numarator * invers(numitor)) % MOD
for i in range(2, k + 3):
suma = (suma + pu(i, k)) % MOD
numarator = (numarator * (n - i + 1)) % MOD
numarator = (numarator * invers(n - i)) % MOD
numitor = (numitor * (i - 1)) % MOD
numitor = (-numitor * invers(k + 3 - i)) % MOD
if numitor < 0:
numitor += MOD
y = (numarator * invers(numitor)) % MOD
sol = (sol + suma * y) % MOD
print(sol)
else:
print("Datele nu corespund restrictiilor impuse")

if __name__ == "__main__":
main()

</syntaxhighlight>

== Explicatie ==
∑5i=1i*3=1**3+2**3+3**3+4**3+5**3=225

1683 - xor1

2024-05-18T16:48:35Z

Oros Ioana Diana:

Se consideră o matrice cu un număr infinit de linii și coloane indexate începând cu <code>0</code>.

Pe prima linie matricea conține șirul numerelor naturale (<code>0, 1, 2, 3 …</code>).

Pe fiecare linie începând cu linia a doua pe poziția <code>j</code> matricea conține suma xor a elementelor situate pe linia anterioara de la poziția <code>0</code> până la poziția <code>j</code>.

= Cerința =
Se cere să se răspundă la <code>q</code> întrebări de forma “Pentru <code>i</code> și <code>j</code> date, să se determine numărul situat pe linia <code>i</code> coloana <code>j</code> a matricei”. Pentru a genera cele <code>q</code> întrebări vor fi cunoscute următoarele valori: .

reprezintă valorile pentru prima întrebare. Următoarele întrebări vor fi generate una din alta folosind următoarea regulă:

= Date de intrare =
Fișierul de intrare <code>xor1IN.txt</code> conține pe prima linie numerele naturale separate prin câte un spaţiu.

= Date de ieșire =
Fișierul de ieșire <code>xor1OUT.txt</code> va conține <code>q</code> linii. Pe linia <code>k</code> se va afișa elementul situat pe linia coloana a 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 =

* Pentru 10% dintre teste <code>1 ≤ q ≤ 100</code>, <code>1 ≤ m ≤ 100</code>
* Pentru alte 10% dintre teste <code>1 ≤ q ≤ 100000</code>, <code>1 ≤ m ≤ 1000</code>
* Pentru alte 30% dintre teste <code>1 ≤ q ≤ 50</code>, <code>1 ≤ m ≤ 30000</code>
* Pentru alte 50% dintre teste <code>1 ≤ q ≤ 100000</code>, <code>1 ≤ m ≤ 108</code>
*
* <code>1 ≤ a,b ≤ 9</code>

= Exemplul 1: =
<code>xor1IN.txt</code>
4 2 3 1 1 5
<code>xor1OUT.txt</code>
2
7
0
1

=== Explicație ===
Avem <code>q=4</code> întrebări.

Pentru <code>i1=2</code>, <code>j1=3</code>, <code>a=1</code>, <code>b=1</code>, <code>m=5</code> se obțin întrebările: <code>(2,3)</code>, <code>(3,4)</code>, <code>(4,0)</code>, <code>(0,1)</code>

Matricea este:

0 1 2 3 4 5 6 …

0 1 3 0 4 1 7 …

0 1 2 2 6 7 0 …

0 1 3 1 7 0 0 …

0 1 2 3 4 4 4 …

…

Se observă că pe pozițiile corespunzătoare întrebărilor avem valorile <code>2</code>, <code>7</code>, <code>0</code> și <code>1</code>.

== Exemplul 2: ==
<code>xor1IN.txt</code>
4 2 3 1 11 5
<code>xor1OUT.txt</code>
'''Datele nu corespund restrictiilor impuse'''

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
def check_restrictions(q, a, b, m):
if not (1 <= a <= 9 and 1 <= b <= 9 and 1 <= q <= 100000 and 1 <= m <= 10**8):
with open("xor1OUT.txt", "w") as g:
g.write("Datele nu corespund restrictiilor impuse")
return False
return True

def main():
with open("xor1IN.txt", "r") as f:
q, i, j, a, b, m = map(int, f.readline().strip().split())

if not check_restrictions(q, a, b, m):
return

results = []
for _ in range(q):
s = 0
P = 1
p = 0
while P <= j:
if ((i + P) & (j - P)) == 0:
s |= (1 << p)
p += 1
P <<= 1

results.append(s)
i = (a * i + b) % m
j = (a * j + b) % m

with open("xor1OUT.txt", "w") as g:
for result in results:
g.write(f"{result}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

1135 - p2sah

2024-05-18T16:37:05Z

Oros Ioana Diana:

Se dă o tablă de șah cu <code>n+1</code> linii (numerotate de sus în jos începând cu <code>1</code>) și <code>2n+1</code> coloane (numerotate de la stânga la dreapta începând cu <code>1</code>). Pe prima linie pătratul din mijloc conține <code>1</code> gram de fân, iar celelalte pătrate de pe prima linie nu conțin nimic. Începând cu linia a doua fiecare pătrat conține o cantitate de fân obținută prin adunarea cantităților de fân din cele <code>3</code> pătrate ale liniei anterioare cu care se învecinează (pe verticală și diagonală). De exemplu dacă <code>n=3</code> tabla are <code>4</code> linii, <code>7</code> coloane și următoarea configurație.

Un cal pleacă de pe prima linie, de pe o coloana <code>k<=n</code>, sare din orice poziție <code>(i,j)</code> în poziția <code>(i+1,j+2)</code> atât timp cât este posibil și mănâncă tot fânul din pătratele prin care trece. De exemplu, pentru <code>n=3</code> și <code>k=2</code>, pătratele prin care trece calul sunt marcate cu asterisc (<code>*</code>)

= Cerinţe =
1. Cunoscând <code>n</code> și <code>k</code>, să se calculeze cantitatea de fân de pe linia <code>k</code> a tablei.

2. Cunoscând <code>n</code> și <code>k</code>, să se calculeze câte grame de fân mănâncă un cal care pleacă de pe prima linie, de pe coloana <code>k</code>.

Întrucât aceste numere pot fi mari, se cere doar restul modulo <code>100003</code> ale acestor numere.

= Date de intrare =
Fișierul de intrare <code>p2sah.in</code> conține pe prima linie un număr <code>t</code> cu valoarea <code>1</code> sau <code>2</code>. Pe a doua linie a fișierului de intrare se găsesc două numere naturale <code>n</code> și <code>k</code> separate printr-un spațiu.

Dacă <code>t=1</code> se va rezolva prima cerință, deci pentru valoarea <code>n</code> citită tabla are <code>n+1</code> linii și <code>2n+1</code> coloane, iar <code>k</code> reprezintă numărul liniei de pe care trebuie calculată cantitatea de fân.

Dacă <code>t=2</code> se va rezolva a doua cerință, deci pentru valoarea <code>n</code> citită tabla are <code>n+1</code> linii și <code>2n+1</code> coloane, iar <code>k</code> reprezintă numărul coloanei din prima linie de unde pleacă calul.

= Date de ieșire =
Dacă <code>t</code> din fișierul de intrare este <code>1</code> se va rezolva doar prima cerință.

În acest caz fișierul de ieșire <code>p2sahIN.txt.txt</code> va conține un singur număr reprezentând cantitatea totală de fân din toate pătratele situate pe tabla pe linia <code>k</code> (trebuie afișat restul modulo <code>100003</code>).

Dacă <code>t</code> din fișierul de intrare este <code>2</code> se va rezolva doar a doua cerință.

În acest caz fișierul de ieșire <code>p2sahOUT.txt</code> va conține un singur număr reprezentând cantitatea totală de fân mâncată de un cal care pleacă de pe linia <code>1</code> și coloana <code>k</code> (trebuie afișat restul modulo <code>100003</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 ≤ k ≤ n ≤ 1.000.000.000</code>
* La cerința 1 pentru 80% dintre teste <code>k ≤ n ≤ 1.000.000</code>, iar pentru alte 20% din teste <code>k ≤ n ≤ 1.000.000.000</code>
* La cerința 2 pentru 30% dintre teste <code>k ≤ n ≤ 1000</code>, pentru alte 30% dintre teste <code>k ≤ n ≤ 1.000.000</code>, iar pentru restul de 40% dintre teste <code>k ≤ n ≤ 1.000.000.000</code>.
* Rezolvarea corectă a primei cerințe asigură 20% din punctajul testului respectiv.
* Rezolvarea corectă a celei de a doua cerințe asigura 70% din punctajul testului respectiv.

= Exemplul 1 =
<code>p2sahIN.txt</code>
1
3 2
<code>p2sahOUT.txt</code>
3

= Exemplul 2 =
<code>p2sahIN.txt</code>
1
3 4
<code>p2sahOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
MOD = 100003

def solve(M, T, S):
if M in S:
return
m = M // 2

solve(m + 1, T, S)
solve(m, T, S)
solve(m - 1, T, S)
solve(m - 2, T, S)
S.add(M)
if M % 2:
T[M] = (1 * T[m] * T[m - 1] + 1 * T[m] * T[m - 1] + 1 * T[m] * T[m] + 1 * T[m + 1] * T[m + 1]) % MOD
else:
T[M] = (1 * T[m] * T[m + 1] + 1 * T[m - 1] * T[m] + 1 * T[m - 2] * T[m] + 1 * T[m - 1] * T[m - 1]) % MOD

def check_restrictions(k, n):
return 1 <= k <= n <= 1_000_000_000

def main():
with open("p2sahIN.txt", "r") as f:
lines = f.readlines()
if len(lines) < 2:
with open("p2sahOUT.txt", "w") as g:
g.write("Datele nu corespund restrictiilor impuse\n")
return

t = int(lines[0].strip())
if t not in (1, 2):
with open("p2sahOUT.txt", "w") as g:
g.write("Datele nu corespund restrictiilor impuse\n")
return

try:
n, k = map(int, lines[1].strip().split())
except ValueError:
with open("p2sahOUT.txt", "w") as g:
g.write("Datele nu corespund restrictiilor impuse\n")
return

if not check_restrictions(k, n):
with open("p2sahOUT.txt", "w") as g:
g.write("Datele nu corespund restrictiilor impuse\n")
return

if t == 1:
k -= 1
sol = 1
p = 3
while k:
if k & 1:
sol = (sol * p) % MOD
p = (p * p) % MOD
k //= 2
else:
T = {0: 0, 1: 1, 2: 1, 3: 2}
S = {0, 1, 2, 3}
n = n + 2 - k
solve(n, T, S)
sol = T[n]

with open("p2sahOUT.txt", "w") as g:
g.write(f"{sol}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

1135 - p2sah

2024-05-18T16:35:41Z

Oros Ioana Diana:

Se dă o tablă de șah cu <code>n+1</code> linii (numerotate de sus în jos începând cu <code>1</code>) și <code>2n+1</code> coloane (numerotate de la stânga la dreapta începând cu <code>1</code>). Pe prima linie pătratul din mijloc conține <code>1</code> gram de fân, iar celelalte pătrate de pe prima linie nu conțin nimic. Începând cu linia a doua fiecare pătrat conține o cantitate de fân obținută prin adunarea cantităților de fân din cele <code>3</code> pătrate ale liniei anterioare cu care se învecinează (pe verticală și diagonală). De exemplu dacă <code>n=3</code> tabla are <code>4</code> linii, <code>7</code> coloane și următoarea configurație.

Un cal pleacă de pe prima linie, de pe o coloana <code>k<=n</code>, sare din orice poziție <code>(i,j)</code> în poziția <code>(i+1,j+2)</code> atât timp cât este posibil și mănâncă tot fânul din pătratele prin care trece. De exemplu, pentru <code>n=3</code> și <code>k=2</code>, pătratele prin care trece calul sunt marcate cu asterisc (<code>*</code>)

= Cerinţe =
1. Cunoscând <code>n</code> și <code>k</code>, să se calculeze cantitatea de fân de pe linia <code>k</code> a tablei.

2. Cunoscând <code>n</code> și <code>k</code>, să se calculeze câte grame de fân mănâncă un cal care pleacă de pe prima linie, de pe coloana <code>k</code>.

Întrucât aceste numere pot fi mari, se cere doar restul modulo <code>100003</code> ale acestor numere.

= Date de intrare =
Fișierul de intrare <code>p2sah.in</code> conține pe prima linie un număr <code>t</code> cu valoarea <code>1</code> sau <code>2</code>. Pe a doua linie a fișierului de intrare se găsesc două numere naturale <code>n</code> și <code>k</code> separate printr-un spațiu.

Dacă <code>t=1</code> se va rezolva prima cerință, deci pentru valoarea <code>n</code> citită tabla are <code>n+1</code> linii și <code>2n+1</code> coloane, iar <code>k</code> reprezintă numărul liniei de pe care trebuie calculată cantitatea de fân.

Dacă <code>t=2</code> se va rezolva a doua cerință, deci pentru valoarea <code>n</code> citită tabla are <code>n+1</code> linii și <code>2n+1</code> coloane, iar <code>k</code> reprezintă numărul coloanei din prima linie de unde pleacă calul.

= Date de ieșire =
Dacă <code>t</code> din fișierul de intrare este <code>1</code> se va rezolva doar prima cerință.

În acest caz fișierul de ieșire <code>p2sahIN.txt.txt</code> va conține un singur număr reprezentând cantitatea totală de fân din toate pătratele situate pe tabla pe linia <code>k</code> (trebuie afișat restul modulo <code>100003</code>).

Dacă <code>t</code> din fișierul de intrare este <code>2</code> se va rezolva doar a doua cerință.

În acest caz fișierul de ieșire <code>p2sahOUT.txt</code> va conține un singur număr reprezentând cantitatea totală de fân mâncată de un cal care pleacă de pe linia <code>1</code> și coloana <code>k</code> (trebuie afișat restul modulo <code>100003</code>).

= Restricții și precizări =

* <code>1 ≤ k ≤ n ≤ 1.000.000.000</code>
* La cerința 1 pentru 80% dintre teste <code>k ≤ n ≤ 1.000.000</code>, iar pentru alte 20% din teste <code>k ≤ n ≤ 1.000.000.000</code>
* La cerința 2 pentru 30% dintre teste <code>k ≤ n ≤ 1000</code>, pentru alte 30% dintre teste <code>k ≤ n ≤ 1.000.000</code>, iar pentru restul de 40% dintre teste <code>k ≤ n ≤ 1.000.000.000</code>.
* Rezolvarea corectă a primei cerințe asigură 20% din punctajul testului respectiv.
* Rezolvarea corectă a celei de a doua cerințe asigura 70% din punctajul testului respectiv.

= Exemplul 1 =
<code>p2sahIN.txt</code>
1
3 2
<code>p2sahOUT.txt</code>
3

= Exemplul 2 =
<code>p2sahIN.txt</code>
1
3 4
<code>p2sahOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
MOD = 100003

def solve(M, T, S):
if M in S:
return
m = M // 2

solve(m + 1, T, S)
solve(m, T, S)
solve(m - 1, T, S)
solve(m - 2, T, S)
S.add(M)
if M % 2:
T[M] = (1 * T[m] * T[m - 1] + 1 * T[m] * T[m - 1] + 1 * T[m] * T[m] + 1 * T[m + 1] * T[m + 1]) % MOD
else:
T[M] = (1 * T[m] * T[m + 1] + 1 * T[m - 1] * T[m] + 1 * T[m - 2] * T[m] + 1 * T[m - 1] * T[m - 1]) % MOD

def check_restrictions(k, n):
return 1 <= k <= n <= 1_000_000_000

def main():
with open("p2sahIN.txt", "r") as f:
lines = f.readlines()
if len(lines) < 2:
with open("p2sahOUT.txt", "w") as g:
g.write("Datele nu corespund restrictiilor impuse\n")
return

t = int(lines[0].strip())
if t not in (1, 2):
with open("p2sahOUT.txt", "w") as g:
g.write("Datele nu corespund restrictiilor impuse\n")
return

try:
n, k = map(int, lines[1].strip().split())
except ValueError:
with open("p2sahOUT.txt", "w") as g:
g.write("Datele nu corespund restrictiilor impuse\n")
return

if not check_restrictions(k, n):
with open("p2sahOUT.txt", "w") as g:
g.write("Datele nu corespund restrictiilor impuse\n")
return

if t == 1:
k -= 1
sol = 1
p = 3
while k:
if k & 1:
sol = (sol * p) % MOD
p = (p * p) % MOD
k //= 2
else:
T = {0: 0, 1: 1, 2: 1, 3: 2}
S = {0, 1, 2, 3}
n = n + 2 - k
solve(n, T, S)
sol = T[n]

with open("p2sahOUT.txt", "w") as g:
g.write(f"{sol}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

4045 - Wl

2024-05-18T16:27:36Z

Oros Ioana Diana:

= Cerința =
Kida a descoperit un nou joc, prin care pornind de la un număr oarecare poate ajunge la alte numere prin niște pași simpli: dacă la un moment de timp, <code>T</code>, Kida are numărul W, atunci la momentul de timp <code>T + 1</code> ea poate să ajungă la orice alt număr <code>L</code> dacă:

* <code>L < W</code>
* <code>L</code> este divizibil cu <code>W - L</code>
* <code>W</code> este divizibil cu <code>W - L</code>
* <code>2 * L ≥ W</code>

Kida are o mulțime de N numere, notată cu D. Acum, ea își pune Q întrebări de tipul: Dacă aș porni la momentul de timp T = 0 și aș avea numărul x, care este momentul de timp minim la care aș putea sa ajung la un număr din mulțimea D folosind regulile jocului descris mai sus? Dacă nu se poate ajunge la niciun număr din mulțimea D, atunci Kida va considera că răspunsul este -1.
== Date de intrare ==
Prima linie a input-ului conține numărul N. Pe a doua linie se află N numere naturale, reprezentând elementele mulțimii D. A treia linie conține numărul Q. Ultima linie va conțin cele Q numere, reprezentând întrebările pe care și le pune Kida.
== Date de ieșire ==
Prima linie a input-ului conține numărul N. Pe a doua linie se află N numere naturale, reprezentând elementele mulțimii D. A treia linie conține numărul Q. Ultima linie va conțin cele Q numere, reprezentând întrebările pe care și le pune Kida.
== Restricții și precizări ==
*1 ≤ N ≤ 10 000
*1 ≤ D[i] ≤ 100 000
*0 ≤ x ≤ 100 000
*1 ≤ Q ≤ 100 000
*Subtask #1: Răspunsul pentru fiecare întrebare este cel mult 1 – 10 puncte
*Subtask #2: Răspunsul pentru fiecare întrebare este cel mult 2 – alte 20 de puncte
*Subtask #3: Fără restricții – alte 70 de puncte

= Exemplu: =
Intrare
2
3 4
5
7 8 10 3 64
Ieșire
2
1
2
0
4
== Rezolvare ==
<syntaxhighlight lang="python" line="1">
from collections import deque

INF = float('inf')
MAX_VAL = 100001

def check_restrictions(n, initial_values, queries):
if not (1 <= n <= 100):
print("Datele nu corespund restrictiilor impuse")
return False
if not all(1 <= x <= 100000 for x in initial_values):
print("Datele nu corespund restrictiilor impuse")
return False
if not (1 <= len(queries) <= 100):
print("Datele nu corespund restrictiilor impuse")
return False
if not all(1 <= x <= 100000 for x in queries):
print("Datele nu corespund restrictiilor impuse")
return False
return True

def lee(n, initial_values, queries):
minim = [INF] * (MAX_VAL + 1)
q = deque(initial_values)

for x in initial_values:
minim[x] = 0

while q:
x = q.popleft()
for d in range(1, int(x**0.5) + 1):
if x % d == 0:
if x + d <= MAX_VAL and minim[x + d] > minim[x] + 1:
minim[x + d] = minim[x] + 1
q.append(x + d)
if x + (x // d) <= MAX_VAL and minim[x + (x // d)] > minim[x] + 1:
minim[x + (x // d)] = minim[x] + 1
q.append(x + (x // d))

results = []
for x in queries:
if minim[x] == INF:
results.append(-1)
else:
results.append(minim[x])

return results

def main():
n = int(input())
initial_values = list(map(int, input().split()))
q = int(input())
queries = list(map(int, input().split()))

if check_restrictions(n, initial_values, queries):
results = lee(n, initial_values, queries)
for res in results:
print(res)

if __name__ == "__main__":
main()

</syntaxhighlight>

4045 - Wl

2024-05-18T16:24:10Z

Oros Ioana Diana:

== Cerința ==
Kida a descoperit un nou joc, prin care pornind de la un număr oarecare poate ajunge la alte numere prin niște pași simpli: dacă la un moment de timp, T, Kida are numărul W, atunci la momentul de timp T + 1 ea poate să ajungă la orice alt număr L dacă:

*L < W
*L este divizibil cu W - L
*W este divizibil cu W - L
*2 * L ≥ W

Kida are o mulțime de N numere, notată cu D. Acum, ea își pune Q întrebări de tipul: Dacă aș porni la momentul de timp T = 0 și aș avea numărul x, care este momentul de timp minim la care aș putea sa ajung la un număr din mulțimea D folosind regulile jocului descris mai sus? Dacă nu se poate ajunge la niciun număr din mulțimea D, atunci Kida va considera că răspunsul este -1.
== Date de intrare ==
Prima linie a input-ului conține numărul N. Pe a doua linie se află N numere naturale, reprezentând elementele mulțimii D. A treia linie conține numărul Q. Ultima linie va conțin cele Q numere, reprezentând întrebările pe care și le pune Kida.
== Date de ieșire ==
Prima linie a input-ului conține numărul N. Pe a doua linie se află N numere naturale, reprezentând elementele mulțimii D. A treia linie conține numărul Q. Ultima linie va conțin cele Q numere, reprezentând întrebările pe care și le pune Kida.
== Restricții și precizări ==
*1 ≤ N ≤ 10 000
*1 ≤ D[i] ≤ 100 000
*0 ≤ x ≤ 100 000
*1 ≤ Q ≤ 100 000
*Subtask #1: Răspunsul pentru fiecare întrebare este cel mult 1 – 10 puncte
*Subtask #2: Răspunsul pentru fiecare întrebare este cel mult 2 – alte 20 de puncte
*Subtask #3: Fără restricții – alte 70 de puncte
== Exemplul 1 ==
; Intrare
: 2
: 3 4
: 5
: 7 8 10 3 64
; Ieșire
: 2
: 1
: 2
: 0
: 4
 
== Exemplul 2 ==
; Intrare
: 3
: 5 6 7
: 4
: 2 8 11 14
; Iesire
: 3
: 1
: -1
: 3
 d
== Rezolvare ==
<syntaxhighlight lang="python" line>
#4045 - Wl
def find_divisors(n):
divisors = set()

# Adăugăm divizorii primi ai lui n în mulțime
i = 2
while i * i <= n:
if n % i == 0:
divisors.add(i)
while n % i == 0:
n //= i
i += 1

if n > 1:
divisors.add(n)

return divisors

def min_time_to_reach_d(x, divisors_d):
time = 0

# Pentru fiecare divizor prim al lui x, calculăm timpul minim
for divisor in divisors_d:
while x % divisor == 0 and (x // divisor) % 2 == 0:
x //= divisor
time += 1

if x > 1:
time += 1

return time

def main():
# Citirea datelor de intrare
N = int(input())
D = list(map(int, input().split()))
Q = int(input())
questions = list(map(int, input().split()))

# Verificarea restricțiilor
if not (1 <= N <= 10000 and all(1 <= d <= 100000 for d in D) and 1 <= Q <= 100000 and all(0 <= x <= 100000 for x in questions)):
print("false")
return

# Găsirea divizorilor primi ai elementelor din D
divisors_D = set()
for number in D:
divisors_D.update(find_divisors(number))

# Răspuns la fiecare întrebare
for question in questions:
# Calculăm timpul minim pentru a ajunge la un număr din D
time_to_reach_D = min_time_to_reach_d(question, divisors_D)

if time_to_reach_D == 0:
print(-1)
else:
print(time_to_reach_D)

if __name__ == "__main__":
main()

</syntaxhighlight>

2412 - Sub Mat 1

2024-05-18T15:05:24Z

Oros Ioana Diana:

Se consideră o matrice <code>A</code> cu următoarele proprietăţi:

* conţine <code>n</code> linii şi <code>m</code> coloane;
* conţine doar valorile <code>0</code> şi <code>1</code>;
* pe fiecare linie valorile sunt plasate în ordine crescătoare.

Definim o submatrice determinată de perechea de linii <code>L1</code> şi <code>L2</code> (<code>L1 ≤ L2</code>) şi de perechea de coloane <code>C1</code> şi <code>C2</code> (<code>C1 ≤ C2</code>) ca fiind totalitatea elementelor matricei <code>A[i,j]</code> pentru care <code>L1 ≤ i ≤ L2</code> şi <code>C1 ≤ j ≤ C2</code>.

Dacă toate elementele unei submatrice sunt egale cu <code>0</code>, atunci submatricea se numeşte nulă.

Asupra matricei <code>A</code> putem efectua una sau mai multe operaţii de interschimbări de linii. Prin astfel de interschimbări liniile matricei pot fi rearanjate astfel încât matricea <code>A</code> să conţină cel puţin o submatrice nulă cu număr maxim de elemente.

= Cerința =
Fiind dată o astfel de matrice se cere să se determine numărul maxim de zerouri dintr-o submatrice nulă ce se poate obţine printr-o rearanjare a liniilor matricei date.

= Date de intrare =
Fișierul de intrare <code>submat1IN.txt</code> conţine pe prima linie două numere naturale <code>n m</code>, separate printr-un spaţiu, reprezentând numărul de linii, respectiv numărul de coloane ale matricei <code>A</code>. Pe următoarele <code>n</code> linii ale fişierului sunt descrise cele <code>n</code> linii ale matricei <code>A</code>; pe fiecare linie din cele <code>n</code> vor fi scrise câte <code>m</code> valori din mulţimea <code>{0, 1}</code>, separate prin spaţii, reprezentând în ordine elementele liniei respective.

= Date de ieșire =
Fișierul de ieșire <code>submat1OUT.txt</code> va conţine o singură linie pe care va fi scris un număr natural reprezentând numărul maxim de elemente pe care îl conţine o submatrice nulă rezultată în urma rearanjărilor liniilor matricei <code>A</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, m ≤ 1000</code>
* Pentru <code>60%</code> din teste <code>n, m ≤ 100</code>.

= Exemplul 1: =
<code>submat1IN.txt</code>
3 5
0 0 0 1 1
0 1 1 1 1
0 0 0 0 1
<code>submat1OUT.txt</code>
6

=== Explicație ===
Dacă rearanjăm liniile astfel încât matricea rezultată să fie următoarea:

<code>0 0 0 1 1</code>

<code>0 0 0 0 1</code>

<code>0 1 1 1 1</code>

atunci se observă că submatricea determinată de prima şi a doua linie şi de prima şi a treia coloană conţine <code>6</code> valori de <code>0</code> (<code>6</code> fiind numărul maxim posibil).

== Exemplul 2: ==
<code>submat1IN.txt</code>
1 5
0 0 0 1 1
0 1 1 1 1
0 0 0 0 1
<code>submat1OUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
def verifica_restricii(n, m):
return 2 <= n <= 1000 and 2 <= m <= 1000

def main():
with open('submat1IN.txt', 'r') as fin:
n, m = map(int, fin.readline().split())

if not verifica_restricii(n, m):
with open('submat1OUT.txt', 'w') as fout:
fout.write("Datele nu corespund restrictiilor impuse\n")
return
a = [0] * n
with open('submat1IN.txt', 'r') as fin:
next(fin)
for i in range(n):
linie = list(map(int, fin.readline().split()))
a[i] = linie.count(0)

a.sort(reverse=True)
aria = 0
for i in range(n):
if aria < (i + 1) * a[i]:
aria = (i + 1) * a[i]

with open('submat1OUT.txt', 'w') as fout:
fout.write(str(aria) + '\n')

if __name__ == '__main__':
main()

</syntaxhighlight>

2387 - Mosia 1

2024-05-18T14:49:14Z

Oros Ioana Diana:

Păcală a primit, aşa cum era învoiala, un petec de teren de pe moşia boierului. Terenul este împrejmuit complet cu segmente drepte de gard ce se sprijină la ambele capete de câte un par zdravăn. La o nouă prinsoare, Păcală iese iar in câştig şi primeşte dreptul să strămute nişte pari, unul câte unul, cum i-o fi voia, astfel încât să-şi extindă suprafaţa de teren. Dar învoiala prevede că fiecare par poate fi mutat în orice direcţie, dar nu pe o distanţă mai mare decât o valoare dată (scrisă pe fiecare par) şi fiecare segment de gard, fiind cam şubred, poate fi rotit şi prelungit de la un singur capăt, celălalt rămânând nemişcat.

= Cerința =
Cunoscând poziţiile iniţiale ale parilor şi valoarea înscrisă pe fiecare par, se cere suprafaţa maximă cu care poate să-şi extindă Păcală proprietatea. Se ştie că parii sunt daţi într-o ordine oarecare, poziţiile lor iniţiale sunt date prin numere întregi de cel mult <code>3</code> cifre, distanțele pe care fiecare par poate fi deplasat sunt numere naturale strict pozitive şi figura formată de terenul iniţial este un poligon neconcav.

= Date de intrare =
Fișierul de intrare <code>mosia1IN.txt</code> conţine <code>n+1</code> linii cu următoarele valori:

<code>n</code> – numărul de pari

<code>x[1] y[1] d[1]</code> – coordonatele iniţiale şi distanţa pe care poate fi mutat parul <code>1</code>

<code>x[2] y[2] d[2]</code> – coordonatele iniţiale şi distanţa pe care poate fi mutat parul <code>2</code>

. . .

<code>x[n] y[n] d[n]</code> – coordonatele iniţiale şi distanţa pe care poate fi mutat parul <code>n</code>

= Date de ieșire =
Fișierul de ieșire <code>mosia1OUT.txt</code> se scrie un număr real cu <code>4</code> zecimale ce reprezintă suprafața maximă cu care se poate mări moșia. Î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>3 < N ≤ 200</code> număr natural
* <code>–1000 < x[i], y[i] < 1000</code> numere întregi
* <code>0 < d[i] ≤ 20</code> numere întregi
* poligonul neconcav se defineşte ca un poligon convex cu unele vârfuri coliniare
* poziţiile parilor sunt date într-o ordine oarecare
* poligonul obţinut după mutarea parilor poate fi concav
* poziţiile finale ale parilor nu sunt in mod obligatoriu numere naturale

= Exemplul 1: =
<code>mosia1IN.txt</code>
4
-3 0 2
3 0 3
0 6 2
0 -6 6
<code>mosia1OUT.txt</code>
30.0000

=== Explicație ===
Prin mutarea parilor <code>1</code> si <code>2</code> cu câte <code>2</code> și respectiv <code>3</code> unități, se obține un teren având suprafaţa cu <code>30</code> de unităţi mai mare decât terenul iniţial.

== Exemplul 2: ==
<code>mosia1IN.txt</code>
2
-3 0 2
3 0 3
0 6 2
0 -6 6
<code>mosia1OUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
import math

m = 10000000.0

def cit():
global n, p
p = []
with open("mosia1IN.txt", "r") as f:
n = int(f.readline().strip())
for _ in range(n):
x, y, d = map(int, f.readline().strip().split())
p.append({'x': x, 'y': y, 'd': d})

def poz(pp, u):
i = pp
j = u
i0 = 0
j0 = -1
while i < j:
if p[i]['si'] - p[j]['si'] > 1/m or (abs(p[i]['si'] - p[j]['si']) < 1/m and p[i]['di'] - p[j]['di'] > 1/m and p[i]['si'] < 0) or (abs(p[i]['si'] - p[j]['si']) < 1/m and p[j]['di'] - p[i]['di'] > 1/m and p[i]['si'] > 0):
p[i], p[j] = p[j], p[i]
aux1 = -i0
i0 = -j0
j0 = aux1
i += i0
j += j0
return i

def quick(p, u):
if p < u:
k = poz(p, u)
quick(p, k - 1)
quick(k + 1, u)

def preprocesare():
global p
i0 = 0
for i in range(1, n):
if p[i]['x'] < p[i0]['x'] or (p[i]['x'] == p[i0]['x'] and p[i]['y'] < p[i0]['y']):
i0 = i
p[0], p[i0] = p[i0], p[0]
for i in range(1, n):
p[i]['di'] = math.sqrt((p[i]['x'] - p[0]['x'])**2 + (p[i]['y'] - p[0]['y'])**2)
p[i]['si'] = (p[i]['y'] - p[0]['y']) / p[i]['di']
quick(1, n-1)
p = [p[-1]] + p + [p[0]]

def arie(i):
return p[i]['d'] * math.sqrt((p[i-1]['x'] - p[i+1]['x'])**2 + (p[i-1]['y'] - p[i+1]['y'])**2) / 2.0

def pd():
global sol
s0 = [0] * (n + 2)
s1 = [0] * (n + 2)
for i in range(1, n):
s0[i+1] = max(s0[i], s1[i])
s1[i+1] = s0[i] + arie(i + 1)
sol = max(s0[n], s1[n])
s0[0] = 0
s1[0] = arie(1)
s0[1] = s1[1] = s1[0]
for i in range(2, n):
s0[i] = max(s0[i-1], s1[i-1])
s1[i] = s0[i-1] + arie(i + 1)
sol = max(sol, s0[n-1])

def verifica_restrictii():
if not (3 < n <= 200):
return False
for punct in p:
if not (-1000 < punct['x'] < 1000 and -1000 < punct['y'] < 1000 and 0 < punct['d'] <= 20):
return False
return True

def main():
global sol
cit()
if not verifica_restrictii():
with open("mosia1OUT.txt", "w") as f:
f.write("Datele nu corespund restrictiilor impuse")
return
preprocesare()
pd()
with open("mosia1OUT.txt", "w") as f:
f.write(f"{sol:.4f}")

if __name__ == "__main__":
main()

</syntaxhighlight>

0702 - Pascal

2024-05-18T14:43:29Z

Oros Ioana Diana:

Triunghiul lui Pascal este un aranjament geometric de numere ce poartă numele celebrului matematician francez Blaise Pascal (19 iunie 1623 – 19 august 1662), deoarece el a fost prima persoană care a descoperit importanţa tuturor modelelor din componenţa acestuia.

Triunghiul începe cu numărul <code>1</code>. Acest rând este considerat rândul <code>0</code> al triunghiului. Restul numerelor din acest triunghi se formează ca suma celor două numere de deasupra (considerând că toate numerele din afara triunghiului sunt întotdeauna zero). Prin urmare, rândul <code>1</code> va fi format din <code>1 = 0 + 1</code>, <code>1 = 1 + 0</code>, iar rândul <code>2</code> va fi format din <code>1 = 0 + 1</code>, <code>2 = 1 + 1</code>, <code>1 = 1 + 0</code>.

Fie <code>n</code> și <code>p</code> două numere naturale nenule cu proprietățile:

* <code>p</code> este număr prim;
* <code>n+1</code> este o putere naturală a lui <code>p</code>;

Notăm cu <code>M(p)</code> numărul de multipli de <code>p</code> din primele <code>n+1</code> rânduri ale triunghiului lui Pascal.

= Cerința =
Să se scrie un program care citeşte numerele naturale <code>n</code> şi <code>p</code> și determină numărul <code>M(p)</code>.

= Date de intrare =
Fișierul de intrare <code>pascalIN.txt</code> conține pe prima linie numerele naturale <code>n</code> și <code>p</code> separate printr-un spațiu.

= Date de ieșire =
Fișierul de ieșire <code>pascalOUT.txt</code> va conține pe prima linie numărul <code>M(p)</code> cu semnificația de mai sus. Î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 ≤ 109</code>
* <code>2 ≤ p ≤ 103</code>
* <code>30%</code> din teste au <code>n ≤ 104</code>
* <code>50%</code> din teste au <code>n ≤ 106</code>

= Exemplul 1: =
<code>pascalIN.txt</code>
7 2
<code>pascalOUT.txt</code>
9

= Explicație =
În primele <code>8</code> rânduri ale triunghiului se găsesc <code>9</code> multipli de <code>2</code>: <code>2,4,6,4,10,10,6,20,6</code>.

= Exemplul 2: =
<code>pascalIN.txt</code>
2196 13
<code>pascalOUT.txt</code>
1660932

= Explicație =
În primele <code>2197</code> rânduri ale triunghiului se găsesc <code>1660932</code> multipli de <code>13</code>.

== Rezolvare ==
<syntaxhighlight lang="python" line>
#0702 - Pascal
def is_prime(num):
if num < 2:
return False
for i in range(2, int(num**0.5) + 1):
if num % i == 0:
return False
return True

def calculate_M_pascal(n, p):
M_p = 0
current_power = 1

while current_power <= n + 1:
M_p += (n + 1) // current_power
current_power *= p

return M_p

def check_restrictions(n, p):
if not (2 <= n <= 10**9):
return False
if not (2 <= p <= 10**3):
return False
if n > 10**4 and p > 2:
return False
if n > 10**6 and p > 2:
return False
return True

def main():
# Citirea datelor de intrare
with open('pascalin.txt', 'r') as file:
n, p = map(int, file.readline().split())

# Verificare restricții
if not check_restrictions(n, p):
print("false")
return

# Verificare dacă p este prim
if not is_prime(p):
print("false")
return

# Calculul lui M(p)
result = calculate_M_pascal(n, p)

# Scrierea rezultatului în fișierul de ieșire
with open('pascalout.txt', 'w') as file:
file.write(str(result))

if __name__ == "__main__":
main()

</syntaxhighlight>

1769 - albume

2024-05-18T14:40:03Z

Oros Ioana Diana:

Tudoraș are o pasiune pentru muzică. El deține câte <code>K</code> albume din discografia fiecăreia dintre cele <code>C</code> formații pe care le ascultă. În fiecare zi, Tudoraș extrage la întamplare exact <code>Q</code> albume din colecția sa, pe care le ascultă în cursul zilei.

La finalul zilei, Tudoraș analizează albumele ascultate. Concret, el numără de la câte formații diferite provin cele Q albume alese și își notează această valoare.

Care va fi media aritmetică a valorilor notate, dacă procesul se repetă pentru un număr infinit de zile? Cu alte cuvinte, care este valoarea medie (expected value) a numărului de formații ascultate într-o zi?

= Date de intrare =
Fișierul <code>albumeIN.txt</code> conține pe prima linie trei valori separate prin spațiu: <code>C K Q</code>.

= Date de ieșire =
Fișierul <code>albumeOUT.txt</code> trebuie să conțină pe prima linie o singură valoare reală: media aritmetică a valorilor notate de Tudoraș. Î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 ≤ C, K ≤ 1000</code>
* <code>1 ≤ Q ≤ min(1000, C*K)</code>
* Pentru teste în valoare de 10 puncte, <code>K = 1</code>.
* Pentru alte teste în valoare de 10 puncte, <code>Q = C * K</code>.
* Pentru alte teste în valoare de 20 de puncte, <code>C * K ≤ 10</code>.
* În fiecare zi, toate albumele au probabilitate egală de a fi extrase.
* Rezultatul este considerat corect dacă are o eroare absolută de cel mult <code>10-6</code>.

= Exemplul 1 =
<code>albumeIN.txt</code>
2 2 2
<code>albumeOUT.txt</code>
1.666666667

= Exemplul 2 =
<code>albumeIN.txt</code>
232 654 27
<code>albumeOUT.txt</code>
25.542102567

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
def verifica_restrictii(c, k, q):
if 1 <= c <= 1000 and 1 <= k <= 1000 and 1 <= q <= min(1000, c * k):
return True
return False

def main():
try:
with open("albumeIN.txt", "r") as fin:
c, k, q = map(int, fin.readline().split())

if not verifica_restrictii(c, k, q):
with open("albumeOUT.txt", "w") as fout:
fout.write("Datele nu corespund restrictiilor impuse")
return

a = 1.0
for i in range(q):
a *= (k * (c - 1.0) - i) / (k * c - i)

rezultat = (1.0 - a) * c
with open("albumeOUT.txt", "w") as fout:
fout.write(f"{rezultat:.9f}")
except Exception as e:
with open("albumeOUT.txt", "w") as fout:
fout.write(f"Eroare: {str(e)}")

if __name__ == "__main__":
main()

</syntaxhighlight>

0673 - Dif Sub

2024-05-18T14:35:57Z

Oros Ioana Diana:

= Cerința =
Considerăm un arbore binar cu <code>n</code> noduri în care fiecare nod este numerotat de la <code>1</code> la <code>n</code> și conține o valoare număr natural. Să se determine diferența în valoare absolută a sumei valorilor memorate în subarborele stâng al rădăcinii și suma valorilor memorate în subarborele drept al rădăcinii.

= Date de intrare =
Fișierul de intrare <code>difsubIN.txt</code> conține pe prima linie numărul <code>n</code>. Fiecare dintre următoarele <code>n</code> linii contine câte <code>3</code> numere <code>X st dr</code>; linia <code>i + 1</code> din fișier conține informatiile despre nodul numerotat cu <code>i</code>: <code>X</code> reprezintă valoare din nod, <code>st</code> reprezintă numărul de ordine al descendentului stâng sau <code>0</code> dacă nodul <code>i</code> nu are descendent stâng, iar <code>dr</code> reprezintă numărul de ordine al descendentului drept sau <code>0</code> dacă nodul <code>i</code> nu are descendent drept.

= Date de ieșire =
Fișierul de ieșire <code>difsubOUT.txt</code> va conține pe prima linie numărul <code>D</code>, cu semnificația precizată. Î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 ≤ 1000</code>
* valorile din nodurile arborelui vor fi mai mici sau egale cu <code>1.000.000</code>

= Exemplul 1: =
<code>difsubIN.txt</code>
6
2 3 5
6 0 6
1 0 0
7 1 2
4 0 0
10 0 0
<code>difsubOUT.txt</code>
9

= Exemplul 2: =
<code>difsubIN.txt</code>
1001
2 3 5
6 0 6
1 0 0
7 1 2
4 0 0
10 0 0
<code>difsubOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
def check_restrictions(n, x):
if not (1 <= n <= 1000):
return False
if not all(0 <= val <= 1000000 for val in x):
return False
return True

def SRD(k, st, dr, x):
global d
if st[k] != 0:
SRD(st[k], st, dr, x)
d += x[k]
if dr[k] != 0:
SRD(dr[k], st, dr, x)

def main():
global d
with open("difsubIN.txt", "r") as f:
n = int(f.readline().strip())
x = [0] * (n + 1)
st = [0] * (n + 1)
dr = [0] * (n + 1)
nod = [0] * (n + 1)

for i in range(1, n + 1):
vals = f.readline().strip().split()
if len(vals) != 3:
with open("difsubOUT.txt", "w") as g:
g.write("Datele nu corespund restrictiilor impuse")
return

x[i] = int(vals[0])
st[i] = int(vals[1])
dr[i] = int(vals[2])
if st[i]:
nod[st[i]] = 1
if dr[i]:
nod[dr[i]] = 1

if not check_restrictions(n, x[1:]):
with open("difsubOUT.txt", "w") as g:
g.write("Datele nu corespund restrictiilor impuse")
return

rad = 1
while nod[rad]:
rad += 1

d = 0
SRD(st[rad], st, dr, x)
s = d
d = 0
SRD(dr[rad], st, dr, x)

with open("difsubOUT.txt", "w") as g:
if s > d:
g.write(str(s - d))
else:
g.write(str(d - s))

if __name__ == "__main__":
main()

</syntaxhighlight>

0674 - Count Sub

2024-05-18T14:31:11Z

Oros Ioana Diana:

= Cerința =
Considerăm un arbore binar cu <code>n</code> noduri în care fiecare nod este numerotat de la <code>1</code> la <code>n</code> și conține o valoare număr natural. Se dau <code>k</code> noduri din arbore și se cere determinarea, pentru fiecare nod, a numărului de noduri din subarborele cu rădăcina în acel nod.

= Date de intrare =
Fișierul de intrare <code>countsubIN.txt</code> conține pe prima linie numărul <code>n</code>. Fiecare dintre următoarele <code>n</code> linii contine câte <code>3</code> numere <code>X st dr</code>; linia <code>i + 1</code> din fișier conține informatiile despre nodul numerotat cu <code>i</code>: <code>X</code> reprezintă valoare din nod, <code>st</code> reprezintă numărul de ordine al descendentului stâng sau <code>0</code> dacă nodul <code>i</code> nu are descendent stâng, iar <code>dr</code> reprezintă numărul de ordine al descendentului drept sau <code>0</code> dacă nodul <code>i</code> nu are descendent drept.

Pe următoarea linie se află numărul <code>k</code>, iar pe fiecare dintre următoarele <code>k</code> linii se află câte un număr natural cuprins între <code>1</code> și <code>n</code>, reprezentând nodul curent.

= Date de ieșire =
Fișierul de ieșire <code>countsubOUT.txt</code> va conține <code>k</code> linii; fiecare linie va conține numărul de noduri din subarborele cu rădăcina în nodul corespunzător. Î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 ≤ 1000</code>
* valorile din nodurile arborelui vor fi mai mici sau egale cu <code>1.000.000</code>
* <code>1 ≤ k ≤ 1000</code>

= Exemplul 1: =
<code>countsubIN.txt</code>
6
2 3 5
6 0 6
1 0 0
7 1 2
4 0 0
10 0 0
4
1
2
4
2
<code>countsubOUT.txt</code>
3
2
6
2

= Exemplul 2: =
<code>countsubIN.txt</code>
1001
2 3 5
6 0 6
1 0 0
7 1 2
4 0 0
10 0 0
4
1
2
4
2
<code>countsubOUT.txt</code>
Datele nu corespund restrictiilor impuse

= Explicație =
Exemplul corespunde arborelui de mai jos, în care au fost marcate cu albastru valorile din noduri, iar cu roșu numerele de ordine ale nodurilor.Rezolvare<syntaxhighlight lang="python" line="1">
def check_restrictions(n, k):
if not (1 <= n <= 1000):
return False
if not (1 <= k <= 1000):
return False
return True

def count(k, s, d):
if k == 0:
return 0
else:
return 1 + count(s[k], s, d) + count(d[k], s, d)

def main():
with open("countsubIN.txt", "r") as fin:
try:
n = int(fin.readline().strip())
except ValueError:
with open("countsubOUT.txt", "w") as fout:
fout.write("Datele nu corespund restrictiilor impuse\n")
return

s = [0] * (n + 1)
d = [0] * (n + 1)

for i in range(1, n + 1):
line = fin.readline().strip().split()
if len(line) != 3:
with open("countsubOUT.txt", "w") as fout:
fout.write("Datele nu corespund restrictiilor impuse\n")
return
x, s[i], d[i] = map(int, line)

try:
k = int(fin.readline().strip())
except ValueError:
with open("countsubOUT.txt", "w") as fout:
fout.write("Datele nu corespund restrictiilor impuse\n")
return

queries = []
for _ in range(k):
try:
queries.append(int(fin.readline().strip()))
except ValueError:
with open("countsubOUT.txt", "w") as fout:
fout.write("Datele nu corespund restrictiilor impuse\n")
return

if not check_restrictions(n, k):
with open("countsubOUT.txt", "w") as fout:
fout.write("Datele nu corespund restrictiilor impuse\n")
return

with open("countsubOUT.txt", "w") as fout:
for y in queries:
fout.write(f"{count(y, s, d)}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

0677 - Nivele Bin

2024-05-18T14:25:19Z

Oros Ioana Diana:

= Cerința =
Considerăm un arbore binar cu <code>n</code> noduri în care fiecare nod este numerotat de la <code>1</code> la <code>n</code> și conține o valoare număr natural. În acest arbore rădăcina este considerată pe nivelul <code>0</code>, descendenții direcți ai rădăcinii pe nivelul <code>1</code>, etc. Să se determine numărul de nivele <code>k</code> din arbore și, pentru fiecare nivel <code>i</code> de la <code>0</code> la <code>k</code>, numărul de noduri situate pe acel nivel.

= Date de intrare =
Fișierul de intrare <code>nivelebinIN.txt</code> conține pe prima linie numărul <code>n</code>. Fiecare dintre următoarele <code>n</code> linii conține câte <code>3</code> numere <code>X st dr</code>; linia <code>i + 1</code> din fișier conține informațiile despre nodul numerotat cu <code>i</code>: <code>X</code> reprezintă valoare din nod, <code>st</code> reprezintă numărul de ordine al descendentului stâng sau <code>0</code> dacă nodul <code>i</code> nu are descendent stâng, iar <code>dr</code> reprezintă numărul de ordine al descendentului drept sau <code>0</code> dacă nodul <code>i</code> nu are descendent drept.

= Date de ieșire =
Fișierul de ieșire <code>nivelebinOUT.txt</code> va conține pe prima linie numărul <code>k</code>, iar pe a doua linie <code>k+1</code> numere naturale separate prin exact un spațiu, al <code>i</code>-lea număr reprezentând numărul de noduri situate pe nivelul <code>i-1</code> din arbore. Î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 ≤ 1000</code>
* valorile din nodurile arborelui vor fi mai mici sau egale cu <code>1.000.000</code>

= Exemplul 1: =
<code>nivelebinIN.txt</code>
6
2 3 5
6 0 6
1 0 0
7 1 2
4 0 0
10 0 0
<code>nivelebinOUT.txt</code>
3
1 2 3

= Explicație =
Exemplul corespunde arborelui de mai jos, în care au fost marcate cu albastru valorile din noduri, iar cu roșu numerele de ordine ale nodurilor.

Arborele conține trei nivele:

* nivelul <code>0</code> conține doar rădăcina, nodul numerotat cu <code>4</code>
* nivelul <code>1</code> conține două noduri, cele numerotate cu <code>1 2</code>
* nivelul <code>2</code> conține trei noduri, cele numerotate cu <code>3 5 6</code>

== Exemplul 2: ==
<code>nivelebinIN.txt</code>
1001
2 3 5
6 0 6
1 0 0
7 1 2
4 0 0
10 0 0
<code>nivelebinOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
def completniv(k, niv, nivele, s, d):
if k != 0:
nivele[k] = niv
completniv(s[k], niv + 1, nivele, s, d)
completniv(d[k], niv + 1, nivele, s, d)

def verifica_restrictii(n, noduri):
if not (1 <= n <= 1000):
return False
for x, s, d in noduri:
if x > 1000000 or s > 1000000 or d > 1000000:
return False
return True

def main():
try:
with open("nivelebinIN.txt", "r") as fin:
n = int(fin.readline().strip())
noduri = [tuple(map(int, fin.readline().strip().split())) for _ in range(n)]

if not verifica_restrictii(n, noduri):
raise ValueError("Datele nu corespund restrictiilor impuse")

s = [0] * (n + 1)
d = [0] * (n + 1)
p = [0] * (n + 1)
nivele = [0] * (n + 1)

for i in range(1, n + 1):
x, s[i], d[i] = noduri[i-1]
p[s[i]] = 1
p[d[i]] = 1

r = 0
for i in range(1, n + 1):
if p[i] == 0:
r = i
break

completniv(r, 0, nivele, s, d)

nivmax = max(nivele)

with open("nivelebinOUT.txt", "w") as fout:
fout.write(f"{nivmax + 1}\n")
for niv in range(nivmax + 1):
k = sum(1 for j in range(1, n + 1) if nivele[j] == niv)
fout.write(f"{k} ")

except ValueError as e:
with open("nivelebinOUT.txt", "w") as fout:
fout.write(str(e))

if __name__ == "__main__":
main()

</syntaxhighlight>

0677 - Nivele Bin

2024-05-18T14:23:44Z

Oros Ioana Diana:

= Cerința =
Considerăm un arbore binar cu <code>n</code> noduri în care fiecare nod este numerotat de la <code>1</code> la <code>n</code> și conține o valoare număr natural. În acest arbore rădăcina este considerată pe nivelul <code>0</code>, descendenții direcți ai rădăcinii pe nivelul <code>1</code>, etc. Să se determine numărul de nivele <code>k</code> din arbore și, pentru fiecare nivel <code>i</code> de la <code>0</code> la <code>k</code>, numărul de noduri situate pe acel nivel.

= Date de intrare =
Fișierul de intrare <code>nivelebinIN.txt</code> conține pe prima linie numărul <code>n</code>. Fiecare dintre următoarele <code>n</code> linii conține câte <code>3</code> numere <code>X st dr</code>; linia <code>i + 1</code> din fișier conține informațiile despre nodul numerotat cu <code>i</code>: <code>X</code> reprezintă valoare din nod, <code>st</code> reprezintă numărul de ordine al descendentului stâng sau <code>0</code> dacă nodul <code>i</code> nu are descendent stâng, iar <code>dr</code> reprezintă numărul de ordine al descendentului drept sau <code>0</code> dacă nodul <code>i</code> nu are descendent drept.

= Date de ieșire =
Fișierul de ieșire <code>nivelebinOUT.txt</code> va conține pe prima linie numărul <code>k</code>, iar pe a doua linie <code>k+1</code> numere naturale separate prin exact un spațiu, al <code>i</code>-lea număr reprezentând numărul de noduri situate pe nivelul <code>i-1</code> din arbore.

= Restricții și precizări =

* <code>1 ≤ n ≤ 1000</code>
* valorile din nodurile arborelui vor fi mai mici sau egale cu <code>1.000.000</code>

= Exemplul 1: =
<code>nivelebinIN.txt</code>
6
2 3 5
6 0 6
1 0 0
7 1 2
4 0 0
10 0 0
<code>nivelebinOUT.txt</code>
3
1 2 3

= Explicație =
Exemplul corespunde arborelui de mai jos, în care au fost marcate cu albastru valorile din noduri, iar cu roșu numerele de ordine ale nodurilor.

Arborele conține trei nivele:

* nivelul <code>0</code> conține doar rădăcina, nodul numerotat cu <code>4</code>
* nivelul <code>1</code> conține două noduri, cele numerotate cu <code>1 2</code>
* nivelul <code>2</code> conține trei noduri, cele numerotate cu <code>3 5 6</code>

== Exemplul 2: ==
<code>nivelebinIN.txt</code>
1001
2 3 5
6 0 6
1 0 0
7 1 2
4 0 0
10 0 0
<code>nivelebinOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
def completniv(k, niv, nivele, s, d):
if k != 0:
nivele[k] = niv
completniv(s[k], niv + 1, nivele, s, d)
completniv(d[k], niv + 1, nivele, s, d)

def verifica_restrictii(n, noduri):
if not (1 <= n <= 1000):
return False
for x, s, d in noduri:
if x > 1000000 or s > 1000000 or d > 1000000:
return False
return True

def main():
try:
with open("nivelebinIN.txt", "r") as fin:
n = int(fin.readline().strip())
noduri = [tuple(map(int, fin.readline().strip().split())) for _ in range(n)]

if not verifica_restrictii(n, noduri):
raise ValueError("Datele nu corespund restrictiilor impuse")

s = [0] * (n + 1)
d = [0] * (n + 1)
p = [0] * (n + 1)
nivele = [0] * (n + 1)

for i in range(1, n + 1):
x, s[i], d[i] = noduri[i-1]
p[s[i]] = 1
p[d[i]] = 1

r = 0
for i in range(1, n + 1):
if p[i] == 0:
r = i
break

completniv(r, 0, nivele, s, d)

nivmax = max(nivele)

with open("nivelebinOUT.txt", "w") as fout:
fout.write(f"{nivmax + 1}\n")
for niv in range(nivmax + 1):
k = sum(1 for j in range(1, n + 1) if nivele[j] == niv)
fout.write(f"{k} ")

except ValueError as e:
with open("nivelebinOUT.txt", "w") as fout:
fout.write(str(e))

if __name__ == "__main__":
main()

</syntaxhighlight>

3724 - Dreptunghi 2

2024-05-18T14:18:10Z

Oros Ioana Diana:

Avem la dispoziție un dreptunghi de dimensiuni <code>N x M</code>. Ne este util ca dreptunghiul nostru să se asemene cu o matrice, de aceea vom considera că are <code>N</code> linii și <code>M</code> coloane. Vom segmenta si numerota dreptunghiul nostru după un anumit cod <code>C</code>. Prin segmentare se înțelege trasarea unei linii orizontale sau verticale la o anumită poziție <code>k</code>, ce va despărți dreptunghiul nostru în alte două dreptunghiuri mai mici:

* de dimensiuni <code>k x M</code> (cel de sus) și <code>(N - k) x M</code> (cel de jos) – în cazul unei linii (H)orizontale, operație codificată prin <code>Hk</code>
* de dimensiuni <code>N x k</code> (cel din stânga) și <code>N x (M - k)</code> (cel din dreapta) – în cazul unei linii <code>V</code>erticale, operație codificată prin <code>Vk</code>

Numerotarea dreptunghiului se realizează cu numerele naturale <code>1</code>, <code>2</code>, <code>3</code>, … în această ordine.

Codul <code>C</code> pentru segmentarea și numerotarea unui dreptunghi se definește recursiv. Dacă <code>C1</code> și <code>C2</code> sunt coduri de segmentare și numerotare, atunci:

* <code>*</code> – în fiecare căsuță a dreptunghiului se va scrie valoarea curentă a numerotării. După aceea, această valoare este incrementată pentru a fi folosită de o ulterioară operație de tipul <code>*</code>;
* <code>HkC1C2</code> – se trasează linia orizontală la poziția <code>k</code>, se segmentează și numerotează dreptunghiul de sus conform codului <code>C1</code>, apoi se continuă cu segmentarea și numerotarea dreptunghiului de jos conform codului <code>C2</code>;
* <code>VkC1C2</code> – se trasează linia verticală la poziția <code>k</code>, se segmentează și numerotează dreptunghiul din stânga conform codului <code>C1</code>, apoi se continuă cu segmentarea și numerotarea dreptunghiului din dreapta conform codului <code>C2</code>.

De exemplu, dreptunghiul de dimensiuni <code>8 x 6</code> (<code>8</code> linii, <code>6</code> coloane) segmentat și numerotat conform codului <code>C = H5H3V2**V3**V5V2***</code>, va arăta ca în Figura 1.

Un cod de segmentare și numerotare <code>C</code> este valid pentru un dreptunghi de dimensiuni <code>N x M</code> dacă și numai dacă pentru fiecare operație de tipul <code>HkC1C2</code> și de tipul <code>VkC1C2</code> din cadrul lui <code>C</code>, poziția <code>k</code> la care se trage linia orizontală, sau verticală respectiv, se află strict în interiorul dreptunghiului curent (adică pe ambele părți ale liniei trasate există cel puțin o linie si cel puțin o coloană rămase care vor fi ulterior numerotate conform definiției recursive a codului <code>C</code>).

Un cod de segmentare și numerotare <code>C</code> valid pentru un dreptunghi de dimensiuni <code>N x M</code> generează mai multe subdiviziuni (dreptunghiuri mai mici) delimitate de liniile orizontale și verticale trasate în cadrul lui <code>C</code>. De exemplu, pentru dreptunghiul din Figura 1 codul <code>C</code> din exemplul de mai sus generează <code>7</code> subdiviziuni.

Codul <code>C</code> nu este unic determinat. Pentru dreptunghiul segmentat și numerotat din Figura 1 există <code>4</code> coduri echivalente, pe care le scriem în ordine lexicografică în cele ce urmează:

1. <code>H3V2**H2V3**V2*V3**</code>

2. <code>H3V2**H2V3**V5V2***</code>

3. <code>H5H3V2**V3**V2*V3**</code>

4. <code>H5H3V2**V3**V5V2***</code>

Pentru stabilirea ordinii lexicografice a două codificări, fiecare informație compactă ce face parte din secvență se va considera entitate separată: adică simbolurile <code>H</code>, <code>V</code>, <code>*</code> de tip caracter, respectiv numerele <code>k</code> de tip întreg, indiferent de numărul de cifre din care sunt formate.

La nivel de caractere ordinea lexicografică este <code>H < V < *</code>. Numerele se vor compara în funcție de valoarea lor, de exemplu <code>1 < 7 < 12</code>. Vom considera că un caracter este mai mic lexicografic decât un număr întreg.

De exemplu, următoarele două coduri echivalente sunt scrise în ordine lexicografică:

1. <code>V7*V6**</code>

2. <code>V13V7***</code>

și corespund dreptunghiului de mai jos:

= Cerința =
Se dă un cod de segmentare și numerotare și se cere să se afle:

1. numărul de subdiviziuni pe care acesta le generează;

2. dimensiunile unui dreptunghi de arie minimă pentru care acest cod este valid;

3. numărul de codificări distincte modulo <code>1.000.000.007</code>, echivalente cu codul citit (în acest număr va fi inclus și codul inițial);

4. primul cod în ordine lexicografică echivalent cu cel dat.

= Date de intrare =
De la intrarea standard se vor citi:

* de pe prima linie valoarea lui <code>P</code>;
* de pe linia următoare un șir de caractere reprezentând codul de segmentare și numerotare <code>C</code>.

= Date de ieșire =

* Dacă valoarea citită pentru <code>P</code> este <code>1</code>, atunci la ieșirea standard se va tipări numărul de subdiviziuni pe care codul <code>C</code> le generează;
* Dacă valoarea citită pentru <code>P</code> este <code>2</code>, atunci la ieșirea standard se vor tipări două numere <code>N</code> și <code>M</code> separate printr-un spațiu, dimensiunile unui dreptunghi de arie minimă pentru care codul <code>C</code> citit este valid. În caz că există mai multe, se acceptă oricare;
* Dacă valoarea citită pentru <code>P</code> este <code>3</code>, atunci la ieșirea standard se va tipări numărul de codificări distincte modulo <code>1.000.000.007</code> echivalente cu codul citit (în acest număr va fi inclus și codul <code>C</code> citit).
* Dacă valoarea citită pentru <code>P</code> este <code>4</code>, atunci la ieșirea standard se va tipări primul cod în ordine lexicografică echivalent cu cel dat;

= Restricții și precizări =

* <code>0 < lungimea codului C (număr de caractere) < 350</code>
* Pentru teste în valoare de 14 puncte avem <code>P = 1</code>.
* Pentru teste în valoare de 21 de puncte avem <code>P = 2</code>.
* Pentru teste în valoare de 29 de puncte avem <code>P = 3</code>.
* Pentru teste în valoare de 36 de puncte avem <code>P = 4</code>.

= Exemplul 1: =
Intrare
1
H3V2**H2V3**V2*V3**
Ieșire
7

=== Explicație ===
În urma segmentării se obțin <code>7</code> dreptunghiuri.

= Exemplul 2: =
Intrare
2
H3V2**H2V3**V2*V3**
Ieșire
6 6

=== Explicație ===
Cel mai mic dreptunghi pentru care codul este valid are <code>6</code> linii și <code>6</code> coloane.

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
MOD = 1000000007

class RetType:
def __init__(self, type, offset, cnt, s1, s2):
self.type = type
self.offset = offset
self.cnt = cnt
self.s1 = s1
self.s2 = s2

sir = ""
din = [0] * 355
pos = 0
cntDrept = 0
cntStr = 1
lenH = 0
lenV = 0

def parseInt():
global pos
s = 0
while pos < len(sir) and '0' <= sir[pos] <= '9':
s = s * 10 + int(sir[pos]) - int('0')
pos += 1
return s

def solve(h, v):
global pos, cntDrept, cntStr, lenH, lenV, din
currType = sir[pos]
pos += 1
if currType == '*':
cntDrept += 1
lenH = max(lenH, h + 1)
lenV = max(lenV, v + 1)
return RetType('*', 0, 0, "", "*")
k = parseInt()
ret = RetType(currType, k, 1, "", "")

aux1 = solve(h, v)
if aux1.type == currType:
ret.cnt += aux1.cnt
ret.s1 += aux1.s1
ret.s1 += currType
ret.s1 += str(k - aux1.offset)
ret.s1 += aux1.s2
else:
cntStr = (1 * cntStr * din[aux1.cnt]) % MOD
ret.s1 += currType
ret.s1 += str(k)
ret.s1 += aux1.s1 + aux1.s2

newH = h
newV = v
if currType == 'H':
newH += k
else:
newV += k
aux2 = solve(newH, newV)
if aux2.type == currType:
ret.cnt += aux2.cnt
ret.offset += aux2.offset
ret.s1 += aux2.s1
ret.s2 += aux2.s2
else:
cntStr = (1 * cntStr * din[aux2.cnt]) % MOD
ret.s2 += aux2.s1 + aux2.s2

return ret

def restrictii(type, sir):
if not (1 <= type <= 4):
print("Datele nu corespund restrictiilor impuse")
return False
if not (0 < len(sir) < 350):
print("Datele nu corespund restrictiilor impuse")
return False
return True

def main():
global pos, sir, cntStr, din
type = int(input())
sir = input().strip()

if not restrictii(type, sir):
return

din[0] = din[1] = 1
for i in range(2, 351):
din[i] = 0
for j in range(i):
din[i] = (din[i] + 1 * din[j] * din[i - j - 1]) % MOD

aux = solve(0, 0)
cntStr = (1 * cntStr * din[aux.cnt]) % MOD

if type == 1:
print(cntDrept)
elif type == 2:
print(lenH, lenV)
elif type == 3:
print(cntStr)
else:
print(aux.s1 + aux.s2)

if __name__ == "__main__":
main()

</syntaxhighlight>

4203 - Number of Points

2024-05-18T14:15:29Z

Oros Ioana Diana:

În planul <code>xOy</code> se găsesc <code>n</code> puncte de coordonate numere naturale nenule, nu neapărat aflate pe poziții distincte.

= Cerința =
Pentru fiecare punct din plan de coordonate <code>(x, y)</code> trebuie să spuneți câte alte puncte au coordonatele <code>(p, q)</code> cu proprietatea că <code>1 ≤ p < x</code> și <code>1 ≤ q ≤ y</code> (atenție, <code>p</code> este strict mai mic decât <code>x</code>, iar <code>q</code> este mai mic sau egal cu <code>y</code>).

= Date de intrare =
Fișierul de intrare <code>numberofpointsIN.txt</code> conține pe prima linie, separate prin câte un spațiu, numerele <code>n</code>, <code>A</code>, <code>B</code>, <code>C</code>, <code>D</code>, <code>x1</code>, <code>y1</code>, <code>x2</code>, <code>y2</code>, unde <code>n</code> este numărul de puncte din plan, <code>(x1, y1)</code> sunt coordonatele primului punct din plan, iar <code>(x2, y2)</code> sunt coordonatele celui de-al doilea punct. Coordonatele restului punctelor se generează după formulele:

* <code>xi</code> <code>= (xi-2</code> <code>* A + xi-1</code> <code>* B + C) % D + 1</code>, pentru orice <code>i=3..n</code>
* <code>yi</code> <code>= (yi-2</code> <code>* A + yi-1</code> <code>* B + C) % D + 1</code>, pentru orice <code>i=3..n</code>

= Date de ieșire =
Fișierul de ieșire <code>numberofpointsOUT.txt</code> va conține exact <code>n</code> linii, pe linia <code>i</code> (cu <code>i = 1..n</code>) se va afla un singur număr natural reprezentând numărul de puncte care au abscisa strict mai mică decât <code>xi</code> și ordonata mai mică sau egală decât <code>yi</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 ≤ 200.000</code>
* <code>1 ≤ A, B, C, D, x1, y1, x2, y2 ≤ 1.000.000</code>

= Exemplul 1: =
<code>numberofpointsIN.txt</code>
7 19 17 11 23 4 5 7 2
<code>numberofpointsOUT.txt</code>
1
1
2
2
4
0
5

=== Explicații ===
Cele șapte puncte generate au coordonatele: <code>(4, 5)</code>, <code>(7, 2)</code>, <code>(23, 3)</code>, <code>(7, 9)</code>, <code>(16, 15)</code>, <code>(3, 1)</code> și <code>(22, 15)</code>. Primul punct, de coordonate <code>(4, 5)</code> are un singur punct care îndeplinește cerințele, anume cel de coordonate <code>(3, 1)</code>. Al cincilea punct, de coordonate <code>(16, 15)</code> are <code>4</code> puncte care îndeplinesc condițiile, anume <code>(4, 5)</code>, <code>(7, 2)</code>, <code>(7, 9)</code> și <code>(3, 1)</code>.

== Exemplul 2: ==
<code>numberofpointsIN.txt</code>
0 19 17 11 23 4 5 7 2
<code>numberofpointsOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
import sys

def read_input(file):
with open(file, "r") as f:
data = f.read().split()
return list(map(int, data))

def write_output(file, data):
with open(file, "w") as f:
f.write(data)

class Punct:
def __init__(self, x, y, ind):
self.x = x
self.y = y
self.ind = ind

def csort(a, b):
if a.x != b.x:
return a.x - b.x
return a.y - b.y

def update(tree, node, st, dr, poz):
if st == dr:
tree[node] += 1
return
mid = (st + dr) // 2
if poz <= mid:
update(tree, 2 * node, st, mid, poz)
else:
update(tree, 2 * node + 1, mid + 1, dr, poz)
tree[node] = tree[2 * node] + tree[2 * node + 1]

def query(tree, node, st, dr, val):
if dr <= val:
return tree[node]
if st == dr:
return 0
mid = (st + dr) // 2
q1 = query(tree, 2 * node, st, mid, val)
q2 = 0
if val > mid:
q2 = query(tree, 2 * node + 1, mid + 1, dr, val)
return q1 + q2

def verifica_restrictii(n, A, B, C, D):
if not (1 <= n <= 200000 and 1 <= A <= 1000000 and 1 <= B <= 1000000 and 1 <= C <= 1000000 and 1 <= D <= 1000000):
return False
return True

def main():
data = read_input("numberofpointsIN.txt")
n, A, B, C, D = data[0], data[1], data[2], data[3], data[4]

if not verifica_restrictii(n, A, B, C, D):
write_output("numberofpointsOUT.txt", "Datele nu corespund restrictiilor impuse")
return

v = []
idx = 5
for i in range(1, n + 1):
if i <= 2:
x, y = data[idx], data[idx + 1]
idx += 2
else:
x = (v[i - 3].x * A + v[i - 2].x * B + C) % D + 1
y = (v[i - 3].y * A + v[i - 2].y * B + C) % D + 1
v.append(Punct(x, y, i))

v.sort(key=lambda p: (p.x, p.y))

CMAX = 1000000
tree = [0] * (4 * CMAX + 1)
ans = [0] * (n + 1)
same_x = [0] * (CMAX + 1)

for i in range(n):
ans[v[i].ind] = query(tree, 1, 1, CMAX, v[i].y) - same_x[v[i].x]
same_x[v[i].x] += 1
update(tree, 1, 1, CMAX, v[i].y)

output = "\n".join(map(str, ans[1:]))
write_output("numberofpointsOUT.txt", output)

if __name__ == "__main__":
main()

</syntaxhighlight>

4203 - Number of Points

2024-05-18T14:15:17Z

Oros Ioana Diana:

În planul <code>xOy</code> se găsesc <code>n</code> puncte de coordonate numere naturale nenule, nu neapărat aflate pe poziții distincte.

= Cerința =
Pentru fiecare punct din plan de coordonate <code>(x, y)</code> trebuie să spuneți câte alte puncte au coordonatele <code>(p, q)</code> cu proprietatea că <code>1 ≤ p < x</code> și <code>1 ≤ q ≤ y</code> (atenție, <code>p</code> este strict mai mic decât <code>x</code>, iar <code>q</code> este mai mic sau egal cu <code>y</code>).

= Date de intrare =
Fișierul de intrare <code>numberofpointsIN.txt</code> conține pe prima linie, separate prin câte un spațiu, numerele <code>n</code>, <code>A</code>, <code>B</code>, <code>C</code>, <code>D</code>, <code>x1</code>, <code>y1</code>, <code>x2</code>, <code>y2</code>, unde <code>n</code> este numărul de puncte din plan, <code>(x1, y1)</code> sunt coordonatele primului punct din plan, iar <code>(x2, y2)</code> sunt coordonatele celui de-al doilea punct. Coordonatele restului punctelor se generează după formulele:

* <code>xi</code> <code>= (xi-2</code> <code>* A + xi-1</code> <code>* B + C) % D + 1</code>, pentru orice <code>i=3..n</code>
* <code>yi</code> <code>= (yi-2</code> <code>* A + yi-1</code> <code>* B + C) % D + 1</code>, pentru orice <code>i=3..n</code>

= Date de ieșire =
Fișierul de ieșire <code>numberofpointsOUT.txt</code> va conține exact <code>n</code> linii, pe linia <code>i</code> (cu <code>i = 1..n</code>) se va afla un singur număr natural reprezentând numărul de puncte care au abscisa strict mai mică decât <code>xi</code> și ordonata mai mică sau egală decât <code>yi</code>.

= Restricții și precizări =

* <code>1 ≤ n ≤ 200.000</code>
* <code>1 ≤ A, B, C, D, x1, y1, x2, y2 ≤ 1.000.000</code>

= Exemplul 1: =
<code>numberofpointsIN.txt</code>
7 19 17 11 23 4 5 7 2
<code>numberofpointsOUT.txt</code>
1
1
2
2
4
0
5

=== Explicații ===
Cele șapte puncte generate au coordonatele: <code>(4, 5)</code>, <code>(7, 2)</code>, <code>(23, 3)</code>, <code>(7, 9)</code>, <code>(16, 15)</code>, <code>(3, 1)</code> și <code>(22, 15)</code>. Primul punct, de coordonate <code>(4, 5)</code> are un singur punct care îndeplinește cerințele, anume cel de coordonate <code>(3, 1)</code>. Al cincilea punct, de coordonate <code>(16, 15)</code> are <code>4</code> puncte care îndeplinesc condițiile, anume <code>(4, 5)</code>, <code>(7, 2)</code>, <code>(7, 9)</code> și <code>(3, 1)</code>.

== Exemplul 2: ==
<code>numberofpointsIN.txt</code>
0 19 17 11 23 4 5 7 2
<code>numberofpointsOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
import sys

def read_input(file):
with open(file, "r") as f:
data = f.read().split()
return list(map(int, data))

def write_output(file, data):
with open(file, "w") as f:
f.write(data)

class Punct:
def __init__(self, x, y, ind):
self.x = x
self.y = y
self.ind = ind

def csort(a, b):
if a.x != b.x:
return a.x - b.x
return a.y - b.y

def update(tree, node, st, dr, poz):
if st == dr:
tree[node] += 1
return
mid = (st + dr) // 2
if poz <= mid:
update(tree, 2 * node, st, mid, poz)
else:
update(tree, 2 * node + 1, mid + 1, dr, poz)
tree[node] = tree[2 * node] + tree[2 * node + 1]

def query(tree, node, st, dr, val):
if dr <= val:
return tree[node]
if st == dr:
return 0
mid = (st + dr) // 2
q1 = query(tree, 2 * node, st, mid, val)
q2 = 0
if val > mid:
q2 = query(tree, 2 * node + 1, mid + 1, dr, val)
return q1 + q2

def verifica_restrictii(n, A, B, C, D):
if not (1 <= n <= 200000 and 1 <= A <= 1000000 and 1 <= B <= 1000000 and 1 <= C <= 1000000 and 1 <= D <= 1000000):
return False
return True

def main():
data = read_input("numberofpointsIN.txt")
n, A, B, C, D = data[0], data[1], data[2], data[3], data[4]

if not verifica_restrictii(n, A, B, C, D):
write_output("numberofpointsOUT.txt", "Datele nu corespund restrictiilor impuse")
return

v = []
idx = 5
for i in range(1, n + 1):
if i <= 2:
x, y = data[idx], data[idx + 1]
idx += 2
else:
x = (v[i - 3].x * A + v[i - 2].x * B + C) % D + 1
y = (v[i - 3].y * A + v[i - 2].y * B + C) % D + 1
v.append(Punct(x, y, i))

v.sort(key=lambda p: (p.x, p.y))

CMAX = 1000000
tree = [0] * (4 * CMAX + 1)
ans = [0] * (n + 1)
same_x = [0] * (CMAX + 1)

for i in range(n):
ans[v[i].ind] = query(tree, 1, 1, CMAX, v[i].y) - same_x[v[i].x]
same_x[v[i].x] += 1
update(tree, 1, 1, CMAX, v[i].y)

output = "\n".join(map(str, ans[1:]))
write_output("numberofpointsOUT.txt", output)

if __name__ == "__main__":
main()

</syntaxhighlight>

4267 - Perechi Puncte

2024-05-18T14:09:57Z

Oros Ioana Diana:

Se dau <code>n</code> puncte în plan, nu neapărat distincte, fiecare punct fiind dat prin coordonatele sale <code>(x, y)</code>, unde <code>x</code> și <code>y</code> sunt numere naturale. Spunem că două puncte <code>(x, y)</code> și <code>(i, j)</code> sunt simetrice dacă <code>x = j</code> și <code>y = i</code>.

= Cerința =
Să se determine numărul perechilor de puncte simetrice.

= Date de intrare =
Programul citește de la tastatură, separate prin spații, numerele naturale <code>n</code>, <code>x1</code>, <code>y1</code>, <code>x2</code>, <code>y2</code>, <code>A</code>, <code>B</code>, <code>C</code>, <code>D</code>, unde <code>n</code> este numărul de puncte, <code>(x1, y1)</code> sunt coordonatele primului punct, <code>(x2, y2)</code> sunt coordonatele celui de-al doilea punct, iar restul punctelor <code>(x[i], y[i])</code> se generează după formulele:

* <code>x[i] = (x[i - 1] * A + x[i - 2] * B + C) % D</code>, <code>i = 3..n</code>
* <code>y[i] = (y[i - 1] * A + y[i - 2] * B + C) % D</code>, <code>i = 3..n</code>

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

= Restricții și precizări =

* <code>10 ≤ n ≤ 6.000.000</code>
* <code>0 ≤ x1, y1, x2, y2 ≤ 30.000</code>
* <code>2 ≤ A, B, C, D ≤ 30.000</code>
* Punctele generate nu sunt neapărat distincte. Dacă de exemplu se generează de <code>5</code> ori punctul <code>(2,9)</code> și de <code>7</code> ori punctul <code>(9,2)</code>, atunci se obțin <code>5 * 7 = 35</code> de perechi simetrice.
* Simetricul punctului <code>(x, x)</code> este un alt punct <code>(x, x)</code>.

= Exemplu: =
Intrare
15 2 3 5 2 30 20 50 100
Ieșire
55 

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
def verifica_restrictii(n, X, Y, X_, Y_, a, b, c, d):
if not (10 <= n <= 6000000):
return False
if not (0 <= X <= 30000 and 0 <= Y <= 30000 and 0 <= X_ <= 30000 and 0 <= Y_ <= 30000):
return False
if not (2 <= a <= 30000 and 2 <= b <= 30000 and 2 <= c <= 30000 and 2 <= d <= 30000):
return False
return True

def main():
data = input("").split()

n = int(data[0])
X = int(data[1])
Y = int(data[2])
X_ = int(data[3])
Y_ = int(data[4])
a = int(data[5])
b = int(data[6])
c = int(data[7])
d = int(data[8])

if not verifica_restrictii(n, X, Y, X_, Y_, a, b, c, d):
print("Datele nu corespund restrictiilor impuse")
return

from collections import defaultdict
points = defaultdict(int)

points[(X, Y)] += 1
points[(X_, Y_)] += 1

simetrice = 0

if X == Y_ and Y == X_:
simetrice += 1

for i in range(3, n + 1):
x, y = X, Y
X, Y = X_, Y_
X_ = (X * a + x * b + c) % d
Y_ = (Y * a + y * b + c) % d

simetrice += points[(Y_, X_)]
points[(X_, Y_)] += 1

print(f"{simetrice}")

if __name__ == "__main__":
main()

</syntaxhighlight>

3897 - Josephus Sequence

2024-05-18T14:00:44Z

Oros Ioana Diana:

= Cerința =
Josephus este un matematician înrăit.

Într-o zi acesta se joacă cu primele <code>N</code> numere prime, când se decide să își construiască propiul său șir circular format din aceste numere. Pe prima poziție se va afla primul număr prim, adică <code>2</code>, iar mai apoi se parcurge circular șirul din <code>K</code> în <code>K</code>, completându-se cu restul de numere prime, până la repartizarea tuturor.

Din nefericire lui Josephus, i-a venit somnul, așa, că vă roagă pe voi să îi construiți șirul.

= Date de intrare =
Fișierul de intrare <code>josephusIN.txt</code> conține pe prima linie numărul <code>N</code> și numărul <code>K</code>.

= Date de ieșire =
Fișierul de ieșire <code>josephusOUT.txt</code> va conține <code>N</code> numere naturale separate prin câte un spaţiu, reprezentând şirul lui Josephus. Î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 ≤ 1.000.000</code>
* <code>1 ≤ K ≤ 1.000.000.000</code>
* cel de-al <code>1.000.000</code> număr prim este <code>15.485.863</code>

= Exemplul 1: =
<code>josephusIN.txt</code>
5 4
<code>josephusOUt.txt</code>
2 5 11 7 3

=== Explicație ===
Distribuirea se face astfel:

<code>2 5 11 7 3</code> numărând din <code>4</code> în <code>4</code>, începând cu primul termen, se obţine următoarea listă:

<code>2 3 5 7 11</code> reprezentând primele <code>5</code> numere prime.

== Exemplul 2: ==
<code>josephusIN.txt</code>
0 4
<code>josephusOUt.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
import sys

def gen_primes(valMAX):
prime = [False] * (valMAX + 1)
primes = []
prime[2] = True
for i in range(3, valMAX + 1, 2):
prime[i] = True

for i in range(3, int(valMAX**0.5) + 1, 2):
if prime[i]:
for j in range(i*i, valMAX + 1, i + i):
prime[j] = False

primes.append(2)
for i in range(3, valMAX + 1, 2):
if prime[i]:
primes.append(i)

return primes

def build_aib(n):
aib = [0] * (n + 1)
for i in range(1, n + 1):
aib[i] += 1
if i + (i & -i) <= n:
aib[i + (i & -i)] += aib[i]
return aib

def update_add_aib(aib, n, pos, val):
while pos <= n:
aib[pos] += val
pos += (pos & -pos)

def query_sum_aib(aib, pos):
sum = 0
while pos >= 1:
sum += aib[pos]
pos -= (pos & -pos)
return sum

def query_range_sum_aib(aib, le, ri):
return query_sum_aib(aib, ri) - query_sum_aib(aib, le - 1)

def bs_aib(aib, n, val, logn):
sum = 0
pos = 0
for i in range(logn, -1, -1):
if pos + (1 << i) <= n and sum + aib[pos + (1 << i)] < val:
sum += aib[pos + (1 << i)]
pos += (1 << i)
return pos + 1

def put_int(x):
sys.stdout.write(str(x) + ' ')

def check_restrictions(n, k):
return 1 <= n <= 1000000 and 1 <= k <= 1000000000

def main():
with open("josephusIN.txt", "r") as fin:
n, k = map(int, fin.read().split())

with open("josephusOUT.txt", "w") as fout:
if not check_restrictions(n, k):
fout.write("Datele nu corespund restrictiilor impuse\n")
return

valMAX = 15485863
primes = gen_primes(valMAX)
logn = 31 - (n).bit_length() + 1
aib = build_aib(n)

v = [0] * (n + 1)
v[1] = 2
update_add_aib(aib, n, 1, -1)

st = 1
for i in range(2, n + 1):
ezk = (k - 1) % query_sum_aib(aib, n) + 1

if query_range_sum_aib(aib, st, n) >= ezk:
st = bs_aib(aib, n, ezk + query_sum_aib(aib, st - 1), logn)
else:
st = bs_aib(aib, n, ezk - query_range_sum_aib(aib, st, n), logn)

v[st] = primes[i - 1]
update_add_aib(aib, n, st, -1)

for i in range(1, n + 1):
fout.write(f"{v[i]} ")
fout.write("\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

1901 - Median Heaps

2024-05-18T13:50:57Z

Oros Ioana Diana:

= Cerința =
Se dă un vector de <code>N</code> numere naturale nenule, indexat de la <code>1</code>.

Se cere să se raspundă la <code>Q</code> interogări de tipul:

* pentru un interval <code>[l, r]</code> din vector, aflați costul total mimin, al egalizării tuturor elementelor din interval.

Într-un interval <code>[l, r]</code>, puteți crește sau micșora fiecare element cu costul <code>x</code> unde <code>x</code> este diferența dintre valoarea nouă și valoarea inițială. Costul total este suma acestor costuri.

= Date de intrare =

* pe prima linie numărul <code>N</code>.
* pe a doua linie <code>N</code> numere naturale nenule : , , … .
* pe a treia linie numărul <code>Q</code>.
* pe următoarele <code>Q</code> linii <code>2</code> numere: <code>l, r</code>.

= Date de ieșire =
Se vor afișa <code>Q</code> numere pe fiecare linie, reprezentând constul total minim, al fiecărui interval <code>l r</code>.

= Restricții și precizări =

* <code>1 ≤ N, Q ≤ 100.000</code>
* <code>1 ≤ l ≤ r ≤ 100.000</code>
* <code>1 ≤</code> <code>≤ 1.000.000.000</code>

= Exemplu: =
Intrare
9
3 2 16 15 12 6 20 4 5
3
2 7
2 2
3 8
Ieșire
31
0
29

= Explicație =
Pentru intervalul <code>[2, 7]</code>, costul total minim este <code>31</code>, deoarece egalizăm fiecare număr din interval cu <code>12</code>.

Pentru intervalul <code>[2, 2]</code>, costul total minim este <code>0</code>, deoarece avem un singur element în interval.

Pentru intervalul <code>[3, 8]</code>, costul total minim este <code>29</code>, deoarece egalizăm fiecare număr din interval cu <code>12</code>

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
import math

Nmax = 100001

class Query:
def __init__(self, st, dr, pos):
self.st = st
self.dr = dr
self.pos = pos

def update(aib, aibs, pos, val1, val2):
while pos < Nmax:
aib[pos] += val1
aibs[pos] += val2
pos += pos & -pos

def query(aib, aibs, pos, c):
sum_val = 0
s = 0
while pos > 0:
sum_val += aib[pos]
if aibs is not None:
s += aibs[pos]
pos -= pos & -pos
return sum_val if c == 1 else s

def add(k, N, V, S, aib, aibs):
update(aib, aibs, N[k], 1, V[S[N[k]]])

def delete(k, N, V, S, aib, aibs):
update(aib, aibs, N[k], -1, -V[S[N[k]]])

def binary_search(pos, n, aib):
st, dr = 1, n
ans = -1
while st <= dr:
mid = (st + dr) // 2
q = query(aib, None, mid, 1)
if q >= pos:
dr = mid - 1
ans = mid
else:
st = mid + 1
return ans

def verify_restrictions(n, q, ranges):
if not (1 <= n <= 100000 and 1 <= q <= 100000):
return False
for l, r in ranges:
if not (1 <= l <= r <= 100000):
return False
return True

def main():
n = int(input())
V = [0] * (n + 1)

values = list(map(int, input().split()))
for i in range(1, n + 1):
V[i] = values[i-1]

q = int(input())
ranges = []
Q = []
for i in range(1, q + 1):
st, dr = map(int, input().split())
ranges.append((st, dr))
Q.append(Query(st, dr, i))

if not verify_restrictions(n, q, ranges):
print("Datele nu corespund restrictiilor impuse")
return

block = int(math.sqrt(n))
S = list(range(n + 1))
S[1:] = sorted(S[1:], key=lambda x: V[x])
N = [0] * (n + 1)
for i in range(1, n + 1):
N[S[i]] = i

Q.sort(key=lambda x: (x.dr // block, x.st if x.dr // block % 2 == 0 else -x.st))
aib = [0] * Nmax
aibs = [0] * Nmax
Rez = [0] * (q + 1)

st, dr = 1, 0
for i in range(1, q + 1):
s, d = Q[i-1].st, Q[i-1].dr
while st < s:
delete(st, N, V, S, aib, aibs)
st += 1
while st > s:
st -= 1
add(st, N, V, S, aib, aibs)
while dr < d:
dr += 1
add(dr, N, V, S, aib, aibs)
while dr > d:
delete(dr, N, V, S, aib, aibs)
dr -= 1

poss = (d - s + 2) // 2
ans = binary_search(poss, n, aib)
s1 = query(aib, aibs, n, 2)
h1 = query(aib, None, n, 1)
s2 = query(aib, aibs, ans, 2)
h2 = query(aib, None, ans, 1)
s1 -= s2
h1 -= h2

Rez[Q[i-1].pos] = s1 - h1 * V[S[ans]] + (-s2 + h2 * V[S[ans]])

for i in range(1, q + 1):
print(Rez[i])

if __name__ == "__main__":
main()

</syntaxhighlight>

1854 - Arbore Binar Complet

2024-05-18T13:41:39Z

Oros Ioana Diana:

Un arbore binar complet este un arbore binar în care toate nivelurile, cu excepția ultimului sunt ocupate în întregime. În general, deși nu este obligatoriu, toate nodurile de pe ultimul nivel sunt grupate în partea stânga a acestuia.

Arborele binar de mai jos este complet:

Înălțimea unui arbore binare complet este , unde este numărul de noduri.

Pentru reprezentarea unui arbore binar complet se poate folosi un tablou unidimensional <code>A</code> cu <code>n</code> elemente, în felul următor:

* rădăcinii arborelui îi corespunde elementul <code>A[1]</code>;
* dacă unui nod îi corespunde elementul <code>A[k]</code>, descendentului stâng îi va corespunde elementul <code>A[2*k]</code>, iar celui drept îi va corespunde elementul <code>A[2*k+1]</code>.

Observăm că pentru un nod <code>A[k]</code>, nodul părinte este <code>A[k/2]</code>, unde <code>k/2</code> este câtul împărțirii, fără zecimale.

Într-un arbore reprezentat astfel, nodurile de pe ultimul nivel sunt grupate în stânga. Dacă nodurile nu sunt grupate în stânga, sunt necesare câteva elemente în plus în vector, iar unele dintre ele nu vor fi folosite – nu vor avea un nod corespunzător.

= Cerința =
Se dau <code>n</code> numere naturale, reprezentând în ordine valorile nodurilor dintr-un arbore binar complet și <code>m</code> operații de tip <code>1</code> sau <code>2</code>, aplicate unui nod <code>k</code>.

Operația de tip <code>1</code> determină valoarea nodului părinte a lui <code>k</code>, iar operația de tip <code>2</code> determină suma valorilor fiilor nodului <code>k</code>. Dacă <code>k=1</code> sau dacă nodul <code>k</code> nu are fii, rezultatul va fi <code>0</code>.

Afișați pentru fiecare operație rezultatul ei.

= Date de intrare =
Fișierul de intrare <code>completIN.txt</code> conține pe prima linie numărul <code>n</code>, pe linia a doua <code>n</code> numere naturale, pe linia a treia <code>m</code>, iar pe următoarele <code>m</code> linii câte o pereche <code>op k</code>. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Date de ieșire =
Fișierul de ieșire <code>completOUT.txt</code> va conține rezultatele celor <code>m</code> operații, în ordine, câte unul pe linie.

= Restricții și precizări =

* <code>1 ≤ n ≤ 100000</code>
* cele <code>n</code> numere citite vor fi mai mici decât <code>1.000.000</code>
* <code>1 ≤ m ≤ 100000</code>
* <code>1 ≤ op ≤ 2</code>
* <code>1 ≤ k ≤ n</code>

= Exemplul 1: =
<code>completIN.txt</code>
12
15 5 18 35 32 23 12 43 29 25 22 13
8
2 9
1 7
2 5
1 8
1 1
2 6
1 9
2 4
<code>completOUt.txt</code>
0
18
47
35
0
13
35
72

=== Exemplul 2: ===
<code>completIN.txt</code>
0
15 5 18 35 32 23 12 43 29 25 22 13
8
2 9
1 7
2 5
1 8
1 1
2 6
1 9
2 4
<code>completOUt.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
def verifica_restrictii(n, m, operatii, arb):
if not (1 <= n <= 100000):
return False
if not all(0 <= num < 1000000 for num in arb[1:]): # index 0 este ignorat
return False
if not (1 <= m <= 100000):
return False
if not all(1 <= op <= 2 and 1 <= k <= n for op, k in operatii):
return False
return True

def main():
with open("completIN.txt", "r") as fin:
n = int(fin.readline().strip())
arb = [0] + list(map(int, fin.readline().strip().split()))
m = int(fin.readline().strip())
operatii = [tuple(map(int, fin.readline().strip().split())) for _ in range(m)]

if not verifica_restrictii(n, m, operatii, arb):
with open("completOUT.txt", "w") as fout:
fout.write("Datele nu corespund restrictiilor impuse\n")
return

with open("completOUT.txt", "w") as fout:
for op, k in operatii:
if op == 1:
if k == 1:
fout.write("0\n")
else:
fout.write(f"{arb[k//2]}\n")

elif op == 2:
if k*2 > n and k*2+1 > n:
fout.write("0\n")
elif k*2 <= n and k*2+1 > n:
fout.write(f"{arb[k*2]}\n")
elif k*2 <= n and k*2+1 <= n:
fout.write(f"{arb[k*2] + arb[k*2+1]}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

2338 - Ski Pass

2024-05-18T13:24:42Z

Oros Ioana Diana:

:

= Cerința =
La un parc de sporturi de iarnă au venit <code>G</code> grupuri de schiori numerotate de la <code>1</code> la <code>G</code>. Aceștia coboară pe

una dintre cele <code>2</code> pârtii disponibile dar urcă cu același teleschi. Teleschiul folosește T-bar-uri, o modalitate eficientă de a urca schiorii pe vârful pârtiei.

Un T-bar poate trage maxim <code>2</code> schiori odată. Deoarece sunt <code>2</code> pârtii, se formează <code>2</code> rânduri de oameni de-o parte și de alta a punctului de urcare în teleschi. Se știe că <code>2</code> schiori nu vor folosi același T-bar decât dacă fac parte din același grup. De asemenea, niciun schior nu se baga în fața altuia (toți sunt foarte corecți și răbdători). Atunci când un T-bar sosește, primul om de la una dintre cozi se urcă în el și pleacă sau așteaptă să se

urce încă cineva (din același grup cu el). Acest al doilea schior trebuie sa fie totuși primul de la coada lui (nimeni nu se bagă în față).

Care este numărul minim de T-bar-uri ce trebuie folosite astfel încât toți schiorii de la ambele rânduri să ajungă în vârful pârtiei?

= Date de intrare =
Pe prima linie a fișierului de intrare <code>skipassIN.txt</code> se află numărul de grupuri <code>G</code>. Pe următoarele două linii sunt descrise cele <code>2</code> cozi în felul următor: numărul <code>N</code> de oameni de la acea coada urmat de <code>N</code> numere reprezentând grupul din care face parte al <code>i</code>-lea schior (1<=i<=N).

= Date de ieșire =
În fișierul de ieșire <code>skipassOUT.txt</code> se află un singur număr reprezentând numărul minim de T-bar-uri ce trebuie

folosite.

= Restricții și precizări =

* <code>1 ≤ G ≤ 50</code>
* <code>1 ≤ N ≤ 1000</code>
* Pentru 40% din punctaj una dintre cozi va fi formata doar din oameni din același grup.
* Pentru 60% din punctaj <code>N <= 10</code>
* Pentru 90% din punctaj <code>N <= 300</code>
* Atenție la limita de memorie!

= Exemplu 1: =
<code>skipassIN.txt</code>
4
6 1 2 1 3 3 4
4 3 1 2 4
<code>skipassOUt.txt</code>
6

=== Explicație ===
Schiorii urca în următoarea ordine:

Primul de la a <code>2</code>-a coada singur

Primii de la ambele cozi

Primii de la ambele cozi

Primul de la prima coada

Primii <code>2</code> de la prima coada

Primii de la ambele cozi

= Exemplu 2: =
<code>skipassIN.txt</code>
51
6 1 2 1 3 3 4
4 3 1 2 4
<code>skipassOUt.txt</code>
Datele nu corespund restrictiilor impuse
 
== Rezolvare ==
<syntaxhighlight lang="python" line="1">
def verifica_restrictii(g, n1, n2):
if not (1 <= g <= 50 and 1 <= n1 <= 1000 and 1 <= n2 <= 1000):
with open("skipassOUT.txt", "w") as fout:
fout.write("Datele nu corespund restrictiilor impuse")
return False
return True

def citeste_datele(filename):
with open(filename, "r") as fin:
g = int(fin.readline().strip())
q1 = list(map(int, fin.readline().strip().split()))
q2 = list(map(int, fin.readline().strip().split()))
return g, q1, q2

def main():
g, q1, q2 = citeste_datele("skipassIN.txt")
n1 = len(q1)
n2 = len(q2)

if not verifica_restrictii(g, n1, n2):
return

# Initialize dp array with a large number
dp = [[float('inf')] * (n2 + 1) for _ in range(n1 + 1)]
dp[0][0] = 0

for i in range(n1 + 1):
for j in range(n2 + 1):
if i > 0:
dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1)
if j > 0:
dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1)
if i > 0 and j > 0:
dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1)
if i > 1 and q1[i - 1] == q1[i - 2]:
dp[i][j] = min(dp[i][j], dp[i - 2][j] + 1)
if j > 1 and q2[j - 1] == q2[j - 2]:
dp[i][j] = min(dp[i][j], dp[i][j - 2] + 1)
if i > 0 and j > 0 and q1[i - 1] == q2[j - 1]:
dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1)

with open("skipassOUT.txt", "w") as fout:
fout.write(str(dp[n1][n2]))

if __name__ == "__main__":
main()

</syntaxhighlight>

2163 - Episodul 3

2024-05-18T13:17:15Z

Oros Ioana Diana:

= Enunț =
Zoli joacă cu un labirint de dimensiune <code>N x N</code>, format din camere de dimensiune <code>1 x 1</code>, inițial toate inaccesibile. Auzind că Zoli este mare informatician, Dănutz și D’Umbră au decis să îl pună la încercare, după cum urmează:

<code>1 x y</code>: Dănutz transformă camera inaccesibilă <code>(x, y)</code> într-una accesibilă.

<code>2 x1 y1 x2 y2</code>: D’Umbră îl întreabă pe Zoli care este numărul minim de camere ce trebuie traversate pentru a ajunge din camera accesibilă <code>(x1, y1)</code> în camera accesibilă <code>(x2, y2)</code>.

= Cerința =
Zoli a rezolvat deja această problemă, fiind una banală. El s-a dus să se joace LOL și este curios dacă o poți rezolva și tu. Pentru <code>M</code> evenimente de forma celor de mai sus, să se scrie un program care le procesează și afișează în fișierul de ieșire rezultatele operațiilor de tip <code>2</code>, în ordinea în care acestea apar în fișierul de intrare.

= Date de intrare =
Fișierul de intrare <code>episodul3IN.txt</code> conține pe prima linie numerele <code>N</code> și <code>M</code>, iar pe următoarele <code>M</code> linii cele <code>M</code> operații.

= Date de ieșire =
Fișierul de ieșire <code>episodul3OUT.txt</code> va conține pe fiecare linie rezultatele operațiilor de tipul <code>2</code>, în ordinea în care acestea apar î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>1 ≤ N ≤ 1000</code>
* <code>1 ≤ M ≤ 250.000</code>
* <code>1 ≤ x, y ≤ N</code>
* pentru operațiile de tipul <code>1</code>: camera <code>(x, y)</code> va avea exact o cameră vecină pe linie sau coloană deja accesibilă la momentul transformării sale, excepție făcând camera care este transformată prima.
* InParser
* OutParser

= Exemplul 1: =
<code>episodul3IN.txt</code>
5 7
1 1 1
1 1 2
2 1 1 1 2
1 2 2
1 1 3
2 1 3 2 2
2 1 1 2 2
<code>episodul3OUT.txt</code>
2
3
3

= Exemplul 2: =
<code>episodul3IN.txt</code>
1001 7
1 1 1
1 1 2
2 1 1 1 2
1 2 2
1 1 3
2 1 3 2 2
2 1 1 2 2
<code>episodul3OUT.txt</code>
Datele nu corespund restrictiilor impuse
 
== Rezolvare ==
<syntaxhighlight lang="python" line="1">
class InParser:
def __init__(self, filename):
self.fin = open(filename, "r")
self.buff = self.fin.read()
self.sp = -1
self.length = len(self.buff)

def read_ch(self):
self.sp += 1
if self.sp < self.length:
return self.buff[self.sp]
return ''

def __lshift__(self, n):
c = self.read_ch()
while c and not c.isdigit() and c != '-':
c = self.read_ch()
if not c:
return self
sgn = 1
if c == '-':
n[0] = 0
sgn = -1
else:
n[0] = int(c)
c = self.read_ch()
while c.isdigit():
n[0] = 10 * n[0] + int(c)
c = self.read_ch()
n[0] *= sgn
return self

class OutParser:
def __init__(self, filename):
self.fout = open(filename, "w")
self.buff = []
self.sp = 0

def __del__(self):
self.fout.write("".join(self.buff))
self.fout.close()

def __lshift__(self, vu32):
if isinstance(vu32, int):
self.buff.append(str(vu32))
elif isinstance(vu32, str):
self.buff.append(vu32)
return self

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
Nmax = 1005
getNode = [[0] * Nmax for _ in range(Nmax)]
T = [[0] * (Nmax * Nmax) for _ in range(22)]
nodes = 0
dist = [0] * (Nmax * Nmax)

def getKthAncestor(K, node):
for i in range(10, -1, -1):
if K & (1 << i):
node = T[i][node]
K -= (1 << i)
return node

def getLCA(node1, node2):
if node1 == node2:
return node1
pos = dist[node1] + 1
i = 0
while (1 << i) <= dist[node1]:
i += 1
for i in range(i, -1, -1):
if T[i][node1] != T[i][node2]:
node1 = T[i][node1]
node2 = T[i][node2]
pos -= (1 << i)
return T[0][node1]

def main():
fin = InParser("episodul3IN.txt")
fout = OutParser("episodul3OUT.txt")

N = [0]
M = [0]
fin << N << M
N = N[0]
M = M[0]

if not (1 <= N <= 1000) or not (1 <= M <= 250000):
fout << "Datele nu corespund restrictiilor impuse"
return

global nodes
for _ in range(M):
t = [0]
fin << t
t = t[0]
if t == 1:
i = [0]
j = [0]
fin << i << j
i = i[0]
j = j[0]
if not (1 <= i <= N and 1 <= j <= N):
fout << "Datele nu corespund restrictiilor impuse"
return
nodes += 1
getNode[i][j] = nodes
for d in range(4):
ni = i + dx[d]
nj = j + dy[d]
if getNode[ni][nj] != 0:
T[0][nodes] = getNode[ni][nj]
dist[nodes] = 1 + dist[getNode[ni][nj]]
if dist[nodes] == 0:
dist[nodes] = 1
for i in range(1, 22):
if (1 << i) <= dist[nodes]:
T[i][nodes] = T[i - 1][T[i - 1][nodes]]
elif t == 2:
i = [0]
j = [0]
i2 = [0]
j2 = [0]
fin << i << j << i2 << j2
i = i[0]
j = j[0]
i2 = i2[0]
j2 = j2[0]
if not (1 <= i <= N and 1 <= j <= N and 1 <= i2 <= N and 1 <= j2 <= N):
fout << "Datele nu corespund restrictiilor impuse"
return
node1 = getNode[i][j]
node2 = getNode[i2][j2]
if dist[node1] > dist[node2]:
node1, node2 = node2, node1
sameLevel = getKthAncestor(dist[node2] - dist[node1], node2)
LCA = getLCA(node1, sameLevel)
fout << dist[node1] + dist[node2] - 2 * dist[LCA] + 1 << "\n"

if __name__ == "__main__":
main()

</syntaxhighlight>

2163 - Episodul 3

2024-05-18T13:16:36Z

Oros Ioana Diana:

= Enunț =
Zoli joacă cu un labirint de dimensiune <code>N x N</code>, format din camere de dimensiune <code>1 x 1</code>, inițial toate inaccesibile. Auzind că Zoli este mare informatician, Dănutz și D’Umbră au decis să îl pună la încercare, după cum urmează:

<code>1 x y</code>: Dănutz transformă camera inaccesibilă <code>(x, y)</code> într-una accesibilă.

<code>2 x1 y1 x2 y2</code>: D’Umbră îl întreabă pe Zoli care este numărul minim de camere ce trebuie traversate pentru a ajunge din camera accesibilă <code>(x1, y1)</code> în camera accesibilă <code>(x2, y2)</code>.

= Cerința =
Zoli a rezolvat deja această problemă, fiind una banală. El s-a dus să se joace LOL și este curios dacă o poți rezolva și tu. Pentru <code>M</code> evenimente de forma celor de mai sus, să se scrie un program care le procesează și afișează în fișierul de ieșire rezultatele operațiilor de tip <code>2</code>, în ordinea în care acestea apar în fișierul de intrare.

= Date de intrare =
Fișierul de intrare <code>episodul3IN.txt</code> conține pe prima linie numerele <code>N</code> și <code>M</code>, iar pe următoarele <code>M</code> linii cele <code>M</code> operații.

= Date de ieșire =
Fișierul de ieșire <code>episodul3OUT.txt</code> va conține pe fiecare linie rezultatele operațiilor de tipul <code>2</code>, în ordinea în care acestea apar î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>1 ≤ N ≤ 1000</code>
* <code>1 ≤ M ≤ 250.000</code>
* <code>1 ≤ x, y ≤ N</code>
* pentru operațiile de tipul <code>1</code>: camera <code>(x, y)</code> va avea exact o cameră vecină pe linie sau coloană deja accesibilă la momentul transformării sale, excepție făcând camera care este transformată prima.
* InParser
* OutParser

= Exemplul 1: =
<code>episodul3IN.txt</code>
5 7
1 1 1
1 1 2
2 1 1 1 2
1 2 2
1 1 3
2 1 3 2 2
2 1 1 2 2
<code>episodul3OUT.txt</code>
2
3
3

= Exemplul 2: =
<code>episodul3IN.txt</code>
1001 7
1 1 1
1 1 2
2 1 1 1 2
1 2 2
1 1 3
2 1 3 2 2
2 1 1 2 2
<code>episodul3OUT.txt</code>
2
3
3
 
== Rezolvare ==
<syntaxhighlight lang="python" line="1">
class InParser:
def __init__(self, filename):
self.fin = open(filename, "r")
self.buff = self.fin.read()
self.sp = -1
self.length = len(self.buff)

def read_ch(self):
self.sp += 1
if self.sp < self.length:
return self.buff[self.sp]
return ''

def __lshift__(self, n):
c = self.read_ch()
while c and not c.isdigit() and c != '-':
c = self.read_ch()
if not c:
return self
sgn = 1
if c == '-':
n[0] = 0
sgn = -1
else:
n[0] = int(c)
c = self.read_ch()
while c.isdigit():
n[0] = 10 * n[0] + int(c)
c = self.read_ch()
n[0] *= sgn
return self

class OutParser:
def __init__(self, filename):
self.fout = open(filename, "w")
self.buff = []
self.sp = 0

def __del__(self):
self.fout.write("".join(self.buff))
self.fout.close()

def __lshift__(self, vu32):
if isinstance(vu32, int):
self.buff.append(str(vu32))
elif isinstance(vu32, str):
self.buff.append(vu32)
return self

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
Nmax = 1005
getNode = [[0] * Nmax for _ in range(Nmax)]
T = [[0] * (Nmax * Nmax) for _ in range(22)]
nodes = 0
dist = [0] * (Nmax * Nmax)

def getKthAncestor(K, node):
for i in range(10, -1, -1):
if K & (1 << i):
node = T[i][node]
K -= (1 << i)
return node

def getLCA(node1, node2):
if node1 == node2:
return node1
pos = dist[node1] + 1
i = 0
while (1 << i) <= dist[node1]:
i += 1
for i in range(i, -1, -1):
if T[i][node1] != T[i][node2]:
node1 = T[i][node1]
node2 = T[i][node2]
pos -= (1 << i)
return T[0][node1]

def main():
fin = InParser("episodul3IN.txt")
fout = OutParser("episodul3OUT.txt")

N = [0]
M = [0]
fin << N << M
N = N[0]
M = M[0]

if not (1 <= N <= 1000) or not (1 <= M <= 250000):
fout << "Datele nu corespund restrictiilor impuse"
return

global nodes
for _ in range(M):
t = [0]
fin << t
t = t[0]
if t == 1:
i = [0]
j = [0]
fin << i << j
i = i[0]
j = j[0]
if not (1 <= i <= N and 1 <= j <= N):
fout << "Datele nu corespund restrictiilor impuse"
return
nodes += 1
getNode[i][j] = nodes
for d in range(4):
ni = i + dx[d]
nj = j + dy[d]
if getNode[ni][nj] != 0:
T[0][nodes] = getNode[ni][nj]
dist[nodes] = 1 + dist[getNode[ni][nj]]
if dist[nodes] == 0:
dist[nodes] = 1
for i in range(1, 22):
if (1 << i) <= dist[nodes]:
T[i][nodes] = T[i - 1][T[i - 1][nodes]]
elif t == 2:
i = [0]
j = [0]
i2 = [0]
j2 = [0]
fin << i << j << i2 << j2
i = i[0]
j = j[0]
i2 = i2[0]
j2 = j2[0]
if not (1 <= i <= N and 1 <= j <= N and 1 <= i2 <= N and 1 <= j2 <= N):
fout << "Datele nu corespund restrictiilor impuse"
return
node1 = getNode[i][j]
node2 = getNode[i2][j2]
if dist[node1] > dist[node2]:
node1, node2 = node2, node1
sameLevel = getKthAncestor(dist[node2] - dist[node1], node2)
LCA = getLCA(node1, sameLevel)
fout << dist[node1] + dist[node2] - 2 * dist[LCA] + 1 << "\n"

if __name__ == "__main__":
main()

</syntaxhighlight>

2493 - Recc

2024-05-18T13:11:14Z

Oros Ioana Diana:

= Enunț =
Ana Mia are o recurență liniară de forma <code>P[N] = A[1]*P[N-1] + A[2]*P[N-2] + A[3]*P[N-3] + A[4]*P[N-4]</code>, <code>N ≥ 5</code>. Studiind-o, îi vine o idee MAXIMĂ de problemă: “Pentru câte cvadriplete <code>(P[1], P[2], P[3], P[4])</code> din mulțimea numerelor naturale <code>[1, B]</code> valoarea <code>P[N]</code> modulo <code>K</code> are valoarea <code>X</code>?”

= Cerința =
Scrieți un program care citind <code>N</code>, <code>B</code>, <code>X</code>, <code>K</code>, și numerele <code>A[i], 1 ≤ i ≤ 4</code> rezolvă problema Anei.

= Date de intrare =
Fișierul de intrare <code>reccIN.txt</code> conține pe prima linie numerele <code>N</code>, <code>B</code>, <code>X</code>, <code>K</code>, separate printr-un spațiu, iar pe a doua linie <code>4</code> numere naturale separate prin spații, reprezentând numerele <code>A[i], 1 ≤ i ≤ 4</code>.

= Date de ieșire =
Fișierul de ieșire <code>reccOUT.txt</code> va conține pe prima linie numărul <code>ANS</code>, răspunsul problemei puse de Ana Mia. Î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 ≤ N ≤ 10^18</code>
* <code>1 ≤ B ≤ 1000</code>
* <code>1 ≤ K ≤ 10^9</code>
* <code>0 ≤ X < K</code>
* numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât <code>1.000.000.000</code>

= Exemplul 1: =
<code>reccIN.txt</code>
6 2 3 4
1 2 3 1
<code>reccOUT.txt</code>
2

=== Explicație ===
Soluțiile sunt <code>(2, 1, 2, 1)</code> și <code>(2, 2, 2, 1)</code>

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

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
class Matrice:
def __init__(self):
self.M = [[0] * 4 for _ in range(4)]

def inmultire(A, B, K):
C = Matrice()
for i in range(4):
for j in range(4):
for k in range(4):
C.M[i][j] = (C.M[i][j] + A.M[i][k] * B.M[k][j]) % K
return C

def putere(A, N, K):
if N == 1:
return A
if N % 2 == 1:
return inmultire(A, putere(A, N - 1, K), K)
P = putere(A, N // 2, K)
return inmultire(P, P, K)

def verificare_restrictii(N, B, K, X):
if not (5 <= N <= 10**18):
return False
if not (1 <= B <= 1000):
return False
if not (1 <= K <= 10**9):
return False
if not (0 <= X < K):
return False
return True

def F(val, vs, vd, I):
st, dr = 1, I
while st <= dr:
mij = (st + dr) // 2
if vs[mij] == val:
return vd[mij]
if vs[mij] < val:
st = mij + 1
else:
dr = mij - 1
return 0

def main():
with open("reccIN.txt", "r") as f:
# Citim prima linie și împărțim valorile
linia1 = f.readline().strip().split()
N = int(linia1[0])
B = int(linia1[1])
X = int(linia1[2])
K = int(linia1[3])

if not verificare_restrictii(N, B, K, X):
with open("reccOUT.txt", "w") as g:
g.write("Datele nu corespund restrictiilor impuse\n")
return

# Citim a doua linie și împărțim valorile
linia2 = f.readline().strip().split()
A = [int(val) for val in linia2]

C = Matrice()
for i in range(4):
C.M[3 - i][3] = A[i] % K

for i in range(3):
C.M[i + 1][i] = 1

C = putere(C, N - 4, K)

for i in range(4):
A[i] = C.M[i][3]

vs = []
vd = []
I = 0
for i in range(1, B + 1):
for j in range(1, B + 1):
vs.append((A[0] * i % K + A[1] * j % K) % K)
I += 1

vs.sort()

vd = [0] * (I + 1)
vd[0] = 1
II = 1
for i in range(1, I):
if vs[II - 1] != vs[i]:
vs[II] = vs[i]
vd[II] = 1
II += 1
else:
vd[II - 1] += 1
I = II

sol = 0
for i in range(1, B + 1):
for j in range(1, B + 1):
v = (A[2] * i % K + A[3] * j % K) % K
v = (X - v + K) % K
sol += F(v, vs, vd, I)

with open("reccOUT.txt", "w") as g:
g.write(f"{sol}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

2018 - Rogvaiv

2024-05-18T13:04:29Z

Oros Ioana Diana:

= Cerința =
Vecinul meu, Dorel, tocmai s-a mutat la casă şi vrea să-şi vopsească gardul. Fiind îndrăgostit de frumos, a cumpărat 7 cutii de vopsea: roşu, orange, galben, verde, albastru, indigo şi violet. Acum însă, are o dilemă: în câte moduri poate vopsi cele <code>n</code> uluci ale gardului, ştiind că fiecare ulucă poate fi vopsită cu oricare dintre culorile cumpărate?

= Date de intrare =
Fișierul de intrare <code>rogvaivIN.txt</code> conține pe prima linie numărul <code>n</code>.

= Date de ieșire =
Fișierul de ieșire <code>rogvaivOUT.txt</code> va conține pe prima linie numărul de moduri în care Dorel poate vopsi gardul, modulo <code>1.000.000.007</code>.

= Restricții și precizări =

* numărul <code>n</code> are cel mult <code>1.000.000</code> de cifre. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Exemplu: =
<code>rogvaivIN.txt</code>
3
<code>rogvaivOUT.txt</code>
343

=== Explicație ===
Fiecare ulucă poate fi vopsită cu una din cele <code>7</code> culori, deci avem <code>7•7•7=343</code> moduri.

 
== Rezolvare ==
<syntaxhighlight lang="python" line="1">
def verifica_restrictii(a):
if len(a) > 1000001:
return False
if not a.isdigit():
return False
return True

def main():
try:
with open("rogvaivIN.txt", "r") as f:
a = f.read().strip()
except FileNotFoundError:
with open("rogvaivOUT.txt", "w") as g:
g.write("Datele nu corespund restrictiilor impuse")
return

if not verifica_restrictii(a):
with open("rogvaivOUT.txt", "w") as g:
g.write("Datele nu corespund restrictiilor impuse")
return

n = len(a)
s = 0
for i in range(n):
s = (s * 10 + int(a[i])) % 1000000006

c = [0] * 50
i = 0
while s != 0:
i += 1
c[i] = s % 2
s = s // 2

p = 1
for j in range(i, 0, -1):
if c[j] == 1:
p = ((p * p) * 7) % 1000000007
else:
p = (p * p) % 1000000007

with open("rogvaivOUT.txt", "w") as g:
g.write(str(p))

if __name__ == "__main__":
main()

</syntaxhighlight>

2043 - Subsecventa

2024-05-18T12:50:58Z

Oros Ioana Diana:

= Cerința =
O echipă de cercetători de la Agenţia Spaţială Europeană au recepţionat un mesaj provenit dintr-o

altă galaxie. În urma analizelor complexe efectuate asupra mesajului recepţionat, ei au descoperit că

mesajul conţine mai multe subsecvenţe neîntrerupte de caractere care sunt palindroame. Se ştie că o

secvenţă de caractere este un ''palindrom'' dacă prin citirea ei de la stânga la dreapta şi de la dreapta la

stânga se obţin aceleaşi caractere. Mesajul recepţionat este codificat doar cu literele mari A, B, …, Z

ale alfabetului englez şi nu conţine alte caractere.

Pentru analiza mesajului recepţionat cercetătorii au nevoie de un program care să determine subsecvenţa palindrom de lungime maximă. În cazul în care există mai multe subsecvenţe

care au aceeaşi lungime maximă, se va reţine subsecvenţa care apare prima dată

în scrierea mesajului, citit de la stânga spre dreapta.

De exemplu, pentru mesajul “CABABAD”, subsecvenţa palindrom cu lungimea maximă este “ABABA” şi are lungimea 5.

= Date de intrare =
În fișierul de intrare <code>subsecventaIN.txt</code> este scris şirul de caractere ale mesajului. Mesajul este format

doar din litere mari ale alfabetului englez şi are cel mult 100.000 de caractere.

= Date de ieșire =
Fișierul de ieșire <code>subsecventaOUt.txt</code> va conține pe prima linie un număr natural reprezentând lungimea

maximă a unei subsecvenţe palindrom, iar pe a doua linie se va scrie subsecvenţa

palindrom de lungime maximă care apare prima dată în mesaj. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* Mesajul conţine doar litere mari şi are cel mult <code>100.000</code> de caractere.
* Pentru 60% din teste numărul de caractere din fişierul de intrare este cel mult <code>1.000</code>.

= Exemplu 1: =
<code>subsecventaIN.txt</code>
CABABAD
<code>subsecventaOUT.txt</code>
5
ABABA

=== Explicație ===
Cea mai lungă subsecvenţă palindrom are lungimea 5.

== Exemplu 2: ==
<code>subsecventaIN.txt</code>
CABABADa
<code>subsecventaOUT.txt</code>
Datele nu corespund restrictiilor impuse
 
== Rezolvare ==
<syntaxhighlight lang="python" line="1">
def citire(file_in):
with open(file_in, 'r') as fin:
s = fin.read().strip()
return s

def init(s):
n = len(s)
t = ['^']
for char in s:
t.append('#')
t.append(char)
t.append('#')
t.append('\0')
return ''.join(t)

def manacher(t):
n = len(t)
P = [0] * n
C = R = 0
maxpal = 1

for i in range(1, n - 1):
j = 2 * C - i
if R > i:
P[i] = min(R - i, P[j])

while t[i + 1 + P[i]] == t[i - 1 - P[i]]:
P[i] += 1

if i + P[i] > R:
C = i
R = i + P[i]

if P[i] > P[maxpal]:
maxpal = i

rez = P[maxpal]
ind = (maxpal - 1 - rez) // 2
return rez, ind

def verifica_restrictii(s):
if not s.isalpha() or not s.isupper() or len(s) > 100000:
return False
return True

def main():
file_in = "subsecventaIN.txt"
file_out = "subsecventaOUT.txt"
s = citire(file_in)

if not verifica_restrictii(s):
with open(file_out, 'w') as fout:
fout.write("Datele nu corespund restrictiilor impuse")
return

t = init(s)
rez, ind = manacher(t)

with open(file_out, 'w') as fout:
fout.write(f"{rez}\n")
fout.write(f"{s[ind:ind + rez]}")

if __name__ == "__main__":
main()

</syntaxhighlight>

== Explicatie ==
Cea mai lungă subsecvenţă palindrom are lungimea 5.
 
Există o singură subsecvenţă palindrom de lungime 5 în mesaj: ABABA.

1760 - Optim

2024-05-18T12:31:52Z

Oros Ioana Diana:

Gigel primea de la mama lui, ca temă, o foaie pe care era scris un şir de <code>N</code> numere întregi. Singurul calcul pe care ştia să îl facă până acum era suma tuturor numerelor. Pentru aceasta el plasa <code>N-1</code> semne de adunare, +, între numerele aflate pe poziţii consecutive în şir şi calcula astfel suma acestor numere. Între timp a crescut şi a învăţat şi operaţia de înmulţire pentru care foloseşte semnul *. Din şirul celor <code>N-1</code> semne de adunare, îi trece prin minte să înlocuiască <code>K</code> semne + cu <code>K</code> semne *.

Îşi dă seama că tema se complică, deoarece înmulţirile trebuie efectuate înaintea adunărilor, dar nu se dă bătut şi duce calculul până la capăt.

= Cerința =
Scrieţi un program care să determine valoarea minimă pe care o poate obţine şi valoarea maximă pe care o poate obţine după înlocuirea menţionată.

= Date de intrare =
Fişierul de intrare <code>optimIN.txt</code> conţine pe prima linie numerele naturale <code>N</code> şi <code>K</code>, separate printr-un spaţiu, reprezentând numărul de numere întregi din şir, respectiv numărul de operaţii de înmulţire ce vor fi efectuate. Pe cea de a doua linie se află <code>N</code> numere întregi separate prin câte un spaţiu, , reprezentând numerele din şir.

= Date de ieșire =
Fişierul de ieşire <code>optimOUT.txt</code> va conţine pe o singură linie, separate printr-un spaţiu, în ordine crescătoare, cele două valori 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>2 ≤ N ≤ 30</code>
* <code>0 ≤ K ≤ 9; K < N</code>
* <code>-8 ≤ xi</code> <code>≤ 8, 1 ≤ i ≤ N</code>

= Exemplu 1: =
<code>optimIN.txt</code>
6 3
2
0
3
-1
7
-4
<code>optimOUt.txt</code>
-31 86

=== Explicație ===
<code>2 * 0 + 3 * (-1) + 7 * (-4) = -31</code>

<code>2 + 0 + 3 * (-1) * 7 * (-4) = 86</code>.

= Exemplu 2: =
<code>optimIN.txt</code>
6 8
2
0
3
-1
7
-4
<code>optimOUt.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
def verificare_restrictii(N, K, A):
if not (2 <= N <= 30) or not (0 <= K <= 9) or not (K < N):
return False
if not all(-8 <= x <= 8 for x in A):
return False
return True

def back(lv, k, aux, suma, A, N):
global maxim, minim
if lv == N:
suma += aux
if suma > maxim:
maxim = suma
if suma < minim:
minim = suma
return
if N - lv > k:
back(lv + 1, k, A[lv], suma + aux, A, N)
if k > 0:
back(lv + 1, k - 1, aux * A[lv], suma, A, N)

def main():
global maxim, minim

with open("optimIN.txt", "r") as fin:
N, K = map(int, fin.readline().strip().split())
A = [int(fin.readline().strip()) for _ in range(N)]

if not verificare_restrictii(N, K, A):
with open("optimOUT.txt", "w") as fout:
fout.write("Datele nu corespund restrictiilor impuse\n")
return

maxim = -2000000000
minim = 2000000000

back(1, K, A[0], 0, A, N)

with open("optimOUT.txt", "w") as fout:
fout.write(f"{minim} {maxim}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

3698 - Bemo

2024-05-18T10:19:32Z

Oros Ioana Diana:

Se dă o matrice cu <code>R</code> linii şi <code>C</code> coloane de numere distincte de la <code>1</code> la <code>R * C</code>. Bemo, personajul emoţional, doreşte să urmărească cel mai bun drum din colţul superior stânga, de coordonate <code>(1, 1)</code>, în colţul inferior dreapta, de coordonate <code>(R, C)</code>. Un drum este o secvenţă de numere din matrice în care fiecare număr se găseşte în jos sau la dreapta numărului anterior, adică dacă <code>(i, j)</code> este poziţia unui număr de pe un drum, atunci următorul număr poate fi cel de pe poziţia <code>(i + 1, j)</code> sau cel de pe poziţia <code>(i, j + 1)</code>. Pentru a determina dacă un drum <code>A</code> este mai bun decât un drum <code>B</code>, numerele fiecărui drum se vor sorta şi se va alege cel mai mic lexicografic, de exemplu <code>[1,3,5,6,8] < [1,4,5,6,7]</code>.

= Date de intrare =
Fișierul de intrare <code>bemoIN.txt</code> conține pe prima linie două numere naturale <code>R</code> și <code>C</code>, unde <code>R</code> este numărul liniilor, iar <code>C</code> numărul coloanelor matricei lui Bemo. Pe următoarele <code>R</code> linii se vor găsi câte <code>C</code> numere separate printr-un spaţiu. Fiecare număr va fi unic şi va fi cuprins în intervalul <code>[1, R*C]</code>.

= Date de ieșire =
Fișierul de ieșire <code>bemoOUT.txt</code> va conține <code>R+C-1</code> numere reprezentând cel mai bun drum pe care Bemo îl poate alege. Numerele vor fi scrise separate printr-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>0 < R, C < 1501</code>;
* Pentru 40% din teste: <code>0 < R</code>, <code>C < 751</code>;
* Pentru 70% din teste: <code>0 < R, C < 1301</code>;
* Spunem că un drum <code>A =</code> (<code>a1</code>, <code>a2</code>, …, <code>aR+C-1</code>) este mai mic lexicografic decât un drum <code>B =</code> (<code>b1</code>, <code>b2</code>,…, <code>bR+C-1</code>) dacă există o poziție <code>p</code> astfel încât <code>ap</code> <code>< bp</code> și <code>a1</code> <code>= b1</code>, <code>a2</code> <code>= b2</code>, …, <code>ap-1</code> <code>= bp-1</code>.

= Exemplu 1: =
<code>bemoIN.txt</code>
4 4
7 4 13 3
8 11 12 2
10 9 1 5
16 14 15 6
<code>bemoOUT.txt</code>
7 4 11 9 1 5 6

= Exemplu 2: =
<code>bemoIN.txt</code>
4 1502
7 4 13 3
8 11 12 2
10 9 1 5
16 14 15 6
<code>bemoOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
import sys

NMAX = 2011

A = [[0] * NMAX for _ in range(NMAX)]
row = [0] * (NMAX * NMAX)
col = [0] * (NMAX * NMAX)
selected = [0] * (NMAX * NMAX)
elems = [0] * (2 * NMAX)

R = C = nelems = 0

def ReadInput():
global R, C
with open("bemoIN.txt", "r") as f:
data = f.read().split()
R, C = int(data[0]), int(data[1])

# Verifică imediat după citirea dimensiunilor
if not (0 < R < 1501 and 0 < C < 1501):
with open("bemoOUT.txt", "w") as f:
f.write("Datele nu corespund restrictiilor impuse\n")
sys.exit()

index = 2
for i in range(1, R + 1):
for j in range(1, C + 1):
A[i][j] = int(data[index])
row[A[i][j]] = i
col[A[i][j]] = j
index += 1

def Solve():
global nelems
selected[A[1][1]] = 1
nelems = 1
elems[1] = A[1][1]

if R == 1 and C == 1:
return

selected[A[R][C]] = 1
nelems += 1
elems[nelems] = A[R][C]

for i in range(1, R * C + 1):
if selected[i]:
continue

li, ls, before = 1, nelems, 0

while li <= ls:
mid = (li + ls) // 2
if row[elems[mid]] <= row[i] and col[elems[mid]] <= col[i]:
before = mid
li = mid + 1
else:
ls = mid - 1

if before == 0:
continue

if row[i] <= row[elems[before + 1]] and col[i] <= col[elems[before + 1]]:
for j in range(nelems, before, -1):
elems[j + 1] = elems[j]
elems[before + 1] = i
nelems += 1
selected[i] = 1

if nelems != R + C - 1:
with open("bemoOUT.txt", "w") as f:
f.write("Not enough elements selected!\n")
sys.exit()

def WriteOutput():
with open("bemoOUT.txt", "w") as f:
for i in range(1, nelems + 1):
f.write(f"{elems[i]}")
if i < nelems:
f.write(" ")
f.write("\n")

def main():
ReadInput()
Solve()
WriteOutput()

if __name__ == "__main__":
main()

</syntaxhighlight>

1115 - Avarcolaci

2024-05-18T07:45:45Z

Oros Ioana Diana:

Un vârcolac bântuie ulițele satului Bosston, semănând panică printre săteni. Satul Bosston este compus din <code>2*N</code> săteni, fiecare dintre aceștia fiind rudă cu exact un vârcolac. Vârcolacii sunt codificați cu numere naturale. Pentru a afla care este vârcolacul care le cauzează probleme, aceștia s-au dus la vraciul local. Acesta a spus că, dacă există un vârcolac <code>V</code> astfel încât oricum s-ar împărți cei <code>2*N</code> săteni în două grupuri de <code>N</code> săteni, există cel puțin un sătean în primul grup și cel puțin un sătean în al doilea care să fie rude cu <code>V</code>, atunci vârcolacul <code>V</code> sigur este cel care bântuie satul. Dacă nu există un astfel de vârcolac, atunci sătenii nu își pot da seama cine le bântuie satul.

= Cerință =
Cunoscând <code>N</code> și indicii vârcolacilor cu care se înrudesc fiecare dintre cei <code>2*N</code> săteni, să se determine vârcolacul care bântuie satul, în cazul în care acesta există.

= Date de intrare =
Fișierul de intrare <code>avarcolaciIN.txt</code> conține pe prima linie numărul <code>T</code> de teste. Următoarele <code>2*T</code> linii conțin cele <code>T</code> teste. Prima linie dintr-un test conține numărul natural <code>N</code>, indicând faptul că avem <code>2*N</code> săteni în Bosston. Următoarea linie conține <code>2*N</code> elemente, al <code>i</code>-lea dintre aceste elemente reprezentând indicele vârcolacului cu care este rudă al <code>i</code>-lea sătean.

= Date de ieșire =
Fișierul de ieșire <code>avarcolaciOUt.txt</code> va conține <code>T</code> linii, câte una pentru fiecare test din fișierul de intrare. Dacă vârcolacul care bântuie satul nu poate fi determinat, atunci se va afișa textul ”Mozart” (fără ghilimele). Dacă vârcolacul poate fi determinat, atunci se va afișă indicele acestuia. Î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 ≤ T ≤ 15</code>
* <code>1 ≤ N ≤ 500.000</code>
* Pentru 10% din teste se garantează că <code>N = 1</code>
* Pentru 20% din teste se garantează că <code>N < 10</code>
* Pentru 40% din teste se garantează că <code>N <= 500</code>
* Pentru 80% din teste se garantează că <code>N <= 50.000</code>
* Indicii vârcolacilor sunt numere întregi pozitive mai mici ca <code>109</code>
* Pentru 50% din teste indicii vârcolacilor sunt mai mici strict ca <code>32762</code>
* ATENȚIE! Satul conține <code>2*N</code> săteni!
* ATENȚIE la limita de memorie!
* ATENȚIE! În cazul în care sunt mai multe soluții pentru vârcolacul care bântuie satul, se acceptă oricare dintre ele.

= Exemplu 1: =
<code>avarcolaciIN.txt</code>
3
2
1 4 3 4
1
1 1
3
4 1 4 4 4 4
<code>avarcolaciOUT.txt</code>
Mozart
1
4

= Explicație =

# Dacă împărțim în grupuri vârcolacii asociați celor <code>4</code> săteni obținem <code>(1, 3) (4, 4)</code> și nu avem un vârcolac atât în primul grup, cât și în al doilea.
# Vârcolacul <code>1</code> bântuie satul.
# Vârcolacul <code>4</code> bântuie satul – nu putem împărți sătenii în două grupuri astfel încât <code>4</code> să nu fie în niciunul dintre ele.

== Exemplu 2: ==
<code>avarcolaciIN.txt</code>
16
2
1 4 3 4
1
1 1
3
4 1 4 4 4 4
<code>avarcolaciOUT.txt</code>
Datele nu corespund restrictiilor impuse
 
== Rezolvare ==
<syntaxhighlight lang="python" line="1">
def verifica_restrictii(nr_teste, n, el):
TMAX = 15
NMAX = 500000
EL_MAX = int(1e9)

if not (1 <= nr_teste <= TMAX):
return False
if not (1 <= n <= NMAX):
return False
if not (0 <= el <= EL_MAX):
return False

return True

def main():
with open("avarcolaciIN.txt", "rt") as f_in, open("avarcolaciOUt.txt", "wt") as f_out:
nr_teste = int(f_in.readline().strip())

if not verifica_restrictii(nr_teste, 1, 0):
f_out.write("Datele nu corespund restrictiilor impuse\n")
return

potential = [0] * (nr_teste + 1)

for test in range(1, nr_teste + 1):
n = int(f_in.readline().strip())
if not verifica_restrictii(1, n, 0):
f_out.write("Datele nu corespund restrictiilor impuse\n")
return

maj, cnt = -1, 0

elements = list(map(int, f_in.readline().split()))
if not all(verifica_restrictii(1, 1, el) for el in elements):
f_out.write("Datele nu corespund restrictiilor impuse\n")
return

for el in elements:
if maj == -1:
maj = el
cnt = 1
else:
if el == maj:
cnt += 1
else:
cnt -= 1
if cnt == 0:
maj = el
cnt = 1

potential[test] = maj

with open("avarcolaciIN.txt", "rt") as f_in:
nr_teste = int(f_in.readline().strip())

for test in range(1, nr_teste + 1):
n = int(f_in.readline().strip())
elements = list(map(int, f_in.readline().split()))

cnt = 0
for x in elements:
if x == potential[test]:
cnt += 1

with open("avarcolaciOUt.txt", "a") as f_out:
if cnt > n:
f_out.write(f"{potential[test]}\n")
else:
f_out.write("Mozart\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

1117 - Volum

2024-05-18T07:39:03Z

Oros Ioana Diana:

K.L. 2.0 și-a dorit o piscină pe un grid <code>A</code> cu <code>N</code> linii și <code>M</code> coloane. Cum K.L. 2.0 nu a fost foarte inspirat, el a uitat să își niveleze terenul înainte de a construi piscina, astfel încât fiecare celulă de coordonate <code>(i, j)</code> a gridului are o înalțime <code>Ai,j</code> (<code>1 ≤ i ≤ N</code> și <code>1 ≤ j ≤ M</code>). La un moment dat începe o ploaie puternică, care umple piscina cu apă. După terminarea ploii, K.L. 2.0 se întreabă câtă apă are în piscină.

Dintr-o celulă apa se varsă în celulele vecine cu care are o latură comună şi care au înălţimea strict mai mică decât celula curentă. Apa de pe marginea piscinei se scurge în exterior.

= Cerință =
Pentru <code>N</code>, <code>M</code> și gridul <code>A</code> date, să se determine volumul de apă care a rămas în piscină.

= Date de intrare =
Fișierul de intrare <code>volumIN.txt</code> conține pe prima linie două numere naturale <code>N</code> și <code>M</code>, reprezentând dimensiunile grid-ului, iar pe fiecare dintre următoarele <code>N</code> linii se află câte <code>M</code> numere, reprezentând înălțimile terenului, separate prin câte un spațiu.

= Date de ieșire =
Fișierul de ieșire <code>volumOUT.txt</code> va conține un singur număr, reprezentând volumul de apă care a rămas în piscină. Î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>3 ≤ N, M ≤ 752</code>
* <code>0 ≤ Ai,j ≤ 109 + 2</code>
* Pentru 30% din punctaj, <code>3 ≤ N, M ≤ 82</code>.
* Pentru 40% din punctaj, <code>0 ≤ Ai,j ≤ 103 + 2</code>.
* Volumul apei este suma unităţilor de apă care rămâne în celulele piscinei.

= Exemplul 1: =
<code>volum.in</code>
3 3
2 2 2
2 0 2
2 2 2
<code>volum.out</code>
2

= Explicație =
După ploaie rămân două unități de apă în celula cu înălțimea <code>0</code>. Nu pot rămâne <code>3</code> unități, deoarece o unitate s-ar scurge prin una din cele 4 celule vecine în exteriorul piscinei.

= Exemplul 2: =
<code>volumIN.txt</code>
3 3
3 3 3
3 0 2
3 3 3
<code>volumOUT.txt</code>
2

= Explicație =
După ploaie rămân două unități de apă în celula cu înălțimea <code>0</code>. Nu pot rămâne <code>3</code> unități, deoarece o unitate s-ar scurge prin celula vecină cu valoarea <code>2</code> în exteriorul piscinei.

== Exemplul 3: ==
<code>volumIN.txt</code>
1 3
3 3 3
3 0 2
3 3 3
<code>volumOUT.txt</code>
Datele nu corespund restrictiilor impuse

= Exemplul 4: =
<code>volumIN.txt</code>
5 5
2 2 3 3 3
2 2 3 1 3
2 3 1 3 3
2 2 3 2 2
2 2 2 2 2
<code>volumOUT.txt</code>
4

= Explicație =
După ploaie rămân câte două unități de apă în celulele cu înălțimea <code>1</code>. Nu pot rămâne câte <code>3</code> unități. De exemplu, din celula <code>(2,4)</code> apa se poate scurge în celula <code>(2,5)</code> şi apoi în exterior, respectiv din celula <code>(3,3)</code> în şirul de celule <code>(4,3) - (5,3)</code> şi apoi în exterior.

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

maxn = 755
n, m = 0, 0
v = [[0] * maxn for _ in range(maxn)]
f = [[0] * maxn for _ in range(maxn)]
sol = 0
hp = []
d1 = [0, 0, -1, 1]
d2 = [1, -1, 0, 0]

def add_element(x, y, h):
global sol
if x <= 0 or y <= 0 or x > n or y > m:
return
if f[x][y] == 1:
return

if h < v[x][y]:
h = v[x][y]
sol += h - v[x][y]

heapq.heappush(hp, (h, x, y))
f[x][y] = 1

def check_constraints():
if not (3 <= n <= 752 and 3 <= m <= 752):
return False
for i in range(1, n + 1):
for j in range(1, m + 1):
if not (0 <= v[i][j] <= 10**9 + 2):
return False
return True

def main():
global n, m, sol

with open("volumIN.txt", "r") as fin:
n, m = map(int, fin.readline().split())
for i in range(1, n + 1):
v[i][1:m + 1] = map(int, fin.readline().split())

if not check_constraints():
with open("volumOUT.txt", "w") as fout:
fout.write("Datele nu corespund restrictiilor impuse\n")
return

for i in range(1, n + 1):
add_element(i, 1, v[i][1])
add_element(i, m, v[i][m])
for j in range(1, m + 1):
add_element(1, j, v[1][j])
add_element(n, j, v[n][j])

while len(hp) > 0:
hc, xc, yc = heapq.heappop(hp)

for i in range(4):
add_element(xc + d1[i], yc + d2[i], hc)

with open("volumOUT.txt", "w") as fout:
fout.write(f"{sol}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

1042 - Subsecvente

2024-05-18T07:20:48Z

Oros Ioana Diana:

Fie <code>n</code> un număr natural și <code>M={S1,S2,…,Sn}</code> o mulțime de șiruri de caractere nevide. Fie <code>Sk</code> un șir de caractere din <code>M</code>. Atunci, orice caracter al lui <code>Sk</code> aparține mulțimii <code>{'a','b'}</code>. Notăm prin <code>|Sk|</code> numărul caracterelor șirului <code>Sk</code> sau, echivalent, lungimea sa. O subsecvență <code>Sk[i:j]</code> a lui <code>Sk</code> este formată din caracterele situate pe pozițiile consecutive <code>i, i+1, .., j</code>. Astfel, dacă <code>Sk = 'abbbaababa'</code>, atunci <code>Sk[3:6] = 'bbaa'</code> sau subsecvența evidențiată: <code>'abbbaababa'</code>.

= Cerința =
Fiind dată o mulțime <code>M</code>, se cere să se determine lungimea maximă a unei subsecvențe care se găsește în toate șirurile din <code>M</code>.

= Date de intrare =
Fișierul de intrare <code>subsecventeIN.txt</code> conține pe prima linie un număr natural <code>n</code> egal cu cardinalul mulțimii <code>M</code>. Pe fiecare din următoarele <code>n</code> linii se găsește câte un șir din mulțimea <code>M</code>.

= Date de ieșire =
Fișierul de ieșire <code>subsecventeOUT.txt</code> va conține pe prima linie un singur număr natural egal cu lungimea subsecvenței găsite. Î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 < 5</code>
* Dacă <code>|S| = |S1| + |S2| + … + |Sn|</code>, atunci <code>|S| < 50 001</code>
* Se garantează că va exista întotdeauna soluție
* Se garantează că rezultatul nu va depăși <code>60</code>
* Pentru <code>30%</code> din teste: <code>|S| < 101</code>
* Pentru <code>55%</code> din teste: <code>|S| < 3 501</code>
* Pentru <code>80%</code> din teste: <code>|S| < 10 001</code>

= Exemplu 1: =
<code>subsecventeIN.txt</code>
4
abbabaaaaabb
aaaababab
bbbbaaaab
aaaaaaabaaab
<code>subsecventeOUT.txt</code>
5

= Explicație =
Lungimea unei subsecvenţe comune de lungime maximă este <code>5</code>.

În exemplu subsecvența comună de lungime <code>5</code> este <code>aaaab</code>:

<code>abbabaaaaabb</code>, <code>aaaababab</code>, <code>bbbbaaaab</code>, <code>aaaaaaabaaab</code>.
:

== Exemplu 2: ==
<code>subsecventeIN.txt</code>
7
abbabaaaaabb
aaaababab
bbbbaaaab
aaaaaaabaaab
<code>subsecventeOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
import sys

# Definim constantele
NODES = 2600100

# Inițializăm variabilele
p2, lg, mask, i, j, k, p, q, n = 0, 0, 0, 0, 0, 0, 0, 0, 0
s = [[0] * NODES for _ in range(2)]
cod = [0] * NODES
a = [""] * 50010

def sol(nod):
if not nod or cod[nod] != mask:
return 0
sa = sol(s[0][nod])
sb = sol(s[1][nod])
return max(sa, sb) + 1

def main():
global p2, lg, mask, i, j, k, p, q, n
# Citim datele de intrare
with open("subsecventeIN.txt", "r") as infile:
data = infile.read().strip().split()

n = int(data[0])
sequences = data[1:]

# Verificăm restricțiile
if not (1 < n < 5) or sum(len(seq) for seq in sequences) >= 50001:
with open("subsecventeOUT.txt", "w") as outfile:
outfile.write("Datele nu corespund restrictiilor impuse\n")
return

p2 = 1
n = 1
mask = 0
for sequence in sequences:
lg = len(sequence)
mask |= p2
for i in range(1, lg + 1):
j = min(i + 59, lg)
p = 1
for k in range(i, j + 1):
q = ord(sequence[k-1]) - ord('a')
if not s[q][p]:
s[q][p] = n + 1
n += 1
p = s[q][p]
cod[p] |= p2
p2 <<= 1

cod[1] = mask
result = sol(1) - 1
with open("subsecventeOUT.txt", "w") as outfile:
outfile.write(f"{result}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

0739 - Cuburi 1

2024-05-18T07:13:50Z

Oros Ioana Diana:

= Cerința =
Fie <code>n</code> cuburi de aceeaşi mărime, cu feţe colorate. Culorile sunt codificate prin câte o literă de la <code>A</code> la <code>M</code>. Pentru fiecare cub se cunosc culorile feţelor în ordinea: bază, capac, faţă frontală, faţă laterală dreapta, faţa din spate, faţă laterală stânga. Să se determine numărul maxim de cuburi care, răsturnate şi rotite convenabil, pot fi puse unul peste altul astfel încât să formeze un turn cu toate feţele uniform colorate (fiecare faţă a turnului sa fie de aceeaşi culoare, de la primul, până la ultimul cub al turnului).

= Date de intrare =
Fișierul de intrare <code>cuburi1IN.txt</code> conține pe prima linie numărul de cuburi <code>n</code>, iar pe a următoarele <code>n</code> linii culorile fețelor celor <code>n</code> cuburi.

= Date de ieșire =
Fișierul de ieșire <code>cuburi1OUt.txt</code> va conține pe prima linie un singur număr ce reprezintă numărul maxim de cuburi care, răsturnate şi rotite convenabil, pot fi puse unul peste altul astfel încât să formeze un turn cu feţele uniform colorate. Î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 ≤ 50000</code>
* cuburile ce formează un turn sunt aşezate numai unul peste celalalt, nu şi unul lângă celălalt;
* culorile fetelor unui cub se pot repeta pentru două sau mai multe dintre cele 6 feţe ale sale;
* orice cub poate fi rotit sau răsturnat pentru a fi adus într-o poziţie convenabilă;
* culorile fetelor cuburilor care nu formează feţele laterale ale turnului nu au nici o importanţă;
* culorile fețelor sunt litere mari din mulțimea <code>{A,B,...,M}</code>

= Exemplu 1: =
<code>cuburi1IN.txt</code>
3
ACADEB
FBCDAE
AEDCBB
<code>cuburi1OUt.txt</code>
2

= Exemplu 2: =
<code>cuburi1IN.txt</code>
3000000000
ACADEB
FBCDAE
AEDCBB
<code>cuburi1OUt.txt</code>
Datele nu corespund restrictiilor impuse

= Explicație =
Primul cub poate fi păstrat în poziţia sa, având feţele laterale <code>A</code>, <code>D</code>, <code>E</code>, <code>B</code> (frontal, lateral-dreapta, spate, lateral-stânga), iar al treilea cub poate fi răsturnat astfel încât să aibă capacele <code>B</code> şi <code>C</code>, şi rotit astfel încât să aibă feţele laterale să fie tot <code>A</code>, <code>D</code>, <code>E</code>, <code>B</code>.Rezolvare

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

def f(a, b, c, d, i, v, verif):
if c < a:
a, c = c, a
if d < b:
b, d = d, b
if b < a or (b == a and d < c):
a, b = b, a
c, d = d, c
rez = a + b + c + d
if verif[rez] != i:
verif[rez] = i
v[rez] += 1
return v[rez]
verif[rez] = i
return 0

def main():
try:
with open("cuburi1IN.txt", "r") as infile:
n = int(infile.readline().strip())
if not (0 <= n <= 50000):
raise ValueError

v = defaultdict(int)
verif = defaultdict(int)
mx = 0

for i in range(1, n + 1):
c = infile.readline().strip()
if len(c) != 6 or not all('A' <= char <= 'M' for char in c):
raise ValueError

mx = max(mx, f(c[2], c[3], c[4], c[5], i, v, verif))
mx = max(mx, f(c[0], c[3], c[1], c[5], i, v, verif))
mx = max(mx, f(c[0], c[2], c[1], c[4], i, v, verif))

with open("cuburi1OUT.txt", "w") as outfile:
outfile.write(str(mx))

except ValueError:
with open("cuburi1OUT.txt", "w") as outfile:
outfile.write("Datele nu corespund restrictiilor impuse")

if __name__ == "__main__":
main()

</syntaxhighlight>

0707 - Sum K

2024-05-18T07:08:26Z

Oros Ioana Diana:

<code>sumk</code> este un joc de perspicacitate, cu <code>N</code> stagii numerotate de la <code>1</code> la <code>N</code>. Un joc se termină cu succes dacă jucătorul a parcurs în ordine, de la <code>1</code> la <code>N</code>, toate cele <code>N</code> stagii ale jocului şi în fiecare stagiu a obţinut exact <code>K</code> puncte. Fiecare stagiu are <code>N</code> niveluri, numerotate de asemenea de la <code>1</code> la <code>N</code>. Jucătorul are posibilitatea să câştige <code>0</code>, <code>1</code>, …, <code>K</code> puncte pe oricare nivel al stagiului curent.

Dacă jucătorul se găseşte în stagiul <code>i</code> pe nivelul <code>j</code> și numărul total de puncte obţinute până în acel moment în acest stagiu este mai mic decât <code>K</code>, el va trece în mod obligatoriu pe nivelul <code>j+1</code> al stagiului <code>i</code>. Dacă jucătorul primește cel puţin un punct pe nivelul <code>j</code> și astfel punctajul său în stagiul <code>i</code> devine exact <code>K</code>, atunci jucătorul trece în mod automat pe nivelul <code>j</code> al stagiului <code>i+1</code> sau termină jocul cu succes dacă <code>i=N</code>.

= Cerința =
Cunoscând numărul <code>N</code> de stagii ale jocului şi numărul <code>K</code> de puncte care trebuie să fie obţinute în fiecare stagiu, să se determine numărul de posibilităţi modulo <code>578537</code> pentru ca jocul să se termine cu succes.

= Date de intrare =
Fișierul de intrare <code>sumkIN.txt</code> conține pe prima linie două numere naturale <code>N K</code> cu semnificația descrisă anterior.

= Date de ieșire =
Fișierul de ieșire <code>sumkOUT.txt</code> va conține pe prima linie un singur număr natural <code>P</code> reprezentând numărul total de posibilităţi modulo <code>578537</code> pentru ca jocul să se termine cu succes. Î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 ≤ K ≤ N ≤ 500</code>
* Fie <code>x</code> punctajul final într-un stagiu oarecare. Atunci dacă <code>x ≠ K</code>, jocul se termină cu eșec.
* Pentru <code>20%</code> din teste, <code>K ≤ N ≤ 10</code>, iar pentru <code>30%</code> din teste, <code>K≤N≤100</code>

= Exemplu 1: =
<code>sumkIN.txt</code>
2 2
<code>sumkOUT.txt</code>
5

= Exemplu 2: =
<code>sumkIN.txt</code>
2 3
<code>sumkOUT.txt</code>
Datele nu corespund restrictiilor impuse.

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
def calcul(z1, z2, n, a):
x = [0] * 502
for j in range(1, n + 1):
s = 0
for i in range(1, j + 1):
t = z1[i]
t = (t * z2[j - i + 1]) % a
s = (s + t) % a
x[j] = s
for j in range(1, n + 1):
z1[j] = x[j]

def main():
try:
with open("sumkIN.txt", "rt") as fin:
n, k = map(int, fin.readline().split())
except Exception as e:
with open("sumkOUT.txt", "wt") as fout:
fout.write("Eroare la citirea datelor de intrare.")
return

if not (1 <= k <= n <= 500):
with open("sumkOUT.txt", "wt") as fout:
fout.write("Datele nu corespund restrictiilor impuse.")
return

r = [0] * 502
z = [0] * 502
r[1] = 1
a = 578537

for j in range(1, k + 1):
for i in range(2, n + 1):
r[i] = (r[i - 1] + r[i]) % a

v = n
z[1] = 1
while v != 0:
if v % 2 == 1:
calcul(z, r, n, a)
calcul(r, r, n, a)
v = v // 2

s = 0
for i in range(1, n + 1):
s = (s + z[i]) % a

with open("sumkOUT.txt", "wt") as fout:
fout.write(f"{int(s)}")

if __name__ == "__main__":
main()

</syntaxhighlight>