Bitnami MediaWiki - User contributions [en]

1489 - Bile1

2024-06-04T09:07:13Z

Danciu: Pagină nouă: Algorel a primit un set de <code>n</code> bile numerotate de la <code>1</code> la <code>n</code> pe care trebuie să le pună în trei cutii identice astfel încât în nicio cutie să nu fie două bile numerotate cu numere consecutive. = Cerința = În câte moduri poate face Algorel acest lucru? = Date de intrare = Fișierul de intrare <code>bile1.in</code> conține pe prima linie numărul <code>n</code>. = Date de ieșire = Fișierul de ieșire <code>bile1.out</code> v...

Algorel a primit un set de <code>n</code> bile numerotate de la <code>1</code> la <code>n</code> pe care trebuie să le pună în trei cutii identice astfel încât în nicio cutie să nu fie două bile numerotate cu numere consecutive.

= Cerința =
În câte moduri poate face Algorel acest lucru?

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

= Date de ieșire =
Fișierul de ieșire <code>bile1.out</code> va conține pe prima linie numărul de moduri de distribuire a bilelor.

= Restricții și precizări =

* <code>n ≤ 300</code>

= Exemplu: =
<code>bile1.in</code>
4
<code>bile1.out</code>
24

== Rezolvare ==
<syntaxhighlight lang="python3">
MOD = 1000000007

def count_ball_distributions(n):
dp = [[0 for _ in range(4)] for _ in range(n + 1)]

for i in range(1, n + 1):
dp[i][1] = 3

for i in range(2, n + 1):
for j in range(1, 4):
dp[i][j] = 0

if j < 3:
dp[i][j] += dp[i - 1][j - 1] * 3
dp[i][j] += dp[i - 2][1] * 3

if j <= dp[i - 1][0]:
dp[i][j] += dp[i - 1][j - 1]

return dp[n][1] % MOD

def main():
with open("bile1.in", "r") as input_file:
n = int(input_file.readline())

ball_distributions_count = count_ball_distributions(n)

with open("bile1.out", "w") as output_file:
output_file.write(str(ball_distributions_count))

if __name__ == "__main__":
main()

</syntaxhighlight>

3090 - divizori5

2024-06-04T09:04:49Z

Danciu: Pagină nouă: Fie <code>D</code>, <code>K</code> și <code>P</code> trei numere naturale. == Cerința == Să se determine numărul de numere naturale, notat cu <code>T</code>, având următoarele proprietăți: * au exact <code>D</code> divizori; * descompunerea în factori primi a acestor numere conține exact <code>K</code> numere prime; * toți factorii primi din descompunerea numerelor sunt mici sau egali cu <code>P</code>. == Date de intrare == Fișierul de intrare <code>divizori.i...

Fie <code>D</code>, <code>K</code> și <code>P</code> trei numere naturale.

== Cerința ==
Să se determine numărul de numere naturale, notat cu <code>T</code>, având următoarele proprietăți:

* au exact <code>D</code> divizori;
* descompunerea în factori primi a acestor numere conține exact <code>K</code> numere prime;
* toți factorii primi din descompunerea numerelor sunt mici sau egali cu <code>P</code>.

== Date de intrare ==
Fișierul de intrare <code>divizori.in</code> conține pe primul rând numerele <code>D</code>, <code>K</code> și <code>P</code> cu semnificația de mai sus, despărțite prin câte un spațiu.

== Date de iesire ==
Fișierul de ieșire <code>divizori.out</code> va conține pe primul rând restul împărțirii numărului <code>T</code> la <code>3000017</code>

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

* <code>2 ≤ D ≤ 1014</code>
* <code>1 ≤ K ≤ 100</code>
* <code>2 ≤ P ≤ 1.000.000</code>

= Exemplul 1: =
<code>divizori.in</code>
6 2 5
<code>divizori.out</code>
6

=== Explicație ===
<code>D = 6</code>, <code>K = 2</code>, <code>P = 5</code>. Sunt <code>T = 6</code> numere cu exact <code>6</code> divizori ce conțin în descompunerea în factori primi exact două numere prime mai mici sau egale decât <code>5</code>: <code>2132</code>, <code>2152</code>, <code>2231</code>, <code>2251</code>, <code>3152</code>, <code>3251</code>.

= Exemplul 2: =
<code>divizori.in</code>
18 3 10
<code>divizori.out</code>
12

= Exemplul 3: =
<code>divizori.in</code>
10 8 17
<code>divizori.out</code>
0

=== Explicație ===
<code>D = 10</code>, <code>K = 8</code>, <code>P = 17</code>. Nu există numere cu exact <code>10</code> divizori ce conțin în descompunerea în factori primi exact <code>8</code> numere prime mai mici sau egale cu <code>17</code> deoarece sunt doar <code>7</code> numere prime mai mici sau egale decât <code>17</code>.

== Rezolvare ==
<syntaxhighlight lang="python3">
MOD = 3000017

def count_numbers_with_properties(d, k, p):
dp = [[0 for _ in range(k + 1)] for _ in range(d + 1)]

for i in range(k + 1):
for j in range(1, d + 1):
if j == 1:
dp[j][i] = 1

for i in range(2, d + 1):
for j in range(1, k + 1):
dp[i][j] = 0

for num_divisors in range(1, i):
if j >= 2:
dp[i][j] += dp[num_divisors][j - 1] * dp[i - num_divisors][j]
else:
# If j = 1, all prime factors must be distinct
if num_divisors == 1:
dp[i][j] += dp[num_divisors][j]

total_numbers = 0
for i in range(1, d + 1):
for j in range(1, k + 1):
# Limit prime factors to 'p'
if max_prime_factor_up_to_p(dp[i][j], p) == dp[i][j]:
total_numbers += dp[i][j]

return total_numbers % MOD

def max_prime_factor_up_to_p(n, p):
max_prime_factor = 1
while n % 2 == 0:
n //= 2
max_prime_factor = 2

for i in range(3, int(p ** 0.5) + 1, 2):
while n % i == 0:
n //= i
max_prime_factor = i

if n > 1:
max_prime_factor = n

return max_prime_factor

def main():
with open("divizori.in", "r") as input_file:
d, k, p = map(int, input_file.readline().split())

number_count = count_numbers_with_properties(d, k, p)

with open("divizori.out", "w") as output_file:
output_file.write(str(number_count))

if __name__ == "__main__":
main()

</syntaxhighlight>

2000 - Sir9

2024-06-04T09:01:08Z

Danciu: Pagină nouă: Corneluș a învățat să numere. El pornește întotdeauna de la <code>1</code>, numără din <code>1</code> în <code>1</code>, nu greșește niciodată numărul următor, însă ezită uneori și atunci spune numărul curent de mai multe ori. Sora lui, Corina, îl urmărește și face tot felul de calcule asupra modurilor în care numără fratele ei. Astfel, ea urmărește până la cât numără (<code>U</code>), câte numere spune în total (<code>N</code>) și, pentru...

Corneluș a învățat să numere. El pornește întotdeauna de la <code>1</code>, numără din <code>1</code> în <code>1</code>, nu greșește niciodată numărul următor, însă ezită uneori și atunci spune numărul curent de mai multe ori. Sora lui, Corina, îl urmărește și face tot felul de calcule asupra modurilor în care numără fratele ei. Astfel, ea urmărește până la cât numără (<code>U</code>), câte numere spune în total (<code>N</code>) și, pentru a aprecia cât de ezitant este, numărul maxim de repetări (<code>R</code>) ale unei valori. De exemplu, el poate număra până la <code>8</code> astfel: <code>1 2 3 3 4 5 6 7 7 7 7 8 8</code>. În acest caz, numără până la <code>8</code> (<code>U=8</code>), spune <code>13</code> numere (<code>N=13</code>) și ezită cel mai mult la <code>7</code>, spunându‑l de <code>4</code> ori (<code>R=4</code>).

= Cerințe =
1) Cunoscând numărul total de numere <code>N</code> și ultimul număr spus <code>U</code>, trebuie să calculați câte șiruri diferite au exact <code>N</code> numere și se termină cu numărul <code>U</code>.

2) Cunoscând numărul total de numere <code>N</code> și numărul maxim de repetări <code>R</code> ale unei valori, trebuie să calculați câte șiruri diferite au exact <code>N</code> numere și fiecare valoare se repetă de cel mult <code>R</code> ori.

Deoarece numărul de șiruri poate fi foarte mare, calculați restul împărțirii acestui număr la <code>20173333</code>.

= Date de intrare =
Din fișierul <code>sir9.in</code> se citesc trei numere naturale, <code>P</code>, <code>N</code> și <code>X</code>, scrise în această ordine, cu câte un spațiu între ele. <code>P</code> poate avea una dintre valorile <code>1</code> sau <code>2</code>, iar <code>N</code> este numărul de numere din șir. Când <code>P</code> are valoarea <code>1</code>, numărul <code>X</code> reprezintă ultimul număr spus (<code>U</code>), iar când <code>P</code> are valoarea <code>2</code>, <code>X</code> reprezintă numărul maxim de repetări ale unei valori (<code>R</code>).

= Date de ieșire =
În fișierul <code>sir9.out</code> se scrie o singură valoare, astfel:

* dacă <code>P</code> a avut valoarea <code>1</code>, valoarea reprezintă numărul de șiruri distincte care au exact <code>N</code> numere și se termină cu numărul <code>X</code>;
* dacă <code>P</code> a avut valoarea <code>2</code>, valoarea reprezintă numărul de șiruri distincte care au exact <code>N</code> numere și fiecare număr se repetă de cel mult <code>X</code> ori.

În ambele cazuri, deoarece numărul rezultat poate fi foarte mare, se va scrie restul împărțirii acestui număr la <code>20173333</code>.

= Restricții și precizări =

* <code>1 ≤ N ≤ 100.000</code>
* <code>X ≤ N</code>
* testele cu <code>P=1</code> vor totaliza 50% din punctaj, restul de 50% din punctaj fiind pentru <code>P=2</code>;
* pentru teste cumulând 50 de puncte valoarea lui <code>N</code> nu depășește <code>1000</code>;
* Ultima valoare spusă poate să apară de mai multe ori.

= Exemplul 1 =
<code>sir9.in</code>
1 5 3
<code>sir9.out</code>
6

=== Explicație ===
Se rezolvă cerința 1. Pentru <code>N=5</code>, <code>X=3</code>, sunt <code>6</code> șiruri care au exact <code>N</code> numere și se termină cu <code>3</code>: <code>1 1 1 2 3</code>, <code>1 1 2 2 3</code>, <code>1 1 2 3 3</code>, <code>1 2 2 2 3</code>, <code>1 2 2 3 3</code>, <code>1 2 3 3 3</code>.

= Exemplul 2 =
<code>sir9.in</code>
2 5 2
<code>sir9.out</code>
8

=== Explicație ===
Se rezolvă cerința 2. Pentru <code>N=5</code>, <code>X=2</code>, sunt <code>8</code> șiruri care au exact <code>N</code> numere și fiecare număr se repetă de cel mult <code>2</code> ori: <code>1 1 2 2 3</code>, <code>1 1 2 3 3</code>, <code>1 1 2 3 4</code>, <code>1 2 2 3 3</code>, <code>1 2 2 3 4</code>, <code>1 2 3 3 4</code>, <code>1 2 3 4 4</code>, <code>1 2 3 4 5</code>.

= Exemplul 3 =
<code>sir9.in</code>
2 10 3
<code>sir9.out</code>
274

=== Explicație ===
Se rezolvă cerința 2. Pentru <code>N=10</code>, <code>X=3</code>, sunt <code>274</code> de șiruri care au exact <code>10</code> numere și fiecare număr se repetă de cel mult <code>3</code> ori.

== Rezolvare ==
<syntaxhighlight lang="python3">
MOD = 20173333

def count_sequences_ending_with_u(n, u):
dp = [[0 for _ in range(u + 1)] for _ in range(n + 1)]

for i in range(u + 1):
dp[0][i] = 1

for i in range(1, n + 1):
for j in range(u + 1):
dp[i][j] = 0

for k in range(1, j):
if j >= k:
dp[i][j] += dp[i - 1][j - k]
if j >= 2:
dp[i][j] += dp[i - 1][j - 2]

return dp[n][u] % MOD

def count_sequences_with_max_repeats_r(n, r):
dp = [[0 for _ in range(r + 1)] for _ in range(n + 1)]

for i in range(r + 1):
dp[0][i] = 1

for i in range(1, n + 1):
for j in range(r + 1):
dp[i][j] = 0

for k in range(1, j):
if j >= k:
dp[i][j] += dp[i - 1][j]
if j >= 2:
dp[i][j] += dp[i - 1][j - 1]

return dp[n][r] % MOD

def main():
with open("sir9.in", "r") as input_file:
p, n, x = map(int, input_file.readline().split())

if p == 1:
sequences_count = count_sequences_ending_with_u(n, x)
else:
sequences_count = count_sequences_with_max_repeats_r(n, x)

with open("sir9.out", "w") as output_file:
output_file.write(str(sequences_count))

if __name__ == "__main__":
main()

</syntaxhighlight>

3691 - crescator2

2024-06-04T08:58:38Z

Danciu: Pagină nouă: Fie un șir <code>a</code> de <code>N</code> numere întregi. Trebuie construit un nou șir <code>b</code>(tot cu <code>N</code> elemente) astfel: * dacă , atunci * dacă , atunci poate avea orice valoare strict pozitivă * dacă , atunci poate avea orice valoare strict pozitivă cu excepția lui * Se garantează că și au valori strict pozitive și între oricare două valori strict pozitive se va afla cel mult una strict negativă. == Cerinta == Știindu-se și...

Fie un șir <code>a</code> de <code>N</code> numere întregi. Trebuie construit un nou șir <code>b</code>(tot cu <code>N</code> elemente) astfel:

* dacă , atunci
* dacă , atunci poate avea orice valoare strict pozitivă
* dacă , atunci poate avea orice valoare strict pozitivă cu excepția lui
*

Se garantează că și au valori strict pozitive și între oricare două valori strict pozitive se va afla cel mult una strict negativă.

== Cerinta ==
Știindu-se șirul <code>a</code>, să se calculeze numărul de moduri de a forma șirul <code>b</code> astfel încât acesta să fie crescător (nu neapărat strict). Deoarece acest număr poate fi foarte mare, se va afișa doar restul împărțirii la <code>1.000.000 007</code>.

== Date de intrare ==
Fișierul de intrare <code>crescator.in</code> conține pe prima linie un număr natural <code>N</code> și pe cea de-a doua <code>N</code> numere întregi separate prin câte un spațiu.

== Date de iesire ==
Fișierul de ieșire <code>crescator.out</code> conține pe singura sa linie numărul cerut modulo <code>1.000.000 007</code>

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

* <code>1 ≤ N ≤ 300.000</code>
*
* Pentru <code>35</code> de puncte, <code>1 ≤ N ≤ 1000</code> și
* Pentru alte <code>20</code> de puncte,

= Exemplu: =
<code>crescator.in</code>
6
1 0 3 0 -4 5
<code>crescator.out</code>
12

=== Explicație ===
Cele <code>12</code> șiruri crescătoare <code>b</code> sunt: <code>1 1 3 3 3 5</code>, <code>1 1 3 3 5 5</code>, <code>1 1 3 4 5 5</code>, <code>1 1 3 5 5 5</code>, <code>1 2 3 3 3 5</code>, <code>1 2 3 3 5 5</code>, <code>1 2 3 4 5 5</code>, <code>1 2 3 5 5 5</code>, <code>1 3 3 3 3 5</code>, <code>1 3 3 3 5 5</code>, <code>1 3 3 4 5 5</code>, <code>1 3 3 5 5 5</code>.

== Rezolvare ==
<syntaxhighlight lang="python3">
def sort_and_count_frequencies(numbers):
sorted_numbers = sorted(numbers)

element_counts = {}

for number in sorted_numbers:
if number in element_counts:
element_counts[number] += 1
else:
element_counts[number] = 1

return element_counts

def main():
numbers = list(map(int, input().split()))

element_counts = sort_and_count_frequencies(numbers)

for number, count in element_counts.items():
print(f"{number}: {count}")

if __name__ == "__main__":
main()

</syntaxhighlight>

1645 - Fibocel

2024-06-04T08:52:38Z

Danciu: Pagină nouă: Toată lumea ştie că Fibocel este pasionat de numere şi că vrea să iasă în evidenţă cu orice preţ. Într-o zi, el s-a decis să numească un număr ''fibocel'' (după numele lui) dacă numărul de biţi egali cu <code>1</code> din reprezentarea binară a numărului este un număr Fibonacci. Cum asta nu e de ajuns pentru el, Fibocel s-a decis să propună şi o problemă la concursul lui preferat de la Iaşi. = Cerința = Să se raspundă la <code>Q</code> întreb...

Toată lumea ştie că Fibocel este pasionat de numere şi că vrea să iasă în evidenţă cu orice preţ. Într-o zi, el s-a decis să numească un număr ''fibocel'' (după numele lui) dacă numărul de biţi egali cu <code>1</code> din reprezentarea binară a numărului este un număr Fibonacci.

Cum asta nu e de ajuns pentru el, Fibocel s-a decis să propună şi o problemă la concursul lui preferat de la Iaşi.

= Cerința =
Să se raspundă la <code>Q</code> întrebări de forma: Câte numere fibocel există în intervalul închis <code>[A, B]</code>?

= Date de intrare =
Fișierul de intrare <code>fibocel.in</code> conține pe prima linie numărul natural <code>Q</code>, iar pe următoarele <code>Q</code> linii se găsesc câte două numere naturale <code>A</code> şi <code>B</code> separate prin exact un spaţiu, reprezentând extremităţile intervalului la care se referă întrebarea.

= Date de ieșire =
Fișierul de ieșire <code>fibocel.out</code> va conține exact <code>Q</code> numere, câte unul pe o linie, reprezentând răspunsurile la cele <code>Q</code> întrebări, în ordinea în care ele apar în fişierul de intrare.

= Restricții și precizări =

* <code>1 ≤ Q ≤ 50.000</code>
* <code>1 ≤ A ≤ B ≤ 1015</code>
* Şirul Fibonacci se defineşte astfel: , pentru
* Pentru 40% din teste <code>B ≤ 1.000.000</code>

= Exemplul 1 =
<code>fibocel.in</code>
1
15 16
<code>fibocel.out</code>
1

=== Explicație ===
<code>15(10) =1111(2)</code> nu este fibocel (are <code>4</code> biţi de <code>1</code> iar <code>4</code> nu este număr Fibonacci)

<code>16(10) =10000(2)</code> este fibocel (are <code>1</code> bit de <code>1</code> iar <code>1</code> este număr Fibonacci)

= Exemplul 2 =
<code>fibocel.in</code>
7
1 13
13 31
13 131
31 131
131 313
313 1313
1313 3131
<code>fibocel.out</code>
13
14
76
63
97
421
667

== Rezolvare ==
<syntaxhighlight lang="python3">
def is_fibocel(n):
bit_count = 0
while n > 0:
if n % 2 == 1:
bit_count += 1
n //= 2

previous = 0
current = 1
while current <= bit_count:
if current == bit_count:
return True
previous, current = current, previous + current

return False

def count_fibocel_numbers(a, b):
count = 0
for num in range(a, b + 1):
if is_fibocel(num):
count += 1

return count

def main():
with open("fibocel.in", "r") as input_file:
q = int(input_file.readline())

with open("fibocel.out", "w") as output_file:
for _ in range(q):
a, b = map(int, input_file.readline().split())
fibocel_count = count_fibocel_numbers(a, b)
output_file.write(str(fibocel_count) + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

2181 - inversum

2024-06-04T08:49:01Z

Danciu: Pagină nouă: = Cerința = Fie o permutare <code>P</code> a mulțimii <code>{1, 2, 3, ... N}</code>. Se numește inversiune o pereche <code>(i, j), i < j</code> pentru care <code>P[i] > P[j]</code>. Fie funcția <code>M(N) = suma numărului de inversiuni a fiecărei permutare a numerelor {1, 2, 3, ... N}</code>. Pentru <code>N</code> dat, să se calculeze <code>M(N)</code> modulo <code>1000003</code>. = Date de intrare = Programul citește de la tastatură numărul <code>N</code>. = Dat...

= Cerința =
Fie o permutare <code>P</code> a mulțimii <code>{1, 2, 3, ... N}</code>. Se numește inversiune o pereche <code>(i, j), i < j</code> pentru care <code>P[i] > P[j]</code>. Fie funcția <code>M(N) = suma numărului de inversiuni a fiecărei permutare a numerelor {1, 2, 3, ... N}</code>. Pentru <code>N</code> dat, să se calculeze <code>M(N)</code> modulo <code>1000003</code>.

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

= Date de ieșire =
Programul va afișa pe ecran numărul <code>S</code>, reprezentând valoarea <code>M(N)</code> modulo <code>1000003</code>.

= Restricții și precizări =

* <code>1 ≤ N ≤ 1.000.000</code>

= Exemplu: =
Intrare
3
Ieșire
9

== Rezolvare ==
<syntaxhighlight lang="python3">
MOD = 1000003

def calculate_inversion_sum(n):
total_inversions = 0
factorial = 1

for i in range(1, n + 1):
factorial *= i

current_inversions = i * (n - i)

total_inversions += current_inversions

total_inversions %= MOD

return total_inversions

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

inversion_sum = calculate_inversion_sum(n)
print(inversion_sum)

if __name__ == "__main__":
main()

</syntaxhighlight>

0679 - calatorie

2024-06-04T08:47:23Z

Danciu: Pagină nouă: Dorești să mergi în vacanță și ai hotărât deja destinația. Formal, te afli în punctul <code>(0,0)</code> al unui sistem cartezian de axe și trebuie să ajungi în punctul de coordonate <code>(X,X)</code>. Țara în care te afli are drumuri paralele cu axele de coordonate la fiecare abscisă și la fiecare ordonată număr natural. În fiecare moment, dacă eşti în punctul de coordonate <code>(a,b)</code>, ai 2 variante de deplasare: în punctul <code>(a,b+1)</co...

Dorești să mergi în vacanță și ai hotărât deja destinația. Formal, te afli în punctul <code>(0,0)</code> al unui sistem cartezian de axe și trebuie să ajungi în punctul de coordonate <code>(X,X)</code>. Țara în care te afli are drumuri paralele cu axele de coordonate la fiecare abscisă și la fiecare ordonată număr natural. În fiecare moment, dacă eşti în punctul de coordonate <code>(a,b)</code>, ai 2 variante de deplasare: în punctul <code>(a,b+1)</code> sau în punctul <code>(a+1,b)</code>. La fiecare astfel de pas consumi un litru de carburant. Prin unele puncte de forma <code>(a,a)</code> nu poți trece, iar în celelalte puncte care au abscisa egală cu ordonata poți trece și în plus, acolo se află câte o stație de benzină unde poți să „faci plinul”. Prin toate punctele care nu au abscisa egală cu ordonata poți trece dar acolo nu se află stații de benzină. Rezervorul mașinii tale are o capacitate de <code>K</code> litri.

= Cerința =
Determinați numărul de trasee distincte prin care poți ajunge la destinație. Două trasee sunt distincte dacă diferă prin cel puţin un punct.

= Date de intrare =
Fișierul <code>calatorie.in</code> conține pe prima linie două numere separate printr-un spațiu, <code>X</code> și <code>K</code>, cu semnificația din enunț.

Pe linia a <code>2</code>-a se găsește un număr <code>N</code>, care reprezintă numărul de puncte de forma <code>(a,a)</code> care nu pot fi traversate. Pe fiecare dintre următoarele <code>N</code> linii se află câte un număr <code>a</code>, cu semnificația că punctul <code>(a,a)</code> nu poate fi vizitat.

= Date de ieșire =
Fișierul <code>calatorie.out</code> conține pe prima linie un singur număr natural reprezentând valoarea cerută, modulo <code>997</code>.

= Restricții și precizări =

* <code>1 ≤ X ≤ 50000</code>
* <code>2 ≤ K ≤ 50</code>
* <code>0 ≤ N ≤ 10</code>
* Călătoria începe cu rezervorul plin;
* Se garantează că există cel puțin un drum.

= Exemplu: =
Intrare
3 10
1
1
Ieșire
8

== Rezolvare ==
<syntaxhighlight lang="python3">
MOD = 997

def count_distinct_paths(x, k, blocked_points):
dp = [[0 for _ in range(x + 1)] for _ in range(x + 1)]

dp[0][0] = 1

for i in range(1, x + 1):
for j in range(1, x + 1):
if (i == j) and (j in blocked_points):
continue

if j <= i:
if dp[i - 1][j] > 0 and j + k >= i:
dp[i][j] += dp[i - 1][j]

if dp[i][j - 1] > 0:
dp[i][j] += dp[i][j - 1]

elif i <= j:
if dp[i + 1][j] > 0 and j - k >= i:
dp[i][j] += dp[i + 1][j]

if dp[i][j + 1] > 0:
dp[i][j] += dp[i][j + 1]

return dp[x][x] % MOD

def main():
with open("calatorie.in", "r") as input_file:
x, k = map(int, input_file.readline().split())
n = int(input_file.readline())
blocked_points = set()
for _ in range(n):
blocked_points.add(int(input_file.readline()))

distinct_paths = count_distinct_paths(x, k, blocked_points)

with open("calatorie.out", "w") as output_file:
output_file.write(str(distinct_paths))

if __name__ == "__main__":
main()

</syntaxhighlight>

1236 - Pastile

2024-06-04T08:44:27Z

Danciu: Pagină nouă: Manole este extrem de răcit. Din această cauză a mers la medicul de familie care l-a sfătuit urmeze un tratament cu <code>N</code> pastile, din care trebuie să ia în fiecare zi câte o jumătate. A cumpărat de la farmacie o cutie în care se aflau exact <code>N</code> pastile, fiecare dintre ele având pe suprafață o dungă care marchează jumătatea ei. Manole începe să își ia tratamentul și constată că poate proceda doar astfel: * scoate din cutie o pasti...

Manole este extrem de răcit. Din această cauză a mers la medicul de familie care l-a sfătuit urmeze un tratament cu <code>N</code> pastile, din care trebuie să ia în fiecare zi câte o jumătate. A cumpărat de la farmacie o cutie în care se aflau exact <code>N</code> pastile, fiecare dintre ele având pe suprafață o dungă care marchează jumătatea ei.

Manole începe să își ia tratamentul și constată că poate proceda doar astfel:

* scoate din cutie o pastilă întreagă din care folosește, în ziua respectivă, doar jumătate din ea, iar jumătatea rămasă o pune înapoi în cutie;
* scoate din cutie o jumătate de pastilă, rămasă din una din zilele anterioare, pe care o folosește în ziua respectivă.

= Cerința =
Scrieți un program care determină numărul de posibilități în care poate lua toate cele N pastile, procedând după procedeul descris mai sus.

= Date de intrare =
Fișierul de intrare <code>pastile.in</code> conține pe prima linie numărul natural <code>N</code>.

= Date de ieșire =
Fișierul de ieșire <code>pastile.out</code> va conține pe prima linie numărul determinat.

= Restricții și precizări =

* <code>1 ≤ N ≤ 50.000</code>

= Exemplu: =
<code>pastile.in</code>
3
<code>pastile.out</code>
5

=== Explicație ===
Dacă notăm cu <code>P</code> o pastilă întreagă și cu <code>J</code> o jumătate de pastilă atunci Manole avea <code>5</code> posibilități:

<code>P J P J P J</code>

<code>P P J J P J</code>

<code>P J P P J J</code>

<code>P P P J J J</code>

<code>P P J P J J</code>

== Rezolvare ==
<syntaxhighlight lang="python3">
def calculate_possibilities(n):
dp = [0] * (n + 1)
dp[1] = 1

for i in range(2, n + 1):

dp[i] = 2 * dp[i - 1]

return dp[n]

def main():
with open("pastile.in", "r") as input_file:
n = int(input_file.readline())

possibilities = calculate_possibilities(n)

with open("pastile.out", "w") as output_file:
output_file.write(str(possibilities))

if __name__ == "__main__":
main()

</syntaxhighlight>

0695 - SumAll

2024-06-04T08:42:34Z

Danciu: Pagină nouă: = Cerința = Fie <code>N</code> un număr natural format din cifre nenule. Să se determine suma tuturor numerelor distincte ce se pot forma cu toate cifrele numărului <code>N</code>. = Date de intrare = Fișierul de intrare <code>sumall.in</code> conține pe prima linie numărul <code>N</code>. = Date de ieșire = Fișierul de ieșire <code>sumall.out</code> va conţine pe prima linie suma tuturor numerelor distincte ce se pot forma cu toate cifrele numărului <code>N</...

= Cerința =
Fie <code>N</code> un număr natural format din cifre nenule.

Să se determine suma tuturor numerelor distincte ce se pot forma cu toate cifrele numărului <code>N</code>.

= Date de intrare =
Fișierul de intrare <code>sumall.in</code> conține pe prima linie numărul <code>N</code>.

= Date de ieșire =
Fișierul de ieșire <code>sumall.out</code> va conţine pe prima linie suma tuturor numerelor distincte ce se pot forma cu toate cifrele numărului <code>N</code>.

= Restricții și precizări =

* <code>0 < N < 1019</code>

= Exemplu: =
<code>sumall.in</code>
123
<code>sumall.out</code>
1332

= Explicație =
Toate numerele distincte ce se pot forma cu cifrele <code>1</code>, <code>2</code>, <code>3</code> sunt:

<code>123</code>, <code>132</code>, <code>213</code>, <code>231</code>, <code>312</code>, <code>321</code>.

<code>123 + 132 + 213 + 231 + 312 + 321 = 1332</code>

= Exemplu: =
<code>sumall.in</code>
788
<code>sumall.out</code>
2553

= Explicație =
Toate numerele distincte ce se pot forma cu cifrele <code>7</code>, <code>8</code>, <code>8</code> sunt:

<code>788</code>, <code>878</code>, <code>887</code>

<code>788 + 878 + 887 = 2553</code>

== Rezolvare ==
<syntaxhighlight lang="python3">
def generate_numbers(n, digits, used_digits, current_number, numbers):
if len(current_number) == len(digits):
numbers.append(int(current_number))
return

for digit in digits:
if digit not in used_digits:
used_digits[digit] = True

current_number += digit

generate_numbers(n, digits, used_digits, current_number, numbers)

current_number = current_number[:-1]

used_digits[digit] = False

def calculate_sum_of_distinct_numbers(n):
digits = [int(d) for d in str(n)]

numbers = [] # List to store distinct numbers
used_digits = {} # Dictionary to track used digits

generate_numbers(n, digits, used_digits, "", numbers)

numbers.sort()

sum_of_distinct_numbers = 0
for i in range(len(numbers)):
if i == 0 or numbers[i] != numbers[i - 1]:
sum_of_distinct_numbers += numbers[i]

return sum_of_distinct_numbers

def main():
with open("sumall.in", "r") as input_file:
n = int(input_file.readline())

sum_of_distinct_numbers = calculate_sum_of_distinct_numbers(n)

with open("sumall.out", "w") as output_file:
output_file.write(str(sum_of_distinct_numbers))

if __name__ == "__main__":
main()

</syntaxhighlight>

3249 - sumimp3

2024-06-04T08:40:15Z

Danciu: Pagină nouă: = Cerința = Se citește un număr natural <code>n</code>. Calculați și afișați câte din submulțimile mulțimii <code>{1, 2, ..., n}</code> sunt formate dintr-un număr impar de elemente. Datorită faptului că există foarte multe submulțimi, rezultatul trebuie calculat modulo <code>9001</code>. = Date de intrare = Programul citește de la tastatură numărul <code>n</code>. = Date de ieșire = Programul va afișa pe ecran numărul de submulțimi formate din număr...

= Cerința =
Se citește un număr natural <code>n</code>. Calculați și afișați câte din submulțimile mulțimii <code>{1, 2, ..., n}</code> sunt formate dintr-un număr impar de elemente. Datorită faptului că există foarte multe submulțimi, rezultatul trebuie calculat modulo <code>9001</code>.

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

= Date de ieșire =
Programul va afișa pe ecran numărul de submulțimi formate din număr impar de elemente, modulo <code>9001</code>.

= Restricții și precizări =

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

= Exemplu: =
Intrare
4
Ieșire
8

=== Explicație ===
Submulțimile mulțimii <code>{1, 2, ..., n}</code> care sunt formate dintr-un număr impar de elemente sunt <code>{1}</code>, <code>{1,2,3}</code>, <code>{1,2,4}</code>, <code>{1,3,4}</code>, <code>{2}</code>, <code>{2,3,4}</code>, <code>{3}</code>, <code>{4}</code>.

== Rezolvare ==
<syntaxhighlight lang="python3">
MOD = 9001

def count_odd_subsets(n):
dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]

dp[0][0] = 1
dp[i][0] = 0

for i in range(1, n + 1):
for j in range(i + 1):
if j == 0:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % MOD

odd_subsets = 0
for j in range(n + 1):
if j % 2 == 1:
odd_subsets += dp[n][j]

return odd_subsets % MOD

def main():
n = int(input())
odd_subsets_count = count_odd_subsets(n)
print(odd_subsets_count)

if __name__ == "__main__":
main()

</syntaxhighlight>

3248 - subimp2

2024-06-04T08:38:24Z

Danciu: Pagină nouă: = Cerința = Se citește un număr natural <code>n</code>. Calculați și afișați câte din submulțimile mulțimii <code>{1, 2, ..., n}</code> sunt formate dintr-un număr impar de elemente. = 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 de submulțimi formate din număr impar de elemente. = Restricții și precizări = * <code>1 ≤ n ≤ 60</code> = Exemplu: = Intrare 4 Ie...

= Cerința =
Se citește un număr natural <code>n</code>. Calculați și afișați câte din submulțimile mulțimii <code>{1, 2, ..., n}</code> sunt formate dintr-un număr impar de elemente.

= 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 de submulțimi formate din număr impar de elemente.

= Restricții și precizări =

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

= Exemplu: =
Intrare
4
Ieșire
8

=== Explicație ===
Submulțimile mulțimii <code>{1, 2, ..., n}</code> care sunt formate dintr-un număr impar de elemente sunt <code>{1}</code>, <code>{1,2,3}</code>, <code>{1,2,4}</code>, <code>{1,3,4}</code>, <code>{2}</code>, <code>{2,3,4}</code>, <code>{3}</code>, <code>{4}</code>.

== Rezolvare ==
<syntaxhighlight lang="python3">
def count_odd_subsets(n):
dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]

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

for i in range(1, n + 1):
for j in range(i + 1):
if j == 0:
dp[i][j] = dp[i - 1][j]

else:
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]

odd_subsets = 0
for j in range(n + 1):
if j % 2 == 1:
odd_subsets += dp[n][j]

return odd_subsets

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

odd_subsets_count = count_odd_subsets(n)
print(odd_subsets_count)

if __name__ == "__main__":
main()

</syntaxhighlight>

1012 - aranjare

2024-06-04T08:36:13Z

Danciu: Pagină nouă: = Cerința = Dorel tocmai a învățat la școală despre permutări. El a reținut faptul că <code>n</code> persoane pot fi aranjate pe <code>n</code> locuri în <code>n!</code> moduri, unde . Pentru a vă pune pe voi la încercare Dorel mai alege un număr <code>p</code> și vă întreabă în câte moduri putem aranja <code>n</code> persoane numerotate de la <code>1</code> la <code>n</code> pe <code>n</code> locuri, numerotate şi ele de la <code>1</code> la <code>n</cod...

= Cerința =
Dorel tocmai a învățat la școală despre permutări. El a reținut faptul că <code>n</code> persoane pot fi aranjate pe <code>n</code> locuri în <code>n!</code> moduri, unde . Pentru a vă pune pe voi la încercare Dorel mai alege un număr <code>p</code> și vă întreabă în câte moduri putem aranja <code>n</code> persoane numerotate de la <code>1</code> la <code>n</code> pe <code>n</code> locuri, numerotate şi ele de la <code>1</code> la <code>n</code>, astfel încât suma dintre numărul persoanei și numărul locului să fie divizibilă cu <code>p</code>?

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

= Date de ieșire =
Programul va afișa pe ecran numărul <code>m</code>, reprezentând numărul de moduri cerut. Deoarece acest număr ar putea fi foarte mare, rezultatul se va afișa modulo <code>100019</code>.

= Restricții și precizări =

* <code>1 ≤ p ≤ n ≤ 100.000</code>
* locurile și persoanele sunt numerotate de la <code>1</code> la <code>n</code>

= Exemplu: =
Intrare
8 4
Ieșire
16

= Explicație =
Avem <code>8</code> persoane și <code>8</code> locuri. Persoanele <code>1</code> și <code>5</code> se pot așeza pe locurile <code>3</code> și <code>7</code> în <code>2!</code> moduri, persoanele <code>2</code> și <code>6</code> pe locurile <code>2</code> și <code>6</code> în <code>2!</code> moduri, persoanele <code>3</code> și <code>7</code> pe locurile <code>1</code> și <code>5</code> în <code>2!</code> moduri, iar persoanele <code>4</code> și <code>8</code> pe locurile <code>4</code> și <code>8</code> în <code>2!</code> moduri. În total vom avea <code>2</code> <code>4 =16</code> moduri de aranjare.

== Rezolvare ==
<syntaxhighlight lang="python3">
MOD = 100019

def count_valid_arrangements(n, p):
total_arrangements = 0
dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]

dp[1][1] = 1

for i in range(2, n + 1):
for j in range(1, n + 1):
current_arrangements = 0

if (i + j) % p == 0:
current_arrangements += dp[i - 1][j]

if i != j:
current_arrangements += dp[i][j - 1]

dp[i][j] = current_arrangements

for j in range(1, n + 1):
total_arrangements += dp[n][j]

return total_arrangements % MOD

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

valid_arrangements = count_valid_arrangements(n, p)
print(valid_arrangements)

if __name__ == "__main__":
main()

</syntaxhighlight>

1011 - p3factoriale

2024-06-04T08:34:09Z

Danciu: Pagină nouă: = Cerința = Se dau <code>a</code>, <code>b</code>, <code>c</code> și <code>p</code> numere naturale, astfel încât <code>a ≥ b + c</code> și <code>p</code> număr prim. Să se afle dacă numărul este divizibil cu <code>p</code>, și să se afle exponentul lui <code>p</code> în descompunerea în factori primi a acestui număr. = Date de intrare = Programul citește de la tastatură numerele <code>a</code>, <code>b</code>, <code>c</code> și <code>p</code>, separate...

= Cerința =
Se dau <code>a</code>, <code>b</code>, <code>c</code> și <code>p</code> numere naturale, astfel încât <code>a ≥ b + c</code> și <code>p</code> număr prim. Să se afle dacă numărul este divizibil cu <code>p</code>, și să se afle exponentul lui <code>p</code> în descompunerea în factori primi a acestui număr.

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

= Date de ieșire =
Programul va afișa pe ecran numărul <code>e</code>, reprezentând exponentul lui <code>p</code> în descompunerea în factori primi a numărului natural . Dacă numărul nu este divizibil cu <code>p</code>, atunci se va afișa <code>0</code>.

= Restricții și precizări =

* <code>1 ≤ a , b , c ≤ 1.000.000.000</code>
* <code>a ≥ b + c</code>
* <code>2 ≤ p ≤ 1.000</code>

= Exemplu: =
Intrare
12 4 5 3
Ieșire
3

= Explicație =
Știm de la matematică faptul că numărul este natural, deci putem vorbi despre divizibilitatea lui prin <code>p</code> ( Numărul reprezintă combinări de elemente luate câte ).

De asemenea se știe că exponentul numărului prim <code>p</code> în descompunerea în factori primi a numărului <code>a</code>! este , unde prin am notat partea întreagă a lui .

În exemplul dat avem , deci exponentul este <code>3</code>.

== Rezolvare ==
<syntaxhighlight lang="python3">
def count_p_in_factorial(n, p):
exponent = 0
while n % p == 0:
n //= p
exponent += 1
return exponent

def is_divisible_by_p(a, b, c, p):
exponent_a = count_p_in_factorial(a, p)
exponent_b = count_p_in_factorial(b, p)
exponent_c = count_p_in_factorial(c, p)

if exponent_a - exponent_b - exponent_c < 0:
return 0

exponent = exponent_a - exponent_b - exponent_c
return exponent

def main():
a, b, c, p = map(int, input().split())

if a >= b + c:
exponent = is_divisible_by_p(a, b, c, p)
print(exponent)
else:
print("0")

if __name__ == "__main__":
main()

</syntaxhighlight>

3025 - PCR

2024-06-04T08:32:34Z

Danciu: Pagină nouă: = Cerința = Se dă <code>n</code> un număr natural. Cifrele lui <code>n</code> se permută pentru a forma un număr natural, de aceeași lungime cu <code>n</code>, și care să fie palindrom. Aflați câte asemenea numere se pot obține. = 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 de palindromuri care se pot obține prin permutarea cifrelor lui <code>n</code>. = Restricții ș...

= Cerința =
Se dă <code>n</code> un număr natural. Cifrele lui <code>n</code> se permută pentru a forma un număr natural, de aceeași lungime cu <code>n</code>, și care să fie palindrom. Aflați câte asemenea numere se pot obține.

= 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 de palindromuri care se pot obține prin permutarea cifrelor lui <code>n</code>.

= Restricții și precizări =

* <code>0 ≤ n ≤ 1038</code>
* PCR este prescurtarea de la [[Index.php/Clasele 9-10 lecția 25 - 1 apr 2015|Permutări Cu Repetiţie]]

= Exemplu: =
Intrare
1102022
Ieșire
4

=== Explicație ===
Permutând cifrele lui <code>1102022</code> se pot obține următoarele palindromuri de aceeași lungime cu <code>1102022</code>: <code>1022201</code>, <code>1202021</code>, <code>2012102</code>, <code>2102012</code>.

== Rezolvare ==
<syntaxhighlight lang="python3">
def count_palindrome_permutations(n):
total_palindromes = 0
num_even_digits = 0
num_odd_digits = 0
duplicated_digit_count = 0

while n > 0:
digit = n % 10
if digit % 2 == 0:
num_even_digits += 1
else:
num_odd_digits += 1
n //= 10

if num_even_digits > 1 or num_odd_digits > 1:
duplicated_digit_count = 1

if num_even_digits % 2 == 0:
total_palindromes += (num_even_digits // 2)! * (num_odd_digits // 2)!

if num_odd_digits % 2 == 0:
total_palindromes += (num_odd_digits // 2)! * (num_even_digits // 2)!

if num_odd_digits == 1 and num_even_digits > 0:
total_palindromes += (num_even_digits // 2)! * duplicated_digit_count

if num_even_digits == 1 and num_odd_digits > 0:
total_palindromes += (num_odd_digits // 2)! * duplicated_digit_count

return total_palindromes

def main():
n = int(input())
palindrome_count = count_palindrome_permutations(n)
print(palindrome_count)

if __name__ == "__main__":
main()

</syntaxhighlight>

3876 - sum max min

2024-06-04T08:30:38Z

Danciu: Pagină nouă: = Cerința = Se dă un șir de <code>N</code> numere întregi. Pentru fiecare subșir nevid al șirului dat se consideră valoarea întreagă <code>D</code> egală cu diferența dintre elementul maxim și cel minim aflat în subșir. Să se afle suma valorilor <code>D</code> ale tuturor subșirurilor nevide, mai mici sau egale decât un număr întreg <code>T</code> dat modulo . = Date de intrare = Programul citește de la tastatură numerele <code>N</code> și <code>T</cod...

= Cerința =
Se dă un șir de <code>N</code> numere întregi. Pentru fiecare subșir nevid al șirului dat se consideră valoarea întreagă <code>D</code> egală cu diferența dintre elementul maxim și cel minim aflat în subșir. Să se afle suma valorilor <code>D</code> ale tuturor subșirurilor nevide, mai mici sau egale decât un număr întreg <code>T</code> dat modulo .

= Date de intrare =
Programul citește de la tastatură numerele <code>N</code> și <code>T</code>, iar apoi <code>N</code> numere întregi, separate prin spații.

= Date de ieșire =
Programul va afișa pe ecran valoarea cerută în enunț.

= Restricții și precizări =

* <code>1 ≤ N, T ≤ 1.000.000</code>
* cele <code>N</code> numere citite vor fi din intervalul <code>[0, 1.000.000]</code>
* se numește subșir al unui șir o succesiune de elemente(nu neapărat consecutive în acesta) ale acestuia, considerate în ordinea în care apar în șir
* pentru teste în valoare de <code>20</code> de puncte <code>N ≤ 20</code>

= Exemplu: =
Intrare
5 2
1 7 2 3 4
Ieșire
11

=== Explicație ===
Dacă considerăm șirul indexat de la <code>1</code>, un exemplu de subșir ce respectă condiția din enunț este cel format din elementele de pe pozițiile <code>1</code>, <code>3</code> și <code>4</code>, <code>D</code> fiind egal în acest caz cu <code>2</code>, deci egal cu <code>T = 2</code>. Un alt subșir bun este cel format de elementele de pe pozițiile <code>3</code>, respectiv <code>4</code>, <code>D</code> fiind egal în acest caz cu <code>1</code>, deci mai mic decât <code>T = 2</code>. Subșirul format de elementele de pe pozițiile <code>2</code> și <code>3</code> nu respectă condiția din enunț pentru că în cazul acestuia <code>D = 5 > T = 2</code>. Analizând toate subșirurile se obține în final suma <code>11</code>.

== Rezolvare ==
<syntaxhighlight lang="python3">
MOD = 1000000007

def calculate_subarray_sums(n, t, numbers):
total_sum = 0 # Initialize total sum

for i in range(n):
max_so_far = numbers[i]
min_so_far = numbers[i]
subarray_count = 1

for j in range(i + 1, n):
max_so_far = max(max_so_far, numbers[j])
min_so_far = min(min_so_far, numbers[j])

difference = max_so_far - min_so_far

if difference <= t:
contribution = (subarray_count * difference) % MOD

total_sum = (total_sum + contribution) % MOD

subarray_count += 1

return total_sum

def main():
n, t = map(int, input().split())
numbers = list(map(int, input().split()))

subarray_sum = calculate_subarray_sums(n, t, numbers)
print(subarray_sum)

if __name__ == "__main__":
main()

</syntaxhighlight>

0722 - Cifru

2024-06-04T08:28:07Z

Danciu: Pagină nouă: Alibaba trebuie să descopere cifrul care deschide cufărul cu comoara cea mare. Cifrul este foarte greu de găsit. El a descoperit mai multe pietre, fiecare piatră având o altă culoare, pe fiecare piatră fiind scris un număr natural cu cel mult <code>4</code> cifre. Alibaba observă că numerele de pe fiecare piatră sunt distincte două câte două. Regula după care se formează cifrul este una foarte simplă, şi Alibaba a reuşit să o obţină destul de uşor: cif...

Alibaba trebuie să descopere cifrul care deschide cufărul cu comoara cea mare. Cifrul este foarte greu de găsit. El a descoperit mai multe pietre, fiecare piatră având o altă culoare, pe fiecare piatră fiind scris un număr natural cu cel mult <code>4</code> cifre. Alibaba observă că numerele de pe fiecare piatră sunt distincte două câte două. Regula după care se formează cifrul este una foarte simplă, şi Alibaba a reuşit să o obţină destul de uşor: cifrul este format din alăturarea într-o anumită ordine a tuturor pietrelor. Ceea ce Alibaba mai ştie este că pe poziţia <code>p</code> din cifru se găseşte cu siguranţă cifra <code>k</code>.

= Cerința =
Scrieţi un program care determină numărul de variante de cifruri pe care va trebui să le încerce Alibaba. Numărul fiind foarte mare se va calcula modulo <code>46337</code>.

= Date de intrare =
Fișierul de ieșire <code>cifru.out</code> va conține pe prima linie trei numere naturale <code>n</code>, <code>p</code> şi <code>k</code> separate printr-un spaţiu, reprezentând numărul total de numere de pe pergament, poziţia <code>p</code> şi respectiv cifra <code>k</code> care se găseşte pe poziţia <code>p</code> în cifru. Pe următoarele <code>n</code> linii se găseşte câte unul din cele <code>n</code> numere de pe pergament.

= Date de ieșire =
Pe prima linie a fişierului de ieşire <code>cifru.out</code> se va scrie un număr natural reprezentând numărul de variante modulo <code>46337</code> de cifruri pe care va trebui să le încerce Alibaba.

= Restricții și precizări =

* <code>0 < n < 25</code>
* Numerele de pe fiecare piatră sunt strict pozitive mai mici decât <code>10000</code> şi sunt distincte două câte două.
* <code>0 ≤ k ≤ 9</code>
* Două cifruri diferă între ele prin ordinea de aşezare a pietrelor, chiar dacă numărul obţinut prin citirea numerelor de pe pietre este aceeaşi. De exemplu dacă există trei pietre având inscripţionate numerele <code>12</code>, <code>3</code> şi respectiv <code>123</code>, ele se pot lipi astfel: <code>12-3-123</code>, <code>123-12-3</code>, cele două cifruri considerându-se diferite, cifrele având culori diferite.

== Rezolvare ==
<syntaxhighlight lang="python3">
MOD = 46337

def count_cipher_variants(n, p, k, numbers):
"""Calculates the number of cipher variants modulo MOD."""

total_variants = 1 # One variant with all numbers fixed except for the given one
fixed_numbers = set([k]) # Set of fixed numbers (initially only k)
remaining_numbers = set(numbers) - fixed_numbers # Set of remaining numbers

for i in range(p - 1, -1, -1):
choices_for_position_i = len(remaining_numbers)
total_variants *= choices_for_position_i

fixed_numbers.add(numbers.pop(i)) # Add the number to fixed numbers
remaining_numbers.remove(numbers.pop(i)) # Remove it from remaining numbers
return total_variants % MOD

def main():
n, p, k = map(int, input().split())
numbers = [int(input()) for _ in range(n)]

cipher_variants = count_cipher_variants(n, p, k, numbers)
print(cipher_variants)

if __name__ == "__main__":
main()

</syntaxhighlight>

4168 - Secvente 6

2024-06-04T08:23:59Z

Danciu: Pagină nouă: Notăm cu <code>[x, y]</code>, o secvență de numere naturale nenule <code>x, x + 1, x + 2, ..., y</code>, cu <code>x ≤ y</code>. Considerăm că secvența <code>[p, q]</code> include secvența <code>[a, b]</code> dacă are loc relația <code>p ≤ a ≤ b ≤ q</code>. Se dau <code>N</code> secvențe speciale de forma <code>[a, b]</code> și apoi <code>T</code> secvențe de interogare <code>[L,R]</code>. Orice secvență care include cel puțin o secvență specială va...

Notăm cu <code>[x, y]</code>, o secvență de numere naturale nenule <code>x, x + 1, x + 2, ..., y</code>, cu <code>x ≤ y</code>.

Considerăm că secvența <code>[p, q]</code> include secvența <code>[a, b]</code> dacă are loc relația <code>p ≤ a ≤ b ≤ q</code>.

Se dau <code>N</code> secvențe speciale de forma <code>[a, b]</code> și apoi <code>T</code> secvențe de interogare <code>[L,R]</code>. Orice secvență care include cel puțin o secvență specială va fi numită secvență super-specială. Numărul de secvențe super-speciale pe care o secvență <code>[L, R]</code> le include va fi denumit capacitatea secvenței <code>[L, R]</code>.

= Cerința =
Pentru fiecare secvență de interogare, să se determine capacitatea sa.

= Date de intrare =
Fișierul de intrare <code>secvente.in</code> conține pe prima linie numărul natural <code>N</code>, reprezentând numărul de secvențe speciale. Pe următoarele <code>N</code> linii se află câte două numere naturale nenule <code>a</code> și <code>b</code>, separate printr-un spațiu, reprezentând secvențele speciale. Pe linia <code>N+2</code> se află numărul natural <code>T</code>, reprezentând numărul de secvențe de interogare, iar pe următoarele <code>T</code> linii se află câte două numere naturale nenule <code>L</code> și <code>R</code>, separate printr-un spațiu, reprezentând secvențele de interogare.

= Date de ieșire =
Fișierul de ieșire <code>secvente.out</code> va conține <code>T</code> linii. Pe cea de a <code>i</code>-a linie din fișier se va scrie un singur număr natural, reprezentând capacitatea celei de a <code>i</code>-a secvențe de interogare, în ordinea din fișierul de intrare.

= Restricții și precizări =

* <code>1 ≤ N ≤ 100.000</code>
* <code>1 ≤ a ≤ b ≤ 1.000.000.000</code>
* <code>1 ≤ T ≤ 100.000</code>
* <code>1 ≤ L ≤ R ≤ 1.000.000.000</code>

= Exemplu: =
<code>secvente.in</code>
2
2 4
3 3
3
2 4
1 5
2 5
<code>secvente.out</code>
4
9
6

=== Explicație ===
Secvența de interogare <code>[2,4]</code> conține secvențele super-speciale <code>[2,3]</code>, <code>[2,4]</code>, <code>[3,3]</code> și <code>[3,4]</code>. Se observă că <code>[2, 2]</code> nu este o secvență super-specială deoarece nu include pe niciuna dintre cele două secvențe speciale (<code>[2, 4]</code> și <code>[3, 3]</code>).

Secvența de interogare <code>[1,5]</code> conține secvențele super-speciale <code>[1,3]</code>, <code>[1,4]</code>, <code>[1,5]</code>, <code>[2,3]</code>, <code>[2,4]</code>, <code>[2,5]</code>, <code>[3,3]</code>, <code>[3,4]</code> și <code>[3,5]</code>.

Secvența de interogare <code>[2,5]</code> conține secvențele super-speciale <code>[2,3]</code>, <code>[2,4]</code>, <code>[2,5]</code>, <code>[3,3]</code>, <code>[3,4]</code> și <code>[3,5]</code>.

== Rezolvare ==
<syntaxhighlight lang="python3">
def read_special_sequences(n):
special_sequences = []
for _ in range(n):
a, b = map(int, input().split())
special_sequences.append((a, b))
return special_sequences

def read_query_sequences(t):
query_sequences = []
for _ in range(t):
l, r = map(int, input().split())
query_sequences.append((l, r))
return query_sequences

def is_super_special(query_sequence, special_sequences):
for a, b in special_sequences:
if a <= query_sequence[0] <= query_sequence[1] <= b:
return True
return False

def count_super_special_sequences(query_sequence, special_sequences):
count = 0
for a, b in special_sequences:
if a <= query_sequence[0] <= b <= query_sequence[1]:
count += 1
return count

def main():
n = int(input())
special_sequences = read_special_sequences(n)

t = int(input())
query_sequences = read_query_sequences(t)

for query_sequence in query_sequences:
super_special_count = count_super_special_sequences(query_sequence, special_sequences)
print(super_special_count)

if __name__ == "__main__":
main()

</syntaxhighlight>

0599 - Covoare

2024-06-04T08:20:47Z

Danciu: Pagină nouă: = Cerința = Se consideră o încăpere de lungime <code>m</code> și lățime <code>n</code> împărțită în <code>n*m</code> zone pătrate, sub forma unei matrice cu <code>n</code> linii și <code>m</code> coloane. Încăperea este acoperită în totalitate cu <code>p</code> covoare de diferite dimensiuni și culori astfel încât acestea nu se suprapun și încăperea este acoperită în totalitate. Mai mult fiecare zonă pătrată a încăperii este acoperită cu un si...

= Cerința =
Se consideră o încăpere de lungime <code>m</code> și lățime <code>n</code> împărțită în <code>n*m</code> zone pătrate, sub forma unei matrice cu <code>n</code> linii și <code>m</code> coloane. Încăperea este acoperită în totalitate cu <code>p</code> covoare de diferite dimensiuni și culori astfel încât acestea nu se suprapun și încăperea este acoperită în totalitate. Mai mult fiecare zonă pătrată a încăperii este acoperită cu un singur covor.

Gigel, administratorul clădirii, este responsabil cu spălarea covoarelor. Astfel el a notat, în ordine, dimensiunile și culoarea fiecărui covor, în ordine, de sus în jos și de la stânga la dreapta. Covoarele au fost scoase și spălate, dar acum Gigel vă cere ajutorul.

Cunoscând dimensiunile încăperii, numărul de covoare precum și dimensiunile și culoarea fiecărui covor, să se refacă așezarea inițială a acestora.

= Date de intrare =
Fișierul de intrare <code>covoare.in</code> conține pe prima linie numerele <code>n m p</code>, iar pe a următoarele <code>p</code> linii câte trei numere <code>a b c</code> reprezentând lungimea, lățimea și culoarea fiecărui covor.

= Date de ieșire =
Fișierul de ieșire <code>covoare.out</code> va conține o matrice <code>A</code> cu <code>n</code> linii și <code>m</code> coloane, <code>A[i][j]</code> reprezentând culoarea covorului care acoperă zona <code>i j</code>. Fiecare linie a matricei va fi scrisă pe o linie a fișierului, elementele unei linii fiind separate prin exact un spațiu.

= Restricții și precizări =

* <code>1 ≤ n, m ≤ 100</code>
* covoarele trebuie așezate în ordinea dată, și nu pot fi rotite
* culoarea unui covor este un număr natural nenul

= Exemplu: =
<code>covoare.in</code>
5 6 8
3 2 2
1 1 1
2 3 2
1 1 4
4 2 3
2 2 1
2 1 1
2 1 3
<code>covoare.out</code>
2 2 2 1 2 2
2 2 2 4 2 2
3 3 3 3 2 2
3 3 3 3 1 1
1 1 3 3 1 1

== Rezolvare ==
<syntaxhighlight lang="python3">
def read_input(n, m, p):
carpets = []
for _ in range(p):
a, b, c = map(int, input().split())
carpets.append((a, b, c))
return carpets

def is_valid_placement(carpets, n, m):
used_area = [[False for _ in range(m)] for _ in range(n)]
for a, b, _ in carpets:
for i in range(n - a + 1):
for j in range(m - b + 1):
if used_area[i][j]:
return False
for x in range(a):
for y in range(b):
used_area[i + x][j + y] = True

return True

def place_carpets(carpets, n, m):
"""Arranges the carpets on the floor."""
floor = [[0 for _ in range(m)] for _ in range(n)]
for a, b, c in carpets:
for i in range(n - a + 1):
for j in range(m - b + 1):
if not used_area[i][j]:
for x in range(a):
for y in range(b):
floor[i + x][j + y] = c
used_area[i + x][j + y] = True
break
return floor

def print_floor(floor, n, m):
for i in range(n):
for j in range(m):
print(floor[i][j], end=" ")
print()

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

if not is_valid_placement(carpets, n, m):
print("IMPOSIBIL")
return

floor = place_carpets(carpets, n, m)
print_floor(floor, n, m)

if __name__ == "__main__":
main()

</syntaxhighlight>

2235 - tsunami

2024-06-04T07:55:16Z

Danciu: Pagină nouă: Tsunamiul este valul mareic ce se propagă prin apa oceanelor/mărilor, ca urmare a producerii unor erupţii subacvatice sau/şi a unor cutremure submarine sau de coastă foarte puternice. Cercetătorii doresc să preîntâmpine efectele unor posibile valuri mareice prin marcarea şi clasificarea zonelor al căror risc de inundare este ridicat. Teritoriul studiat a fost împărţit în <code>n×m</code> pătrate identice (zone) rezultând o hartă digitizată, reprezentat...

Tsunamiul este valul mareic ce se propagă prin apa oceanelor/mărilor, ca urmare a producerii unor erupţii subacvatice sau/şi a unor cutremure submarine sau de coastă foarte puternice.

Cercetătorii doresc să preîntâmpine efectele unor posibile valuri mareice prin marcarea şi clasificarea zonelor al căror risc de inundare este ridicat.

Teritoriul studiat a fost împărţit în <code>n×m</code> pătrate identice (zone) rezultând o hartă digitizată, reprezentată sub forma unui tablou bidimensional cu <code>n</code> linii şi <code>m</code> coloane, fiecare element al tabloului memorând cota (înălţimea) terenului din pătratul unitate corespunzător. Zonele de apă au cota <code>0</code>, iar zonele de uscat au cote mai mari decât <code>0</code>.

Orice tsunami este clasificat în funcţie de înălţimea valului mareic, pe o scară de la <code>1</code> la <code>10</code>. Cercetătorii doresc să marcheze zonele de risc ce pot fi afectate de un potenţial tsunami.

Iniţial, valul mareic apare în toate zonele de cotă <code>0</code> vecine cu cel puţin o zonă de uscat. O zonă teritorială poate fi afectată dacă are cota strict mai mică decât înălţimea valului mareic şi se află în vecinătatea apei sau în vecinătatea unei zone afectate. Două pătrate unitate se învecinează dacă au o latură comună.

= Cerința =
Dată fiind harta digitizată a zonelor monitorizate, să se determine numărul zonelor de uscat afectate de un tsunami de înălțime <code>h</code>.

= Date de intrare =
Fișierul de intrare <code>tsunami.in</code> conține pe prima linie trei numere naturale <code>n</code>, <code>m</code> şi <code>h</code> separate prin câte un spațiu, reprezentând dimensiunile hărții, respectiv înălțimea valului mareic. Pe următoarele <code>n</code> linii sunt scrise câte <code>m</code> numere naturale separate prin câte un spațiu reprezentând, în ordine, cotele din cele <code>n×m</code> pătrate teritoriale unitate ale hărții.

= Date de ieșire =
Fișierul de ieșire <code>tsunami.out</code> conţine o singură valoare ce reprezintă numărul pătratelor unitate afectate de un tsunami de înălţime <code>h</code>.

= Restricții și precizări =

* <code>2 ≤ n,m ≤ 1000</code>
* <code>1 ≤ h ≤ 10</code>
* Zona monitorizată nu conţine lacuri interioare (pătrate unitate învecinate, având cota <code>0</code>, înconjurate complet de pătrate unitate având cote strict mai mari decît <code>0</code>)
* Cotele sunt numere naturale ≤ <code>1000</code>

= Exemplu: =
<code>tsunami.in</code>
6 7 3
0 0 4 2 5 0 0
1 0 0 7 3 6 0
2 3 0 5 2 2 0
0 7 5 4 0 0 0
0 5 2 3 0 2 0
0 4 4 8 0 2 0
<code>tsunami.out</code>
6

=== Explicație ===
Zonele inundate sunt reprezentate îngroşat în tabloul bidimensional:
{| class="wikitable"
|<code>0</code>
|<code>0</code>
|<code>4</code>
|<code>2</code>
|<code>5</code>
|<code>0</code>
|<code>0</code>
|-
|<code>1</code>
|<code>0</code>
|<code>0</code>
|<code>7</code>
|<code>3</code>
|<code>6</code>
|<code>0</code>
|-
|<code>2</code>
|<code>3</code>
|<code>0</code>
|<code>5</code>
|<code>2</code>
|<code>2</code>
|<code>0</code>
|-
|<code>0</code>
|<code>7</code>
|<code>5</code>
|<code>4</code>
|<code>0</code>
|<code>0</code>
|<code>0</code>
|-
|<code>0</code>
|<code>5</code>
|<code>2</code>
|<code>3</code>
|<code>0</code>
|<code>2</code>
|<code>0</code>
|-
|<code>0</code>
|<code>4</code>
|<code>4</code>
|<code>8</code>
|<code>0</code>
|<code>2</code>
|<code>0</code>
|}

== Rezolvare ==
<syntaxhighlight lang="python3">
import sys

def is_valid_land(grid, n, m, i, j):
"""Checks if the given cell (i, j) is a valid land area."""
if 0 <= i < n and 0 <= j < m:
return grid[i][j] > 0
return False

def mark_affected_areas(grid, n, m, h):
"""Marks affected land areas starting from water cells."""
affected_count = 0
stack = []

# Initialize stack with water cells adjacent to land
for i in range(n):
for j in range(m):
if grid[i][j] == 0:
for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
new_i = i + di
new_j = j + dj
if is_valid_land(grid, n, m, new_i, new_j):
stack.append((new_i, new_j))

# Mark affected land areas using DFS
while stack:
i, j = stack.pop()
if grid[i][j] > 0 and grid[i][j] <= h:
grid[i][j] = -1 # Mark as affected
affected_count += 1

for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
new_i = i + di
new_j = j + dj
if is_valid_land(grid, n, m, new_i, new_j) and grid[new_i][new_j] > 0:
stack.append((new_i, new_j))

return affected_count

def main():
"""Reads input, marks affected areas, and prints the result."""
n, m, h = map(int, input().split())

# Read the grid data
grid = []
for _ in range(n):
row = list(map(int, input().split()))
grid.append(row)

# Mark affected land areas and count them
affected_count = mark_affected_areas(grid, n, m, h)

# Print the number of affected land areas
print(affected_count)

if __name__ == "__main__":
sys.stdin = open("tsunami.in")
sys.stdout = open("tsunami.out", "w")
main()
sys.stdin.close()
sys.stdout.close()

</syntaxhighlight>

3114 - abq

2024-06-04T07:51:46Z

Danciu: Pagină nouă: = Cerință = Alexandru a învățat azi despre numerele romane și cum se scriu acestea. Fiind distras de ce spuneau colegii a ajuns acasă și a realizat că nu știe cum să transforme un număr din cifre arabe în cifre romane. Deoarece a doua zi are un test numai din acest capitol, vă roagă să îl ajutați la transformarea unui număr <code>N</code> dat, scris cu cifre arabe în cifre romane. = Date de intrare = Fișierul <code>cifre_romane.in</code> conține un num...

= Cerință =
Alexandru a învățat azi despre numerele romane și cum se scriu acestea. Fiind distras de ce spuneau colegii a ajuns acasă și a realizat că nu știe cum să transforme un număr din cifre arabe în cifre romane. Deoarece a doua zi are un test numai din acest capitol, vă roagă să îl ajutați la transformarea unui număr <code>N</code> dat, scris cu cifre arabe în cifre romane.

= Date de intrare =
Fișierul <code>cifre_romane.in</code> conține un număr natural <code>N</code> scris cu cifre arabe.

= Date de ieșire =
Fișierul <code>cifre_romane.out</code> va conține scrierea cu cifre romane a lui <code>N</code>.

= Restricții =

* <code>1≤N≤3999</code>
* cifrele romane sunt:
** <code>I=1</code>
** <code>V=5</code>
** <code>X=10</code>
** <code>L=50</code>
** <code>C=100</code>
** <code>D=500</code>
** <code>M=1000</code>

= Exemplu =
<code>cifre_romane.in</code>
4
<code>cifre_romane.out</code>
IV

== Rezolvare ==
<syntaxhighlight lang="python3">
import sys

def convert_to_roman(num):
"""Converts a given number from Arabic numerals to Roman numerals."""
roman_numerals = {
1: "I",
5: "V",
10: "X",
50: "L",
100: "C",
500: "D",
1000: "M"
}

result = ""
while num > 0:
# Find the largest Roman numeral that is less than or equal to the current number
for key in sorted(roman_numerals.keys(), reverse=True):
if num >= key:
result += roman_numerals[key]
num -= key
break

return result

def main():
"""Reads input and converts numbers to Roman numerals."""
num = int(input())

# Check if the number is within the valid range
if 1 <= num <= 3999:
roman_numeral = convert_to_roman(num)
print(roman_numeral)
else:
print("Numarul nu este in intervalul valid (1 ≤ N ≤ 3999).")

if __name__ == "__main__":
sys.stdin = open("cifre_romane.in")
sys.stdout = open("cifre_romane.out", "w")
main()
sys.stdin.close()
sys.stdout.close()

</syntaxhighlight>

1870 - Easy xy

2024-06-04T07:47:22Z

Danciu: Pagină nouă: = Cerința = Se dă un vector <code>v</code> cu <code>N</code> elemente numere naturale numerotate de la <code>1</code> la <code>N</code> și <code>M</code> întrebări de forma: * <code>x y p</code>: se afișează valoarea ce s-ar afla pe poziția <code>p</code> dacă <code>v[x...y]</code> ar fi ordonat crescător. Să se răspundă la cele <code>M</code> întrebări. = Date de intrare = Fișierul de intrare <code>easyxy.in</code> conține pe prima linie numerele <code>N...

= Cerința =
Se dă un vector <code>v</code> cu <code>N</code> elemente numere naturale numerotate de la <code>1</code> la <code>N</code> și <code>M</code> întrebări de forma:

* <code>x y p</code>: se afișează valoarea ce s-ar afla pe poziția <code>p</code> dacă <code>v[x...y]</code> ar fi ordonat crescător.

Să se răspundă la cele <code>M</code> întrebări.

= Date de intrare =
Fișierul de intrare <code>easyxy.in</code> conține pe prima linie numerele <code>N</code> și <code>M</code>. Pe următoarea linie se află <code>N</code> elemente ce reprezintă elementele vectorului. Pe următoarele <code>M</code> linii se află întrebările.

= Date de ieșire =
Fișierul de ieșire <code>easyxy.out</code> va conține pe fiecare linie <code>i</code> răspunsul la întrebarea <code>i</code>, în ordinea în care acestea apar în fișierul de intrare.

= Restricții și precizări =

* <code>1 ≤ N,M ≤ 100.000</code>
* Elementele vectorului sunt <code>≤ 1.000.000.000</code>
* Pentru orice întrebare, <code>1 ≤ x ≤ p ≤ y ≤ N</code>

= Exemplu: =
<code>easyxy.in</code>
6 3
1 3 2 5 6 3
1 3 2
1 6 5
3 5 4
<code>easyxy.out</code>
2
5
5

== Rezolvare ==
<syntaxhighlight lang="python3">
import sys
import bisect

def solve_test_case(n, m, arr):
prefix_sums = [0] * (n + 1)
for i in range(1, n + 1):
prefix_sums[i] = prefix_sums[i - 1] + arr[i - 1]

for _ in range(m):
x, y, p = map(int, input().split())

total_sum = prefix_sums[y] - prefix_sums[x - 1]

left = 0
right = total_sum

while left <= right:
mid = (left + right) // 2

count_less = bisect.bisect_left(prefix_sums, mid)

if count_less < p:
left = mid + 1
else:
right = mid

answer = right

print(answer)

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

arr = list(map(int, input().split()))

for _ in range(m):
solve_test_case(n, m, arr)

if __name__ == "__main__":
sys.stdin = open("easyxy.in")
sys.stdout = open("easyxy.out", "w")
main()
sys.stdin.close()
sys.stdout.close()

</syntaxhighlight>

2725 - Aib

2024-06-04T07:42:26Z

Danciu: Pagină nouă: Aveți la dispoziție un număr natural nenul <code>n</code> și o permutare <code>a = (a[1], a[2], ..., a[n])</code> a mulțimii <code>{1, 2, ..., n}</code>. = Cerința = Pentru fiecare număr <code>a[i]</code> trebuie să determinați câte numere mai mici decât <code>a[i]</code> se află la stânga sa, adică în secvența <code>a[1], a[2], ..., a[i-1]</code>. = Date de intrare = Programul citește de la tastatură numărul <code>n</code>, iar apoi <code>n</code> numere...

Aveți la dispoziție un număr natural nenul <code>n</code> și o permutare <code>a = (a[1], a[2], ..., a[n])</code> a mulțimii <code>{1, 2, ..., n}</code>.

= Cerința =
Pentru fiecare număr <code>a[i]</code> trebuie să determinați câte numere mai mici decât <code>a[i]</code> se află la stânga sa, adică în secvența <code>a[1], a[2], ..., a[i-1]</code>.

= Date de intrare =
Programul citește de la tastatură numărul <code>n</code>, iar apoi <code>n</code> numere naturale separate prin spații reprezentând permutarea.

= Date de ieșire =
Programul va afișa pe ecran pentru fiecare <code>i=1..n</code> câte numere mai mici decât <code>a[i]</code> se află la stânga sa.

= Restricții și precizări =

* <code>3 ≤ n ≤ 100.000</code>

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

=== Explicație ===
Sunt <code>0</code> numere mai mici decât <code>3</code> și aflate la stânga lui <code>3</code>.

Sunt <code>0</code> numere mai mici decât <code>1</code> și aflate la stânga lui <code>1</code>

Sunt <code>2</code> numere mai mici decât <code>6</code> și aflate la stânga lui <code>6</code> (acestea sunt primele două numere din șir, adică <code>3</code> și <code>1</code>)

== Rezolvare ==
<syntaxhighlight lang="python3">
def count_smaller(arr):
n = len(arr)
result = [0] * n
bit = [0] * (n + 1)

def update(x, val):
while x <= n:
bit[x] += val
x += x & -x

def query(x):
s = 0
while x > 0:
s += bit[x]
x -= x & -x
return s

for i in range(n - 1, -1, -1):
result[i] = query(arr[i])
update(arr[i], 1)

return result

def main():
n = int(input("Introduceti n: "))
arr = list(map(int, input("Introduceti permutarea: ").split()))

smaller_counts = count_smaller(arr)
for count in smaller_counts:
print(count, end=" ")

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

2012 - TSM

2024-06-04T07:38:32Z

Danciu: Pagină nouă: = Enunț = TH, Seba, Șcuțu și Năstuț se joacă noul joc numit TSM. TSM are un sistem de tip multiplayer foarte interesant: se formează două echipe care se vor confrunta, una ce conține <code>4</code> jucători ce vor avea rol de apărători și alta ce conține un singur jucător cu rol de atacator (foarte necinstit). Mygo a auzit că cei <code>4</code> prieteni și-au făcut echipă, iar pe el nu l-au invitat, așa că decide să îi provoace la joc. Într-o rundă...

= Enunț =
TH, Seba, Șcuțu și Năstuț se joacă noul joc numit TSM. TSM are un sistem de tip multiplayer foarte interesant: se formează două echipe care se vor confrunta, una ce conține <code>4</code> jucători ce vor avea rol de apărători și alta ce conține un singur jucător cu rol de atacator (foarte necinstit). Mygo a auzit că cei <code>4</code> prieteni și-au făcut echipă, iar pe el nu l-au invitat, așa că decide să îi provoace la joc. Într-o rundă de joc acțiunile se petrec pe un câmp de luptă, inițial gol, iar apărătorii disting următoarele evenimente:

<code>1 x</code> : TH observă că Mygo a trimis pe câmpul de luptă un tanc de coeficient <code>x</code> și își anunță aliații.

<code>2 K</code> : Seba consideră că cel mai periculos tip de tanc aflat pe câmpul de luptă este cel cu al <code>K</code> – lea cel mai mic coeficient și îl afișează în consolă, pe un nou rând.

<code>3</code> : Năstuț scrie în consolă, pe un nou rând, coeficientul cel mai mic al unui tanc aflat în momentul respectiv pe câmpul de luptă.

<code>4</code> : Șcuțu trage cu tunul într-un tanc de coeficient egal cu ultimul scris de Seba în consolă și îl elimină.

= Cerința =
Pentru un joc cu <code>M</code> evenimente, simulați parcursul jocului.

Cei <code>4</code> prieteni au folosit aceste două bucăți de cod ca să poată să câștige, așa că ți le oferă și ție:

InParser

OutParser

= Date de intrare =
Fișierul de intrare <code>tsm.in</code> conține pe prima linie numărul <code>M</code>, reprezentând numărul de evenimente, iar pe următoarele <code>M</code> linii câte un eveniment, cu formatul explicat mai sus.

= Date de ieșire =
Fișierul de ieșire <code>tsm.out</code> va conține pentru fiecare eveniment de tipul <code>2</code> și <code>3</code>, răspunsul lor, fiecare pe câte o linie, în ordinea în care acestea apar în fișierul de intrare.

= Restricții și precizări =

* <code>1 ≤ M ≤ 1.000.000</code>
* pentru evenimentele de tip <code>1</code>, <code>1 ≤ x ≤ 1.000.000</code>
* se garantează că orice alt eveniment va putea fi procesat.
* între oricare <code>2</code> evenimente de tip <code>4</code> va exista cel puțin un eveniment de tip <code>2</code>.

= Exemplu: =
<code>tsm.in</code>
14
1 2
1 3
3
1 2
1 1
1 1
3
1 4
2 3
2 1
4
2 1
4
3
<code>tsm.out</code>
2
1
3
1
1
2

== Rezolvare ==
<syntaxhighlight lang="python3">
from heapq import heappush, heappop

def main():
events = [] # Lista de evenimente
tanks = [] # Coada de tancuri (heap)

with open("tsm.in", "r") as fin, open("tsm.out", "w") as fout:
m = int(fin.readline()) # Numărul de evenimente

for _ in range(m):
event = fin.readline().split()
event_type = int(event[0])
events.append(event)

for event in events:
event_type = int(event[0])

if event_type == 1:
tank_coeff = int(event[1])
heappush(tanks, tank_coeff)

elif event_type == 2:
k = len(tanks)
if k > 0:
temp_tanks = tanks.copy()
temp_tanks.sort()
fout.write(str(temp_tanks[k - int(event[1])]) + "\n")

elif event_type == 3:
if tanks:
fout.write(str(tanks[0]) + "\n")

elif event_type == 4:
if tanks:
tank_to_remove = heappop(tanks)
while tanks and tank_to_remove != tanks[0]:
tank_to_remove = heappop(tanks)

if __name__ == "__main__":
main()

</syntaxhighlight>

2779 - Cnt SQ

2024-06-04T07:35:39Z

Danciu: Pagină nouă: = Cerința = Se dă o matrice binară (valori <code>0</code> și <code>1</code>). Să se determine câte pătrate există cu proprietatea că acestea au pe marginea lor doar valori <code>1</code>. = Date de intrare = Fișierul de intrare <code>cntsq.in</code> conține pe prima linie numerele <code>N</code> și <code>M</code>, reprezentând numărul de linii și numărul de coloane ale matricei, apoi <code>N</code> linii, pe fiecare câte <code>M</code> valori <code>0</code>...

= Cerința =
Se dă o matrice binară (valori <code>0</code> și <code>1</code>). Să se determine câte pătrate există cu proprietatea că acestea au pe marginea lor doar valori <code>1</code>.

= Date de intrare =
Fișierul de intrare <code>cntsq.in</code> conține pe prima linie numerele <code>N</code> și <code>M</code>, reprezentând numărul de linii și numărul de coloane ale matricei, apoi <code>N</code> linii, pe fiecare câte <code>M</code> valori <code>0</code> sau <code>1</code>, neseparate prin niciun spațiu, reprezentând elementele matricei.

= Date de ieșire =
Fișierul de ieșire <code>cntsq.out</code> va conține pe prima linie numărul <code>C</code>, reprezentând numărul de pătrate ce conțin doar <code>1</code> pe marginea lor.

= Restricții și precizări =

* <code>1 ≤ N, M ≤ 1000</code>
* Se consideră pătrat și cel de latură <code>1</code> (conține doar un element).
* Fie un pătrat determinat de <code>(i1, j1)</code> colțul stânga sus, <code>(i2, j2)</code> colțul dreapta jos. Se definește marginea pătratului ca fiind mulțimea de puncte <code>(x, y)</code> care respectă cel puțin una din condițiile: <code>((x = i1 sau x = i2) și (j1 ≤ y ≤ j2))</code> sau <code>((y = j1 sau y = j2) și (i1 ≤ x ≤ i2))</code>.

= Exemplu: =
<code>cntsq.in</code>
3 3
111
101
111
<code>cntsq.out</code>
9
<code>cntsq.in</code>
7 7
0000000
0111100
0101111
0100101
0111111
0000011
0000011
<code>cntsq.out</code>
27

== Rezolvare ==
<syntaxhighlight lang="python3">
def count_squares(matrix):
n, m = len(matrix), len(matrix[0])
dp = [[0] * (m + 1) for _ in range(n + 1)]
count = 0

for i in range(1, n + 1):
for j in range(1, m + 1):
if matrix[i - 1][j - 1] == 1:
dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
size = dp[i][j]
while size > 0:
count += 1
size -= 1

return count

def main():
with open("cntsq.in", "r") as fin, open("cntsq.out", "w") as fout:
n, m = map(int, fin.readline().split())
matrix = []
for _ in range(n):
row = list(map(int, fin.readline().strip()))
matrix.append(row)

result = count_squares(matrix)
fout.write(str(result) + "\n")

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

2477 – Tricolor

2024-06-04T07:33:02Z

Danciu: Pagină nouă: Tanaka are un arbore (un tri) cu <code>N</code> noduri numerotate de la <code>1</code> la <code>N</code>. El vrea să coloreze nodurile arborelui în alb sau negru astfel încât numărul de perechi (neordonate) de noduri înfrățite să fie maxim. Două noduri sunt înfrățite dacă și numai dacă ambele sunt albe și fie sunt legate direct printr-o muchie, fie lanțul elementar unic dintre ele conține doar noduri negre. = Cerința = Dându-se un arbore cu <code>N</code...

Tanaka are un arbore (un tri) cu <code>N</code> noduri numerotate de la <code>1</code> la <code>N</code>. El vrea să coloreze nodurile arborelui în alb sau negru astfel încât numărul de perechi (neordonate) de noduri înfrățite să fie maxim. Două noduri sunt înfrățite dacă și numai dacă ambele sunt albe și fie sunt legate direct printr-o muchie, fie lanțul elementar unic dintre ele conține doar noduri negre.

= Cerința =
Dându-se un arbore cu <code>N</code> noduri, să se afle numărul maxim de perechi de noduri înfrățite ale sale care se poate obține.

= Date de intrare =
Fișierul de intrare <code>tricolor.in</code> va conține pe primul rând un număr natural nenul <code>T</code> ce reprezintă numărul de teste. Urmează <code>T</code> teste, fiecare test va descrie un arbore pentru care trebuie să se rezolve cerința. Pe primul rând al unui test apare un număr natural <code>N</code> ce reprezintă numărul de noduri ale arborelui din testul respectiv. Pe următoarele <code>N-1</code> rânduri vor apărea câte o pereche de numere întregi <code>x y</code> separate printr-un spațiu, care indică existența unei muchii între nodul <code>x</code> și nodul <code>y</code>.

= Date de ieșire =
Fișierul de ieșire <code>tricolor.out</code> va conține <code>T</code> rânduri. Fiecare rând va conține soluția pentru câte un test, în aceeași ordine ca în fișierul de intrare.

= Restricții și precizări =

* <code>1 ≤ T ≤ 10</code>
* <code>1 ≤ N ≤ 5 000</code>
* Într-un test oarecare, <code>1 ≤ x, y ≤ N</code>, <code>x ≠ y</code>
* Pentru <code>5</code> puncte, <code>T = 1</code> și <code>N ≤ 15</code>
* Pentru alte <code>10</code> puncte, <code>T = 1</code> și <code>N ≤ 20</code>
* Pentru alte <code>5</code> puncte, toți arborii descriși au exact <code>2</code> frunze și <code>N ≤ 500</code>
* Pentru alte <code>10</code> puncte, pentru toți arborii descriși există exact două noduri ale arborelui de care se leagă toate frunzele, situate la capetele unui lanț elementar și <code>N ≤ 500</code>.
* Pentru alte <code>50</code> de puncte, <code>N ≤ 500</code>
* Pentru alte <code>20</code> de puncte, nu există restricții suplimentare.

= Exemplu: =
<code>tricolor.in</code>
2
8
1 2
2 3
2 4
4 5
5 6
6 7
6 8
2
1 2
<code>tricolor.out</code>
7
1

=== Explicație ===
<code>T = 2</code>, avem două teste în fișierul de intrare. În primul test arborele are <code>8</code> noduri și cu o colorare optimă putem obține un număr maxim de <code>7</code> perechi de noduri înfrățite.

Perechile înfrățite sunt: <code>(1, 3)</code>, <code>(1, 4)</code>, <code>(3, 4)</code>, <code>(4, 5)</code>, <code>(5, 7)</code>, <code>(5, 8)</code>, <code>(7, 8)</code>.

În al doilea test arborele are <code>2</code> noduri legate cu o singură muchie. Este optim să colorăm ambele noduri în alb obținând o pereche de noduri înfrățite.

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

def maxFriendPairs(N, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)

def dfs(node, parent):
nonlocal ans
black_count = 0
white_count = 1

for child in graph[node]:
if child != parent:
black_subtree_count, white_subtree_count = dfs(child, node)
black_count += white_subtree_count
white_count += black_subtree_count

ans = max(ans, black_count * (black_count - 1) // 2 + white_count * (white_count - 1) // 2)
return black_count, white_count

ans = 0
dfs(1, -1)
return ans

def main():
with open("tricolor.in", "r") as fin, open("tricolor.out", "w") as fout:
T = int(fin.readline())
for _ in range(T):
N = int(fin.readline())
edges = []
for _ in range(N - 1):
u, v = map(int, fin.readline().split())
edges.append((u, v))
fout.write(str(maxFriendPairs(N, edges)) + "\n")

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

1757 – Sec

2024-06-04T07:08:48Z

Danciu: Pagină nouă: În timp ce-și bea sortimentul preferat de vin sec, vrăjitorului Arpsod i-a venit în minte o problemă de informatică ce are un enunț cel puțin la fel de sec și anume: Dându-se un arbore binar cu <code>N</code> noduri și rădăcina în nodul <code>1</code>, să se răspundă la <code>Q</code> întrebări de forma: “sunt cei doi fii ai nodului <code>X</code> identici?” Doi fii sunt identici dacă au același număr de subarbori și aceștia sunt identici (mai ex...

În timp ce-și bea sortimentul preferat de vin sec, vrăjitorului Arpsod i-a venit în minte o problemă de informatică ce are un enunț cel puțin la fel de sec și anume:

Dându-se un arbore binar cu <code>N</code> noduri și rădăcina în nodul <code>1</code>, să se răspundă la <code>Q</code> întrebări de forma: “sunt cei doi fii ai nodului <code>X</code> identici?”

Doi fii sunt identici dacă au același număr de subarbori și aceștia sunt identici (mai exact, pentru orice <code>i=1, 2, ..., N</code> subarborele <code>i</code> al primului este identic cu subarborele <code>i</code> al celui de-al doilea).

= Cerința =
Cunoscându-se arborele, să se răspundă la cele <code>Q</code> întrebări de forma indicată în enunţ.

= Date de intrare =
Pe prima linie a fișierului <code>sec.in</code> se află numărul natural <code>N</code>, reprezentând numărul de noduri ale arborelui. Următoarele <code>N-1</code> linii conțin perechi de forma <code>( x, y )</code> cu semnificația că există muchie între nodul <code>x</code> și nodul <code>y</code>. Pe a <code>(N+1)</code>-a linie se va afla numărul natural <code>Q</code>, reprezentând numărul de întrebări. Pe următoarele <code>Q</code> linii se va afla câte un număr natural reprezentând eticheta nodului ai cărui fii vor fi analizați.

= Date de ieșire =
Fișierul <code>sec.out</code> va avea <code>Q</code> linii. Pe fiecare linie va fi scris cuvântul <code>DA</code> dacă cei doi fii sunt identici respectiv <code>NU</code> în caz contrar .

= Restricții și precizări =

* <code>1 ≤ N ≤ 200.000</code>
* <code>1 ≤ Q ≤ 500.000</code>
* Nodurile arborelui sunt etichetate de la <code>1</code> la <code>N</code>.
* Rădăcina va fi mereu în nodul <code>1</code>.
* Fii NU sunt identici dacă unul dintre ei trebuie oglindit / rotit pentru a arăta ca celălalt.
* În cazul în care nodul cerut nu are fii, se va afișa <code>DA</code> (se consideră că sunt doi fii <code>NULL</code> identici)
* Se garantează că pentru <code>30%</code> din teste <code>1 ≤ N ≤ 1000</code> și <code>1 ≤ Q ≤ 3000</code>

= Exemplu: =
<code>sec.in</code>
9
1 2
1 3
2 4
2 5
3 6
4 8
5 9
6 7
4
1
2
3
7
<code>sec.out</code>
NU
DA
NU
DA

=== Explicație ===
Nodurile 2, 7, 8, 9 au ambii fii identici. Celelalte noduri nu au aceasta proprietate

== Rezolvare ==
<syntaxhighlight lang="python3">
from collections import defaultdict, deque
import hashlib
import sys

sys.setrecursionlimit(300000)

def read_input(file):
with open(file, 'r') as f:
data = f.read().split()
index = 0
N = int(data[index])
index += 1
edges = []
for _ in range(N - 1):
x = int(data[index])
y = int(data[index + 1])
index += 2
edges.append((x, y))
Q = int(data[index])
index += 1
queries = []
for _ in range(Q):
queries.append(int(data[index]))
index += 1
return N, edges, Q, queries

def build_tree(N, edges):
tree = defaultdict(list)
for x, y in edges:
tree[x].append(y)
tree[y].append(x)
return tree

def dfs(node, parent, tree, hashes):
children = []
for child in tree[node]:
if child != parent:
children.append(dfs(child, node, tree, hashes))

children.sort()
subtree_hash = hashlib.sha256(''.join(children).encode()).hexdigest()
hashes[node] = subtree_hash
return subtree_hash

def solve(N, edges, Q, queries):
tree = build_tree(N, edges)
hashes = {}

dfs(1, -1, tree, hashes)

results = []
for node in queries:
children = [child for child in tree[node] if child != node]
if len(children) < 2:
results.append("DA")
else:
if hashes[children[0]] == hashes[children[1]]:
results.append("DA")
else:
results.append("NU")

return results

def write_output(file, results):
with open(file, 'w') as f:
for result in results:
f.write(result + "\n")

def main():
N, edges, Q, queries = read_input('sec.in')
results = solve(N, edges, Q, queries)
write_output('sec.out', results)

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

4229 – Kdist

2024-06-04T06:53:24Z

Danciu: Pagină nouă: Bujorel s-a apucat de pomicultură şi a însămânţat un arbore (graf conex aciclic) cu <code>N</code> noduri, fiecare nod având o culoare dată dintr-un interval <code>[1, K]</code>. Acum, după ce arborele a crescut, el doreşte să ştie, pentru fiecare culoare, suma distanţelor dintre toate perechile de noduri ale arborelui ce au culoarea respectivă. Distanţa dintre două noduri se defineşte ca fiind numărul de muchii de pe drumul dintre cele două noduri. = Ceri...

Bujorel s-a apucat de pomicultură şi a însămânţat un arbore (graf conex aciclic) cu <code>N</code> noduri, fiecare nod având o culoare dată dintr-un interval <code>[1, K]</code>. Acum, după ce arborele a crescut, el doreşte să ştie, pentru fiecare culoare, suma distanţelor dintre toate perechile de noduri ale arborelui ce au culoarea respectivă. Distanţa dintre două noduri se defineşte ca fiind numărul de muchii de pe drumul dintre cele două noduri.

= Cerința =
Deoarece Bujorel a folosit foarte mult îngrăşământ la plantarea arborelui, acesta a crescut foarte mult şi voi trebuie să scrieţi un program care calculează suma distanţelor dintre nodurile cu aceeaşi culoare.

= Date de intrare =
Pe prima linie se află două numere naturale <code>N</code> şi <code>K</code>, numărul de noduri ale arborelui, respectiv numărul de culori în care sunt vopsite nodurile. Pe următoarele <code>N-1</code> linii este descris arborele, fiecare linie conţinând două numere naturale <code>x</code> şi <code>y</code>, reprezentând o muchie dintre nodul <code>x</code> şi nodul <code>y</code>. În continuare sunt prezente <code>N</code> linii, a <code>i</code>-a dintre aceste linii având un număr întreg <code>c</code> aparţinând intervalului <code>[1, K]</code> reprezentând culoarea nodului <code>i</code>.

= Date de ieșire =
Se vor afișa <code>K</code> linii, cea de-a <code>i</code>-a linie conţinând suma distanţelor dintre toate perechile de noduri ce au culoarea i.

= Restricții și precizări =

* <code>1 ≤ K ≤ N ≤ 200.000</code>
* În calcularea sumei distanţelor dintre nodurile cu aceeaşi culoare, fiecare pereche de noduri <code>(x, y)</code> va fi considerată o singură dată.

= Exemplu: =
Intrare
6 3
1 2
1 3
3 4
3 5
5 6
1
2
2
1
2
3
Ieșire
2
6
0

=== Explicație ===
Pentru culoarea <code>1</code> avem o pereche: <code>(1, 4)</code>, cu distanţa <code>2</code>. Pentru culoarea <code>2</code> avem trei perechi: <code>(2, 3)</code> cu distanţa <code>2</code>, <code>(2, 5)</code> cu distanţa <code>3</code> și <code>(3, 5)</code> cu distanţa <code>1</code>. Pentru culoarea <code>3</code> avem un singur nod cu această culoare, deci răspunsul este <code>0</code>.\

== Rezolvare ==
<syntaxhighlight lang="python3">
from collections import defaultdict, deque

def calculate_color_distances(n, k, edges, colors):

tree = defaultdict(list)
for u, v in edges:
tree[u].append(v)
tree[v].append(u)

color_nodes = defaultdict(list)
for i in range(n):
color_nodes[colors[i]].append(i + 1)

def bfs_distance_sum(start, valid_nodes):
visited = set()
queue = deque([(start, 0)])
visited.add(start)
distance_sum = 0
node_count = 0

while queue:
node, dist = queue.popleft()
distance_sum += dist
node_count += 1

for neighbor in tree[node]:
if neighbor not in visited and neighbor in valid_nodes:
visited.add(neighbor)
queue.append((neighbor, dist + 1))

return distance_sum, node_count

color_distance_sums = [0] * k
for color in range(1, k + 1):
nodes = color_nodes[color]
if len(nodes) < 2:
continue

total_distance_sum = 0
for node in nodes:
dist_sum, node_count = bfs_distance_sum(node, set(nodes))
total_distance_sum += dist_sum

color_distance_sums[color - 1] = total_distance_sum // 2

return color_distance_sums

n, k = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(n - 1)]
colors = [int(input()) for _ in range(n)]

result = calculate_color_distances(n, k, edges, colors)
for dist_sum in result:
print(dist_sum)

</syntaxhighlight>

1200 – Spiriduși

2024-06-04T03:51:57Z

Danciu: Pagină nouă: Mei și Satsuki s-au întors de curând în casa de vacanță a familiei lor. Această casă este formată din <code>N</code> camere, unite între ele prin <code>N-1</code> culoare, astfel încât să se poată ajunge din orice cameră în orice altă cameră. Intrarea în casă se face prin camera <code>1</code>. Deoarece casa n-a fost locuită timp de mai multe luni, în fiecare cameră <code>i</code> s-au stabilit <code>s[i]</code> spiriduși de praf. Cele două fete dore...

Mei și Satsuki s-au întors de curând în casa de vacanță a familiei lor. Această casă este formată din <code>N</code> camere, unite între ele prin <code>N-1</code> culoare, astfel încât să se poată ajunge din orice cameră în orice altă cameră. Intrarea în casă se face prin camera <code>1</code>. Deoarece casa n-a fost locuită timp de mai multe luni, în fiecare cameră <code>i</code> s-au stabilit <code>s[i]</code> spiriduși de praf.

Cele două fete doresc să-și amenajeze un spațiu de joacă întins pe mai multe camere. Ele vor să stabilească două camere <code>a</code> și <code>b</code> (nu neapărat distincte), astfel încât drumul cel mai scurt de la intrarea în casă până în camera <code>b</code> trece prin camera <code>a</code>. Fetele vor merge apoi din camera <code>a</code> în camera <code>b</code> pe drumul cel mai scurt (fără a trece de două ori prin aceeași cameră), gonind spiridușii de praf aflați în fiecare cameră prin care trec, inclusiv pe cei din camerele <code>a</code> și <code>b</code>. După ce fetele ajung în camera <code>b</code>, ele consideră că toate camerele din care au gonit spiridușii de praf au fost alese pentru spațiul de joacă.

Fetele au stabilit pentru fiecare cameră <code>i</code> un coeficient <code>p[i]</code> care reprezintă cât de plăcută ar fi camera <code>i</code> pentru spațiul lor de joacă. În plus, ele au convenit că nu vor goni în total mai mult de <code>C</code> spiriduși ai prafului din camerele prin care trec.

= Cerința =
Cunoscând valorile lui <code>N</code> și <code>C</code>, numărul de spiriduși ai prafului <code>s[i]</code>, coeficienții <code>p[i]</code> pentru fiecare cameră <code>i</code>, cât și modul în care sunt unite camerele prin culoare, să se determine suma maximă a coeficienților <code>p</code> ai camerelor alese pentru un spațiu de joacă ce respectă condițiile impuse de Mei și Satsuki.

= Date de intrare =
Pe prima linie a fișierului de intrare <code>spiridusi.in</code> se vor afla două numere naturale <code>N</code> și <code>C</code> cu semnificația din enunț. Pe a doua linie se vor afla <code>N</code> numere naturale separate prin câte un spațiu, al <code>i</code>-lea dintre acestea reprezentând numărul de spiriduși <code>s[i]</code> aflați în camera <code>i</code>. Pe a treia linie se vor afla <code>N</code> numere întregi separate prin câte un spațiu, al <code>i</code>-lea dintre acestea reprezentând coeficientul <code>p[i]</code> al camerei <code>i</code>. Pe următoarele <code>N-1</code> linii se vor afla câte două numere întregi <code>x</code> și <code>y</code> separate printr-un spațiu, semnificând existența unui culoar ce unește camerele <code>x</code> și <code>y</code>.

= Date de ieșire =
În fișierul de ieșire <code>spiridusi.out</code> se va afișa o singură linie conținând un singur număr natural, reprezentând suma maximă a coeficienților <code>p</code> ai camerelor alese pentru un spațiu de joacă ce respectă condițiile impuse de Mei și Satsuki.

= Restricții și precizări =

* <code>1 ≤ N ≤ 100 000</code>
* <code>1 ≤ C ≤ 20 000 000</code>
* <code>1 ≤ s[i] ≤ 20 000 000</code>, pentru orice <code>i</code>, <code>1 ≤ i ≤ N</code>.
* <code>-10 000 ≤ p[i] ≤ 10 000</code>, pentru orice <code>i</code>, <code>1 ≤ i ≤ N</code>.
* <code>1 ≤ x, y ≤ N</code>
* Pentru 20% din teste, fiecare cameră are maximum <code>2</code> vecini.
* Pentru 30% din teste, <code>N ≤ 1 000</code>.
* Se garantează că pentru orice cameră <code>x</code>, numărul total de spiriduși aflați în camerele de pe drumul cel mai scurt de la camera <code>1</code> la camera <code>x</code> nu depășește <code>1 000 000 000</code>.

= Exemplu: =
<code>spiridusi.in</code>
6 8
2 4 6 2 4 1
3 10 11 -2 4 5
1 2
2 3
2 4
4 5
4 6
<code>spiridusi.out</code>
13

= Explicație =
Dacă alegem camerele <code>a = 2</code> și <code>b = 6</code>, obținem un spațiu de joacă format din camerele <code>2</code>, <code>4</code> și <code>6</code>.

Numărul total de spiriduși goniți din aceste camere este <code>4 + 2 + 1 = 7</code>, care este mai mic sau egal decât <code>C = 8</code>.

Suma coeficienților <code>p</code> ai acestor camere este <code>10 + (-2) + 5 = 13</code>, maximul posibil ce se poate obține.

== Rezolvare ==
<syntaxhighlight lang="python3">
import sys

nmax = 10**5
logmax = 17

dx = [[] for _ in range(nmax+5)]
up = [[0] * (logmax+5) for _ in range(nmax+5)]
sum_val = [[0] * (logmax+5) for _ in range(nmax+5)]
Psum = [[0] * (logmax+5) for _ in range(nmax+5)]

def build(node, father):
for i in range(1, logmax+1):
up[node][i] = up[up[node][i-1]][i-1]
sum_val[node][i] = sum_val[node][i-1] + sum_val[up[node][i-1]][i-1]
Psum[node][i] = Psum[node][i-1] + Psum[up[node][i-1]][i-1]
for next_node in dx[node]:
if next_node != father:
up[next_node][0] = node
sum_val[next_node][0] = s[node]
Psum[next_node][0] = p[node]
build(next_node, node)

def dfs(node, father):
for next_node in dx[node]:
if next_node != father:
if s[next_node] > c:
dfs(next_node, node)
else:
next_S = s[next_node]
next_P = p[next_node]
next_A = next_node
for i in range(logmax, -1, -1):
if up[next_A][i] and next_S + sum_val[next_A][i] <= c:
next_S += sum_val[next_A][i]
next_P += Psum[next_A][i]
next_A = up[next_A][i]
dp[next_node] = max(next_P, p[next_node])
dfs(next_node, node)

if __name__ == "__main__":
sys.stdin = open("spiridusi.in", "r")
sys.stdout = open("spiridusi.out", "w")

n, c = map(int, input().split())
s = [0] * (nmax+5)
p = [0] * (nmax+5)
dp = [0] * (nmax+5)
ans = 0

s_input = input().split()
p_input = input().split()

for i in range(1, n+1):
s[i] = int(s_input[i-1])
for i in range(1, n+1):
p[i] = int(p_input[i-1])
for i in range(1, n):
x, y = map(int, input().split())
dx[x].append(y)
dx[y].append(x)
build(1, 0)
if s[1] <= c:
dp[1] = p[1]
dfs(1, 0)
for i in range(1, n+1):
ans = max(ans, dp[i])
print(ans)

</syntaxhighlight>

1116 – Karb

2024-06-04T03:46:30Z

Danciu: Pagină nouă: În perioada Campionatului Mondial din Brazilia se preconizează o creştere a traficului de cafea. Se ştie că sunt <code>N</code> orase, conectate prin <code>N-1</code> străzi bidirecţionale, astfel încât se poate ajunge din orice oraş în altul. În prezent există <code>K</code> carteluri de cafea aflate în oraşe distincte, care își exercita influența în propriul oraș. Se ştie că fiecare din aceste carteluri doreşte să-şi extindă influenţa în oraşel...

În perioada Campionatului Mondial din Brazilia se preconizează o creştere a traficului de cafea. Se ştie că sunt <code>N</code> orase, conectate prin <code>N-1</code> străzi bidirecţionale, astfel încât se poate ajunge din orice oraş în altul. În prezent există <code>K</code> carteluri de cafea aflate în oraşe distincte, care își exercita influența în propriul oraș. Se ştie că fiecare din aceste carteluri doreşte să-şi extindă influenţa în oraşele vecine. Astfel, la un moment de timp, un cartel poate să-şi extindă influenţa într-un oraş vecin doar dacă acesta nu se află sub influenţa altui cartel. O dată ce un cartel îşi extinde influenta asupra unui nou oraş, cartelul îşi poate extinde influenţa şi în oraşele vecine acestuia. Se ştie că până la începerea campionatului mondial, fiecare oraş va fi sub influenţa unui cartel.

ABIN (Agência Brasileira de Inteligência) doreşte să afle în câte moduri poate fi dominată ţara de influenţele celor <code>K</code> carteluri la data începerii campionatului mondial, modulo <code>666013</code>.

= Cerință =
Cunoscând numărul de orașe <code>N</code>, modul în care acestea sunt conectate, numărul de carteluri inițiale <code>K</code> și cele <code>K</code> orașe în care se află cartelurile, să se determine numărul de moduri în care ţara poate fi împărţită între cartelurile de cafea, modulo <code>666013</code>.

= Date de intrare =
Fișierul de intrare <code>karb.in</code> conține pe prima linie două numere naturale <code>N</code> şi <code>K</code>, reprezentând numărul de oraşe, respectiv numărul cartelurilor existente iniţial. Pe a doua linie din fişier se vor afla <code>K</code> numere, reprezentând oraşele în care se află cele <code>K</code> carteluri. Pe următoarele <code>N-1</code> linii se vor afla câte două numere naturale, reprezentând o legătură între cele două oraşe.

= Date de ieșire =
Fișierul de ieșire <code>karb.out</code> va conține pe prima linie un singur număr natural reprezentând numărul de moduri modulo <code>666013</code>.

= Restricții și precizări =

* <code>1 ≤ K ≤ N ≤ 100 000</code>
* Pentru teste în valoare de 10% din punctaj se garantează că <code>k ≤ n ≤ 7</code>, iar pentru alte 20% din teste se garantează că <code>k = 2</code>.
* Două oraşe sunt vecine dacă există o stradă bidirecțională între ele.

= Exemplu: =
<code>karb.in</code>
6 3
3 4 5
1 2
1 3
2 4
2 5
4 6
<code>karb.out</code>
5

= Explicație =
Cele <code>5</code> moduri posibile:

# <code>(3) (1, 2, 5) (4, 6)</code>
# <code>(3, 1) (2, 5) (4, 6)</code>
# <code>(3, 1, 2) (5) (4, 6)</code>
# <code>(3, 1) (5) (2, 4, 6)</code>
# <code>(3) (5) (1, 2, 4, 6)</code>

== Rezolvare ==
<syntaxhighlight lang="python3">
import sys
from collections import defaultdict, deque

MOD = 666013

def dfs(nod, G, special, viz, T, D):
viz[nod] = True

sons = 0
for fiu in G[nod]:
if viz[fiu]:
continue
sons += 1
T[fiu] = nod
dfs(fiu, G, special, viz, T, D)

if sons == 0:
if special[nod]:
D[nod][0] = 0
D[nod][1] = 1
else:
D[nod][0] = 1
D[nod][1] = 0
return

localD = [[1] * (sons + 1), [0] * (sons + 1)]

ind = 0
for fiu in G[nod]:
if T[fiu] != nod:
continue

ind += 1
localD[0][ind] = (localD[0][ind - 1] * (D[fiu][0] + D[fiu][1])) % MOD
localD[1][ind] = (localD[0][ind - 1] * D[fiu][1] + localD[1][ind - 1] * (D[fiu][0] + D[fiu][1])) % MOD

if not special[nod]:
D[nod][0] = localD[0][ind]
D[nod][1] = localD[1][ind]
else:
D[nod][0] = 0
D[nod][1] = localD[0][ind]

def main():
sys.stdin = open("karb.in", "r")
sys.stdout = open("karb.out", "w")

n, k = map(int, sys.stdin.readline().split())
special = [0] * (n + 1)
viz = [False] * (n + 1)
T = [0] * (n + 1)
D = [[0, 0] for _ in range(n + 1)]
G = defaultdict(list)

cartel_cities = list(map(int, sys.stdin.readline().split()))
for x in cartel_cities:
special[x] = x

for _ in range(n - 1):
x, y = map(int, sys.stdin.readline().split())
G[x].append(y)
G[y].append(x)

dfs(1, G, special, viz, T, D)

print(D[1][1])

if __name__ == "__main__":
main()

</syntaxhighlight>

4063 – Cartierul

2024-06-04T03:40:37Z

Danciu: Pagină nouă: = Cerința = Avem în cartier un arbore cu nodurile colorate și cu rădăcina nodul <code>1</code>. Pentru fiecare nod <code>i</code> al arborelui să se afișeze câte culori distincte sunt în subarborele cu rădăcina în <code>i</code>. = Date de intrare = Programul citește de la tastatură numărul <code>n</code>, reprezentând numărul de noduri al arborelui. Pe a doua linie se vor afla <code>n</code> valori, cea de a <code>i</code> reprezentând culoarea nodului <c...

= Cerința =
Avem în cartier un arbore cu nodurile colorate și cu rădăcina nodul <code>1</code>. Pentru fiecare nod <code>i</code> al arborelui să se afișeze câte culori distincte sunt în subarborele cu rădăcina în <code>i</code>.

= Date de intrare =
Programul citește de la tastatură numărul <code>n</code>, reprezentând numărul de noduri al arborelui. Pe a doua linie se vor afla <code>n</code> valori, cea de a <code>i</code> reprezentând culoarea nodului <code>i</code>. Urmează <code>n-1</code> linii, pe fiecare linie aflânduse <code>2</code> numere <code>a b</code> indicând faptul ca între <code>a</code> și <code>b</code> este muchie.

= Date de ieșire =
Programul va afișa pe ecran <code>n</code> numere, cel de al <code>i</code>-lea fiind numărul de culori distincte din subarborele cu rădăcina în <code>i</code>.

= Restricții și precizări =

* <code>1 ≤ n ≤ 200.000</code>
* Culorile arborelui sunt numere naturale mai mici sau egale cu <code>1.000.000.000</code>

= Exemplu: =
Intrare
5
2 3 2 2 1
1 2
1 3
3 4
3 5
Ieșire
3 1 2 1 1

== Rezovlare ==
<syntaxhighlight lang="python3">
from collections import defaultdict, deque

def distinct_colors_in_subtrees(n, colors, edges):

tree = defaultdict(list)
for a, b in edges:
tree[a].append(b)
tree[b].append(a)

subtree_colors = [set() for _ in range(n + 1)]
result = [0] * (n + 1)
visited = [False] * (n + 1)

def dfs(node):
visited[node] = True
subtree_colors[node].add(colors[node - 1]) # Add the color of the current node
for neighbor in tree[node]:
if not visited[neighbor]:
dfs(neighbor)
# Merge the color sets of the subtrees
if len(subtree_colors[neighbor]) > len(subtree_colors[node]):
subtree_colors[node], subtree_colors[neighbor] = subtree_colors[neighbor], subtree_colors[node]
subtree_colors[node].update(subtree_colors[neighbor])
result[node] = len(subtree_colors[node])

dfs(1)

return result[1:]

n = int(input())
colors = list(map(int, input().split()))
edges = [tuple(map(int, input().split())) for _ in range(n - 1)]

result = distinct_colors_in_subtrees(n, colors, edges)

print("\n".join(map(str, result)))

</syntaxhighlight>

4155 - Harta3

2024-06-04T03:30:31Z

Danciu: Pagină nouă: = Cerința = Harta unei regiuni este reprezentată într-un sistem de coordonate cartezian și sunt cunoscute coordonatele a <code>n</code> orașe, numerotate de la <code>1</code> la <code>n</code>. Se dorește construirea unor drumuri bidirecționale între anumite perechi de orașe, astfel încât: * să se poate ajunge din orice oraș în oricare altul folosind unul sau mai multe dintre drumurile construite; * suma lungimilor drumurilor construite să fie minimă. Să...

= Cerința =
Harta unei regiuni este reprezentată într-un sistem de coordonate cartezian și sunt cunoscute coordonatele a <code>n</code> orașe, numerotate de la <code>1</code> la <code>n</code>.

Se dorește construirea unor drumuri bidirecționale între anumite perechi de orașe, astfel încât:

* să se poate ajunge din orice oraș în oricare altul folosind unul sau mai multe dintre drumurile construite;
* suma lungimilor drumurilor construite să fie minimă.

Să se determine suma lungimilor drumurilor construite.

= Date de intrare =
Fișierul de intrare <code>harta3.in</code> conține pe prima linie numărul de orașe <code>n</code>, iar pe fiecare dintre următoarele <code>n</code> linii câte două numere întregi <code>x y</code>, reprezentând coordonatele acestora.

= Date de ieșire =
Fișierul de ieșire <code>harta3.out</code> va conține pe prima linie suma lungimilor drumurilor construite, cu cel puțin trei zecimale exacte.

= Restricții și precizări =

* <code>1 ≤ n ≤ 100</code>;
* coordonatele orașelor sunt din intervalul <code>[-200, 200]</code>;
* lungimea drumului dintre două orașe se determină cu formula , unde și sunt coordonatele acestora.

= Exemplu: =
<code>harta3.in</code>
4
1 2
2 -1
6 5
4 2
<code>harta3.out</code>
9.7678

== Explicație ==

== Rezolvare ==
<syntaxhighlight lang="python3">
import math

class Muchie:
def __init__(self, i, j, cost):
self.i = i
self.j = j
self.cost = cost

def find(P, i):
if P[i] == i:
return i
else:
P[i] = find(P, P[i])
return P[i]

def union(P, rank, x, y):
root_x = find(P, x)
root_y = find(P, y)
if root_x != root_y:
if rank[root_x] > rank[root_y]:
P[root_y] = root_x
elif rank[root_x] < rank[root_y]:
P[root_x] = root_y
else:
P[root_y] = root_x
rank[root_x] += 1

def main():
with open("harta3.in", "r") as fin:
n = int(fin.readline().strip())
x = [0] * (n + 1)
y = [0] * (n + 1)
for i in range(1, n + 1):
x[i], y[i] = map(int, fin.readline().strip().split())

M = []
for i in range(1, n):
for j in range(i + 1, n + 1):
cost = math.sqrt((x[i] - x[j]) ** 2 + (y[i] - y[j]) ** 2)
M.append(Muchie(i, j, cost))

M.sort(key=lambda muchie: muchie.cost)

P = [i for i in range(n + 1)]
rank = [0] * (n + 1)
S = 0.0

for muchie in M:
if find(P, muchie.i) != find(P, muchie.j):
union(P, rank, muchie.i, muchie.j)
S += muchie.cost

with open("harta3.out", "w") as fout:
fout.write(f"{S:.4f}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

4118 - regate

2024-06-04T03:27:09Z

Danciu: Pagină nouă: În tărâmul ONI se află <code>N</code> regate legate între ele prin <code>M</code> muchii bidirecționale. Se garantează că se poate ajunge de la orice regat la oricare alt regat folosind aceste muchii. Aceste regate vor să facă alianțe între ele și se vor folosi de puncte de frontieră pentru a realiza acest lucru. Fiecare muchie <code>i</code>, unde <code>1 ≤ i ≤ M</code>, are asociat un număr natural <code>c[i]</code> reprezentând costul construcției unu...

În tărâmul ONI se află <code>N</code> regate legate între ele prin <code>M</code> muchii bidirecționale. Se garantează că se poate ajunge de la orice regat la oricare alt regat folosind aceste muchii. Aceste regate vor să facă alianțe între ele și se vor folosi de puncte de frontieră pentru a realiza acest lucru.

Fiecare muchie <code>i</code>, unde <code>1 ≤ i ≤ M</code>, are asociat un număr natural <code>c[i]</code> reprezentând costul construcției unui punct de frontieră pe aceasta. Mai mult decât atât, fiecare regat <code>i</code>, unde <code>1 ≤ i ≤ N</code>, are asociat un număr natural <code>r[i]</code> reprezentând costul construcției unui punct de frontieră la intrarea acestuia.

Pentru ca regatul <code>X</code> să intre într-o alianță cu regatul <code>Y</code>, unde <code>1 ≤ X, Y ≤ N, X ≠ Y</code>, acesta are două opțiuni:

* construiește un punct de frontieră pe o singură muchie <code>i</code> cu cost <code>c[i]</code>, astfel încât orice drum de la <code>X</code> la <code>Y</code> trece prin acest punct de frontieră;
* construiește un punct de frontieră la intrarea regatului său (regatului <code>X</code>) cu cost <code>r[X]</code>.

Evident, regatul <code>X</code> va alege costul minim pentru a intra într-o alianță cu regatul <code>Y</code>. Vom nota acest cost minim cu <code>Cost(X, Y)</code>. Atenție, costul ca regatul <code>X</code> să intre într-o alianță cu regatul <code>Y</code> poate fi diferit de costul ca regatul <code>Y</code> să intre într-o alianță cu regatul <code>X</code>!

Pentru ca regatul <code>X</code> să fie într-o alianță perfectă acesta trebuie să facă alianță cu toate celalate regate.

Atenție, în formarea unei alianțe nu se iau în considerare punctele de frontieră construite în formarea altor alianțe. Cu alte cuvinte, <code>Cost(X, Y)</code> se calculează independent pentru fiecare pereche <code>(X, Y)</code>!

= Cerința =
Pentru fiecare regat trebuie să calculați costul pe care acesta trebuie să-l plătească pentru a fi într-o alianță perfectă. Cu alte cuvinte, pentru fiecare regat <code>i</code>, unde <code>1 ≤ i ≤ N</code>, trebuie să calculați .

= Date de intrare =
Pe prima linie a fișierului de intrare <code>regate.in</code> se află <code>N</code> și <code>M</code>, numărul de regate, respectiv, numărul de muchii bidirecționale. Pe a doua linie se găsesc numerele <code>r[1]</code>, …, <code>r[N]</code>, separate prin spații, unde <code>r[i]</code> reprezintă costul construcției unui punct de frontieră la intrarea regatului <code>i</code>. Pe următoarele <code>M</code> linii se află câte trei numere naturale <code>a[i]</code>, <code>b[i]</code>, <code>c[i]</code>, separate prin spații, <code>1 ≤ i ≤ M</code>, semnificând că există o muchie bidirecțională între regatul <code>a[i]</code> și regatul <code>b[i]</code>, iar <code>c[i]</code> reprezintă costul construcției unui punct de frontieră pe muchia <code>i</code>.

= Date de ieșire =
În fișierul de ieșire <code>regate.out</code> se vor afișa <code>N</code> linii. Fiecare linie <code>i</code> va conține un singur număr întreg, reprezentând costul ce trebuie plătit pentru ca regatul <code>i</code> să fie într-o alianță perfectă, cu alte cuvinte, .

= Restricții și precizări =

* <code>1 ≤ N ≤ 200.000</code>
* <code>1 ≤ M ≤ 200.000</code>
* <code>1 ≤ c[i]≤ 1.000.000.000</code>
* <code>1 ≤ r[i] ≤ 1.000.000.000</code>
* <code>1 ≤ a[i], b[i] ≤ N</code>, <code>a[i] ≠ b[i]</code> (adică nu există muchie de la un regat la el insuși)
* Între două regate poate exista cel mult o muchie
* Datorită dimensiunilor foarte mari, doar o parte din teste au putut fi folosite.

= Exemplu: =
<code>regate.in</code>
5 5
8 13 9 7 12
1 2 10
2 3 10
3 4 10
4 5 10
1 3 10
<code>regate.out</code>
32
46
36
28
40

=== Explicație ===
De exemplu, pentru regatul <code>2</code> avem:

<code>Cost(2, 1) = 13</code>

<code>Cost(2, 3) = 13</code>

<code>Cost(2, 4) = 10</code>

<code>Cost(2, 5) = 10</code>

Suma acestora este <code>46</code>.

Atenție că, de exemplu, în calculul lui <code>Cost(2, 1)</code>, nu putem pune un punct de frontieră pe muchia <code>(1 ,2)</code> de cost <code>10</code>, deoarece există drumul <code>2 → 3 → 1</code> care nu trece prin muchia <code>(1, 2)</code>.

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

class Graph:
def __init__(self, n):
self.n = n
self.adj_list = [[] for _ in range(n)]

def add_edge(self, u, v, w):
self.adj_list[u].append((v, w))
self.adj_list[v].append((u, w))

def dijkstra(self, src):
dist = [float('inf')] * self.n
dist[src] = 0
pq = [(0, src)]

while pq:
cost, node = heapq.heappop(pq)
if cost > dist[node]:
continue
for neighbor, edge_cost in self.adj_list[node]:
new_cost = cost + edge_cost
if new_cost < dist[neighbor]:
dist[neighbor] = new_cost
heapq.heappush(pq, (new_cost, neighbor))
return dist

def main():
# Citire date de intrare
with open("regate.in", "r") as fin:
N, M = map(int, fin.readline().split())
r = list(map(int, fin.readline().split()))
graph = Graph(N)
for _ in range(M):
a, b, c = map(int, fin.readline().split())
graph.add_edge(a - 1, b - 1, c)

# Calcul costuri minime pentru fiecare regat
total_costs = []
for i in range(N):
dist = graph.dijkstra(i)
total_cost = 0
for j in range(N):
if i != j:
min_edge_cost = min(edge_cost for neighbor, edge_cost in graph.adj_list[j])
total_cost += min(dist[j], r[j], min_edge_cost)
total_costs.append(total_cost)

# Scriere rezultate
with open("regate.out", "w") as fout:
for cost in total_costs:
fout.write(str(cost) + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

3446 - Ateleport

2024-06-04T03:15:45Z

Danciu: Pagină nouă: Marian se află în galaxia OJI-2020 și este anul 11235. În această galaxie există <code>N</code> planete diferite și <code>M</code> canale bidirecţionale de transport de tipul <code>(x, y, t)</code> care îţi permit să te deplasezi de pe planeta <code>x</code> pe planeta <code>y</code> (sau invers) în <code>t</code> secunde. Dar Marian este un adevărat inginer și, pentru că i se pare foarte ineficientă această metodă de transport, a dezvoltat un dispozitiv ca...

Marian se află în galaxia OJI-2020 și este anul 11235. În această galaxie există <code>N</code> planete diferite și <code>M</code> canale bidirecţionale de transport de tipul <code>(x, y, t)</code> care îţi permit să te deplasezi de pe planeta <code>x</code> pe planeta <code>y</code> (sau invers) în <code>t</code> secunde.

Dar Marian este un adevărat inginer și, pentru că i se pare foarte ineficientă această metodă de transport, a dezvoltat un dispozitiv care îți permite teleportarea de pe o planetă <code>x</code> pe orice altă planetă <code>y</code> în <code>P</code> secunde cu condiţia că ai putea ajunge pornind de pe planeta <code>x</code> pe planeta <code>y</code> folosind maxim <code>L</code> canale de transport.

Acest dispozitiv este momentan doar un prototip, așa că nu îl poate folosi mai mult de <code>K</code> ori. Marian se află pe planeta <code>1</code> și te roagă să îi spui care e timpul minim necesar pentru a ajunge pe planeta <code>N</code>.

= Cerința =
Să se scrie un program care calculează timpul minim necesar pentru a ajunge pe planeta <code>N</code> pornind de pe planeta <code>1</code>.

= Date de intrare =
Fișierul de intrare <code>ateleport.in</code> conține pe prima linie <code>5</code> valori <code>N</code>, <code>M</code>, <code>P</code>, <code>L</code>, <code>K</code>, separate printr-un singur spaţiu, cu semnificaţia din enunţ.

Pe fiecare din următoarele <code>M</code> linii se vor afla câte <code>3</code> valori <code>Xi</code>, <code>Yi</code>, <code>Ti</code> care descriu un canal de transport.

= Date de ieșire =
Fișierul de ieșire <code>ateleport.out</code> va conține o singură valoare pe prima linie care reprezintă

timpul minim necesar pentru a ajunge pe planeta <code>N</code> pornind de pe planeta <code>1</code>.

= Restricții și precizări =

* <code>1 < N, M ≤ 10 000</code>;
* <code>0 ≤ L, K ≤ 10</code>;
* <code>1 < Ti</code> <code>, P ≤ 100 000</code>;
* <code>1 < Xi</code> <code>, Yi ≤ N</code>;
* între oricare două planete există cel mult un canal;
* pentru teste în valoare de 30 de puncte se garantează că <code>K = 0</code> și toate canalele de comunicare au <code>Ti = 1</code>;
* pentru ALTE teste în valoare de 20 de puncte se garantează că <code>K = 0</code>;
* pentru ALTE teste în valoare de 20 de puncte se garantează că <code>N ≤ 300</code>;
* se garantează că pentru toate testele există soluţie;
* în concurs s-au acordat 10 puncte din oficiu. Pe site se acordă 10 puncte pentru exemple.

= Exemplul 1 =
<code>ateleport.in</code>
6 7 3 2 1
1 2 2
1 3 5
2 3 4
2 4 23
3 4 6
5 4 7
5 6 9
<code>ateleport.out</code>
14

=== Explicație ===
Dispozitivul se poate folosi cel mult o dată. Pentru a ajunge pe planeta <code>6</code> în timp minim vom parcurge canalul <code>1 → 2</code> apoi ne vom teleporta până pe planeta <code>5</code> de unde vom mai parcurge canalul <code>5 → 6</code>. Costul final este <code>2 + 3</code>(teleportare) <code>+ 9 = 14</code>.

= Exemplul 1 =
<code>ateleport.in</code>
6 7 3 2 0
1 2 2
1 3 5
2 3 4
2 4 23
3 4 6
5 4 7
5 6 9
<code>ateleport.out</code>
27

=== Explicație ===
Dispozitivul nu se poate folosi deloc. Pentru a ajunge pe planeta <code>6</code> de pe planeta <code>1</code> în timp minim, se vor parcurge canalele în ordinea <code>1→3→4→5→6</code> și se obține timpul <code>5+6+7+9=27</code> de secunde.

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

fin = open("ateleport.in", "r")
fout = open("ateleport.out", "w")

NMAX = 10001
TMAX = 11

class Muchie:
def __init__(self, to, cost):
self.to = to
self.cost = cost

muchii = [[] for _ in range(NMAX)]
timp = [[[float('inf') for _ in range(TMAX)] for _ in range(TMAX)] for _ in range(NMAX)]

def ini(n):
for i in range(1, n + 1):
for j in range(11):
for k in range(11):
timp[i][j][k] = float('inf')

class Element:
def __init__(self, nod, tp, p):
self.nod = nod
self.tp = tp
self.p = p

def __lt__(self, other):
return timp[other.nod][other.tp][other.p] < timp[self.nod][self.tp][self.p]

def dijkstra(destinatie, l, k, p):
timp[1][0][0] = 0
pq = []
heapq.heappush(pq, Element(1, 0, 0))

while pq:
relax = heapq.heappop(pq)

for it in muchii[relax.nod]:
# nu ma teleportez
if timp[it.to][relax.tp][0] > timp[relax.nod][relax.tp][relax.p] + it.cost:
timp[it.to][relax.tp][0] = timp[relax.nod][relax.tp][relax.p] + it.cost
heapq.heappush(pq, Element(it.to, relax.tp, 0))

# incep o teleportare
if relax.tp < k:
if timp[it.to][relax.tp + 1][1] > timp[relax.nod][relax.tp][relax.p] + p:
timp[it.to][relax.tp + 1][1] = timp[relax.nod][relax.tp][relax.p] + p
heapq.heappush(pq, Element(it.to, relax.tp + 1, 1))

# continui o teleportare
if relax.p and relax.p < l:
if timp[it.to][relax.tp][relax.p + 1] > timp[relax.nod][relax.tp][relax.p]:
timp[it.to][relax.tp][relax.p + 1] = timp[relax.nod][relax.tp][relax.p]
heapq.heappush(pq, Element(it.to, relax.tp, relax.p + 1))

ans = float('inf')
for j in range(k + 1):
for m in range(l + 1):
ans = min(ans, timp[destinatie][j][m])

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

if __name__ == "__main__":
n, m, p, l, k = map(int, fin.readline().split())
ini(n)

for _ in range(m):
a, b, c = map(int, fin.readline().split())
muchii[a].append(Muchie(b, c))
muchii[b].append(Muchie(a, c))

dijkstra(n, l, k, p)

fin.close()
fout.close()

</syntaxhighlight>

3325 - Ohoo

2024-06-04T03:09:54Z

Danciu: Pagină nouă: == Cerinta == Porumbeii au pornit un război crâncen împotriva ciorilor, dar ele au construit garduri defensive pe toate rutele pe care le-ar putea folosi armata porumbeilor pentru a le ataca cetatea. Pentru a ajunge la cetatea ciorilor armata trebuie sa treacă de gardurile construite de ciori. Pentru că porumbeii obosesc din cauza zborului ei trebuie sa se odihneasca pe statui, astfel armata poate merge doar pe drumurile cunoscute dintre două statui. Există n statui,...

== Cerinta ==
Porumbeii au pornit un război crâncen împotriva ciorilor, dar ele au construit garduri defensive pe toate rutele pe care le-ar putea folosi armata porumbeilor pentru a le ataca cetatea. Pentru a ajunge la cetatea ciorilor armata trebuie sa treacă de gardurile construite de ciori.

Pentru că porumbeii obosesc din cauza zborului ei trebuie sa se odihneasca pe statui, astfel armata poate merge doar pe drumurile cunoscute dintre două statui. Există n statui, iar armata se află inițial pe statuia cu numărul 1, iar cetatea ciorilor se va afla pe cea cu numărul n.

Armata porumbeilor deține un cioc bionic de putere K. Acesta poate sparge garduri cu rezistență mai mica sau egala cu K, armata putând astfel să treacă pe acel drum.

Generalul armatei porumbeilor vă cere să găsiți puterea minimă pe care o poate avea ciocul bionic pentru ca armata să poată ajunge la cetatea ciorilor

== Date de intrare ==
Fișierul de intrare Ohoo.in va conține: Pe prima linie numărul natural n reprezentând numărul de statui și numărul natural m reprezentând numărul de drumuri existente între statui. Pe următoarele m linii se vor găsi câte 3 numere: x, y, r, cu semnificația că există un drum bidirecțional între statuile x și y blocat de un gard de rezistență r.

== Date de iesire ==
Fișierul de ieșire Ohoo.out va conține un singur număr natural K, reprezentând puterea minimă pe care o poate avea ciocul bionic astfel încât armata să poată ajunge la cetatea ciorilor.

== Restrictii si precizari: ==
2 ≤ n ≤ 100.000

1 ≤ m ≤ 250.000

Rezistențele gardurilor sunt numere naturale nenule și nu depășesc 1.000.000

Între două statui pot exista mai multe drumuri cu garduri de rezistențe diferite

Întotdeauna există soluție

Pentru 60% din teste n ≤ 1000 și K ≤ 1000

Se acordă 10 puncte pentru exemplu

Atenție la numele fișirelor de intrare și de ieșire!

== Exemplu ==
Ohoo.in

5 6

1 2 3

1 4 1

2 3 2

3 5 3

4 5 4

3 4 4

Ohoo.out

3

== Explicatie ==
Alegem drumul <code>1-2-3-5</code> folosind o putere maximă de <code>3</code>.

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

def dfs(node, d):
global t
if node == n:
t = True
else:
vis[node] = True
for i, c in graph[node]:
if not t and c <= d and not vis[i]:
dfs(i, d)

def main():
global n, m, vis, t, graph
with open("Ohoo.in", "r") as fin:
n, m = map(int, fin.readline().split())
graph = defaultdict(list)
mz = 0

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

st, dr, sol = 1, mz, mz
while st <= dr:
mij = (st + dr) // 2
vis = [False] * (n + 1)
t = False
dfs(1, mij)
if t:
sol = mij
dr = mij - 1
else:
st = mij + 1

with open("Ohoo.out", "w") as fout:
fout.write(str(sol) + '\n')

if __name__ == "__main__":
main()

</syntaxhighlight>

3061 - oracol

2024-06-04T03:04:00Z

Danciu: Pagină nouă: Gustavo, după ce a realizat că posedă abilitatea de a vedea în viitor, a decis că a venit momentul să treacă la următorul nivel și să-și valorifice capacitățile extrasenzoriale. Pentru a câștiga prestigiu și a deveni mai cunoscut în rândurile magicienilor profesioniști, acesta a ales să debuteze la Olimpiada Națională de Informatică prin prezicerea datelor de intrare pentru anumite probleme propuse în concurs. Primul client al lui Gustavo, Alfredo, ar...

Gustavo, după ce a realizat că posedă abilitatea de a vedea în viitor, a decis că a venit momentul să treacă la următorul nivel și să-și valorifice capacitățile extrasenzoriale. Pentru a câștiga prestigiu și a deveni mai cunoscut în rândurile magicienilor profesioniști, acesta a ales să debuteze la Olimpiada Națională de Informatică prin prezicerea datelor de intrare pentru anumite probleme propuse în concurs. Primul client al lui Gustavo, Alfredo, ar dori să afle într-un mod inedit conținutul unui fișier de intrare aferent unei probleme de concurs, în care sunt scrise elementele unui șir <code>p</code> de <code>N</code> numere întregi. Pentru a face lucrurile mai interesante, Gustavo îi percepe o taxă de <code>C(i,j)</code> bănuți pentru a-i divulga suma numerelor din șirul <code>p</code> cu indici în intervalul <code>[i, j]</code>, anume <code>pi</code> <code>+ pi+1</code> <code>+ ... + pj</code>.

= Cerința =
Dându-se valoarea lui <code>N</code> și toate valorile <code>C(i,j)</code> cu <code>1 ≤ i ≤ j ≤ N</code>, determinați costul total minim pe care trebuie să-l plătească Alfredo pentru a afla toate elementele șirului <code>p</code>.

= Date de intrare =
În fișierul <code>oracol.in</code> se află pe prima linie numărul natural <code>N</code>. Pe următoarele <code>N</code> linii se află taxele percepute de Gustavo astfel: pe linia <code>i+1</code> se vor afla <code>N-i+1</code> numere naturale separate prin câte un spațiu, reprezentând în ordine costurile <code>C(i,i)</code>, <code>C(i,i+1)</code>, …, <code>C(i,N)</code>.

= Date de ieșire =
Fișierul de ieșire <code>oracol.out</code> va conține pe prima linie un singur număr care reprezintă costul total minim pe care trebuie să-l plătească Alfredo pentru a afla șirul <code>p</code>.

= Restricții și precizări =

* <code>1 ≤ N ≤ 1000</code>;
* pentru orice <code>1 ≤ i ≤ j ≤ N</code> se garantează <code>0 ≤ C(i,j) ≤ 1.000.000</code>;
* pentru teste în valoare de <code>48</code> puncte <code>1 ≤ N ≤ 250</code>.

= Exemplu: =
<code>oracol.in</code>
3
4 5 1
6 3
2
<code>oracol.out</code>
6

=== Explicație ===
Costul total minim este <code>6</code> și se obține astfel:

Cu un cost de valoare <code>C(1,3) = 1</code> putem afla suma <code>p1</code> <code>+ p2</code> <code>+ p3</code>.

Cu un cost de valoare <code>C(3,3) = 2</code> putem afla valoarea lui <code>p3</code>.

Cu un cost de valoare <code>C(2,3) = 3</code> putem afla suma <code>p2</code> <code>+ p3</code>.

Din acestea putem afla exact toate elementele șirului <code>p</code>.

== Rezolvare ==
<syntaxhighlight lang="python3">
class DSU:
def __init__(self, n):
self.f = list(range(n))

def find(self, x):
if self.f[x] != x:
self.f[x] = self.find(self.f[x])
return self.f[x]

def union(self, x, y):
self.f[self.find(x)] = self.find(y)

def main():
with open("oracol.in", "r") as fin:
n = int(fin.readline())
costs = []
for _ in range(n):
row = list(map(int, fin.readline().split()))
costs.extend(row)

edges = []
for i in range(n):
for j in range(i + 1, n + 1):
cost = costs.pop(0)
edges.append((i, j, cost))

edges.sort(key=lambda x: x[2])
f = DSU(n + 1)
ans = 0
for e in edges:
if f.find(e[0]) != f.find(e[1]):
ans += e[2]
f.union(e[0], e[1])

with open("oracol.out", "w") as fout:
fout.write(str(ans) + '\n')

if __name__ == "__main__":
main()

</syntaxhighlight>

2933 - TollRoads

2024-06-04T03:00:30Z

Danciu: Pagină nouă: = Cerința = <code>N</code> orașe sunt conectate între ele prin <code>M</code> autostrăzi bidirecționale, fiecare autostradă <code>(a, b)</code> având un cost de tranzit <code>c</code> atașat. Se dorește revizuirea sistemului de taxare, însă sunt câteva aspecte ce trebuie luate în calcul și necesită investigație, deoarece o parte dintre cele <code>N</code> orașe sunt centre comerciale sau turistice importante. Se dorește să se afle răspunsul la o serie de...

= Cerința =
<code>N</code> orașe sunt conectate între ele prin <code>M</code> autostrăzi bidirecționale, fiecare autostradă <code>(a, b)</code> având un cost de tranzit <code>c</code> atașat. Se dorește revizuirea sistemului de taxare, însă sunt câteva aspecte ce trebuie luate în calcul și necesită investigație, deoarece o parte dintre cele <code>N</code> orașe sunt centre comerciale sau turistice importante.

Se dorește să se afle răspunsul la o serie de <code>Q</code> întrebări de forma: <code>(X, T)</code> – câte dintre celelalte <code>N-1</code> orașe au acces către orașul <code>X</code>, cu o taxă totală de cel mult <code>T</code> către fiecare oraș?

= Date de intrare =
Fișierul de intrare <code>tollroads.in</code> conține pe primul rând numerele <code>N, M și Q</code> reprezentând numărul de orașe, numărul de autostrăzi și numărul de interogări. Pe fiecare din următoarele <code>M</code> rânduri sunt scrise câte trei numere <code>a, b, c,</code> separate prin câte un spațiu, reprezentând două orașe între care există o autostradă și costul autostrăzii. Pe următoarele <code>Q</code> rânduri se află scrise câte două numere <code>X</code> și <code>T</code>, separate prin spațiu, reprezentând datele interogărilor, conform enunțului.

= Date de ieșire =
În fișierul de ieșire <code>tollroads.out</code> se vor scrie pe fiecare dintre primele <code>Q</code> rânduri câte un singur număr, reprezentând răspunsurile la interogări, în ordinea în care ele au fost puse.

= Restricții și precizări =

* <code>1 ≤ N ≤ 100.000</code>
* <code>1 ≤ M ≤ 100.000</code>
* <code>1 ≤ a, b ≤ N</code>
* <code>1 ≤ c ≤ 100.000</code>
* <code>1 ≤ T ≤ 100.000</code>
* <code>1 ≤ Q ≤ 100</code>
* între orice două orașe poate exista mai mult de o autostrada

= Exemplu: =
<code>tollroads.in</code>
7 8 5
1 2 1
2 3 2
2 4 4
3 5 1
4 5 1
5 6 2
1 6 5
6 7 1
1 6
1 5
1 4
2 3
4 4
<code>tollroads.out</code>
6
5
3
3
5

=== Explicație ===
Orașele <code>2,3,4,5,6,7</code> au acces către orașul <code>1</code> cu taxă maximă <code>6</code>

Orașele <code>2,3,4,5,6</code> au acces către orașul <code>1</code> cu taxă maximă <code>5</code>

Orașele <code>2,3,5</code> au acces către orașul <code>1</code> cu taxă maximă <code>4</code>

Orașele <code>1,3,5</code> au acces către orașul <code>2</code> cu taxă maximă <code>3</code>

Orașele <code>2,3,5,6,7</code> au acces către orașul <code>4</code> cu taxă maximă <code>4</code>

== Rezolvare ==
<syntaxhighlight lang="python3">
from collections import defaultdict, deque

INF = 2000000002

def main():
f = open("tollroads.in", "r")
g = open("tollroads.out", "w")

n, m, Q = map(int, f.readline().split())

graph = defaultdict(list)
for _ in range(m):
x, y, c = map(int, f.readline().split())
graph[x].append((y, c))
graph[y].append((x, c))

for _ in range(Q):
nod, taxa = map(int, f.readline().split())
dr = [INF] * (n + 1)
din = [[] for _ in range(taxa + 1)]

din[0].append(nod)
dr[nod] = sol = 0

viz = [False] * (n + 1)

for i in range(taxa + 1):
for nod in din[i]:
if viz[nod]:
continue
for ve, co in graph[nod]:
if dr[nod] + co > taxa or viz[ve]:
continue
if dr[ve] > dr[nod] + co:
dr[ve] = dr[nod] + co
din[dr[ve]].append(ve)
viz[nod] = True
din[i] = []

for i in range(1, n + 1):
viz[i] = False
if dr[i] != INF:
sol += 1

g.write(str(sol - 1) + '\n')

f.close()
g.close()

if __name__ == "__main__":
main()

</syntaxhighlight>

2539 - flori4

2024-06-04T02:57:25Z

Danciu: Pagină nouă: Compania lui Jimmy are <code>n</code> plantații cu flori. Pentru fiecare plantație se cunoaște tipul florilor cultivate, respectiv câte tone de flori au fost produse anul acesta. Se cunoaște că plantațiile cu flori sunt conectate prin <code>n - 1</code> drumuri astfel încât la fiecare plantație se poate ajunge de la oricare altă plantație și există un singur mod de ajunge de la plantația <code>x</code> la plantația <code>y</code> , pentru fiecare <code>1 ≤...

Compania lui Jimmy are <code>n</code> plantații cu flori. Pentru fiecare plantație se cunoaște tipul florilor cultivate, respectiv câte tone de flori au fost produse anul acesta. Se cunoaște că plantațiile cu flori sunt conectate prin <code>n - 1</code> drumuri astfel încât la fiecare plantație se poate ajunge de la oricare altă plantație și există un singur mod de ajunge de la plantația <code>x</code> la plantația <code>y</code> , pentru fiecare <code>1 ≤ x, y ≤ n</code>. De asemenea, știm și distanța în km pentru fiecare dintre cele <code>n - 1</code> drumuri.

= Cerința =
Jimmy vrea să aducă toate florile de același tip în același loc, cu cost minim de transport. Dacă avem <code>a</code> tone de flori şi vrem să le trimitem pe o distanță de <code>b</code> kilometri, costul transportului este <code>a * b</code>. Pentru fiecare tip de floare Jimmy vrea să determine costul minim de transport pentru a aduce toate florile de același tip la un loc.

= Date de intrare =
Pe prima linie se va găsi numărul <code>n</code>, apoi, pe cea de-a doua linie, <code>n</code> litere mici separate între ele prin câte un spațiu, care simbolizează tipul de floare produs pe plantația <code>i</code> (fiecare tip de floare este o literă mică a alfabetului englez). Pe cea de-a treia linie se găsesc <code>n</code> numere întregi care reprezintă câte tone din fiecare floare au fost produse pe plantația <code>i</code>. Pe fiecare dintre următoarele <code>n - 1</code> linii se găsesc trei numere naturale <code>x</code>, <code>y</code>, <code>d</code>, cu semnificația că există drum direct între plantațiile <code>x</code> şi <code>y</code>, iar numărul <code>d</code> reprezintă distanța de la <code>x</code> la <code>y</code>.

= Date de ieșire =
Pe prima linie se afișează <code>26</code> de numere separate prin spațiu, al <code>i</code>-lea număr reprezentând costul minim de transport pentru tipul de floare specificat de litera de pe poziția <code>i</code> în alfabetul englez (răspunsurile sunt în ordinea în care literele se găsesc în alfabet).

= Restricții și precizări =

* <code>4 ≤ n < 200 001</code>.
* Fiecare dintre numerele din datele de intrare este un număr natural mai mic decât <code>200 001</code>.
* Destinaţia finală a fiecărui transport este una dintre cele <code>n</code> plantaţii existente.
* Dacă există litere care nu reprezintă codul tipului unei flori, atunci costul minim de transport pentru acel tip este <code>0</code>.
* Pentru <code>20%</code> din teste, <code>n < 1000</code>.
* Pentru alte <code>25%</code> din teste, <code>n < 100 000</code>.

= Exemplu: =
Intrare
4
a b a b
2 4 4 3
1 3 4
3 4 2
1 2 5
Ieșire
8 33 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

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

def dijkstra(graph, start):
n = len(graph)
dist = [float('inf')] * n
dist[start] = 0
pq = [(0, start)] # Priority queue of tuples (distance, vertex)

while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(pq, (dist[v], v))

return dist

def calculate_transport_cost(types, quantities, distances):
n = len(types)
types_cost = [0] * 26

for t in range(26):
nodes = {i for i in range(n) if ord(types[i]) - ord('a') == t}
if not nodes:
continue

dist = dijkstra(distances, next(iter(nodes))) # Selectăm primul nod din set
for i in range(n):
if ord(types[i]) - ord('a') == t:
types_cost[t] += quantities[i] * dist[i]

return types_cost

n = int(input())
types = input().split()
quantities = list(map(int, input().split()))

distances = [[] for _ in range(n)]
for _ in range(n - 1):
x, y, d = map(int, input().split())
distances[x - 1].append((y - 1, d))
distances[y - 1].append((x - 1, d))

result = calculate_transport_cost(types, quantities, distances)

print(*result)

</syntaxhighlight>

4244 - urgenta

2024-06-04T02:43:09Z

Danciu: Pagină nouă: Autorităţile dintr-o zonă de munte intenţionează să stabilească un plan de urgenţă, pentru a reacţiona mai eficient la frecventele calamităţi naturale din zonă. În acest scop au identificat <code>N</code> puncte de interes strategic şi le-au numerotat distinct de la <code>1</code> la <code>N</code>. Punctele de interes strategic sunt conectate prin <code>M</code> căi de acces având priorităţi în funcţie de importanţă. Între oricare două puncte de int...

Autorităţile dintr-o zonă de munte intenţionează să stabilească un plan de urgenţă, pentru a reacţiona mai eficient la frecventele calamităţi naturale din zonă. În acest scop au identificat <code>N</code> puncte de interes strategic şi le-au numerotat distinct de la <code>1</code> la <code>N</code>. Punctele de interes strategic sunt conectate prin <code>M</code> căi de acces având priorităţi în funcţie de importanţă. Între oricare două puncte de interes strategic există cel mult o cale de acces ce poate fi parcursă în ambele sensuri şi cel puţin un drum (format din una sau mai multe căi de acces) ce le conectează.

În cazul unei calamităţi unele căi de acces pot fi temporar întrerupte şi astfel între anumite puncte de interes nu mai există legătură. Ca urmare pot rezulta mai multe grupuri de puncte în aşa fel încât între oricare două puncte din acelaşi grup să existe măcar un drum şi între oricare două puncte din grupuri diferite să nu existe drum.

= Cerința =
Autorităţile estimează gravitatea unei calamităţi ca fiind suma priorităţilor căilor de acces distruse de aceasta şi doresc să determine un scenariu de gravitate maximă, în care punctele de interes strategic să fie împărţite într-un număr de <code>K</code> grupuri.

= Date de intrare =
Fișierul de intrare <code>urgenta.in</code> are următorul format:

<code>N M K</code>

<code>i1 j1 p1</code> – între punctele <code>i1</code> şi <code>j1</code> există o cale de acces de prioritate <code>p1</code>.

<code>i2 j2 p2</code> – între punctele <code>i2</code> şi <code>j2</code> există o cale de acces de prioritate <code>p2</code>.

…

<code>iM jM pM</code> – între punctele <code>iM</code> şi <code>jM</code> există o cale de acces de prioritate <code>pM</code>.

= Date de ieșire =
Fișierul de ieșire <code>urgenta.out</code> va avea următorul format:

<code>gravmax</code> – gravitatea maximă

<code>C</code> – numărul de căi de acces întrerupte de calamitate

<code>k1 h1</code> – între punctele <code>k1</code> şi <code>h1</code> a fost întreruptă calea de acces

<code>k2 h2</code> – între punctele <code>k2</code> şi <code>h2</code> a fost întreruptă calea de acces

…

<code>kC hC</code> – între punctele <code>kC</code> şi <code>hC</code> a fost întreruptă calea de acces

= Restricții și precizări =

* <code>0 < N < 256</code>
* <code>N - 2 < M < 32385</code>
* <code>0 < K < N + 1</code>
* Priorităţile căilor de acces sunt întregi strict pozitivi mai mici decât <code>256</code>.
* Un grup de puncte poate conţine între <code>1</code> şi <code>N</code> puncte inclusiv.
* Dacă există mai multe soluţii, programul va determina una singură.

= Exemplu: =
<code>urgenta.in</code>
7 11 4
1 2 1
1 3 2
1 7 3
2 4 3
3 4 2
3 5 1
3 6 1
3 7 5
4 5 5
5 6 4
6 7 3
<code>urgenta.out</code>
27
8
1 3
1 7
2 4
3 4
3 7
4 5
5 6
6 7

== Rezolvare ==
<syntaxhighlight lang="python3">
class UnionFind:
def __init__(self, n):
self.parent = [i for i in range(n + 1)]
self.rank = [0] * (n + 1)

def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]

def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x != root_y:
if self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x
elif self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
else:
self.parent[root_y] = root_x
self.rank[root_x] += 1

def main():
nMAX = 255
fin = open("urgenta.in", "r")
fout = open("urgenta.out", "w")

n, m, k = map(int, fin.readline().split())
edges = []
edges_fol = [False] * (m + 1)
tat = [0] * (nMAX + 1)
niv = [0] * (nMAX + 1)
grupe, edgfol = n, 0
costall, costfol = 0, 0

for _ in range(m):
a, b, c = map(int, fin.readline().split())
costall += c
edges.append((c, a, b))

edges.sort()

def rad(nod):
if tat[nod]:
return rad(tat[nod])
return nod

def changeDads(nod, newdad):
if tat[nod]:
changeDads(tat[nod], newdad)
tat[nod] = newdad

for i in range(m):
if grupe == k:
break
c, a, b = edges[i]
rada = rad(a)
radb = rad(b)

if rada != radb:
if niv[rada] < niv[radb]:
changeDads(a, radb)
elif niv[rada] > niv[radb]:
changeDads(b, rada)
else:
niv[rada] += 1
changeDads(b, rada)

edges_fol[i] = True
edgfol += 1
costfol += c
grupe -= 1

fout.write(str(costall - costfol) + '\n')
fout.write(str(m - edgfol) + '\n')
for i in range(m):
if not edges_fol[i]:
fout.write(str(edges[i][1]) + ' ' + str(edges[i][2]) + '\n')

fin.close()
fout.close()

if __name__ == "__main__":
main()

</syntaxhighlight>

1974 - TrumpLandia

2024-06-04T02:29:34Z

Danciu: Pagină nouă: După o confruntare eroică, Trump a fost ales democratic președintele unei republici prospere, ''TrumpLandia''. Natural, prima sa prioritate e să construiască o rețea de buncăre, pentru a veni în întâmpinarea unui atac al vecinilor imperaliști. <code>N</code> buncăre au fost deja construite. Trump trebuie să aleagă între <code>M</code> posibile rute bidirecționale pentru a le conecta. Un plan de conectare este alcătuit dintr-un subset minim de astfel de leg...

După o confruntare eroică, Trump a fost ales democratic președintele unei republici prospere, ''TrumpLandia''. Natural, prima sa prioritate e să construiască o rețea de buncăre, pentru a veni în întâmpinarea unui atac al vecinilor imperaliști.

<code>N</code> buncăre au fost deja construite. Trump trebuie să aleagă între <code>M</code> posibile rute bidirecționale pentru a le conecta. Un plan de conectare este alcătuit dintr-un subset minim de astfel de legături, astfel încât din fiecare locație să se poată ajunge în orice altă locație. Costul unui plan este dat de suma distanțelor legăturilor.

Deoarece rutele sunt vulnerabile la bombardamente aeriene, Trump vă cere să estimați un plan de cost minim. În plus, Trump vă cere să calculați <code>Q</code> soluții de rezervă, pentru situația în care una dintre cele <code>M</code> legături este sigur inclusă în plan.

= Date de intrare =
Datele de intrare vor fi citite din fișierul <code>trumplandia.in</code>. Pe prima linie se află trei numere separate prin spațiu: <code>N</code> (numărul de buncăre), <code>M</code> (numărul de rute posibile), <code>Q</code> (numărul de soluții de rezervă).

Pe următoarele <code>M</code> linii se află triplete de forma (<code>nod1</code>, <code>nod2</code>, <code>dist12</code>) ce descriu o posibilă legătură între nodurile <code>nod1</code> și <code>nod2</code> cu distanța <code>dist12</code>.

Pe următoarele <code>Q</code> linii se află câte un număr <code>Qi</code>, reprezentând indexul unei muchii care trebuie inclusă într-un plan de rezervă. (valorile se pot repeta)

= Date de ieșire =
Datele de ieșire vor fi afișate în fișierul <code>trumplandia.out</code>.

Pe prima linie se va afla un număr reprezentând costul celui mai bun plan, pentru situația în care pot fi folosite oricare dintre cele <code>M</code> rute.

Pe următoarele <code>Q</code> linii se află un număr <code>Ci</code> reprezentând costul minim al unui plan care conține muchia <code>Qi</code>.

= Restricții și precizări =

* <code>1 ≤ N ≤ 200.000</code> (pentru <code>30%</code> din teste <code>N ≤ 1000</code>)
* <code>N-1 ≤ M ≤ 200.000</code> (pentru <code>30%</code> din teste <code>M ≤ 1000</code>)
* <code>1 ≤ Q ≤ 300.000</code> (pentru <code>30%</code> din teste <code>Q ≤ 1000</code>)
* distanța asociată unei rute este o valoare întreagă din intervalul <code>[1, 1.000.000.000]</code>.

ATENȚIE!!! Între oricare două buncăre pot exista MAI MULTE rute de distanțe diferite sau nu. Exemplu: <code>(1 2 4)</code> și <code>(1 2 6)</code> sunt două muchii între buncărele <code>1</code> și <code>2</code> de distanțe <code>4</code>, respectiv <code>6</code>.

= Exemplu: =
<code>trumplandia.in</code>
6 8 8
1 2 4
4 1 6
3 1 2
2 3 3
5 2 4
3 4 3
4 5 5
5 6 1
1
2
3
4
5
6
7
8
<code>trumplandia.out</code>
13
14
16
13
13
13
13
14
13

== Rezolvare ==
<syntaxhighlight lang="python3">

with open("trumplandia.in", "r") as fin:
N, M, Q = map(int, fin.readline().split())
edges = [tuple(map(int, fin.readline().split())) for _ in range(M)]
reserve_edges = [int(fin.readline()) for _ in range(Q)]

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

def union(parent, rank, x, y):
x = find(parent, x)
y = find(parent, y)
if x == y:
return False
if rank[x] < rank[y]:
parent[x] = y
elif rank[x] > rank[y]:
parent[y] = x
else:
parent[y] = x
rank[x] += 1
return True

def kruskal(edges, N):
edges.sort(key=lambda x: x[2])

parent = list(range(N + 1))
rank = [0] * (N + 1)
min_cost = 0

mst_edges = []

for edge in edges:
u, v, cost = edge
if find(parent, u) != find(parent, v):
union(parent, rank, u, v)
min_cost += cost
mst_edges.append(edge)

return min_cost, mst_edges

min_cost, mst_edges = kruskal(edges, N)

adj_list = {i: [] for i in range(1, N + 1)}
for edge in mst_edges:
u, v, cost = edge
adj_list[u].append((v, cost))
adj_list[v].append((u, cost))

with open("trumplandia.out", "w") as fout:
fout.write(str(min_cost) + '\n')
for reserve_edge in reserve_edges:
reserve_cost = min_cost

if reserve_edge not in [edge[:2] for edge in mst_edges]:
u, v, cost = edges[reserve_edge - 1]
for edge in mst_edges:
if edge[0] == u or edge[1] == u or edge[0] == v or edge[1] == v:
reserve_cost += cost - edge[2]
break

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

</syntaxhighlight>

0146 - graph

2024-06-04T02:17:23Z

Danciu: Pagină nouă: Călinuţa tocmai a găsit o foaie de hârtie pe care este desenat un graf orientat aciclic cu <code>N</code> noduri şi <code>M</code> arce, fiecare arc având o distanţă de valoare întreagă. = Cerință = Dându-se <code>N</code>, <code>M</code> şi cele <code>M</code> arce cu distanţele dintre ele, trebuie să calculaţi pentru Călinuţa distanţa minimă dintre fiecare două noduri. = Date de intrare = Fișierul de intrare <code>graph.in</code> conține pe prima...

Călinuţa tocmai a găsit o foaie de hârtie pe care este desenat un graf orientat aciclic cu <code>N</code> noduri şi <code>M</code> arce, fiecare arc având o distanţă de valoare întreagă.

= Cerință =
Dându-se <code>N</code>, <code>M</code> şi cele <code>M</code> arce cu distanţele dintre ele, trebuie să calculaţi pentru Călinuţa distanţa minimă dintre fiecare două noduri.

= Date de intrare =
Fișierul de intrare <code>graph.in</code> conține pe prima linie numerele naturale <code>N</code> și <code>M</code> separate printr-un singur spațiu, iar pe următoarele <code>M</code> linii se află câte <code>3</code> numere <code>A</code>, <code>B</code> şi <code>C</code>, reprezentând un arc de la <code>A</code> către <code>B</code> de lungime <code>C</code>.

= Date de ieșire =
Fișierul de ieșire <code>graph.out</code> conține <code>N</code> linii cu câte <code>N</code> valori separate prin câte un spaţiu, reprezentând matricea drumurilor minime. Dacă nu există drum de la un nod <code>a</code> la un nod <code>b</code>, valoarea care trebuie afişată este <code>x</code>.

= Restricții și precizări: =

* <code>N ≤ 1500</code>
* <code>M ≤ 30.000</code>
* Numerele nodurilor sunt valori cuprinse între <code>1</code> şi <code>N</code>
* Lungimea arcelor aparţine intervalului <code>[-1000; 1000]</code>
* Pentru 25% din teste <code>N ≤ 150</code> şi <code>M ≤ 1000</code>
* Pentru alte 40% din teste <code>N ≤ 1000</code>

= Exemplu =
<code>graph.in</code>
8 9
1 2 7
2 3 -1
2 4 -2
2 7 3
8 2 -2
8 6 3
5 4 2
5 6 6
6 7 -5
<code>graph.out</code>
0 7 6 5 x x 10 x
x 0 -1 -2 x x 3 x
x x 0 x x x x x
x x x 0 x x x x
x x x 2 0 6 1 x
x x x x x 0 -5 x
x x x x x x 0 x
x -2 -3 -4 x 3 -2 0

== Rezolvare ==
<syntaxhighlight lang="python3">
def floyd_warshall(graph, N):
distances = [[float('inf')] * N for _ in range(N)]

for i in range(N):
distances[i][i] = 0

for u, v, w in graph:
distances[u - 1][v - 1] = w

for k in range(N):
for i in range(N):
for j in range(N):
if distances[i][k] != float('inf') and distances[k][j] != float('inf'):
distances[i][j] = min(distances[i][j], distances[i][k] + distances[k][j])

return distances

def main():
with open("graph.in", "r") as fin:
N, M = map(int, fin.readline().split())
graph = [tuple(map(int, fin.readline().split())) for _ in range(M)]

distances = floyd_warshall(graph, N)

with open("graph.out", "w") as fout:
for row in distances:
fout.write(" ".join(map(lambda x: str(x) if x != float('inf') else "x", row)) + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

3547 - vacanta2020

2024-06-04T01:57:10Z

Danciu: Pagină nouă: = Cerința = În anul 2020, profitând de lipsa oamenilor de pe şosele, guvernul a construit atâtea şosele încât poţi ajunge din orice oraş al patriei în oricare altul. Drumul dintre două oraşe are şi un cost, cel al benzinei consumate. Dorel s-a hotărât să plece într-o excursie, pornind din oraşul <code>1</code> până într-un oraş oarecare. El profită şi de oferta guvernului de relansare a turismului, având <code>k</code> vouchere de călătorie. Un vo...

= Cerința =
În anul 2020, profitând de lipsa oamenilor de pe şosele, guvernul a construit atâtea şosele încât poţi ajunge din orice oraş al patriei în oricare altul. Drumul dintre două oraşe are şi un cost, cel al benzinei consumate. Dorel s-a hotărât să plece într-o excursie, pornind din oraşul <code>1</code> până într-un oraş oarecare. El profită şi de oferta guvernului de relansare a turismului, având <code>k</code> vouchere de călătorie. Un voucher îl scuteşte de plata benzinei între două oraşe consecutiv vizitate, traseu pe care îl alege el pentru scutirea plăţii, de asemenea nefiind obligatorie folosirea tuturor voucherelor primite. Aflaţi costul minim al călătoriei din oraşul <code>1</code> pâna la fiecare oraş.

= Date de intrare =
Fișierul de intrare <code>vacanta2020.in</code> conține pe prima linie numărul <code>n</code> de oraşe, numărul <code>m</code> de drumuri între aceste oraşe şi numărul <code>k</code> de vouchere, iar pe următoarele <code>m</code> linii câte 3 numere <code>u v c</code> semnificând faptul că între oraşele <code>u</code> şi <code>v</code> există un drum iar costul benzinei pentru parcurgerea lui este <code>c</code>.

= Date de ieșire =
Fișierul de ieșire <code>vacanta2020.out</code> va conține pe prima linie <code>n</code> numere naturale, reprezentând costurile deplasării de la oraşul 1 la fiecare din cele <code>n</code> oraşe.

= Restricții și precizări =

* <code>1 ≤ n ≤ 35.000</code>
* <code>1 ≤ m ≤ 400.000</code>
* <code>1 ≤ k ≤ 10</code>
* <code>1 ≤ u ≠ v ≤ n</code>
* <code>1 ≤ c ≤ 30.000</code>

= Exemplu: =
<code>vacanta2020.in</code>
7 11 1
1 2 7
1 3 2
2 3 3
2 4 1
3 4 6
3 5 10
4 5 4
4 6 20
5 6 2
5 7 11
6 7 3
<code>vacanta2020.out</code>
0 0 0 1 2 4 7

=== Explicație ===
Un traseu de cost minim de la oraşul <code>1</code> la <code>7</code> este <code>1-3-5-6-7</code>, costul acestuia fiind <code>2+10+2+3=17</code>, însă având un voucher se poate elimina costul drumului <code>3-5</code>, care are valoarea <code>10</code>, costul final fiind <code>17-10=7</code>.

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

inf = float('inf')

# Citirea datelor din fișierul de intrare
with open("vacanta2020.in", "r") as f:
n, m, k = map(int, f.readline().split())
G = [[] for _ in range(n + 1)]
for _ in range(m):
x, y, c = map(int, f.readline().split())
G[x].append((y, c))
G[y].append((x, c))

# Initializarea distanțelor
d = [[inf] * (k + 1) for _ in range(n + 1)]
d[1][0] = 0

# Folosirea unui heap pentru a implementa algoritmul lui Dijkstra
pq = [(0, 1, 0)]
while pq:
dist, nod, nr_tickete = heapq.heappop(pq)
if d[nod][nr_tickete] < dist:
continue
for nod1, cost in G[nod]:
# Fără a folosi un bilet
if d[nod1][nr_tickete] > d[nod][nr_tickete] + cost:
d[nod1][nr_tickete] = d[nod][nr_tickete] + cost
heapq.heappush(pq, (d[nod1][nr_tickete], nod1, nr_tickete))
# Folosind un bilet
if nr_tickete < k:
if d[nod1][nr_tickete + 1] > d[nod][nr_tickete]:
d[nod1][nr_tickete + 1] = d[nod][nr_tickete]
heapq.heappush(pq, (d[nod1][nr_tickete + 1], nod1, nr_tickete + 1))

# Scrierea rezultatelor în fișierul de ieșire
with open("vacanta2020.out", "w") as fout:
for i in range(1, n + 1):
mini = min(d[i])
fout.write(str(mini) + ' ')

</syntaxhighlight>

1895 - Festivaluri

2024-06-04T01:53:51Z

Danciu: Pagină nouă: = Cerința = Tudor este foarte indecis, deoarece a fost chemat la <code>r</code> festivaluri și puterea lui fizică nu îi permite să ajungă la toate. În orașul în care locuiește sunt <code>m</code> străzi unidirecţionale și <code>n</code> intersecții numerotate cu numere de la <code>1</code> până la <code>n</code>. Festivalurile au loc în <code>r</code> intersecții. El pornește din intersecția cu numărul <code>z</code>. Pentru a ajunge dintr-o intersecți...

= Cerința =
Tudor este foarte indecis, deoarece a fost chemat la <code>r</code> festivaluri și puterea lui fizică nu îi permite să ajungă la toate. În orașul în care locuiește sunt <code>m</code> străzi unidirecţionale și <code>n</code> intersecții numerotate cu numere de la <code>1</code> până la <code>n</code>. Festivalurile au loc în <code>r</code> intersecții. El pornește din intersecția cu numărul <code>z</code>.

Pentru a ajunge dintr-o intersecție în alta, folosește străzile. Când parcurge o stradă, el consumă o anumită energie, care diferă de la stradă la stradă.

După terminarea fiecărui festival, Tudor se va reîntoarce la casa lui, adică la intersecția cu numărul <code>z</code>, costul drumului de această dată fiind <code>0</code>, pornind din nou la următorul festival.

Întrucât este un om foarte dedicat muzicii, Tudor vrea să participe la cât mai multe festivaluri, dar fără să-și depășească puterea lui fizică <code>p</code>.

Determinați numărul maxim de festivaluri la care poate participa.

= Date de intrare =
Fișierul de intrare <code>festivaluri.in</code> va conține pe prima linie numerele <code>n</code>, <code>m</code>, <code>p</code>, <code>z</code>, <code>r</code>. Pe următoarele <code>m</code> linii se vor afla câte <code>3</code> numere, reprezentând intersecția de unde începe strada, intersecția unde se termină strada și energia consumată pentru a parcurge strada. Pe următorul rând, se va afla cei <code>r</code> indici ai intersecțiilor unde se vor organiza festivalurile.

= Date de ieșire =
Fișierul de ieșire <code>festivaluri.out</code> va conține pe prima linie numărul <code>cnt</code>, reprezentând numărul maxim de festivaluri la care poate participa Tudor.

= Restricții și precizări =

* <code>1 ≤ n , m , z , r ≤ 100</code>
* <code>1 ≤ p≤ 10.000</code>
* numerele de pe cele <code>m+1</code> linii a fișierului de intrare vor fi mai mici decât <code>100</code>
* este posibil ca plecând din intersecția <code>z</code> să nu se poată ajunge în toate intersecțiile

= Exemplu: =
<code>festivaluri.in</code>
7 5 9 2 2
1 2 3
2 4 1
4 5 2
1 4 1
5 7 2
3 5
<code>festivaluri.out</code>
1

== Rezolvare ==
<syntaxhighlight lang="python3">
from collections import defaultdict, deque

class InParser:
def __init__(self, nume):
self.fin = open(nume, "r")

def read_int(self):
return int(self.fin.readline())

def read_values(self):
return map(int, self.fin.readline().split())

class OutParser:
def __init__(self, nume):
self.fout = open(nume, "w")

def write(self, s):
self.fout.write(s)

class Graph:
def __init__(self, n):
self.adj_list = defaultdict(list)
self.n = n

def add_edge(self, u, v, cost):
self.adj_list[u].append((v, cost))

def max_festivals(n, m, p, z, r, streets, festivals):
graph = Graph(n)

for start, end, cost in streets:
graph.add_edge(start, end, cost)

visited = set()
festivals_set = set(festivals)
queue = deque([(z, 0, p)]) # (current_intersection, current_energy_spent, remaining_energy)

cnt = 0
while queue:
intersection, energy_spent, remaining_energy = queue.popleft()

if intersection in festivals_set:
cnt += 1

if cnt == r:
return cnt

if energy_spent > remaining_energy:
continue

for neighbor, cost in graph.adj_list[intersection]:
new_energy_spent = energy_spent + cost
if new_energy_spent <= p and neighbor not in visited:
queue.append((neighbor, new_energy_spent, p - new_energy_spent))
visited.add(neighbor)

return cnt

fin = InParser("festivaluri.in")
fout = OutParser("festivaluri.out")

n, m, p, z, r = fin.read_values()
streets = [tuple(fin.read_values()) for _ in range(m)]
festivals = list(fin.read_values())

cnt = max_festivals(n, m, p, z, r, streets, festivals)
fout.write(str(cnt) + "\n")

fout.fout.close()

</syntaxhighlight>

4161 - Picard

2024-06-04T01:34:59Z

Danciu: Pagină nouă: = Cerința = În galaxia noastră sunt <code>n</code> planete, numerotate de la <code>1</code> la <code>n</code>. Între unele dintre ele sunt calculate și cunoscute salturi warp bidirecționale de durate cunoscute, existând în total <code>m</code> astfel de salturi warp. Prin aceste salturi warp se asigură posibilitatea de navigare între oricare două planete, direct sau prin intermediul mai multor salturi warp intermediare. Flota stelară folosește foarte eficient ac...

= Cerința =
În galaxia noastră sunt <code>n</code> planete, numerotate de la <code>1</code> la <code>n</code>. Între unele dintre ele sunt calculate și cunoscute salturi warp bidirecționale de durate cunoscute, existând în total <code>m</code> astfel de salturi warp. Prin aceste salturi warp se asigură posibilitatea de navigare între oricare două planete, direct sau prin intermediul mai multor salturi warp intermediare. Flota stelară folosește foarte eficient aceste salturi pentru a naviga între planete, adică folosește trasee formate din unul sau mai multe salturi warp astfel încât durata obținută ca sumă a duratelor salturilor warp componente să fie întotdeauna minimă pentru oricare pereche de planete.

Proaspăt pensionat din Flota stelară, sătul de ferenghi și romulani, Jean Luc Picard dorește să se retragă pe o planetă cât mai izolată, adică o planetă pentru care suma duratelor salturilor warp folosite de Flota stelară de la ea la toate celelaltele planete din galaxie să fie maximă. Determinați planetele pe care se poate retrage Picard pentru a obține liniștea dorită. Dacă sunt mai multe planete care pot fi alese, acestea se vor afișa în ordine crescătoare a numerotării și separate prin câte un spațiu.

= Date de intrare =
Fișierul de intrare <code>picard.in</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 planetele <code>i</code> și <code>j</code> există un salt warp bidirecțional de durată <code>L</code>.

= Date de ieșire =
Fișierul de ieșire <code>picard.out</code> va conține planetele cerute în ordine crescătoare a numerotării și separate prin câte un spațiu.

= Restricții și precizări =

* <code>1 ≤ n ≤ 100</code>
* <code>durata oricărui salt este număr întreg din intervalul [1,1000]</code>

= Exemplu: =
<code>picard.in</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>picard.out</code>
1

== Explicație ==
Sumele duratelor minime de la fiecare planetă la toate celelale sunt:
De la planeta 1 la toate celelalte: 27
De la planeta 2 la toate celelalte: 19
De la planeta 3 la toate celelalte: 24
De la planeta 4 la toate celelalte: 19
De la planeta 5 la toate celelalte: 19
De la planeta 6 la toate celelalte: 22
Prin urmare, Jean Luc Picard alege planeta 1.

== Rezolvare ==
<syntaxhighlight lang="python3">
def floyd_warshall(n, distances):
for k in range(1, n + 1):
for i in range(1, n + 1):
for j in range(1, n + 1):
distances[i][j] = min(distances[i][j], distances[i][k] + distances[k][j])

def find_max_distance(n, distances):
max_sum = 0
max_planets = []

for i in range(1, n + 1):
current_sum = sum(distances[i][1:])
if current_sum > max_sum:
max_sum = current_sum
max_planets = [i]
elif current_sum == max_sum:
max_planets.append(i)

return max_planets

if __name__ == "__main__":
with open("picard.in", "r") as fin, open("picard.out", "w") as fout:
n, m = map(int, fin.readline().split())
distances = [[float('inf')] * (n + 1) for _ in range(n + 1)]

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

for _ in range(m):
i, j, L = map(int, fin.readline().split())
distances[i][j] = distances[j][i] = L

floyd_warshall(n, distances)
max_planets = find_max_distance(n, distances)

fout.write(" ".join(map(str, max_planets)))

</syntaxhighlight>

1955 - plimbare1

2024-06-04T01:32:41Z

Danciu: Pagină nouă: = Cerința = Personajul acestei probleme este Lucian. Lucian locuiește în tara lui Verde Împărat, această tară având <code>n</code> orașe, numerotate de la <code>1</code> la <code>n</code>. Cum în orice poveste cu împărați există și o prințesă, și în problema noastră avem o prințesă, să o numim Maria. Maria este fiica lui Verde Împărat și în același timp prietena lui Lucian. În tara lui Verde Împărat se apropie sărbătorile, iar ca să fie sig...

= Cerința =
Personajul acestei probleme este Lucian. Lucian locuiește în tara lui Verde Împărat, această tară având <code>n</code> orașe, numerotate de la <code>1</code> la <code>n</code>. Cum în orice poveste cu împărați există și o prințesă, și în problema noastră avem o prințesă, să o numim Maria. Maria este fiica lui Verde Împărat și în același timp prietena lui Lucian.

În tara lui Verde Împărat se apropie sărbătorile, iar ca să fie sigur de un nou mandat, împăratul a promis că va repara câteva drumuri, astfel încât să se poată ajunge din orice oraș, în oricare alt oraș, mergând doar pe drumuri care nu sunt stricate. Fiecare drum care este stricat are un cost de reparație , și având în vedere că se apropie sărbătorile, Împăratul ar vrea să repare drumurile optim, astfel încât să obțină un cost cât mai mic. Știind că Lucian vrea să-i ceară mâna Mariei, Împăratul i-a încredințat lui Lucian această sarcină, iar în cazul în care nu va putea să o îndeplinească îl va izgoni din tară. Lucian nu a fost prezent mai deloc la orele de algoritmică din liceu și vă cere vouă ajutorul pentru această problema complicată. Având la dispoziție lista drumurilor, precum și lista drumurilor stricate, voi trebuie să-i spuneți lui Lucian care este suma minimă pe care trebuie să o folosească pentru a se putea ajunge din orice oraș în oricare alt oraș.

= Date de intrare =
Fișierul <code>plimbare1.in</code> conține pe prima linie două numere <code>N</code> și <code>M</code>, reprezentând numărul de orașe și numărul de drumuri din tara lui Verde Împărat. Pe următoarele <code>M</code> linii vor fi descrise drumurile sub următoarea formă:

* <code>1 a b</code> – există un drum între <code>a</code> și <code>b</code>;
* <code>2 a b c</code> – există un drum între <code>a</code> și <code>b</code> care poate fi reparat cu costul <code>c</code>.

= Date de ieșire =
Fișierul <code>plimbare1.out</code> conține pe prima linie un număr <code>S</code>, reprezentând costul minim al reparării drumurilor, pentru a se putea ajunge din orice oraș în oricare alt oraș.

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

• <code>1 ≤ M ≤ 120.000</code>

• <code>1 ≤ c ≤ 250</code> – număr natural

• drumurile sunt bidirecționale

= Exemplu: =
<code>plimbare1.in</code>
5 5
1 1 2
1 3 4
2 2 3 6
2 3 5 9
2 4 5 6
<code>plimbare1.out</code>
12

=== Explicație ===
Observăm că nu putem ajunge în orașul <code>3</code> din orașul <code>1</code>, sau din orașul <code>2</code> în orașul <code>3</code>, de aceea trebuie să reparăm un drum, astfel încât să fie posibil să ajungem în orașul <code>3</code>. Astfel, selectam drumul <code>2 3</code> cu costul <code>6</code>. După ce am reparat acest drum observăm că nu putem ajunge în orașul <code>5</code>. Avem două drumuri posibile de reparat pentru a ajunge apoi în orașul <code>5</code> , <code>3 5</code> cu costul <code>9</code> si <code>4 5</code> cu costul <code>6</code>. Îl vom alege pe cel mai mic (cel cu costul <code>6</code>), astfel după ce reparăm și acest drum putem ajunge din orice oraș în oricare altul.

== Rezolvare ==
<syntaxhighlight lang="python3">
Inf = float('inf')

def init(n):
return list(range(n + 1))

def find(x, T):
if x != T[x]:
T[x] = find(T[x], T)
return T[x]

def union(a, b, T):
T[find(a, T)] = find(b, T)

def kruskal(G, n):
rez = 0
T = init(n)
afis = []
for x, y, z in G:
r1 = find(x, T)
r2 = find(y, T)
if r1 != r2:
rez += z
afis.append((x, y))
union(r1, r2, T)
return rez

if __name__ == "__main__":
with open("plimbare1.in", 'r') as fin, open("plimbare1.out", 'w') as fout:
n, m = map(int, fin.readline().split())
G = []
for _ in range(m):
line = list(map(int, fin.readline().split()))
op = line[0]
if op == 1:
x, y = line[1:3]
G.append((x, y, 0))
else:
x, y, w = line[1:4]
G.append((x, y, w))
G.sort(key=lambda x: x[2])
rez = kruskal(G, n)
fout.write(str(rez) + '\n')

</syntaxhighlight>

0616 - Zapada

2024-06-04T01:26:30Z

Danciu: Pagină nouă: = Cerința = Orașul Kruskal are <code>n</code> intersecții unite prin <code>m</code> străzi bidirecționale. Datorită ninsorii de peste noapte, străzile sunt acoperite cu zăpadă. Administratorul orașului, Gigel, a determinat cu mari eforturi pentru fiecare stradă costul deszăpezirii ei și acum dorește deszăpezirea unor străzi astfel încât costul total al deszăpezirii lor să fie minim, și să se poată circula între oricare două intersecții pe străzi de...

= Cerința =
Orașul Kruskal are <code>n</code> intersecții unite prin <code>m</code> străzi bidirecționale. Datorită ninsorii de peste noapte, străzile sunt acoperite cu zăpadă. Administratorul orașului, Gigel, a determinat cu mari eforturi pentru fiecare stradă costul deszăpezirii ei și acum dorește deszăpezirea unor străzi astfel încât costul total al deszăpezirii lor să fie minim, și să se poată circula între oricare două intersecții pe străzi deszăpezite.

Maleficul Costel îl forțează pe Gigel să deszăpezească anumite străzi, din motive doar de el știute. Ajutați-l pe Gigel să determine costul minim pentru deszăpezirea orașului, astfel încât să fie deszăpezite străzile dorite de Costel și să se poată circula între oricare două intersecții pe străzi deszăpezite.

= Date de intrare =
Fișierul de intrare <code>zapada.in</code> conține pe prima linie numerele <code>n m</code>, iar pe următoarele <code>m</code> linii câte un triplet <code>i j c</code>, cu semnificația: există stradă între intersecțiile <code>i j</code> și are costul deszăpezirii egal cu <code>c</code>. Urmează o linie care conține numărul <code>k</code> de străzi pe care Costel le dorește deszăpezite, iar următoarea linie conține <code>k</code> numere distincte între <code>1</code> și <code>m</code>, reprezentând numărul de ordine al străzilor care vor fi obligatoriu deszăpezite.

= Date de ieșire =
Fișierul de ieșire <code>zapada.out</code> va conține pe prima linie costul total minim al deszăpezirii orașului, în condițiile precizate.

= Restricții și precizări =

* <code>1 ≤ n ≤ 100</code>
* <code>1 ≤ k < m ≤ n*(n-1)/2</code>
* costurile deszăpezirii străzilor sunt numere naturale nenule cel mult egale cu <code>1000</code>
* numerele celor <code>k</code> străzi care trebuie deszăpezite sunt dintre numerele de ordine ale celor <code>m</code> străzi date

= Exemplu: =
<code>zapada.in</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
2
2 11
<code>zapada.out</code>
15

= Explicație =
Alături de străzile <code>1-7</code> și <code>6-7</code> care trebuie obligatoriu deszăpezite, se mai deszăpezesc străzile: <code>1-2</code>, <code>2-5</code>, <code>4-5</code> și <code>3-4</code>. Costul total al deszăpezirii acestor străzi este <code>4+5+2+2+1+1=15</code>

== Rezolvare ==
<syntaxhighlight lang="python3">
class Muchie:
def __init__(self, nod1, nod2, cost):
self.nod1 = nod1
self.nod2 = nod2
self.cost = cost

def cmp(a, b):
return a.cost < b.cost

def radacina(a, t):
r = a
while t[r] != r:
r = t[r]
while t[a] != a:
b = t[a]
t[a] = r
a = b
return r

def main():
with open("zapada.in", 'r') as f:
n, m = map(int, f.readline().split())
v = [None] * (m + 1)
for i in range(1, m + 1):
nod1, nod2, cost = map(int, f.readline().split())
v[i] = Muchie(nod1, nod2, cost) # Am adăugat crearea obiectului de tip Muchie
t = list(range(n + 1))

k = int(f.readline())
strazi_dorite = list(map(int, f.readline().split())) # Citim lista de străzi dorite
sum = 0
for x in strazi_dorite: # Iterăm prin străzile dorite și adăugăm costurile lor
sum += v[x].cost
v[x].cost = 0

v = v[1:] # Skip the first element which is None
v.sort(key=lambda x: x.cost)

nr_arb = 1
for i in range(len(v)):
if nr_arb >= n:
break
r1 = radacina(v[i].nod1, t)
r2 = radacina(v[i].nod2, t)
if r1 == r2:
continue
t[r2] = r1
sum += v[i].cost
nr_arb += 1

with open("zapada.out", 'w') as f:
f.write(str(sum))

if __name__ == "__main__":
main()

</syntaxhighlight>

3262 - Rain

2024-06-04T00:17:51Z

Danciu: Pagină nouă: Bariere impermeabile de înălțimi diferite sunt plasate perpendicular pe lungimea unei cuve dreptunghiulare. Distanța dintre oricare două bariere alăturate este de un centimetru. Cuva nu are capac și atunci când plouă destul, cuva este umplută cu apă. Unele bariere pot fi înălțate cu o valoare întreagă care nu poate depăși o valoare dată. = Cerința = Care este numărul minim de bariere care trebuie înălțate astfel încât să fie colectată în cuvă o...

Bariere impermeabile de înălțimi diferite sunt plasate perpendicular pe lungimea unei cuve dreptunghiulare. Distanța dintre oricare două bariere alăturate este de un centimetru. Cuva nu are capac și atunci când plouă destul, cuva este umplută cu apă. Unele bariere pot fi înălțate cu o valoare întreagă care nu poate depăși o valoare dată.

= Cerința =
Care este numărul minim de bariere care trebuie înălțate astfel încât să fie colectată în cuvă o cantitate maximă de apă?

= Date de intrare =
Programul citește de pe prima linie numărul <code>n</code> de bariere. A doua linie conține înălțimile celor <code>n</code> bariere, luate de la stânga la dreapta. A treia linie conține numărul <code>k</code> de bariere cărora li se poate crește înălțimea. Urmează atâtea linii câte bariere sunt cărora le putem crește înălțimea. Fiecare din aceste linii conține numărul barierei și creșterea maximă în centimetri în înălțime care se poate face. Numerotarea barierelor se face începând cu <code>0</code>.

= Date de ieșire =
Programul va afișa pe ecran doi întregi separați prin spațiu, numărul minim de bariere cărora li se va mări înălțimea și cantitatea maximă de apă ce poate fi colectată după mărire.

Observație: Se calculează cantitatea în centimetri cubi deoarece considerăm adâncimea cuvei de un centimetru. Considerăm fața și spatele pereți ai cuvei (cea care este înspre noi și cea care este în spate) ca fiind mai înalte decât înălțimea oricărei bariere. Pereții din stânga și din dreapta ai cuvei coincid cu cea mai din stânga și respectiv cea mai din dreapta barieră, chiar și după ce acestea vor fi eventual înălțate.

= Restricții și precizări =

* <code>1 < n < 1.000.000</code>
* <code>0 < k ≤ n</code>
* înălțimile inițiale ale celor <code>n</code> bariere sunt numere naturale mai mici sau egale cu <code>1.000.000</code>
* barierele vor fi înălțate cu maximum <code>1.000.000</code>

= Exemplu: =
Intrare
6
2 4 2 4 2 1
2
2 1
4 1
Ieșire
1 14

=== Explicație ===
Nu se crește înălțimea barierei <code>2</code> deoarece nu va modifica întreaga cantitate de apă. Vom crește cu <code>1</code> centimetru înălțimea barierei de la poziția <code>4</code>, care va mări cantitatea totală de apă cu <code>1</code> centimetru cub.

== Rezolvare ==
<syntaxhighlight lang="python3">
nMax = 1000000
H = [0] * nMax
max_dH = [0] * nMax
LR = []
RL = []
n = 0
dn = 0
KL = 0
KR = 0
countB = 0
volume = 0
L = -1
R = -1

def input_data():
global n, H, dn, max_dH
n = int(input())
H[:n] = map(int, input().split())
dn = int(input())
for _ in range(dn):
j, dH = map(int, input().split())
max_dH[j] = dH
H[j] += dH

def scan():
global KL, KR, L, R
KL = 0
for i in range(1, n):
if H[KL] < H[i]:
L = KL
LR.append(KL)
KL = i
KR = n - 1
for i in range(n - 2, KL - 1, -1):
if H[KR] < H[i]:
R = KR
RL.append(KR)
KR = i

def solve():
global countB, volume, L, R
if LR:
LR.append(KL)
for i in range(len(LR) - 1):
if max_dH[LR[i]] > 0:
countB += 1
volume += H[LR[i]] * (LR[i + 1] - LR[i])
if RL:
RL.append(KR)
for i in range(len(RL) - 1):
if max_dH[RL[i]] > 0:
countB += 1
volume += H[RL[i]] * (RL[i] - RL[i + 1])
if KL < KR:
if max_dH[KL] > 0:
countB += 1
if max_dH[KR] > 0:
countB += 1
volume += H[KL] * (KR - KL)
else:
HLmax = H[L] if L != -1 else 0
HRmax = H[R] if R != -1 else 0
if HLmax != HRmax:
if H[KL] - max_dH[KL] < max(HRmax, HLmax):
countB += 1

def main():
input_data()
scan()
solve()
print(countB, volume)

if __name__ == "__main__":
main()

</syntaxhighlight>

4170 – FlșiDesc

2024-06-03T23:52:55Z

Danciu: Pagină nouă: Se consideră o listă liniară simplu înlănțuită, alocată dinamic, în care elementele sunt de tipul declarat mai jos: struct Nod { int info; Nod *leg; }; în care câmpul <code>info</code> memorează un număr natural nenul, iar câmpul <code>leg</code> memorează adresa următorului element al listei. = Cerinţa = Să se scrie o funcție C++ cu următorul prototip: void FLsiDesc(Nod *head); Lista are cel puțin un nod și are adresa primului element mem...

Se consideră o listă liniară simplu înlănțuită, alocată dinamic, în care elementele sunt de tipul declarat mai jos:
struct Nod
{
int info;
Nod *leg;
};
în care câmpul <code>info</code> memorează un număr natural nenul, iar câmpul <code>leg</code> memorează adresa următorului element al listei.

= Cerinţa =
Să se scrie o funcție C++ cu următorul prototip:
void FLsiDesc(Nod *head);
Lista are cel puțin un nod și are adresa primului element memorată în pointerul <code>head</code>. Informațiile memorate în noduri sunt ordonate strict descrescător. Funcția inserează noduri astfel încât în final lista va memora în ordine descrescătoare toate numerele de la <code>n</code> la <code>1</code>, unde <code>n</code> este valoarea memorată inițial în primul nod al listei. De exemplu, dacă lista conține inițial informațiile <code>7,4,3</code>, atunci la final lista va fi: <code>7,6,5,4,3,2,1</code>. Dacă lista conține inițial doar informația <code>3</code>, atunci la final lista va fi <code>3,2,1</code>. Dacă lista conține inițial <code>2,1</code>, atunci la final lista va fi <code>2,1</code>. Atenție, doar inserați nodurile care lipsesc, nu efectuați alte operații.

= Important =
Soluţia propusă va conţine definiţia funcţiei cerute. Prezenţa în soluţie a altor instrucţiuni poate duce erori de compilare sau de execuţie care vor avea ca efect depunctarea soluţiei.

== Rezolvare ==
<syntaxhighlight lang="python3">
if node is None or node.info > value:
new_node = Nod(value)
new_node.leg = node
return new_node
else:
node.leg = insert_desc(node.leg, value)

return node

for i in range(head.info, 0, -1):
head = insert_desc(head, i)

return head

head = Nod(7)
head.leg = Nod(4)
head.leg.leg = Nod(3)
head = FLsiDesc(head)
while head:
print(head.info)
head = head.leg
</syntaxhighlight>

3914 - Cuvinte12

2024-06-03T23:42:29Z

Danciu: Pagină nouă: = Cerința = Se citește un cuvânt <code>S</code> format din litere mici distincte ale alfabetului englez și un număr <code>m</code>. Afișați în ordine lexicografică toate cuvintele formate din cel mult <code>m</code> litere ordonate alfabetic din <code>S</code>, în care nu există consoane alăturate și încep cu vocală. = Date de intrare = Programul citește de la tastatură cuvântul <code>S</code> și numărul <code>m</code>. = Date de ieșire = Programul va...

= Cerința =
Se citește un cuvânt <code>S</code> format din litere mici distincte ale alfabetului englez și un număr <code>m</code>. Afișați în ordine lexicografică toate cuvintele formate din cel mult <code>m</code> litere ordonate alfabetic din <code>S</code>, în care nu există consoane alăturate și încep cu vocală.

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

= Date de ieșire =
Programul va afișa pe ecran cuvintele cerute, câte unul pe un rând.

= Restricții și precizări =

* <code>1 < m ≤</code> lungimea lui <code>S ≤ 10</code>

= Exemplu: =
Intrare
barni 3
Ieșire
a
ab
abi
ai
ain
air
an
ar
i
in
ir

== Rezolvare ==
<syntaxhighlight lang="python3">
def generate_words(word, m, current_word, index, vowels_count):
if len(current_word) > m or (len(current_word) > 0 and current_word[-1] in 'aeiou'):
return

if len(current_word) > 0:
print(current_word)

if index == len(word):
return

for i in range(index, len(word)):
if word[i] in 'aeiou':
generate_words(word, m, current_word + word[i], i + 1, 1)
else:
generate_words(word, m, current_word + word[i], i + 1, 0)

word, m = input().split()
m = int(m)
word = ''.join(sorted(word, key=lambda x: 'aeiou'.index(x) if x in 'aeiou' else 99))
generate_words(word, m, '', 0, 0)
</syntaxhighlight>

3913 - Cuvinte11

2024-06-03T23:34:23Z

Danciu: Pagină nouă: = Cerința = Se citește un cuvânt <code>S</code> format din litere mici distincte ale alfabetului englez și un număr <code>m</code>. Afișați în ordine lexicografică toate cuvintele formate din cel puțin <code>m</code> litere ordonate alfabetic din <code>S</code>, în care nu există vocale alăturate și se termină cu consoană. = Date de intrare = Programul citește de la tastatură cuvântul <code>S</code> și numărul <code>m</code>. = Date de ieșire = Progra...

= Cerința =
Se citește un cuvânt <code>S</code> format din litere mici distincte ale alfabetului englez și un număr <code>m</code>. Afișați în ordine lexicografică toate cuvintele formate din cel puțin <code>m</code> litere ordonate alfabetic din <code>S</code>, în care nu există vocale alăturate și se termină cu consoană.

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

= Date de ieșire =
Programul va afișa pe ecran cuvintele cerute, câte unul pe un rând.

= Restricții și precizări =

* <code>1 < m ≤</code> lungimea lui <code>S ≤ 10</code>

= Exemplu: =
Intrare
barni 3
Ieșire
abin
abinr
abir
abn
abnr
abr
anr
bin
binr
bir
bnr
inr

== Rezolvare ==
<syntaxhighlight lang="python3">
def generate_words(word, m, current_word, index, vowels_count):
if len(current_word) >= m:
print(current_word)
if index == len(word):
return

for i in range(index, len(word)):
if word[i] not in 'aeiou':
generate_words(word, m, current_word + word[i], i + 1, 0)
elif vowels_count == 0:
generate_words(word, m, current_word + word[i], i + 1, 1)

word, m = input().split()
m = int(m)
generate_words(word, m, '', 0, 0)
</syntaxhighlight>

0870 - Depou

2024-06-03T23:00:59Z

Danciu: Pagină nouă: = Cerința = Se consideră un depou de cale ferată precum cel din imagine: Pe linia <code>A</code> se află <code>n</code> vagoane, numerotate cu valori distincte de la <code>1</code> la <code>n</code>, într-o ordine oarecare. Vagoanele trebuie mutate pe linia <code>C</code>, în ordinea <code>1 2 .. n</code>. Pentru aceasta se poate muta câte un vagon de pe o linie pe alta, în ordinea indicată de săgeți: * <code>A -> B</code>, * <code>A -> C</code> * <code>B -> C</...

= Cerința =
Se consideră un depou de cale ferată precum cel din imagine:

Pe linia <code>A</code> se află <code>n</code> vagoane, numerotate cu valori distincte de la <code>1</code> la <code>n</code>, într-o ordine oarecare. Vagoanele trebuie mutate pe linia <code>C</code>, în ordinea <code>1 2 .. n</code>. Pentru aceasta se poate muta câte un vagon de pe o linie pe alta, în ordinea indicată de săgeți:

* <code>A -> B</code>,
* <code>A -> C</code>
* <code>B -> C</code>.

Să se determine o succesiune de operații care să mute toate vagoanele de pe linia <code>A</code> pe linia <code>C</code> în ordinea dorită.

= Date de intrare =
Programul citește de la tastatură numărul <code>n</code>, iar apoi <code>n</code> numere naturale distincte cuprinse între <code>1</code> și <code>n</code>, reprezentând ordinea vagoanelor de pe linia <code>A</code>.

= Date de ieșire =
Programul va afișa pe ecran numărul <code>C</code> de operații efectuate, apoi cele <code>C</code> operații. Fiecare operație va fi afișată pe câte o linie a ecranului, și va consta din două caractere de forma <code>X Y</code>, semnificând faptul că se mută un vagon de pe linia <code>X</code> pe linia <code>Y</code>. Dacă nu este posibilă mutarea vagoanelor de pe linia <code>A</code> pe linia <code>C</code>, numărul de operații afișat va fi <code>0</code>.

= Restricții și precizări =

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

= Exemplu: =
Intrare
4
2 1 3 4
Ieșire
6
A B
A B
A C
A C
B C
B C

= Explicație =
Ordinea inițială a vagoanelor este următoarea:

După mutarea vagoanele vor fi în ordinea:

== Rezolvare ==
<syntaxhighlight lang="python3">
def main():
a = [0] * 1001
d = [[0] * 3 for _ in range(2001)]
b = [0] * 1001

n = int(input())
a[1:n + 1] = map(int, input().split())

vf = 0
vagon = 1
op = 0
ok = 1
i = n

while vagon <= n and ok == 1:
if vagon == a[i]:
op += 1
vagon += 1
i -= 1
d[op][0] = 1
d[op][1] = 3
elif vf > 0 and b[vf] == vagon:
op += 1
vagon += 1
vf -= 1
d[op][0] = 2
d[op][1] = 3
elif i >= 1:
op += 1
d[op][0] = 1
d[op][1] = 2
vf += 1
b[vf] = a[i]
i -= 1
elif vagon >= 1 and i == 0 and vf > 0:
ok = 0

if ok == 0:
print(0)
else:
print(op)
for i in range(1, op + 1):
if d[i][0] == 1:
print("A", end=" ")
else:
print("B", end=" ")
if d[i][1] == 2:
print("B")
else:
print("C")

if __name__ == "__main__":
main()

</syntaxhighlight>