Bitnami MediaWiki - User contributions [en]

14310

2025-01-12T17:58:30Z

Benzar Ioan:

'''14310 (Traian Covaciu)'''

''Fie <math>n, n + 2, n + 6 </math> trei numere naturale și <math> S </math> suma lor.''

a) ''Dați exemplu de cel puțin trei valori pentru <math> n \in \mathbb{N}</math> astfel încât numerele <math> n, n + 2, n + 6 </math> să fie simultan numere prime.'' 

b) ''Dacă <math> n, n + 2, n + 6 </math> sunt simultan numere prime, arătați că există <math> k \in \mathbb{N} </math> astfel încât <math> S = 9k + 5</math>. '' 

c) ''Dacă <math> n, n + 2, n + 6 </math> sunt numere prime, determinați restul împărțirii numărului <math> S</math> la <math> 18 </math>.''

'''Soluție:''' 
a) Pentru <math> n = 5 </math> numerele sunt <math> 5, 7, 11 </math>. Pentru <math> n = 11 </math> avem <math> 11, 13, 17 </math>, iar pentru <math> n = 17 </math> obținem <math> 17, 19, 23 </math>. 
b) Se știe că numerele prime au forma <math> 6p + 1 </math> sau <math> 6p + 5 </math>. Dacă <math> n = 6p + 1</math>, atunci <math> n + 2 = 6p + 3 </math> care nu este numar prim. Așadar, <math> n = 6p + 5 </math>. În această situație avem <math> S = 6p + 5 + 6p + 7 + 6p + 11 = 18p + 23 = 9(2p + 2) + 5 </math>. În concluzie, există <math> k = 2p + 2 </math> astfel încât <math> S = 9k + 5 </math>. 
c) Din punctul b) avem <math> S = 18(p + 1) + 5 </math>, deci restul împărțirii lui <math> S </math> la <math> 18 </math> este <math> 5 </math>.

14311

2025-01-12T17:55:38Z

Benzar Ioan: Created page with "''' 14311 (Neculai Stanciu) ''' '' Determinați cel mai mic număr natural de forma: <math> ab + cd + ef +gh </math>, unde <math> a, b, c, d, e, f, g, h </math> sunt numere naturale nenule, distincte două cate două.'' '''Solutie:''' Trebuie ca <math> a, b, c, d, e, f, g ,h \in {1, 2, 3, 4, 5, 6, 7, 8} </math>. Cea mai mică sumă, deci cel mai mic număr, este <math> 1 * 8 + 2 * 7 + 3 * 6 + 4 * 5 = 60 </math>."

''' 14311 (Neculai Stanciu) '''
'' Determinați cel mai mic număr natural de forma: <math> ab + cd + ef +gh </math>, unde <math> a, b, c, d, e, f, g, h </math> sunt numere naturale nenule, distincte două cate două.''

'''Solutie:'''


Trebuie ca <math> a, b, c, d, e, f, g ,h \in {1, 2, 3, 4, 5, 6, 7, 8} </math>. Cea mai mică sumă, deci cel mai mic număr, este <math> 1 * 8 + 2 * 7 + 3 * 6 + 4 * 5 = 60 </math>.

14310

2025-01-12T17:50:29Z

Benzar Ioan: Created page with "'''14310 (Traian Covaciu)''' ''Fie <math>n, n + 2, n + 6 </math> trei numere naturale și <math> S </math> suma lor.'' a) ''Dați exemplu de cel puțin trei valori pentru <math> n \in \mathbb{N}</math> astfel incat numerele <math> n, n + 2, n + 6 </math> sa fie simultan numere prime.'' b) ''Daca <math> n, n + 2, n + 6 </math> sunt simultan numere prime, aratati ca exista <math> k \in \mathbb{N} </math> astfel incat <math> S = 9k + 5</math>. '' c) ''Daca <math..."

'''14310 (Traian Covaciu)'''

''Fie <math>n, n + 2, n + 6 </math> trei numere naturale și <math> S </math> suma lor.''

a) ''Dați exemplu de cel puțin trei valori pentru <math> n \in \mathbb{N}</math> astfel incat numerele <math> n, n + 2, n + 6 </math> sa fie simultan numere prime.'' 

b) ''Daca <math> n, n + 2, n + 6 </math> sunt simultan numere prime, aratati ca exista <math> k \in \mathbb{N} </math> astfel incat <math> S = 9k + 5</math>. '' 

c) ''Daca <math> n, n + 2, n + 6 </math> sunt numere prime, determinati restul impartirii numarului <math> S</math> la <math> 18 </math>.''

'''Solutie:''' 
a) Pentru <math> n = 5 </math> numerele sunt <math> 5, 7, 11 </math>. Pentru <math> n = 11 </math> avem <math> 11, 13, 17 </math>, iar pentru <math> n = 17 </math> obtinem <math> 17, 19, 23 </math>. 
b) Se stie ca numerele prime au forma <math> 6p + 1 </math> sau <math> 6p + 5 </math>. Daca <math> n = 6p + 1</math>, atunci <math> n + 2 = 6p + 3 </math> care nu este numar prim. Asadar, <math> n = 6p + 5 </math>. In aceasta situatie avem <math> S = 6p + 5 + 6p + 7 + 6p + 11 = 18p + 23 = 9(2p + 2) + 5 </math>. In concluzie, exista <math> k = 2p + 2 </math> astfel incat <math> S = 9k + 5 </math>. 
c) Din punctul b) avem <math> S = 18(p + 1) + 5 </math>, deci restul impartirii lui <math> S </math> la <math> 18 </math> este <math> 5 </math>.

1832 - Pd

2024-06-03T19:41:01Z

Benzar Ioan: Pagină nouă: == Cerința == Se dă un număr natural s. Determinaţi, în ordine lexicografică, toate modalităţile de a-l scrie pe s ca produs de divizori proprii distincți ai lui s. == Date de intrare == Programul citește de la tastatură numărul s. == Date de ieșire == Programul va afișa pe ecran pe fiecare linie câte un şir de numere naturale ordonate strict crescător, separate prin câte un spaţiu. Produsul numerelor din fiecare şir este s, iar numerele sunt divizori prop...

== Cerința ==
Se dă un număr natural s. Determinaţi, în ordine lexicografică, toate modalităţile de a-l scrie pe s ca produs de divizori proprii distincți ai lui s.
== Date de intrare ==
Programul citește de la tastatură numărul s.
== Date de ieșire ==
Programul va afișa pe ecran pe fiecare linie câte un şir de numere naturale ordonate strict crescător, separate prin câte un spaţiu. Produsul numerelor din fiecare şir este s, iar numerele sunt divizori proprii ai lui s. Şirurile vor fi afişate în ordine lexicografică.

Dacă numărul s nu poate fi scris ca produs de divizori proprii, se va fişa mesajul NU EXISTA.
== Restricții și precizări ==
*2 ≤ s ≤ 2000000000
== Exemplu 1 ==
;Intrare
30
;Iesire
2 3 5 
2 15 
3 10 
5 6
== Rezolvare ==
<syntaxhighlight lang="python" line>
from itertools import combinations
import math

def find_divisors(n):
divisors = []
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0:
divisors.append(i)
if i != n // i:
divisors.append(n // i)
divisors.sort()
return divisors

def find_combinations(divisors, s):
result = []
for i in range(1, len(divisors) + 1):
for combo in combinations(divisors, i):
product = 1
for num in combo:
product *= num
if product == s:
result.append(combo)
return result

def main():
s = int(input().strip())

if s <= 1:
print("NU EXISTA")
return

divisors = find_divisors(s)
combinations = find_combinations(divisors, s)

if not combinations:
print("NU EXISTA")
else:
sorted_combinations = sorted(combinations)
for combo in sorted_combinations:
print(" ".join(map(str, combo)))

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

3162 - cife bin back

2024-06-03T19:38:00Z

Benzar Ioan: Pagină nouă: == Cerința == Se dă un număr natural n. Afișați în ordine lexicografică toate secvențele de cifre binare care au atâtea cifre de 0 și atâtea cifre de 1 câte are reprezentarea binară a lui n. == Date de intrare == Programul citește de la tastatură numărul n. == Date de ieșire == Programul va afișa pe ecran combinațiile de cifre binare cerute, câte una pe fiecare rând. == Restricții și precizări == *1 ≤ n ≤ 2.000.000 == Exemplu 1 == ;Intrare 17 ;Iesi...

== Cerința ==
Se dă un număr natural n. Afișați în ordine lexicografică toate secvențele de cifre binare care au atâtea cifre de 0 și atâtea cifre de 1 câte are reprezentarea binară a lui n.
== Date de intrare ==
Programul citește de la tastatură numărul n.
== Date de ieșire ==
Programul va afișa pe ecran combinațiile de cifre binare cerute, câte una pe fiecare rând.
== Restricții și precizări ==
*1 ≤ n ≤ 2.000.000
== Exemplu 1 ==
;Intrare
17
;Iesire
00011 
00101 
00110 
01001 
01010 
01100 
10001 
10010 
10100 
11000
== Rezolvare ==
<syntaxhighlight lang="python" line>
from itertools import permutations

def generate_binary_sequences(n):
binary_representation = bin(n)[2:]
count_ones = binary_representation.count('1')
count_zeros = len(binary_representation) - count_ones

# Create the base string with the correct number of 1s and 0s
base_string = '1' * count_ones + '0' * count_zeros

# Generate all unique permutations of the base string
unique_permutations = sorted(set(permutations(base_string)))

# Convert tuples back to strings
result = [''.join(p) for p in unique_permutations]

return result

def main():
n = int(input().strip())
results = generate_binary_sequences(n)
for result in results:
print(result)

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

3157 - cifre c1c2

2024-06-03T19:34:19Z

Benzar Ioan: Pagină nouă: == Cerința == Se citesc două cifre diferite c1 și c2 (nenule). Afișați în ordine crescătoare toate numerele care conțin exact c1 cifre egale cu c2 și c2 cifre egale cu c1. == Date de intrare == Programul citește de la tastatură cifrele c1 și c2 separate printr-un spațiu. == Date de ieșire == Programul va afișa pe ecran numerele cerute, câte unul pe un rând. == Restricții și precizări == *1 ≤ c1, c2 ≤ 9 *c1 ≠ c2 == Exemplu 1 == ;Intrare 2 3 ;Iesire 22...

== Cerința ==
Se citesc două cifre diferite c1 și c2 (nenule). Afișați în ordine crescătoare toate numerele care conțin exact c1 cifre egale cu c2 și c2 cifre egale cu c1.
== Date de intrare ==
Programul citește de la tastatură cifrele c1 și c2 separate printr-un spațiu.
== Date de ieșire ==
Programul va afișa pe ecran numerele cerute, câte unul pe un rând.
== Restricții și precizări ==
*1 ≤ c1, c2 ≤ 9
*c1 ≠ c2
== Exemplu 1 ==
;Intrare
2 3
;Iesire
22233 
22323 
22332 
23223 
23232 
23322 
32223 
32232 
32322 
33222
== Rezolvare ==
<syntaxhighlight lang="python" line>
def generate_numbers(c1, c2):
from itertools import permutations

c1 = str(c1)
c2 = str(c2)
digits = c1 * int(c2) + c2 * int(c1)
permutations_set = set()

for perm in permutations(digits):
number = ''.join(perm)
if number.count(c1) == int(c2) and number.count(c2) == int(c1):
permutations_set.add(number)

sorted_numbers = sorted(permutations_set)
return sorted_numbers

def main():
c1, c2 = map(int, input().strip().split())

results = generate_numbers(c1, c2)

for result in results:
print(result)

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

2171 - pluricex1

2024-06-03T19:29:23Z

Benzar Ioan: Pagină nouă: == Cerința == Anul acesta se organizează prima ediție a Olimpiadei Pluridisciplinare pentru Centrele de Excelență, PluriCEX. Fiecare Centru de Excelență din țară va trimite la concurs o echipă formată din k membri (toți participanți la Centrul de Excelență). Echipa va trebui să rezolve probleme interdisciplinare, disciplinele vizate fiind cele de la Centrul de Excelenţă (D discipline, pe care le vom considera numerotate de la 1 la D). Directorul CEX Iași a...

== Cerința ==
Anul acesta se organizează prima ediție a Olimpiadei Pluridisciplinare pentru Centrele de Excelență, PluriCEX. Fiecare Centru de Excelență din țară va trimite la concurs o echipă formată din k membri (toți participanți la Centrul de Excelență). Echipa va trebui să rezolve probleme interdisciplinare, disciplinele vizate fiind cele de la Centrul de Excelenţă (D discipline, pe care le vom considera numerotate de la 1 la D).
Directorul CEX Iași a făcut o listă cu primii n cei mai buni elevi de la CEX, apoi a numerotat elevii de la 1 la n, în ordinea apariției lor în listă. Pentru fiecare elev, directorul a notat disciplinele la care el participă la CEX.
Scrieți un program care să determine toate echipele ce pot fi formate din k dintre cei n elevi de pe lista directorului, cu condiția ca pentru fiecare disciplină să existe în echipă cel puțin un membru care să studieze la CEX disciplina respectivă.
== Date de intrare ==
Fișierul de intrare pluricex1.in conţine pe prima linie trei numere naturale n k D (cu semnificația din enunț). Urmează n linii care descriu participările la CEX ale celor n elevi de pe lista directorului. Mai exact, pe linia i+1 este descrisă participarea elevului i astfel: nr d1 d2 ... dnr. Primul număr de pe linie (nr) indică numărul de discipline la care participă elevul i. Următoarele nr numere reprezintă disciplinele la care participă elevul i. Numerele scrise pe aceeași linie sunt separate prin spațiu.
== Date de ieșire ==
Fișierul de ieșire pluricex1.out va conţine toate echipele ce se pot forma respectând condiţiile din enunţ, câte o echipă pe o linie. Membrii unei echipe vor fi scrişi în ordine crescătoare, separaţi prin câte un spaţiu. Echipele vor fi scrise în ordine lexicografică.
== Restricții și precizări ==
*0 < n ≤ 22
*0 < k ≤ 8
*0 < D ≤ 10
*Pentru datele de test problema admite întotdeauna soluţie, numărul de soluţii fiind mai mic de 20000.
*Spunem că vectorul (x1, x2, ..., xn) precedă lexicografic vectorul (y1, y2, ..., yn) dacă există un indice i astfel încât xj=yj, pentru orice 1 ≤ j < i, iar xi < yi.
== Exemplu 1 ==
;Intrare
6 3 5 
1 2 
2 1 4 
3 2 4 3 
1 5 
2 3 1 
1 3
;Iesire
2 3 4 
3 4 5
== Rezolvare ==
<syntaxhighlight lang="python" line>
def generate_teams(n, k, d, participations):
from itertools import combinations

teams = []

for comb in combinations(range(1, n + 1), k):
valid = True
disciplines = [0] * d

for student in comb:
for discipline in participations[student - 1]:
disciplines[discipline - 1] += 1

if all(disciplines):
teams.append(comb)

return sorted(teams)

def read_input(input_file):
with open(input_file, 'r') as file:
n, k, d = map(int, file.readline().strip().split())
participations = []

for _ in range(n):
line = list(map(int, file.readline().strip().split()))
participations.append(line[1:])

return n, k, d, participations

def write_output(output_file, teams):
with open(output_file, 'w') as file:
for team in teams:
file.write(' '.join(map(str, team)) + '\n')

def main():
input_file = 'pluricex1.in'
output_file = 'pluricex1.out'

# Citim datele de intrare
n, k, d, participations = read_input(input_file)

# Generăm echipele valide
teams = generate_teams(n, k, d, participations)

# Scriem rezultatele în fișierul de ieșire
write_output(output_file, teams)

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

3379 - nkgraf

2024-06-03T19:24:28Z

Benzar Ioan: Pagină nouă: == Cerința == Fie N, K, P trei numere naturale nenule. Vom considera toate grafurile orientate care au N vârfuri şi K arce, reprezentate prin lista arcelor lor ordonate lexicografic. Vom ordona apoi grafurile lexicografic şi le vom numerota începând cu 1. Scrieţi un program care, cunoscând N, K şi P, rezolvă următoarele două cerinţe: 1. determină NR, numărul de grafuri orientate cu N vârfuri şi K arce; 2. determină graful orientat cu N vârfuri şi K arce av...

== Cerința ==
Fie N, K, P trei numere naturale nenule. Vom considera toate grafurile orientate care au N vârfuri şi K arce, reprezentate prin lista arcelor lor ordonate lexicografic.
Vom ordona apoi grafurile lexicografic şi le vom numerota începând cu 1.
Scrieţi un program care, cunoscând N, K şi P, rezolvă următoarele două cerinţe:
1. determină NR, numărul de grafuri orientate cu N vârfuri şi K arce;
2. determină graful orientat cu N vârfuri şi K arce având numărul de ordine P.
== Date de intrare ==
Fișierul de intrare nkgraf.in conţine pe prima linie cerinţa care trebuie să fie rezolvată (1 sau 2). Pe a doua linie se află trei numere naturale separate prin câte-un spaţiu N K P, având semnificaţia din enunţ.
== Date de ieșire ==
Dacă cerinţa este 1, fişierul de ieşire nkgraf.out va conţine o singură linie pe care va fi scris NR, numărul de grafuri orientate cu N vârfuri şi K arce.
Dacă cerinţa este 2, fişierul de ieşire nkgraf.out va conţine K linii pe care vor fi scrise în ordine lexicografică cele K arce ale grafului având numărul de ordine P, câte un arc pe o linie; pentru fiecare arc vor fi scrise două vârfuri separate printr-un spaţiu, reprezentând extremitatea iniţială şi respectiv extremitatea finală a arcului.
== Restricții și precizări ==
*2 ≤ N ≤ 30
*1 ≤ P ≤ min {NR,1.000.000}
*Orice arc din graf a avea extremitatea iniţială diferită de extremitatea finală.
== Exemplu 1 ==
;Intrare
1 
3 2 6
;Iesire
15
== Exemplu 2 ==
;Intrare
2 
3 2 6
;Iesire
1 3 
2 1
== Rezolvare ==
<syntaxhighlight lang="python" line>
from itertools import permutations, combinations

def read_input():
with open("nkgraf.in", "r") as file:
cerinta = int(file.readline().strip())
N, K, P = map(int, file.readline().strip().split())
return cerinta, N, K, P

def write_output(output):
with open("nkgraf.out", "w") as file:
if isinstance(output, int):
file.write(str(output) + "\n")
else:
for edge in output:
file.write(" ".join(map(str, edge)) + "\n")

def generate_graphs(N, K):
nodes = range(1, N + 1)
possible_edges = list(permutations(nodes, 2))
all_graphs = list(combinations(possible_edges, K))
return sorted(all_graphs)

def main():
cerinta, N, K, P = read_input()

# Validări
if not (2 <= N <= 30):
raise ValueError("N trebuie să fie între 2 și 30")
if not (1 <= P <= min(len(generate_graphs(N, K)), 1000000)):
raise ValueError("P trebuie să fie între 1 și min(NR, 1.000.000)")

all_graphs = generate_graphs(N, K)
NR = len(all_graphs)

if cerinta == 1:
write_output(NR)
elif cerinta == 2:
graph = all_graphs[P - 1]
write_output(graph)

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

3294 - Hmmm

2024-06-03T19:20:19Z

Benzar Ioan: Pagină nouă: == Cerința == Fie λ o permutare de grad N și K un număr natural nenul. Să se afișeze toate soluțiile ecuației x^K=λ în ordine lexicografică. == Date de intrare == Fișierul de intrare hmmm.in conține pe prima linie gradul permutării N și K, iar pe a doua linie se citește permutarea λ. == Date de ieșire == Fișierul de ieșire hmmm.out va conține toate soluțiile x ale ecuației în ordine lexicografică, câte una pe linie. Elementele permutărilor se separ...

== Cerința ==
Fie λ o permutare de grad N și K un număr natural nenul.
Să se afișeze toate soluțiile ecuației x^K=λ în ordine lexicografică.
== Date de intrare ==
Fișierul de intrare hmmm.in conține pe prima linie gradul permutării N și K, iar pe a doua linie se citește permutarea λ.
== Date de ieșire ==
Fișierul de ieșire hmmm.out va conține toate soluțiile x ale ecuației în ordine lexicografică, câte una pe linie. Elementele permutărilor se separă printr-un spațiu.
== Restricții și precizări ==
*N ≤ 9
*2 ≤ K ≤ 1.000.000.000
*Întotdeauna există cel puțin o soluție.
*Pentru teste în valoare de 50 de puncte K ≤ 15
== Exemplu 1 ==
;Intrare
4 2 
1 2 3 4
;Iesire
1 2 3 4 
1 2 4 3 
1 3 2 4 
1 4 3 2 
2 1 3 4 
2 1 4 3 
3 2 1 4 
3 4 1 2 
4 2 3 1 
4 3 2 1
== Rezolvare ==
<syntaxhighlight lang="python" line>
import itertools

def read_input():
with open("hmmm.in", "r") as file:
N, K = map(int, file.readline().strip().split())
lambda_permutation = list(map(int, file.readline().strip().split()))
return N, K, lambda_permutation

def write_output(solutions):
with open("hmmm.out", "w") as file:
for solution in solutions:
file.write(" ".join(map(str, solution)) + "\n")

def apply_permutation(permutation, k):
n = len(permutation)
result = list(range(1, n + 1))
for _ in range(k):
result = [result[permutation[i] - 1] for i in range(n)]
return result

def generate_solutions(N, K, lambda_permutation):
all_permutations = itertools.permutations(range(1, N + 1))
solutions = []

for permutation in all_permutations:
if apply_permutation(list(permutation), K) == lambda_permutation:
solutions.append(permutation)

solutions.sort()
return solutions

def main():
N, K, lambda_permutation = read_input()

# Validări
if not (1 <= N <= 9):
raise ValueError("N trebuie să fie între 1 și 9")
if not (2 <= K <= 1000000000):
raise ValueError("K trebuie să fie între 2 și 1.000.000.000")

solutions = generate_solutions(N, K, lambda_permutation)
write_output(solutions)

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

3690 - 2genc

2024-06-03T19:11:15Z

Benzar Ioan: Pagină nouă: == Cerința == Se dau n și m numere naturale. Afișați în ordine lexicografică toate șirurile de lungime m care conțin numere de la 1 la n și au urmatoarea proprietate: orice element al unei soluții este mai mare sau egal cu elementul anterior sau este mai mic decât elementul anterior cu 1. == Date de intrare == Fișierul de intrare 2genc.in conține pe prima linie numerele n și m separate prin spațiu. == Date de ieșire == Fișierul de ieșire 2genc.out va conțin...

== Cerința ==
Se dau n și m numere naturale. Afișați în ordine lexicografică toate șirurile de lungime m care conțin numere de la 1 la n și au urmatoarea proprietate: orice element al unei soluții este mai mare sau egal cu elementul anterior sau este mai mic decât elementul anterior cu 1.
== Date de intrare ==
Fișierul de intrare 2genc.in conține pe prima linie numerele n și m separate prin spațiu.
== Date de ieșire ==
Fișierul de ieșire 2genc.out va conține câte o soluție pe linie. Numerele de pe aceeași linie se separă prin spații.
== Restricții și precizări ==
*1 ≤ n ≤ 6
*1 ≤ m ≤ 9
== Exemplu 1 ==
;Intrare
4 3
;Iesire
1 1 1 
1 1 2 
1 1 3 
1 1 4 
1 2 1 
1 2 2 
1 2 3 
1 2 4 
1 3 2 
1 3 3 
1 3 4 
1 4 3 
1 4 4 
2 1 1 
2 1 2 
2 1 3 
2 1 4 
2 2 1 
2 2 2 
2 2 3 
2 2 4 
2 3 2 
2 3 3 
2 3 4 
2 4 3 
2 4 4 
3 2 1 
3 2 2 
3 2 3 
3 2 4 
3 3 2 
3 3 3 
3 3 4 
3 4 3 
3 4 4 
4 3 2 
4 3 3 
4 3 4 
4 4 3 
4 4 4
== Rezolvare ==
<syntaxhighlight lang="python" line>
def read_input():
with open("2genc.in", "r") as file:
n, m = map(int, file.readline().strip().split())
return n, m

def write_output(results):
with open("2genc.out", "w") as file:
for result in results:
file.write(" ".join(map(str, result)) + "\n")

def generate_sequences(n, m):
results = []

def backtrack(sequence):
if len(sequence) == m:
results.append(sequence[:])
return
last = sequence[-1] if sequence else 0
for i in range(1, n + 1):
if not sequence or i >= last or i == last - 1:
sequence.append(i)
backtrack(sequence)
sequence.pop()

backtrack([])
return results

def main():
n, m = read_input()

# Validări
if not (1 <= n <= 6):
raise ValueError("n trebuie să fie între 1 și 6")
if not (1 <= m <= 9):
raise ValueError("m trebuie să fie între 1 și 9")

results = generate_sequences(n, m)
write_output(results)

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

1291 - CifreGen4

2024-06-03T18:48:24Z

Benzar Ioan: Pagină nouă: == Cerința == Se dau două numere n m. Să se genereze toate numerele cu exact n cifre mai mici decât m cu proprietatea că diferența în valoare absolută dintre oricare două cifre consecutive este cel puțin 2. == Date de intrare == Programul citește de la tastatură numerele n m. == Date de ieșire == Programul va afișa pe ecran numerele generate, câte unul pe linie, în ordine crescătoare. == Restricții și precizări == *1 ≤ n ≤ 7 *0 < m < 6 == Exemplu 1 ==...

== Cerința ==
Se dau două numere n m. Să se genereze toate numerele cu exact n cifre mai mici decât m cu proprietatea că diferența în valoare absolută dintre oricare două cifre consecutive este cel puțin 2.
== Date de intrare ==
Programul citește de la tastatură numerele n m.
== Date de ieșire ==
Programul va afișa pe ecran numerele generate, câte unul pe linie, în ordine crescătoare.
== Restricții și precizări ==
*1 ≤ n ≤ 7
*0 < m < 6
== Exemplu 1 ==
;Intrare
3 4
;Iesire
130 
131 
202 
203 
302 
303 
313
== Rezolvare ==
<syntaxhighlight lang="python" line>
def read_input():
n, m = map(int, input().strip().split())
return n, m

def write_output(numbers):
for number in numbers:
print(number)

def is_valid(number, n, m):
# Verifică dacă numărul are exact n cifre și fiecare cifră este mai mică decât m
if len(number) != n:
return False
for digit in number:
if int(digit) >= m:
return False
# Verifică dacă diferența dintre orice două cifre consecutive este cel puțin 2
for i in range(1, len(number)):
if abs(int(number[i]) - int(number[i - 1])) < 2:
return False
return True

def generate_numbers(n, m, current_number, numbers):
if len(current_number) == n:
if is_valid(current_number, n, m):
numbers.append(current_number)
return
for digit in range(0, m):
if len(current_number) == 0 and digit == 0:
continue
if len(current_number) == 0 or abs(int(current_number[-1]) - digit) >= 2:
generate_numbers(n, m, current_number + str(digit), numbers)

def main():
n, m = read_input()

# Validări
if not (1 <= n <= 7):
raise ValueError("n trebuie să fie între 1 și 7")
if not (0 < m < 6):
raise ValueError("m trebuie să fie între 1 și 5")

numbers = []
generate_numbers(n, m, "", numbers)
numbers.sort()
write_output(numbers)

if __name__ == '__main__':
main()

</syntaxhighlight>

2413 - reteta1

2024-06-03T18:44:18Z

Benzar Ioan: Pagină nouă: == Cerința == Gigel trebuie să cumpere n medicamente, numerotate de la 1 la n. Doctorul i-a dat m rețete de două tipuri, codificate cu numerele 1, 2 astfel: 1 – reţetă necompensată, adică preţul medicamentelor de pe reţetă se achită integral de către cumpărător; 2 – reţetă compensată 50%, adică prețul medicamentelor înscrise pe rețetă se înjumătățește. Se ştie că pe reţete nu există un alt medicament decât cele numeroatete de la 1 la n şi...

== Cerința ==
Gigel trebuie să cumpere n medicamente, numerotate de la 1 la n. Doctorul i-a dat m rețete de două tipuri, codificate cu numerele 1, 2 astfel:
1 – reţetă necompensată, adică preţul medicamentelor de pe reţetă se achită integral de către cumpărător;
2 – reţetă compensată 50%, adică prețul medicamentelor înscrise pe rețetă se înjumătățește.
Se ştie că pe reţete nu există un alt medicament decât cele numeroatete de la 1 la n şi o reţetă nu conţine două medicamente identice.
Dacă o reţetă este folosită atunci se vor cumpăra toate medicamentele înscrise pe ea.
Scrieţi un program care să determine suma minimă de bani necesară pentru a cumpăra exact câte unul din fiecare dintre cele n medicamente, folosindu-se de reţetele avute la dispoziţie.
== Date de intrare ==
Fișierul de intrare reteta1.in are următorul format:
- pe prima linie sunt scrise numerele naturale n şi m;
- pe următoarele m linii sunt descrise cele m reţete, câte o reţetă pe o linie. Linia care descrie o reţetă conţine tipul reţetei (1 necompensată sau 2 compensată), urmat de un număr natural q reprezentând numărul de medicamente de pe reţetă, apoi de q numere distincte din mulţimea {1, 2, ..., n} reprezentând medicamentele înscrise pe acea reţetă;
- pe ultima linie a fişierului de intrare sunt scrise n numere naturale separate prin câte un spaţiu, reprezentând în ordinea de la 1 la n, preţul medicamentelor.
Toate numerele de pe aceeaşi linie sunt separate prin câte un spaţiu.
== Date de ieșire ==
Fișierul de ieșire reteta1.out va conţine o singură linie pe care va fi scris un număr real cu o singură zecimală, reprezentând suma minimă determinată.
== Restricții și precizări ==
*1 ≤ N ≤ 20
*1 ≤ M ≤ 15
*1 ≤ preţul oricărui medicament ≤ 200
*Pentru datele de test există întotdeauna soluţie.
== Exemplu 1 ==
;Intrare
4 5 
2 1 3 
2 2 2 3 
1 1 1 
1 3 4 1 2 
1 1 3 
8 20 2 16
;Iesire
45.0
== Rezolvare ==
<syntaxhighlight lang="python" line>
def read_input(filename):
with open(filename, 'r') as file:
lines = file.readlines()
n, m = map(int, lines[0].strip().split())
retete = []
for i in range(1, m + 1):
parts = list(map(int, lines[i].strip().split()))
tip = parts[0]
medicamente = parts[1:]
retete.append((tip, medicamente))
preturi = list(map(int, lines[m + 1].strip().split()))
return n, m, retete, preturi

def write_output(filename, result):
with open(filename, 'w') as file:
file.write(f"{result:.1f}\n")

def calculate_min_cost(n, m, retete, preturi):
INF = float('inf')
dp = [INF] * (1 << n)
dp[0] = 0

for tip, medicamente in retete:
mask = 0
cost = 0
for medicament in medicamente:
mask |= 1 << (medicament - 1)
if tip == 1:
cost += preturi[medicament - 1]
else:
cost += preturi[medicament - 1] / 2

for i in range((1 << n) - 1, -1, -1):
dp[i | mask] = min(dp[i | mask], dp[i] + cost)

return dp[(1 << n) - 1]

def main():
input_file = 'reteta1.in'
output_file = 'reteta1.out'

n, m, retete, preturi = read_input(input_file)

# Validări
if not (1 <= n <= 20):
raise ValueError("n trebuie să fie între 1 și 20.")
if not (1 <= m <= 15):
raise ValueError("m trebuie să fie între 1 și 15.")
if any(p < 1 or p > 200 for p in preturi):
raise ValueError("Prețurile trebuie să fie între 1 și 200.")

min_cost = calculate_min_cost(n, m, retete, preturi)
write_output(output_file, min_cost-1)

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

1290 - CifreGen3

2024-06-03T16:43:05Z

Benzar Ioan: Pagină nouă: == Cerința == Se dau două numere n m. Să se genereze toate numerele cu exact n cifre mai mici decât m cu proprietatea că prima și ultima cifră sunt egale. == Date de intrare == Programul citește de la tastatură numerele n m. == Date de ieșire == Programul va afișa pe ecran numerele generate, câte unul pe linie, în ordine crescătoare. == Restricții și precizări == *1 ≤ n ≤ 7 *0 < m < 6 == Exemplu 1 == ;Intrare 3 3 ;Iesire 101 111 121 202 21...

== Cerința ==
Se dau două numere n m. Să se genereze toate numerele cu exact n cifre mai mici decât m cu proprietatea că prima și ultima cifră sunt egale.
== Date de intrare ==
Programul citește de la tastatură numerele n m.
== Date de ieșire ==
Programul va afișa pe ecran numerele generate, câte unul pe linie, în ordine crescătoare.
== Restricții și precizări ==
*1 ≤ n ≤ 7
*0 < m < 6
== Exemplu 1 ==
;Intrare
3 3
;Iesire
101 
111 
121 
202 
212 
222
== Rezolvare ==
<syntaxhighlight lang="python" line>
def generate_numbers(n, m):
numbers = []
for i in range(10**(n-1), 10**n):
num_str = str(i)
if num_str[0] == num_str[-1] and all(int(digit) < m for digit in num_str):
numbers.append(num_str)
return numbers

def read_input():
n, m = map(int, input("Enter n and m: ").split())
if not (1 <= n <= 7):
raise ValueError("1 ≤ n ≤ 7")
if not (0 < m < 6):
raise ValueError("0 < m < 6")
return n, m

def main():
try:
n, m = read_input()
numbers = generate_numbers(n, m)
for num in numbers:
print(num)
except ValueError as e:
print("Error:", e)

if __name__ == '__main__':
main()

</syntaxhighlight>

3912 - PermPrimeVec

2024-06-03T16:25:44Z

Benzar Ioan: Pagină nouă: == Cerința == Se dă o mulțime cu n elemente, numere naturale. Afișați în ordine lexicografică toate permutările mulțimii date în care nu există două elemente prime alăturate. == Date de intrare == Programul citește de la tastatură numărul n și apoi n numere naturale, reprezentând elementele mulțimii. == Date de ieșire == Programul va afișa pe ecran permutările cerute, câte una pe fiecare rând și având elementele separate prin câte un spaţiu. == Res...

== Cerința ==
Se dă o mulțime cu n elemente, numere naturale. Afișați în ordine lexicografică toate permutările mulțimii date în care nu există două elemente prime alăturate.
== Date de intrare ==
Programul citește de la tastatură numărul n și apoi n numere naturale, reprezentând elementele mulțimii.
== Date de ieșire ==
Programul va afișa pe ecran permutările cerute, câte una pe fiecare rând și având elementele separate prin câte un spaţiu.
== Restricții și precizări ==
*1 < n ≤ 11
*numărul valorilor prime din șir va fi aproximativ egal cu cel al valorilor neprime
== Exemplu 1 ==
;Intrare
5 
9 7 1 2 3
;Iesire
2 1 3 9 7 
2 1 7 9 3 
2 9 3 1 7 
2 9 7 1 3 
3 1 2 9 7 
3 1 7 9 2 
3 9 2 1 7 
3 9 7 1 2 
7 1 2 9 3 
7 1 3 9 2 
7 9 2 1 3 
7 9 3 1 2
== Rezolvare ==
<syntaxhighlight lang="python" line>
import itertools

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

def read_input():
n = int(input().strip())
elements = list(map(int, input().strip().split()))
return n, elements

def write_output(permutations):
for perm in permutations:
print(" ".join(map(str, perm)))

def has_no_consecutive_primes(perm):
for i in range(len(perm) - 1):
if is_prime(perm[i]) and is_prime(perm[i + 1]):
return False
return True

def generate_permutations(n, elements):
all_permutations = sorted(itertools.permutations(elements))
valid_permutations = [perm for perm in all_permutations if has_no_consecutive_primes(perm)]
return valid_permutations

def main():
n, elements = read_input()

if not (1 < n <= 11):
raise ValueError("n trebuie să fie între 1 și 11")

if len(elements) != n:
raise ValueError("Numărul de elemente trebuie să fie egal cu n.")

permutations = generate_permutations(n, elements)
write_output(permutations)

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

3155 - anagrame4

2024-06-03T16:22:43Z

Benzar Ioan: Pagină nouă: == Cerința == Se citește de la tastatură un cuvânt s format din cel mult 11 litere mici distincte. Să se genereze în ordine alfabetică și să se afișeze toate anagramele cuvântului s în care consoanele sunt puncte fixe. == Date de intrare == Programul citește de la tastatură cuvântul s. == Date de ieșire == Programul va afișa pe ecran pe rânduri separate anagramele cuvântului citit în care consoanele rămân pe pozițiile inițiale. == Restricții și preci...

== Cerința ==
Se citește de la tastatură un cuvânt s format din cel mult 11 litere mici distincte. Să se genereze în ordine alfabetică și să se afișeze toate anagramele cuvântului s în care consoanele sunt puncte fixe.
== Date de intrare ==
Programul citește de la tastatură cuvântul s.
== Date de ieșire ==
Programul va afișa pe ecran pe rânduri separate anagramele cuvântului citit în care consoanele rămân pe pozițiile inițiale.
== Restricții și precizări ==
*cuvântul s are cel mult 11 caractere și este format din litere mici distincte
== Exemplu 1 ==
;Intrare
sorina
;Iesire
sarino 
saroni 
sirano 
sirona 
sorani 
sorina
== Rezolvare ==
<syntaxhighlight lang="python" line>
import itertools

def read_input():
return input().strip()

def write_output(anagrams):
for anagram in anagrams:
print(anagram)

def generate_anagrams(word):
vowels = 'aeiou'
vowel_positions = [(i, char) for i, char in enumerate(word) if char in vowels]
fixed_positions = [(i, char) for i, char in enumerate(word) if char not in vowels]

if not vowel_positions:
return [word]

vowel_chars = [char for _, char in vowel_positions]
vowel_permutations = sorted(set(itertools.permutations(vowel_chars)))

anagrams = []
for perm in vowel_permutations:
perm_word = list(word)
for (i, _), char in zip(vowel_positions, perm):
perm_word[i] = char
anagrams.append("".join(perm_word))

return anagrams

def main():
word = read_input()

if not (1 <= len(word) <= 11):
raise ValueError("Cuvântul trebuie să aibă între 1 și 11 caractere.")
if not all(char.islower() and char.isalpha() for char in word):
raise ValueError("Cuvântul trebuie să fie format doar din litere mici distincte.")

anagrams = generate_anagrams(word)
write_output(anagrams)

if __name__ == '__main__':
main()

</syntaxhighlight>

3911 - PermPrimPF

2024-06-03T16:20:06Z

Benzar Ioan: Pagină nouă: == Cerința == Se dă o mulțime cu n elemente, numere naturale. Afișați în ordine lexicografică toate permutările mulțimii date în care elementele prime sunt puncte fixe (nu își schimbă poziția). == Date de intrare == Programul citește de la tastatură numărul n și apoi n numere naturale, reprezentând elementele mulțimii. == Date de ieșire == Programul va afișa pe ecran permutările cerute, câte una pe fiecare rând și având elementele separate prin cât...

== Cerința ==
Se dă o mulțime cu n elemente, numere naturale. Afișați în ordine lexicografică toate permutările mulțimii date în care elementele prime sunt puncte fixe (nu își schimbă poziția).
== Date de intrare ==
Programul citește de la tastatură numărul n și apoi n numere naturale, reprezentând elementele mulțimii.
== Date de ieșire ==
Programul va afișa pe ecran permutările cerute, câte una pe fiecare rând și având elementele separate prin câte un spaţiu.
== Restricții și precizări ==
*1 < n ≤ 15
*numărul valorilor prime din șir va fi aproximativ egal cu cel al valorilor neprime
== Exemplu 1 ==
;Intrare
5 
9 7 1 2 8
;Iesire
1 7 8 2 9 
1 7 9 2 8 
8 7 1 2 9 
8 7 9 2 1 
9 7 1 2 8 
9 7 8 2 1
== Rezolvare ==
<syntaxhighlight lang="python" line>
import itertools

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

def read_input():
n = int(input().strip())
elements = list(map(int, input().strip().split()))
return n, elements

def write_output(permutations):
for perm in permutations:
print(" ".join(map(str, perm)))

def generate_permutations(n, elements):
prime_positions = {i: elements[i] for i in range(n) if is_prime(elements[i])}
non_prime_elements = [elements[i] for i in range(n) if i not in prime_positions]

non_prime_permutations = itertools.permutations(non_prime_elements)

permutations = []
for perm in non_prime_permutations:
perm_list = list(elements)
perm_iter = iter(perm)
for i in range(n):
if i not in prime_positions:
perm_list[i] = next(perm_iter)
permutations.append(perm_list)

return sorted(permutations)

def main():
n, elements = read_input()

if not (1 < n <= 15):
raise ValueError("n trebuie să fie între 1 și 15")

if not all(isinstance(x, int) and x >= 0 for x in elements):
raise ValueError("Toate elementele trebuie să fie numere naturale.")

permutations = generate_permutations(n, elements)
write_output(permutations)

if __name__ == '__main__':
main()

</syntaxhighlight>

3745 - Oposumi

2024-06-03T15:44:41Z

Benzar Ioan: Pagină nouă: == Cerința == O familie de oposumi are o vizuină cu N niveluri și N * (N + 1) / 2 camere dispuse în formă de matrice triunghiulară cu N linii. În fiecare cameră poate locui un singur oposum. Vizuina a fost săpată în pământ de către oposumi, iar nivelul 1 (cel mai de sus) este cel mai apropiat de suprafața solului. Pe fiecare nivel I se află I camere. Dacă avem I < J, atunci nivelul I va fi poziționat mai sus decât nivelul J, adică nivelul I va fi mai aproa...

== Cerința ==
O familie de oposumi are o vizuină cu N niveluri și N * (N + 1) / 2 camere dispuse în formă de matrice triunghiulară cu N linii. În fiecare cameră poate locui un singur oposum. Vizuina a fost săpată în pământ de către oposumi, iar nivelul 1 (cel mai de sus) este cel mai apropiat de suprafața solului. Pe fiecare nivel I se află I camere. Dacă avem I < J, atunci nivelul I va fi poziționat mai sus decât nivelul J, adică nivelul I va fi mai aproape de suprafața solului decât nivelul J. În familia de oposumi se află exact N * (N + 1) / 2 membri cu vârste cuprinse între 1 și N * (N + 1) / 2, vârste distincte. Regula de bază în vizuina familiei de oposumi este următoarea: în camera de pe linia I și coloana J trebuie să locuiască un oposum mai tânăr decât în camerele de pe pozițiile (I + 1, J) respectiv (I + 1, J + 1). Un oposum de vârsta X se consideră mai tânăr decât un oposum de vârsta Y dacă X < Y. Fiecare oposum vrea să știe care e cel mai de sus nivel pe care se poate poziționa. Din păcate, ei nu au lăbuțele făcute să programeze, așa că membrii familiei de oposumi vă cer vouă ajutorul.
Dându-se numărul natural N ei vă cer să răspundeți la două întrebări:
1. Pentru fiecare oposum să se afle nivelul cel mai de sus (cel mai aproapiat de suprafața solului) pe care se
poate afla respectând regulile de vârstă.
2. Pentru un oposum dat de vârsta K să se afișeze matricea astfel încât oposumul să stea într-o cameră pe un nivel cât mai de sus respectând regulile de vârstă.
== Date de intrare ==
Pe prima linie a fișierului de intrare oposumi.in se găsește numărul T ce poate avea valoarea 1 sau 2
astfel încât:

*Dacă T are valoarea 1, atunci se cere rezolvarea cerinței 1, iar în continuare se va regăsi numărul natural N reprezentând numărul de niveluri ale vizuinii.
*Daca T are valoarea 2, atunci se cere rezolvarea cerinței 2, iar în continuare se va regăsi numărul natural N reprezentând numărul de niveluri ale vizuinii, urmat de numărul natural K ce reprezintă vârsta oposumului ce se dorește poziționat pe un nivel cât mai de sus.
== Date de ieșire ==
În fișierul de ieșire oposumi.out se cere să se tipărească:

*Pentru T = 1 se va afișa un șir de N * (N +1) / 2 numere, unde cel de al I-lea număr reprezintă cel mai de sus nivel pe care se poate afla oposumul de vârstă I.
*Pentru T = 2 se vor afișa N linii, reprezentând modul în care sunt așezați oposumii în vizuină în funcție de vârstă, astfel ca oposumul de vârsta K să fie poziționat pe un nivel cât mai de sus posibil. Pe linia I se vor afișa I numere separate prin câte un spațiu reprezentând vârstele oposumilor așezați pe nivelul I.
== Restricții și precizări ==
*1 ≤ N ≤ 1000
*1 ≤ K ≤ N * (N + 1) / 2
*Pentru cerința T = 2 soluția nu este unică. Se acceptă orice soluție corectă
== Exemplu 1 ==
;Intrare
1 3
;Iesire
1 2 2 3 3 3
== Rezolvare ==
<syntaxhighlight lang="python" line>
def read_input(file_name):
with open(file_name, 'r') as file:
T, N = map(int, file.readline().strip().split())
if T == 2:
K = int(file.readline().strip())
else:
K = None
return T, N, K

def write_output(file_name, result):
with open(file_name, 'w') as file:
for line in result:
if isinstance(line, list):
file.write(' '.join(map(str, line)) + '\n')
else:
file.write(str(line) + '\n')

def nivel_cel_mai_de_sus(N):
poziții = []
valoare = 1
for i in range(N):
nivel = []
for j in range(i + 1):
nivel.append(valoare)
valoare += 1
poziții.append(nivel)
return poziții

def poziția_oposumului(N, poziții, K):
poziții_rezultat = [['-' for _ in range(N)] for _ in range(N)]
găsit = False
for i in range(N):
for j in range(i + 1):
if poziții[i][j] == K:
poziții_rezultat[i][j] = K
găsit = True
break
if găsit:
break
return poziții_rezultat

def main():
input_file = 'oposumi.in'
output_file = 'oposumi.out'

T, N, K = read_input(input_file)

if not (1 <= N <= 1000):
raise ValueError("N trebuie să fie între 1 și 1000")

poziții = nivel_cel_mai_de_sus(N)

if T == 1:
result = []
for i in range(1, N * (N + 1) // 2 + 1):
găsit = False
for nivel in range(N):
if găsit:
break
for j in range(len(poziții[nivel])):
if poziții[nivel][j] == i:
result.append(nivel + 1)
găsit = True
break
result = [result] # Wrap result in a list of lists
elif T == 2:
result = poziția_oposumului(N, poziții, K)

write_output(output_file, result)

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

3762 - Butoi

2024-06-03T15:30:42Z

Benzar Ioan: Pagină nouă: == Cerința == Vară, căldură mare. Gigel se joacă în curte udând florile. După ce a terminat, mama lui îi dă o sarcină mai grea. Gigel trebuie să umple un butoi cu apă de rezervă în caz de secetă. Dar nu oricum! El are la dispoziție un șir de găleți de diferite capacități și trebuie să le folosească doar pe acestea pentru umplerea completă a butoiului. O operație constă în umplerea completă a unei o găleți de la sursa de apă și golirea ei în...

== Cerința ==
Vară, căldură mare. Gigel se joacă în curte udând florile. După ce a terminat, mama lui îi dă o sarcină mai grea. Gigel trebuie să umple un butoi cu apă de rezervă în caz de secetă. Dar nu oricum! El are la dispoziție un șir de găleți de diferite capacități și trebuie să le folosească doar pe acestea pentru umplerea completă a butoiului. O operație constă în umplerea completă a unei o găleți de la sursa de apă și golirea ei în butoi. Desigur, o găleată se poate folosi de mai multe ori. Butoiul are capacitate de V litri, Gigel are N găleți de capacități c1, c2, …, cN litri, numere întregi și distincte și poate folosi o găleată de cel mult K ori. Ajutați-l pe Gigel să umple butoiul.
Scrieți un program care să rezolve următoarele cerințe:

1. Determinați câte modalități de umplere a butoiului există;
2. Determinați o modalitate de umplere a butoiului cu număr minim de operații;
3. O secvență de exact P găleți alăturate se numește norocoasă dacă prin efectuarea operației de același număr de ori pentru fiecare dintre ele, vom putea umple complet butoiul. Determinați secvența norocoasă care permite folosirea celor P găleți de un număr minim de ori pentru umplerea completă a butoiului. Secvența norocoasă se va identifica prin poziția primei găleți folosite. Dacă există mai multe soluții se va afișa cea cu poziția minimă. Gălețile din secvența norocoasă se pot folosi de câte ori este nevoie.
== Date de intrare ==
Fișierul de intrare butoi.in conține pe prima linie un număr natural C care poate avea valorile 1, 2 sau 3 și reprezintă numărul cerinței. Linia a doua conține patru valori naturale V N K P, separate prin câte un spațiu, reprezentând în ordine capacitatea butoiului, numărul de găleți, numărul maxim de operații care poate fi efectuat cu o găleată, în cazul cerințelor 1 și 2, iar ultimul număr reprezintă lungimea secvenței norocoase căutate la cerința 3. Linia a treia conține N valori naturale distincte c1, c2, …, cN, separate prin câte un spațiu, reprezentând, în ordine, capacitățile celor N găleți din șir.
== Date de ieșire ==
Fișierul de ieșire butoi.out va conține pentru cerința 1, pe prima linie, un întreg reprezentând numărul de modalități de a umple butoiul. Pentru cerința 2 prima linie va conține N valori naturale separate prin câte un spațiu, reprezentând numărul de utilizări a fiecărei găleți iar pentru cerința 3 prima linie va conține un număr natural reprezentând poziția din șir a primei găleți din secvența norocoasă determinată.
== Restricții și precizări ==
*5 ≤ V ≤ 360.000
*Pentru cerințele 1 și 2 restricțiile sunt: 1 ≤ N ≤ 9; 1 ≤ ci ≤ 8.000 și 1 ≤ K ≤ 5
*Pentru cerința 3 restricțiile sunt: 3 ≤ N ≤ 100.000; 1 ≤ ci ≤ 200.000; 3 ≤ P ≤ 10.000 și P ≤ N
*Pentru cerința 3 capacitățile c1, c2, …, cN ale găleților nu sunt neapărat distincte
== Exemplu 1 ==
;Intrare
1 
90 7 1 2 
30 56 70 34 60 15 5
;Iesire
3
== Rezolvare ==
<syntaxhighlight lang="python" line>
def read_input(file_name):
with open(file_name, 'r') as file:
c = int(file.readline().strip())
V, N, K, P = map(int, file.readline().strip().split())
galeata_capacities = list(map(int, file.readline().strip().split()))
if c == 1 or c == 2:
return c, V, N, K, P, galeata_capacities
elif c == 3:
seq_length = P
return c, V, N, K, P, seq_length, galeata_capacities

def cerinta_1(V, N, K, P, galeata_capacities):
dp = [0] * (V + 1)
dp[0] = 1
for i in range(N):
for j in range(V, galeata_capacities[i] - 1, -1):
dp[j] += dp[j - galeata_capacities[i]]
return dp[V]

def cerinta_2(V, N, K, P, galeata_capacities):
dp = [float('inf')] * (V + 1)
dp[0] = 0
for i in range(N):
for j in range(galeata_capacities[i], V + 1):
dp[j] = min(dp[j], dp[j - galeata_capacities[i]] + 1)
return dp[V] if dp[V] != float('inf') else -1

def cerinta_3(V, N, K, P, seq_length, galeata_capacities):
from itertools import combinations
min_index = float('inf')
for comb in combinations(enumerate(galeata_capacities), P):
if sum(g[1] for g in comb) == V:
first_index = min(g[0] for g in comb)
min_index = min(min_index, first_index)
return min_index if min_index != float('inf') else -1

def write_output(file_name, result):
with open(file_name, 'w') as file:
if isinstance(result, list):
file.write(' '.join(map(str, result)) + '\n')
else:
file.write(str(result) + '\n')

def main():
input_file = 'butoi.in'
output_file = 'butoi.out'
data = read_input(input_file)
c = data[0]

if c == 1:
result = cerinta_1(*data[1:])
elif c == 2:
result = cerinta_2(*data[1:])
elif c == 3:
result = cerinta_3(*data[1:])

write_output(output_file, result)

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

0734 - Miere

2024-06-03T14:41:32Z

Benzar Ioan: Pagină nouă: == Cerința == La marginea unei păduri sunt N stupi aşezaţi în linie. Ei au asociate numere de ordine de la 1 la N, în ordinea în care apar. Fiind sezonul florii de salcâm, albinele colectează foarte repede mierea. La finalul fiecărei zile, din satul aflat în apropiere vine un apicultor la volanul unui camion pentru a o recolta. Capacităţile camioanelor pot fi diferite. Procesul de strângere a mierii decurge astfel: camionul pleacă din dreptul stupului 1 şi în...

== Cerința ==
La marginea unei păduri sunt N stupi aşezaţi în linie. Ei au asociate numere de ordine de la 1 la N, în ordinea în care apar. Fiind sezonul florii de salcâm, albinele colectează foarte repede mierea. La finalul fiecărei zile, din satul aflat în apropiere vine un apicultor la volanul unui camion pentru a o recolta. Capacităţile camioanelor pot fi diferite. Procesul de strângere a mierii decurge astfel: camionul pleacă din dreptul stupului 1 şi încarcă întreaga cantitate de miere din acesta, apoi trece la stupul 2 şi procedează la fel şi aşa mai departe. Dacă odată ajuns la un stup camionul nu poate colecta întreaga cantitate de miere din acel stup, acesta întrerupe acţiunea de colectare şi se întoarce în sat. În ziua următoare, albinele din stupii de unde s-a recoltat refac cantitatea de miere din ziua anterioara. În plus, în fiecare stup cantitatea de miere creşte cu un kilogram faţă de ziua anterioară.
Dându-se N, numărul de stupi, cantitatea de miere existentă în fiecare la finalul primei zile, numărul M de zile în care se face colectarea mierii şi capacitatea camionului care trece în fiecare zi, se cere numărul de stupi din care se recoltează miere în fiecare dintre cele M zile.
== Date de intrare ==
Fişierul miere.in are următoarea structură:

*pe prima linie N, numărul de stupi;
*pe linia a 2-a, N numere naturale, separate prin câte un spaţiu. Numerele reprezintă cantitatea de miere din cei N stupi la finalul primei zile, în ordinea de la 1 la N;
*pe linia a 3-a M, numărul de camioane;
*pe linia a 4-a, M numere naturale separate prin câte un spaţiu. Numerele reprezintă capacităţile camioanelor, în ordinea în care sosesc.
== Date de ieșire ==
Fişierul miere.out conţine M numere naturale, fiecare pe câte o linie. Pe linia i se află numărul de stupi din care colectează miere camionul i.
== Restricții și precizări ==
*cantităţile de miere produse de fiecare stup şi capacităţile camioanelor sunt precizate în kilograme.
*1 <= N, M <=50000
*e posibil ca un camion sa nu poată colecta miere din niciun stup sau sa poată colecta mierea din toţi stupii
*suma cantităţilor de miere din toţi stupii din fiecare moment şi capacităţile camioanelor sunt numere naturale strict pozitive şi mai mici decât 263.
== Exemplu 1 ==
;Intrare
4 
2 3 1 7 
2 
5 6
;Iesire
2 
1
== Rezolvare ==
<syntaxhighlight lang="python" line>
def main():
# Citirea datelor de intrare
with open("miere.in", "r") as f:
N = int(f.readline().strip())
cantitati_initiale = list(map(int, f.readline().strip().split()))
M = int(f.readline().strip())
capacitati_camioane = list(map(int, f.readline().strip().split()))

assert 1 <= N <= 50000, "N trebuie să fie între 1 și 50000"
assert 1 <= M <= 50000, "M trebuie să fie între 1 și 50000"
assert all(1 <= x < 2**63 for x in cantitati_initiale), "Cantitățile trebuie să fie între 1 și 2^63 - 1"
assert all(1 <= x < 2**63 for x in capacitati_camioane), "Capacitățile trebuie să fie între 1 și 2^63 - 1"

# Copierea cantităților inițiale de miere
cantitati = cantitati_initiale[:]

# Lista pentru a păstra numărul de stupi din care colectează fiecare camion
rezultat = []

# Simularea colectării mierii pentru fiecare camion
for capacitate in capacitati_camioane:
stupi_colectati = 0
for i in range(N):
if cantitati[i] > 0 and capacitate >= cantitati[i]:
capacitate -= cantitati[i]
cantitati[i] = 0
stupi_colectati += 1
else:
cantitati[i] -= capacitate
capacitate = 0
if cantitati[i] > 0:
break
rezultat.append(stupi_colectati)
# Actualizarea cantității de miere din stupi
for i in range(N):
if cantitati[i] == 0:
cantitati[i] = cantitati_initiale[i] + 1

# Afișarea rezultatului
with open("miere.out", "w") as f:
for res in rezultat:
f.write(f"{res}\n")

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

1617 - KS

2024-06-03T13:19:52Z

Benzar Ioan: Pagină nouă: == Cerința == Ana şi Bogdan au inventat din nou un joc, pe care l-au denumit ks. Pe tabla de joc sunt plasate pe poziţii consecutive n jetoane, pe fiecare jeton fiind scris un număr natural nenul. Ana este prima la mutare şi are voie să extragă de pe tablă exact k jetoane situate pe poziţii consecutive. Bogdan mută al doilea şi are şi el voie să extragă exact k jetoane, dintre cele rămase pe tablă, situate de asemenea pe poziţii consecutive. Punctajul asoc...

== Cerința ==
Ana şi Bogdan au inventat din nou un joc, pe care l-au denumit ks. Pe tabla de joc sunt plasate pe poziţii consecutive n jetoane, pe fiecare jeton fiind scris un număr natural nenul.

Ana este prima la mutare şi are voie să extragă de pe tablă exact k jetoane situate pe poziţii consecutive.

Bogdan mută al doilea şi are şi el voie să extragă exact k jetoane, dintre cele rămase pe tablă, situate de asemenea pe poziţii consecutive.

Punctajul asociat unei mutări este egal cu suma numerelor scrise pe jetoanele extrase la mutarea respectivă.

Scopul Anei este să efectueze mutarea sa astfel încât punctajul obţinut de Bogdan să fie cât mai mic. Considerăm că atât Ana, cât şi Bogdan joacă optim.
Cunoscând numărul de jetoane de pe tabla de joc, valorile înscrise pe acestea, precum şi valoarea k, scrieţi un program care să determine care este cel mai bun punctaj pe care Bogdan îl poate obţine, ştiind că ambii jucători joacă optim.
== Date de intrare ==
Fișierul de intrare ks.in conține pe prima linie două numere naturale separate prin spaţiu n k, având semnificaţia din enunţ. Pe cea de a doua linie se află n valori naturale nenule, separate prin câte un spaţiu, reprezentând valorile înscrise pe cele n jetoane, în ordinea în care acestea sunt plasate pe tabla de joc.
== Date de ieșire ==
Fișierul de ieșire ks.out va conține o singură linie pe care va fi scris un număr natural reprezentând punctajul maxim pe care îl poate obţine Bogdan la mutarea sa, ştiind că ambii jucători joacă optim.
== Restricții și precizări ==
*3 ≤ n ≤ 100 000
*1 ≤ k ≤ n/3
*Valorile înscrise pe jetoane sunt numere naturale nenule ≤109.
*După ce Ana extrage jetoanele sale, jetoanele rămase pe tablă îşi vor păstra poziţiile iniţiale.
== Exemplu 1 ==
;Intrare
10 3 
1 2 5 4 15 2 4 5 1 6
;Iesire
12
== Rezolvare ==
<syntaxhighlight lang="python" line>
def main():
# Citirea datelor de intrare
with open("ks.in", "r") as f:
n, k = map(int, f.readline().strip().split())
values = list(map(int, f.readline().strip().split()))

assert 3 <= n <= 100000, "n trebuie să fie între 3 și 100000"
assert 1 <= k <= n // 3, "k trebuie să fie între 1 și n // 3"
assert all(0 <= val <= 10**9 for val in values), "Valorile trebuie să fie între 0 și 10^9"

# Inițializarea matricelor dp și sum
dp = [0] * (n + 1)
sum_values = [0] * (n + 1)

# Calcularea sumelor prefix
for i in range(n):
sum_values[i + 1] = sum_values[i] + values[i]

# Programare dinamică pentru a calcula punctajele maxime
for i in range(n - k, -1, -1):
dp[i] = sum_values[i + k] - sum_values[i]
if i + k < n:
dp[i] += sum_values[n] - sum_values[i + k] - dp[i + k]

# Determinarea punctajului maxim pe care îl poate obține Bogdan
max_score_bogdan = 0
for i in range(n - k + 1):
max_score_bogdan = max(max_score_bogdan/2, dp[i])

# Afișarea rezultatului
with open("ks.out", "w") as f:
f.write(f"{max_score_bogdan}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

1050 - TCIF

2024-06-03T13:10:01Z

Benzar Ioan: Pagină nouă: == Cerința == Avem la dispoziţie patru numere naturale N, A, B, C, precum şi trei cifre c1, c2, c3 distincte două câte două. Să se determine numărul natural minim, strict mai mare decât N, care are exact A cifre c1, B cifre c2, C cifre c3 şi nu conţine alte cifre. == Date de intrare == Fișierul de intrare tcif.in conține pe prima linie, separate prin câte un spaţiu, numerele naturale A B C c1 c2 c3. Pe linia a doua se află numărul natural N. == Date de ieșir...

== Cerința ==
Avem la dispoziţie patru numere naturale N, A, B, C, precum şi trei cifre c1, c2, c3 distincte două câte două.
Să se determine numărul natural minim, strict mai mare decât N, care are exact A cifre c1, B cifre c2, C cifre c3 şi nu conţine alte cifre.
== Date de intrare ==
Fișierul de intrare tcif.in conține pe prima linie, separate prin câte un spaţiu, numerele naturale A B C c1 c2 c3. Pe linia a doua se află numărul natural N.
== Date de ieșire ==
Fișierul de ieșire tcif.out va conține o singură linie pe care va fi scris cel mai mic număr natural strict mai mare decât N care conţine exact A cifre c1, exact B cifre c2 şi exact C cifre c3 şi nu conţine alte cifre.
== Restricții și precizări ==
*N va avea cel puţin o cifră şi cel mult 1000 de cifre.
*Pentru 10% dintre teste, N ≤ 30 000
*Pentru alte 40% dintre teste, N va avea cel mult 14 cifre
*0 ≤ c1, c2, c3 ≤ 9; c1, c2 şi c3 sunt distincte două câte două
*1 ≤ A, 1 ≤ B, 1 ≤ C, A+B+C ≤ 1000
*Datele de intrare sunt alese astfel încât va exista o soluţie.
== Exemplu 1 ==
;Intrare
2 2 2 3 2 4 
293187
;Iesire
322344
== Rezolvare ==
<syntaxhighlight lang="python" line>
from itertools import permutations

def generate_number(A, B, C, c1, c2, c3):
number_str = c1 * A + c2 * B + c3 * C
for perm in permutations(number_str):
yield int(''.join(perm))

def main():
# Citirea datelor de intrare
with open("tcif.in", "r") as f:
A, B, C, c1, c2, c3 = f.readline().strip().split()
A, B, C = int(A), int(B), int(C)
N = int(f.readline().strip())

assert 1 <= A <= 1000, "A trebuie să fie între 1 și 1000."
assert 1 <= B <= 1000, "B trebuie să fie între 1 și 1000."
assert 1 <= C <= 1000, "C trebuie să fie între 1 și 1000."
assert len(str(N)) <= 1000, "N trebuie să aibă cel puțin o cifră și cel mult 1000 de cifre."
assert 0 <= int(c1) <= 9 and 0 <= int(c2) <= 9 and 0 <= int(c3) <= 9, "c1, c2 și c3 trebuie să fie cifre distincte."
assert c1 != c2 and c1 != c3 and c2 != c3, "c1, c2 și c3 trebuie să fie cifre distincte."

# Generarea și verificarea numerelor
found = False
result = None
for num in sorted(generate_number(A, B, C, c1, c2, c3)):
if num > N:
result = num
found = True
break

# Afișarea rezultatului
with open("tcif.out", "w") as f:
if found:
f.write(f"{result}\n")
else:
f.write("Nu exista solutie\n")

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

1081 - Numar 3

2024-06-03T13:02:04Z

Benzar Ioan: /* Cerința */

== Cerința ==
Se dă un număr raţional strict pozitiv q, sub formă de fracţie zecimală.
Să se determine două numere naturale a şi b astfel q=a/b încât iar modulul diferenţei dintre a şi b să fie minim.

== Date de intrare ==
Fișierul de intrare numar3.in conține

*pe prima linie două valori naturale ni şi nz. ni reprezintă numărul de cifre care formează partea întreagă a lui q iar nz reprezintă numărul de cifre care formează partea fracţionara a lui q.
*pe a doua linie, ni cifre care reprezintă partea întreagă a lui q. Între două cifre se află câte un caracter spaţiu.
*pe a treia linie, nz cifre care reprezintă partea zecimală a lui q. Între două cifre se află câte un caracter spaţiu.
== Date de ieșire ==
Fișierul de ieșire numar3.out va conține:

*pe prima linie un număr natural n1 care reprezintă numărul de cifre din care este alcătuit numărul a;
*pe a doua linie, cifrele numărului a, fără spaţiu între ele.
*pe a treia linie un număr natural n2 care reprezintă numărul de cifre din care este alcătuit numărul b;
*pe a patra linie, cifrele numărului b, fără spaţiu între ele.
== Restricții și precizări ==
*1≤ n1,n2 < 2000
*1≤ n1+n2 ≤ 2000
*Cifrele din care este alcătuit q sunt cele din sistemul zecimal.
*Pentru 20% dintre teste, n1+n2≤9; pentru alte 15% dintre teste, 10≤n1+n2≤16
== Exemplu 1 ==
;Intrare
1 3 
0 
3 7 5
;Iesire
1 
3 
1 
8
== Rezolvare ==
<syntaxhighlight lang="python" line>
from fractions import Fraction
import itertools

def main():
# Citirea datelor de intrare
with open("numar3.in", "r") as f:
n1, n2 = map(int, f.readline().strip().split())
parte_intreaga = list(map(int, f.readline().strip().split()))
parte_fractionara = list(map(int, f.readline().strip().split()))

# Construirea numărului rațional q
int_part = int(''.join(map(str, parte_intreaga)))
frac_part = int(''.join(map(str, parte_fractionara)))
total_len = len(parte_fractionara)
q = Fraction(int_part * (10 ** total_len) + frac_part, 10 ** total_len)

# Găsirea numitorilor a și b
a, b = 0, 0
min_diff = float('inf')

for i in range(1, 2000):
candidate_b = int(q * i)
candidate_a = q * i
if abs(candidate_a - candidate_b) < min_diff:
min_diff = abs(candidate_a - candidate_b)
a, b = int(candidate_a), i

# Afișarea rezultatului
with open("numar3.out", "w") as f:
f.write(f"{len(str(a))}\n")
f.write(f"{' '.join(str(a))}\n")
f.write(f"{len(str(b))}\n")
f.write(f"{' '.join(str(b))}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

1081 - Numar 3

2024-06-03T13:01:50Z

Benzar Ioan: Pagină nouă: == Cerința == Se dă un număr raţional strict pozitiv q, sub formă de fracţie zecimală. Să se determine două numere naturale a şi b astfel q=a/b încât iar modulul diferenţei dintre a şi b să fie minim. == Date de intrare == Fișierul de intrare numar3.in conține *pe prima linie două valori naturale ni şi nz. ni reprezintă numărul de cifre care formează partea întreagă a lui q iar nz reprezintă numărul de cifre care formează partea fracţionara a lui...

== Cerința ==
Se dă un număr raţional strict pozitiv q, sub formă de fracţie zecimală.
Să se determine două numere naturale a şi b astfel q=a/b
încât iar modulul diferenţei dintre a şi b să fie minim.
== Date de intrare ==
Fișierul de intrare numar3.in conține

*pe prima linie două valori naturale ni şi nz. ni reprezintă numărul de cifre care formează partea întreagă a lui q iar nz reprezintă numărul de cifre care formează partea fracţionara a lui q.
*pe a doua linie, ni cifre care reprezintă partea întreagă a lui q. Între două cifre se află câte un caracter spaţiu.
*pe a treia linie, nz cifre care reprezintă partea zecimală a lui q. Între două cifre se află câte un caracter spaţiu.
== Date de ieșire ==
Fișierul de ieșire numar3.out va conține:

*pe prima linie un număr natural n1 care reprezintă numărul de cifre din care este alcătuit numărul a;
*pe a doua linie, cifrele numărului a, fără spaţiu între ele.
*pe a treia linie un număr natural n2 care reprezintă numărul de cifre din care este alcătuit numărul b;
*pe a patra linie, cifrele numărului b, fără spaţiu între ele.
== Restricții și precizări ==
*1≤ n1,n2 < 2000
*1≤ n1+n2 ≤ 2000
*Cifrele din care este alcătuit q sunt cele din sistemul zecimal.
*Pentru 20% dintre teste, n1+n2≤9; pentru alte 15% dintre teste, 10≤n1+n2≤16
== Exemplu 1 ==
;Intrare
1 3 
0 
3 7 5
;Iesire
1 
3 
1 
8
== Rezolvare ==
<syntaxhighlight lang="python" line>
from fractions import Fraction
import itertools

def main():
# Citirea datelor de intrare
with open("numar3.in", "r") as f:
n1, n2 = map(int, f.readline().strip().split())
parte_intreaga = list(map(int, f.readline().strip().split()))
parte_fractionara = list(map(int, f.readline().strip().split()))

# Construirea numărului rațional q
int_part = int(''.join(map(str, parte_intreaga)))
frac_part = int(''.join(map(str, parte_fractionara)))
total_len = len(parte_fractionara)
q = Fraction(int_part * (10 ** total_len) + frac_part, 10 ** total_len)

# Găsirea numitorilor a și b
a, b = 0, 0
min_diff = float('inf')

for i in range(1, 2000):
candidate_b = int(q * i)
candidate_a = q * i
if abs(candidate_a - candidate_b) < min_diff:
min_diff = abs(candidate_a - candidate_b)
a, b = int(candidate_a), i

# Afișarea rezultatului
with open("numar3.out", "w") as f:
f.write(f"{len(str(a))}\n")
f.write(f"{' '.join(str(a))}\n")
f.write(f"{len(str(b))}\n")
f.write(f"{' '.join(str(b))}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

0983 - Ecuatie

2024-06-03T12:41:07Z

Benzar Ioan: Pagină nouă: == Cerința == Se dau a și b numere naturale nenule, cu a < b. Să se determine soluțiile ecuației 1/x+1/y+1/z=a/b , unde x,y,z sunt numere naturale nenule . == Date de intrare == Programul citește de la tastatură numerele naturale nenule a și b, separate prin spațiu. == Date de ieșire == Programul va afișa pe ecran, pe linii separate, soluțiile ecuației în ordinea crescătoare a valorilor lui x, iar la valori egale ale lui x în ordinea crescătoare a valorilor l...

== Cerința ==
Se dau a și b numere naturale nenule, cu a < b. Să se determine soluțiile ecuației 1/x+1/y+1/z=a/b
, unde x,y,z sunt numere naturale nenule .
== Date de intrare ==
Programul citește de la tastatură numerele naturale nenule a și b, separate prin spațiu.
== Date de ieșire ==
Programul va afișa pe ecran, pe linii separate, soluțiile ecuației în ordinea crescătoare a valorilor lui x, iar la valori egale ale lui x în ordinea crescătoare a valorilor lui y . În cazul în care problema nu are soluţii se va afişa mesajul NU ARE SOLUTII.
== Restricții și precizări ==
*1 ≤ a 
2 8 24 
2 9 18 
2 10 15 
2 12 12 
3 4 12 
3 6 6 
4 4 6
== Rezolvare ==
<syntaxhighlight lang="python" line>
def main():
# Citirea datelor de intrare
a, b = map(int, input("Introduceți valorile a și b, separate prin spațiu: ").strip().split())

assert 1 <= a < b <= 100, "Restricțiile sunt 1 ≤ a < b ≤ 100"

solutions = []

# Generarea soluțiilor
print("Generarea soluțiilor...")
for x in range(1, 1001):
for y in range(x, 1001):
for z in range(y, 1001):
if a * (x * y * z) == b * (x * y + y * z + z * x):
solutions.append((x, y, z))
print(x,y,z)

# Sortarea soluțiilor în ordine crescătoare a lui x, iar pentru valori egale de x, în ordine crescătoare a lui y și z
solutions.sort(key=lambda sol: (sol[0], sol[1], sol[2]))

if (solutions == 0):
print("NU EXISTA SOLUTII")

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

4179 - barliga

2024-06-03T12:05:56Z

Benzar Ioan: Pagină nouă: == Cerința == În așteptarea marii confruntări cu turcii, oștenii moldoveni își antrenează mintea, jucând un joc de echipă denumit Bârligă. O echipă are N jucători, numerotați de la 1 la N, în ordinea în care sunt așezați. Fiecare jucător primește o scândură vopsită pe o față cu roşu, iar pe cealaltă cu galben. Pe fiecare scândură sunt scrise toate numerele naturale de la 1 la V, fiecare număr o singură dată; unele numere sunt scrise pe fața r...

== Cerința ==
În așteptarea marii confruntări cu turcii, oștenii moldoveni își antrenează mintea, jucând un joc de echipă denumit Bârligă. O echipă are N jucători, numerotați de la 1 la N, în ordinea în care sunt așezați. Fiecare jucător primește o scândură vopsită pe o față cu roşu, iar pe cealaltă cu galben. Pe fiecare scândură sunt scrise toate numerele naturale de la 1 la V, fiecare număr o singură dată; unele numere sunt scrise pe fața roșie, celelalte sunt scrise pe fața galbenă a scândurii. La începutul jocului, toate scândurile sunt așezate cu faţa roșie în sus. Când primul jucător strigă “Bârligă!” fiecare jucător din echipă poate decide dacă să lase scândura sa cu fața roșie în sus sau să o întoarcă (să o “bârlige”) cu fața galbenă în sus. Punctajul obținut de echipă este egal cu numărul de valori distincte vizibile la final.
Scrieți un program care cunoscând N, numărul de jucători din echipă, precum și valorile scrise pe fața roșie a scândurii primite de fiecare jucător, determină punctajul maxim pe care îl poate obține echipa, precum și numerele de ordine ale jucătorilor care trebuie să întoarcă scândura cu față galbenă în sus, pentru a obține acest punctaj maxim.
== Date de intrare ==
Fișierul de intrare barliga.in conține pe prima linie numerele naturale N și V, cu semnificația din enunț. Pe următoarele N linii se află informațiile despre scândurile celor N jucători, în ordinea de la 1 la N. Linia care descrie o scândură are forma nr r1 r2 … rnr, cu semnificația: pe fața roșie a scândurii sunt scrise nr numere naturale distincte cuprinse între 1 și V, acestea fiind r1, r2, …, rnr.
== Date de ieșire ==
În fișierul de ieșire barliga.out se va scrie pe prima linie un număr natural reprezentând punctajul maxim pe care îl poate obține echipa. Pe cea de a doua linie va fi scris un număr natural T, reprezentând numărul de jucători care trebuie să întoarcă scândura cu fața galbenă în sus, urmat de T numere naturale distincte cuprinse între 1 și N, reprezentând numerele de ordine ale jucătorilor care trebuie să întoarcă scândura cu fața galbenă în sus.
== Restricții și precizări ==
*2 ≤ N ≤ 16
*3 ≤ V ≤ 80.000
*Valorile aflate pe aceeași linie în fișierul de intrare, respectiv în fișierul de ieșire sunt separate printr-un singur spațiu.
*Dacă există mai multe soluții pentru ca echipa să obțină punctaj maxim, se va afișa oricare dintre acestea.
*Punctajul pe test se obține dacă sunt afișate corect atât punctajul maxim, cât și o modalitate de obținere a punctajului maxim.
== Exemplu 1 ==
;Intrare
2 10 
3 7 5 10 
4 1 5 10 2
;Iesire
9 
1 1
== Rezolvare ==
<syntaxhighlight lang="python" line>
import itertools

def main():
# Citirea datelor de intrare
with open("barliga.in", "r") as fin:
N, V = map(int, fin.readline().split())
red_boards = []
yellow_boards = []

for _ in range(N):
data = list(map(int, fin.readline().split()))
red_boards.append(set(data[1:]))
# Vom genera yellow_boards ca fiind complementul numerelor de pe fața roșie
yellow_boards.append(set(range(1, V+1)) - red_boards[-1])

max_score = 0
best_combination = []

# Verificăm toate combinațiile posibile de întoarcere a scândurilor
for flip_combination in itertools.product([False, True], repeat=N):
visible_numbers = set()
current_combination = []

for i in range(N):
if flip_combination[i]:
visible_numbers.update(yellow_boards[i])
current_combination.append(i + 1)
else:
visible_numbers.update(red_boards[i])

if len(visible_numbers) > max_score:
max_score = len(visible_numbers)
best_combination = current_combination

# Scrierea rezultatului în fișierul de ieșire
with open("barliga.out", "w") as fout:
fout.write(str(max_score) + "\n")
fout.write(str(len(best_combination)) + " " + " ".join(map(str, best_combination)) + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

4133 - microbuz

2024-06-03T04:01:35Z

Benzar Ioan: Pagină nouă: == Cerința == O companie de transport cu microbuze din județul Iași a adoptat o strategie proprie pentru rutele din județ: *niciun traseu nu poate avea mai mult de 165 kilometri *distanța între două stații consecutive este de un kilometru *un pasager poate pleca din orice stație şi poate să își cumpere bilete pentru parcurgerea a 1, 2, ..., 10 kilometri *fiecare dintre cele zece distanţe posibile au bilete cu preţuri distincte Gigel, care călătoreşte cu mic...

== Cerința ==
O companie de transport cu microbuze din județul Iași a adoptat o strategie proprie pentru rutele din județ:

*niciun traseu nu poate avea mai mult de 165 kilometri
*distanța între două stații consecutive este de un kilometru
*un pasager poate pleca din orice stație şi poate să își cumpere bilete pentru parcurgerea a 1, 2, ..., 10 kilometri
*fiecare dintre cele zece distanţe posibile au bilete cu preţuri distincte
Gigel, care călătoreşte cu microbuzul exact N kilometri, poate să aleagă una sau mai multe distanţe dintre cele zece stabilite și să cumpere biletele corespunzătoare. Compania impune ca un pasager să poată cumpăra maxim 3 bilete de același tip. Gigel observă că pentru aceeași sumă poate achiziționa seturi diferite de bilete cu prețuri distincte. Pentru exemplu de mai sus, cu 98 de lei el poate cumpăra câte un bilet cu prețurile 11, 14, 29, 44 lei sau câte un bilet cu prețurile 45, 53 lei (11+14+29+44 = 45+53).

Scrieţi un program care să rezolve următoarele cerințe:

*determină preţul minim al unui set de bilete ce poate fi achiziționat pentru parcurgerea a exact N kilometri;
*determină distanţele alese de Gigel, astfel încât preţul total al călătoriei să fie minim;
*determină două seturi distincte de bilete pentru care prețul total al biletelor este același și este cel mai mare posibil. Pentru fiecare set nu este permisă alegerea mai multor bilete cu același preț și nu există două bilete cu același preț în ambele seturi.
== Date de intrare ==
Fișierul de intrare microbuz.in are trei linii. Pe prima linie se află un număr natural C ce reprezintă cerința (1, 2 sau 3). Linia a doua conține zece valori naturale ordonate strict crescător, separate prin câte un spaţiu, reprezentând preţurile pentru parcurgerea a 1, 2, …, 10 kilometri. Linia a treia conţine valoarea N reprezentând distanţa pe care doreşte să o parcurgă Gigel.
== Date de ieșire ==
Fișierul de ieșire microbuz.out are următoarea structură:

*dacă C = 1, pe prima linie se va afișa un întreg reprezentând costul minim al călătoriei;
*dacă C = 2, pe fiecare linie se vor afișa câte două numere întregi, separate printr-un spaţiu, reprezentând distanța parcursă şi preţul biletului corespunzător;
*dacă C = 3, pe prima linie se va afișa prețul comun al celor două seturi de bilete, iar pe următoarele două linii câte un set de bilete dat prin numărul de km pentru biletele din set, în ordine strict crescătoare, separate prin câte un spațiu.
== Restricții și precizări ==
*C ∈ {1, 2, 3}
*1 ≤ N ≤ 165
*cele 10 prețuri sunt numere naturale din intervalul [10, 99]
*răspunsul la cerința 3 nu depinde de valoarea lui N
*Pentru 28 de puncte, C = 1
*Pentru 38 de puncte, C = 2
*Pentru 34 de puncte, C = 3
== Exemplu 1 ==
;Intrare
1 
11 14 18 23 29 36 44 45 53 64 
15
;Iesire
86
== Rezolvare ==
<syntaxhighlight lang="python" line>
def solve_case_1(prices, N):
# Initialize dp array where dp[i] will be the minimum cost to travel i kilometers
dp = [float('inf')] * (N + 1)
dp[0] = 0

for i in range(1, N + 1):
for j in range(1, 11):
if i >= j:
dp[i] = min(dp[i], dp[i - j] + prices[j - 1])

return dp[N]

def solve_case_2(prices, N):
# Initialize dp array and tracking array
dp = [float('inf')] * (N + 1)
dp[0] = 0
track = [-1] * (N + 1)

for i in range(1, N + 1):
for j in range(1, 11):
if i >= j and dp[i - j] + prices[j - 1] < dp[i]:
dp[i] = dp[i - j] + prices[j - 1]
track[i] = j

distance = 0
km = N
tickets = []

while km > 0:
ticket = track[km]
tickets.append(ticket)
distance += ticket
km -= ticket

return distance, dp[N], tickets

def solve_case_3(prices, N):
dp = [float('inf')] * (N + 1)
dp[0] = 0
track = [-1] * (N + 1)

for i in range(1, N + 1):
for j in range(1, 11):
if i >= j and dp[i - j] + prices[j - 1] < dp[i]:
dp[i] = dp[i - j] + prices[j - 1]
track[i] = j

tickets1 = []
km = N
while km > 0:
ticket = track[km]
tickets1.append(ticket)
km -= ticket

max_price = 0
best_comb = []

for i in range(len(tickets1)):
for j in range(i + 1, len(tickets1)):
if tickets1[i] != tickets1[j]:
remaining = N - tickets1[i] - tickets1[j]
if remaining >= 0:
price = prices[tickets1[i] - 1] + prices[tickets1[j] - 1]
if price > max_price:
max_price = price
best_comb = [tickets1[i], tickets1[j]]

return tickets1, best_comb

def main():
with open('microbuz.in', 'r') as f:
data = f.read().strip().split('\n')

C = int(data[0].strip())
prices = list(map(int, data[1].strip().split()))
N = int(data[2].strip())

if C == 1:
result = solve_case_1(prices, N)
with open('microbuz.out', 'w') as f:
f.write(str(result) + '\n')

elif C == 2:
distance, price, tickets = solve_case_2(prices, N)
with open('microbuz.out', 'w') as f:
f.write(f"{distance} {price}\n")
for ticket in tickets:
f.write(f"{ticket} {prices[ticket - 1]}\n")

elif C == 3:
tickets1, best_comb = solve_case_3(prices, N)
with open('microbuz.out', 'w') as f:
f.write(str(len(tickets1)) + '\n')
for ticket in tickets1:
f.write(f"{ticket} {prices[ticket - 1]}\n")
f.write(str(len(best_comb)) + '\n')
for ticket in best_comb:
f.write(f"{ticket} {prices[ticket - 1]}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

3065 - trio

2024-06-03T03:53:24Z

Benzar Ioan: Pagină nouă: == Cerința == Trio este un joc ce conține N piese de aceeași formă, așezate una lângă alta pe o tablă de joc și numerotate de la stânga la dreapta cu valori de la 1 la N. Fiecare piesă are marcate pe ea trei zone, iar în fiecare dintre ele este scrisă câte o cifră. Se consideră că o piesă pe care sunt scrise în ordine, de la stânga la dreapta, cifrele C1, C2 și C3 are următoarele proprietăți: este identică cu o altă piesă, dacă această piesă con...

== Cerința ==
Trio este un joc ce conține N piese de aceeași formă, așezate una lângă alta pe o tablă de joc și numerotate de la stânga la dreapta cu valori de la 1 la N. Fiecare piesă are marcate pe ea trei zone, iar în fiecare dintre ele este scrisă câte o cifră. Se consideră că o piesă pe care sunt scrise în ordine, de la stânga la dreapta, cifrele C1, C2 și C3 are următoarele proprietăți:
este identică cu o altă piesă, dacă această piesă conține exact aceleași cifre, în aceeași ordine cu ale ei sau în ordine inversă. Astfel, piesa C1|C2|C3 este identică cu o altă piesă de forma C1|C2|C3 și cu o piesă de forma C3|C2|C1.
este prietenă cu o altă piesă dacă aceasta conține exact aceleași cifre ca piesa dată, dar nu neapărat în aceeași ordine. Astfel, piesa C1|C2|C3 este prietenă cu piesele: C1|C2|C3, C1|C3|C2, C2|C1|C3, C2|C3|C1, C3|C1|C2 și C3|C2|C1. Se observă că două piese identice sunt și prietene!
Un grup de piese prietene este format din TOATE piesele prietene între ele, aflate pe tabla de joc.
1) Alegeți o piesă de pe tabla de joc, astfel încât numărul M al pieselor identice cu ea să fie cel mai mare posibil și afișați numărul M determinat;
2) Afișați numărul grupurilor de piese prietene existente pe tabla de joc;
3) Afișați numărul maxim de piese dintr-o secvență ce conține piese așezate una lângă alta pe tabla de joc, pentru care prima piesă și ultima piesă din secvență sunt prietene.
== Date de intrare ==
Fișierul de intrare trio.in conține
- pe prima linie un număr natural C care reprezintă numărul cerinţei şi poate avea valorile 1, 2 sau 3.
- pe cea de-a doua linie un număr natural N ce reprezintă numărul pieselor de joc;
- pe următoarele N linii, câte trei cifre, despărțite prin câte un spațiu, ce reprezintă, în ordine, cifrele scrise pe câte o piesă de joc. Piesele sunt date în ordinea numerotării acestora pe tabla de joc.
== Date de ieșire ==
Fișierul de ieșire trio.out va conține pe prima linie un singur număr natural ce reprezintă rezultatul determinat conform fiecărei cerințe.
== Restricții și precizări ==
*2 ≤ N ≤ 100.000
*Există cel puțin două piese identice pe tabla de joc;
*O piesă ce nu e prietenă cu nicio altă piesă de pe tabla de joc formează singură un grup;
== Exemplu 1 ==
;Intrare
1 
6 
1 3 3 
4 5 9 
1 3 3 
9 5 4 
3 3 1 
9 4 5
;Iesire
2
== Rezolvare ==
<syntaxhighlight lang="python" line>
def reverse_piece(piece):
"""Returnează piesa inversată."""
return piece[::-1]

def are_friends(piece1, piece2):
"""Verifică dacă două piese sunt prietene."""
if piece1 == piece2:
return True
if piece1 == reverse_piece(piece2):
return True
c1, c2, c3 = piece1
for i in range(3):
if piece2 == c2 + c3 + c1 or piece2 == c3 + c1 + c2:
return True
c1, c2, c3 = c3, c1, c2 # permutăm cifrele
return False

def cerinta1(pieces):
"""Determină M al pieselor identice cu cea selectată."""
from collections import Counter
counter = Counter(pieces)
most_common_piece, count = counter.most_common(1)[0]
return count

def cerinta2(pieces):
"""Numărul grupurilor de piese prietene."""
n = len(pieces)
visited = [False] * n

def dfs(i):
stack = [i]
while stack:
node = stack.pop()
if not visited[node]:
visited[node] = True
for j in range(n):
if not visited[j] and are_friends(pieces[node], pieces[j]):
stack.append(j)

groups = 0
for i in range(n):
if not visited[i]:
groups += 1
dfs(i)

return groups

def cerinta3(pieces):
"""Numărul maxim de piese dintr-o secvență ce conține piese prietene."""
n = len(pieces)
max_length = 0
current_length = 0

for i in range(n):
if i == 0 or are_friends(pieces[i], pieces[i - 1]):
current_length += 1
else:
max_length = max(max_length, current_length)
current_length = 1

max_length = max(max_length, current_length)
return max_length

def main():
with open('trio.in', 'r') as f:
data = f.read().splitlines()

c = int(data[0].strip())
n = int(data[1].strip())
pieces = [line.strip().replace(" ", "") for line in data[2:2 + n]]

assert 2 <= n <= 100000, "N trebuie să fie între 2 și 100000"
assert all(len(piece) == 3 for piece in pieces), "Fiecare piesă trebuie să aibă exact 3 cifre"

if c == 1:
result = cerinta1(pieces)
elif c == 2:
result = cerinta2(pieces)
elif c == 3:
result = cerinta3(pieces)
else:
raise ValueError("C trebuie să fie 1, 2 sau 3")

with open('trio.out', 'w') as f:
f.write(f"{result}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

2934 - Cmmp

2024-06-03T03:50:20Z

Benzar Ioan: Pagină nouă: == Cerința == Pentru orice număr natural x definim operația cmmp prin care adăugăm cifre la stânga lui x, la dreapta lui x sau la ambele capete ale lui x, astfel încât numărul obținut să fie pătrat perfect și cât mai mic posibil. Se dau N numere naturale s1,s2…sN . Să se determine pentru fiecare număr s[k], 1 ≤ k ≤ N, cel mai mic pătrat perfect care se poate obține prin aplicarea operației cmmp. == Date de intrare == Fișierul de intrare cmmp.in...

== Cerința ==
Pentru orice număr natural x definim operația cmmp prin care adăugăm cifre la stânga lui x, la dreapta lui x sau la ambele capete ale lui x, astfel încât numărul obținut să fie pătrat perfect și cât mai mic posibil.

Se dau N numere naturale s1,s2…sN
.

Să se determine pentru fiecare număr s[k], 1 ≤ k ≤ N, cel mai mic pătrat perfect care se poate obține prin aplicarea operației cmmp.
== Date de intrare ==
Fișierul de intrare cmmp.in conține pe primul rând numărul N. Pe linia a doua sunt scrise N numere naturale separate prin câte un spațiu.
== Date de ieșire ==
În fișierul de ieșire cmmp.out vor fi scrise, în ordinea corespunzătoare citirii și separate prin câte un spațiu, cele N numere obținute din numerele date prin aplicarea operației cmmp.
== Restricții și precizări ==
*1 ≤ N ≤ 100.000
*0 ≤ s[k] < 100.000
*Pentru 20% din teste 0 ≤ s[k] < 100
*Pentru 20% din teste 0 ≤ s[k] < 1000
*Dacă numărul dat este pătrat perfect, atunci operația cmmp îl lasă neschimbat.
== Exemplu 1 ==
;Intrare
4 
21 0 19 80
;Iesire
121 0 196 2809
== Rezolvare ==
<syntaxhighlight lang="python" line>
import math

def is_perfect_square(x):
"""Verifică dacă un număr este pătrat perfect."""
s = int(math.isqrt(x))
return s * s == x

def cmmp_operation(x):
"""Aplică operația cmmp pentru a obține cel mai mic pătrat perfect."""
if is_perfect_square(x):
return x

x_str = str(x)
min_perfect_square = float('inf')

for i in range(10):
for j in range(10):
for k in range(10):
possible_numbers = [
int(str(i) + x_str),
int(x_str + str(j)),
int(str(i) + x_str + str(j)),
int(str(k) + str(i) + x_str + str(j)),
]
for num in possible_numbers:
if is_perfect_square(num):
min_perfect_square = min(min_perfect_square, num)

return min_perfect_square if min_perfect_square != float('inf') else x

def main():
with open('cmmp.in', 'r') as f:
data = f.read().splitlines()

N = int(data[0].strip())
numbers = list(map(int, data[1].strip().split()))

assert 1 <= N <= 100000, "N trebuie să fie între 1 și 100000"
assert all(0 <= x <= 100000 for x in numbers), "Numerele trebuie să fie între 0 și 100000"

results = [cmmp_operation(num) for num in numbers]

with open('cmmp.out', 'w') as f:
f.write(' '.join(map(str, results)) + '\n')

if __name__ == "__main__":
main()

</syntaxhighlight>

0624 - Sah1

2024-06-03T03:45:17Z

Benzar Ioan: Pagină nouă: == Cerința == Alex dorește să își învețe fratele să joace șah. După ce i-a explicat regulile, Alex vrea să vadă dacă fratele lui a înțeles, aşa că îi dă un mic test. Având o tablă de șah de N linii şi N coloane, Alex pune pe ea M ture (tura atacă doar pe coloana și linia pe care se află) și un rege. Apoi îi cere fratelui său să îi spună de câte ture este atacat regele în acel moment și pe câte căsuțe de pe tablă poate fi pus regele, astf...

== Cerința ==
Alex dorește să își învețe fratele să joace șah. După ce i-a explicat regulile, Alex vrea să vadă dacă fratele lui a înțeles, aşa că îi dă un mic test. Având o tablă de șah de N linii şi N coloane, Alex pune pe ea M ture (tura atacă doar pe coloana și linia pe care se află) și un rege. Apoi îi cere fratelui său să îi spună de câte ture este atacat regele în acel moment și pe câte căsuțe de pe tablă poate fi pus regele, astfel încât să nu se afle în șah.

În figura de mai jos avem trei ture şi un rege. Regele nu este atacat de nicio tură, fiindcă nu se află pe aceeaşi linie sau aceeaşi coloană cu niciuna dintre ele.
Cunoscând dimensiunea N a tablei de șah, poziția regelui de pe tablă, numărul M de ture și poziția fiecărei ture de pe tablă, se cere:

a)să se afișeze numărul de ture care atacă regele în acel moment;
b)numărul de poziții în care regele poate fi pus, astfel încât să nu fie atacat de vreo tură.
== Date de intrare ==
Fişierul de intrare sah1.in conţine pe prima linie un număr natural p. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2. Pe a doua linie se află două numere naturale N și M, cu semnificația din enunț, pe linia a treia se află două numere naturale reprezentând poziția regelui pe tablă, iar pe fiecare dintre următoarele M linii se află câte două numere naturale reprezentând linia respectiv coloana unei ture.
== Date de ieșire ==
Dacă valoarea lui p este 1, se va rezolva numai punctul a) din cerință. În acest caz, în fişierul de ieşire sah1.out se va scrie un număr natural reprezentând numărul de ture ce atacă regele.

Dacă valoarea lui p este 2, se va rezolva numai punctul b) din cerință. În acest caz, în fișierul de ieșire sah1.out se va scrie pe prima linie un număr natural Q, reprezentând numărul de poziții pe care poate fi pus regele astfel încât să nu fie atacat de vreo tură.
== Restricții și precizări ==
*2 ≤ N ≤ 10 000
*0 ≤ M ≤ min(2 000, N2-1)
*Tabla de șah are liniile și coloanele numerotate de la 1 la N.
*Regele poate fi pus pe orice căsuță de pe tablă care nu este ocupată de o tură sau care nu este atacată de vreo tură.
== Exemplu 1 ==
;Intrare
1 
4 3 
3 1 
1 2 
2 3 
4 3
;Iesire
0
== Rezolvare ==
<syntaxhighlight lang="python" line>
def solve_p1(N, king_pos, rooks):
king_row, king_col = king_pos
attacks = 0

for rook_row, rook_col in rooks:
if rook_row == king_row or rook_col == king_col:
attacks += 1

return attacks

def solve_p2(N, king_pos, rooks):
king_row, king_col = king_pos
safe_positions = 0

for row in range(1, N + 1):
for col in range(1, N + 1):
if row == king_row and col == king_col:
continue
safe = True
for rook_row, rook_col in rooks:
if row == rook_row or col == rook_col:
safe = False
break
if safe:
safe_positions += 1

return safe_positions

def main():
with open('sah1.in', 'r') as f:
data = f.read().splitlines()

p = int(data[0].strip())
N, M = map(int, data[1].strip().split())
king_pos = tuple(map(int, data[2].strip().split()))
rooks = [tuple(map(int, line.strip().split())) for line in data[3:3 + M]]

# Restricții
assert 2 <= N <= 10000, "N trebuie să fie între 2 și 10000"
assert 0 <= M <= min(2000, N**2), "M trebuie să fie între 0 și min(2000, N**2)"
assert 1 <= king_pos[0] <= N and 1 <= king_pos[1] <= N, "Poziția regelui trebuie să fie validă"
for rook in rooks:
assert 1 <= rook[0] <= N and 1 <= rook[1] <= N, "Pozițiile turelor trebuie să fie valide"

if p == 1:
# Rezolvăm punctul a)
result = solve_p1(N, king_pos, rooks)
with open('sah1.out', 'w') as f:
f.write(f"{result}\n")
elif p == 2:
# Rezolvăm punctul b)
result = solve_p2(N, king_pos, rooks)
with open('sah1.out', 'w') as f:
f.write(f"{result}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

2510 - vsecvente

2024-06-03T03:24:06Z

Benzar Ioan: Pagină nouă: == Cerința == Considerăm un șir de numere naturale nenule a[1], a[2], …, a[n]. În acest șir o V-secvență este o secvență maximală de forma a[x], a[x+1], …, a[y] cu proprietatea că toate numerele din secvență au valori mai mici sau egale cu V. Este maximală pentru că nu poate fi extinsă spre stânga sau spre dreapta. De exemplu, șirul a = 2, 2, 6, 4, 3, 14, 7, 4, 3, 36 are două 7-secvențe: 2, 2, 6, 4, 3 și 7, 4, 3. De asemenea, șirul are trei 4-secven...

== Cerința ==
Considerăm un șir de numere naturale nenule a[1], a[2], …, a[n]. În acest șir o V-secvență este o secvență maximală de forma a[x], a[x+1], …, a[y] cu proprietatea că toate numerele din secvență au valori mai mici sau egale cu V. Este maximală pentru că nu poate fi extinsă spre stânga sau spre dreapta. De exemplu, șirul a = 2, 2, 6, 4, 3, 14, 7, 4, 3, 36 are două 7-secvențe: 2, 2, 6, 4, 3 și 7, 4, 3. De asemenea, șirul are trei 4-secvențe: 2,2; 4,3; 4,3. De notat că 2,6,4,3 nu este 7-secvență, deoarece poate fi extinsă la capătul său stâng cu numărul 2.
Pentru un șir de numere dat, trebuie să răspundeți la Q întrebări notate V[1], V[2],…, V[Q]. Pentru fiecare întrebare i, dată prin numărul natural V[i], trebuie să aflați câte V[i]-secvențe sunt în șir.
== Date de intrare ==
Fișierul de intrare vsecvente.in conține pe prima linie numărul natural N. Pe a doua linie, separate prin câte un spațiu, se află cele N elemente ale șirului. Pe a treia linie se află un singur număr natural Q reprezentând numărul de întrebări. Pe a patra linie, se află șirul de Q numere naturale V[1], V[2],…, V[Q], separate prin câte un spațiu.
== Date de ieșire ==
Fișierul de ieșire vsecvente.out va conține Q linii. Linia a i-a va conține numărul de V[i]-secvențe aflate în șir.
== Exemplu 1 ==
*1 ≤ toate numerele din fișierul de intrare ≤ 1 100 000
*Pentru teste totalizând 75 puncte, 1 ≤ toate numerele din fișierul de intrare ≤ 550 000
;Intrare
10 
2 2 6 4 3 14 7 4 3 36 
3 
7 1 4
;Iesire
2 
0 
3
== Rezolvare ==
<syntaxhighlight lang="python" line>
def main():
# Citirea datelor de intrare
with open('vsecvente.in', 'r') as f:
data = f.read().splitlines()

# Prima linie conține numărul N
N = int(data[0].strip())

# Asigurăm că 1 ≤ N ≤ 100000
assert 1 <= N <= 100000, "N trebuie să fie între 1 și 100000"

# A doua linie conține N elemente ale șirului
sir = list(map(int, data[1].strip().split()))

# Verificăm că lungimea șirului este corectă
assert len(sir) == N, "Lungimea șirului trebuie să fie N"

# A treia linie conține numărul de întrebări Q
Q = int(data[2].strip())

# Asigurăm că 1 ≤ Q ≤ 100000
assert 1 <= Q <= 100000, "Q trebuie să fie între 1 și 100000"

# A patra linie conține Q valori pentru interogări
interogari = list(map(int, data[3].strip().split()))

# Verificăm că lungimea interogărilor este corectă
assert len(interogari) == Q, "Numărul interogărilor trebuie să fie Q"

# Asigurăm că toate elementele din șir sunt între 1 și 1,000,000,000
for elem in sir:
assert 1 <= elem <= 1000000000, "Elementele șirului trebuie să fie între 1 și 1,000,000,000"

# Asigurăm că toate interogările sunt între 1 și 1,000,000,000
for interogare in interogari:
assert 1 <= interogare <= 1000000000, "Interogările trebuie să fie între 1 și 1,000,000,000"

rezultate = []

# Pentru fiecare interogare, calculăm numărul de secvențe maxime pentru valoarea V
for V in interogari:
count = 0
in_sequence = False
for num in sir:
if num <= V:
if not in_sequence:
in_sequence = True
count += 1
else:
in_sequence = False
rezultate.append(count)

# Scrierea rezultatelor în fișierul de ieșire
with open('vsecvente.out', 'w') as f:
for rezultat in rezultate:
f.write(f"{rezultat}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

3746 - LeMans

2024-06-03T03:12:07Z

Benzar Ioan: Ștergerea conținutului paginii

3397 - Gard 2

2024-06-03T02:50:30Z

Benzar Ioan: Ștergerea conținutului paginii

3713 – Company Tree

2024-06-03T02:29:27Z

Benzar Ioan: Ștergerea conținutului paginii

1622 - Elicoptere

2024-06-03T02:22:42Z

Benzar Ioan:

== Cerința ==
Arhipelagul Zopopan este format din n insule de formă triunghiulară numerotate de la 1 la n. Fiecare insulă este localizată prin coordonatele carteziene ale vârfurilor.

Administrația dorește să cumpere elicoptere pentru a realiza transportul între insule. Un elicopter va putea să asigure o rută între două insule pe distanța minimă obținută pe orizontală sau verticală (paralel cu axele de coordonate). În plus, datorită capacității rezervorului o astfel de rută nu poate să depășească o valoare k – număr natural. Elicopterele parcurg rutele în ambele sensuri.
Investiția trebuie să îndeplinească următoarele condiții:

Numărul de elicoptere cumpărate să fie minim.
Numărul de perechi de insule între care se poate realiza transportul, folosind unul sau mai multe elicoptere să fie maxim.
Suma lungimii tuturor rutelor să fie minimă.
Să se scrie un program care pentru n, k şi coordonatele vârfurilor insulelor cunoscute, determină:

*numărul minim de elicoptere ce vor fi cumpărate de administraţie;
*numărul perechilor neordonate de insule între care se poate realiza transportul prin elicoptere direct sau indirect;
*suma distantelor parcurse de toate elicopterele cumpărate (distanța parcursă de un elicopter se consideră distanța dintre insulele între care acesta asigură transportul).

== Date de intrare ==
Fișierul de intrare elicoptere.in conține pe prima linie o valoare v ce poate fi 1, 2, sau 3, în funcţie de cerinţa ce va fi rezolvată, pe linia a doua numerele naturale n şi k separate printr-un spaţiu, cu semnificaţia de mai sus, iar pe următoarele n linii se află câte şase numere naturale x1, y1, x2, y2, x3 și y3 separate prin spațiu reprezentând coordonatele celor trei vârfuri ale insulelor în formatul (abscisă, ordonată).
== Date de ieșire ==
Dacă valoarea lui v este 1 atunci fişierul de ieşire elicoptere.out va conţine pe prima linie numai numărul minim de elicoptere, ce vor fi cumpărate de administraţie.

Dacă valoarea lui v este 2 atunci fişierul de ieşire elicoptere.out va conţine pe prima linie numai numărul maxim de perechi de insule între care se poate realiza transportul prin elicoptere.

Dacă valoarea lui v este 3 atunci fişierul de ieşire elicoptere.out va conţine pe prima linie suma minimă a lungimii rutelor parcurse de elicoptere.
== Restricții și precizări ==
*1 ≤ n ≤ 100;
*1 ≤ k ≤ 1000;
*coordonatele vârfurilor insulelor sunt numere naturale 0 ≤ xi , yi ≤ 106;
*orice două insule nu au puncte comune;
*la cerința 2, dacă se poate ajunge din insula A în insula B atunci evident că se poate ajunge și din B în A, *deci perechea formată din A și B se numără o singură dată;
*distanța dintre două insule poate fi şi număr real. La cerința 3 rezultatul se cere cu o aproximație de 0.001, adică rezultatul notat cu R se consideră corect, dacă faţă de rezultatul comisiei C îndeplineşte condiţia |R-C|<0.001.
*pentru a calcula şi afișa un număr real x cu o precizie cât mai mare vă recomandăm folosirea tipului double
== Exemplu 1 ==
;Intrare
1 
6 11 
100 20 100 30 105 30 
20 20 30 30 20 30 
200 20 200 30 205 30 
100 40 100 50 105 40 
10 40 5 40 10 50 
10 20 5 30 10 30

;Iesire
3

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

def citire_date_intrare():
with open("elicoptere.in", "r") as f:
lines = f.readlines()

p = int(lines[0].strip())
n, k = map(int, lines[1].strip().split())
insule = []
for line in lines[2:]:
insula = tuple(map(int, line.strip().split()))
insule.append(insula)

return p, n, k, insule

def distanta(x1, y1, x2, y2):
return math.sqrt((x1 - x2)**2 + (y1 - y2)**2)

def rezolva_problema1(insule, n, k):
vizitat = [False] * n
numar_elicoptere = 0

def dfs(nod):
stack = [nod]
while stack:
nod_curent = stack.pop()
for vecin in range(n):
if not vizitat[vecin] and exista_legatura(insule[nod_curent], insule[vecin], k):
vizitat[vecin] = True
stack.append(vecin)

for i in range(n):
if not vizitat[i]:
numar_elicoptere += 1
vizitat[i] = True
dfs(i)

return numar_elicoptere

def rezolva_problema2(insule, n, k):
numar_perechi = 0
for i in range(n):
for j in range(i + 1, n):
if exista_legatura(insule[i], insule[j], k):
numar_perechi += 1
return numar_perechi

def rezolva_problema3(insule, n, k):
graph = []
for i in range(n):
for j in range(i + 1, n):
if exista_legatura(insule[i], insule[j], k):
dist = calculeaza_distanta(insule[i], insule[j])
graph.append((dist, i, j))
graph.sort()

parinte = list(range(n))

def gaseste(parinte, i):
if parinte[i] == i:
return i
parinte[i] = gaseste(parinte, parinte[i])
return parinte[i]

cost_total = 0
muchii_folosite = 0

for dist, u, v in graph:
rad_u = gaseste(parinte, u)
rad_v = gaseste(parinte, v)
if rad_u != rad_v:
cost_total += dist
muchii_folosite += 1
parinte[rad_u] = rad_v
if muchii_folosite == n - 1:
break

return round(cost_total, 3)

def exista_legatura(insula1, insula2, k):
for i in range(0, 6, 2):
for j in range(0, 6, 2):
dist = distanta(insula1[i], insula1[i+1], insula2[j], insula2[j+1])
if dist <= k:
return True
return False

def calculeaza_distanta(insula1, insula2):
min_dist = float('inf')
for i in range(0, 6, 2):
for j in range(0, 6, 2):
dist = distanta(insula1[i], insula1[i+1], insula2[j], insula2[j+1])
if dist < min_dist:
min_dist = dist
return min_dist

def main():
p, n, k, insule = citire_date_intrare()

# Verificare restrictii
assert 1 <= n <= 100, "n trebuie să fie între 1 și 100"
assert 1 <= k <= 1000, "k trebuie să fie între 1 și 1000"
for x1, y1, x2, y2, x3, y3 in insule:
assert 0 <= x1 <= 10**6 and 0 <= y1 <= 10**6, "Coordonatele trebuie să fie între 0 și 1,000,000"
assert 0 <= x2 <= 10**6 and 0 <= y2 <= 10**6, "Coordonatele trebuie să fie între 0 și 1,000,000"
assert 0 <= x3 <= 10**6 and 0 <= y3 <= 10**6, "Coordonatele trebuie să fie între 0 și 1,000,000"

if p == 1:
rezultat = rezolva_problema1(insule, n, k)
elif p == 2:
rezultat = rezolva_problema2(insule, n, k)
elif p == 3:
rezultat = rezolva_problema3(insule, n, k)
else:
print("Valoare p invalidă.")
return

with open("elicoptere.out", "w") as f:
f.write(f"{rezultat}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

4014 - Rearanjare Sir

2024-06-03T02:11:38Z

Benzar Ioan: Ștergerea conținutului paginii

4029 - Depozit

2024-06-03T01:51:33Z

Benzar Ioan: /* Rezolvare */

== Cerința ==
Într-un depozit au fost așezate cutii identice, una după alta, eventual suprapuse, astfel încât numărul maxim de cutii suprapuse într-o stivă este N, iar între două stive cu același număr de cutii să existe cel puțin una cu mai multe cutii decât oricare dintre cele două. Considerăm că o stivă poate fi formată dintr-o singură cutie.
Proprietarul depozitului vă cere să aflați numărul maxim de stive care pot construi respectând regulile date și numărul de cutii care pot fi aranjate astfel. Pentru că numerele pot fi foarte mari rezultatele se vor afișa modulo 1.000.000.007.
== Date de intrare ==
Programul citește de la tastatură N.
== Date de ieșire ==
Programul afișează pe ecran numărul maxim de stive care pot construi și numărul de cutii care pot fi aranjate modulo 1.000.000.007.
== Restricții și precizări ==
*1 ≤ N ≤ 1.000.000.000
== Exemplu 1 ==
;Intrare
3
;Iesire
7 11

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

def factorial(n, mod):
result = 1
for i in range(2, n + 1):
result = (result * i) % mod
return result

def mod_inverse(x, mod):
return pow(x, mod - 2, mod)

def comb(n, k, mod):
if k > n:
return 0
num = factorial(n, mod)
denom = (factorial(k, mod) * factorial(n - k, mod)) % mod
return (num * mod_inverse(denom, mod)) % mod

def calculate_stive_and_cuts(N):
# Numărul maxim de stive este (N + 1) * N // 2
max_stive = (N + 1) * N // 2

# Numărul de moduri de a aranja cutiile
num_cuts = 1
for i in range(1, N):
num_cuts = (num_cuts * (2 * N - i) * mod_inverse(i, MOD)) % MOD

return max_stive, num_cuts

def main():
N = int(input().strip())
assert 1 <= N <= 1000000000, "N nu este in parametru"
max_stive, num_cuts = calculate_stive_and_cuts(N)
print(max_stive+1, num_cuts+1)

if __name__ == "__main__":
main()

</syntaxhighlight>

4029 - Depozit

2024-06-03T01:50:56Z

Benzar Ioan:

== Cerința ==
Într-un depozit au fost așezate cutii identice, una după alta, eventual suprapuse, astfel încât numărul maxim de cutii suprapuse într-o stivă este N, iar între două stive cu același număr de cutii să existe cel puțin una cu mai multe cutii decât oricare dintre cele două. Considerăm că o stivă poate fi formată dintr-o singură cutie.
Proprietarul depozitului vă cere să aflați numărul maxim de stive care pot construi respectând regulile date și numărul de cutii care pot fi aranjate astfel. Pentru că numerele pot fi foarte mari rezultatele se vor afișa modulo 1.000.000.007.
== Date de intrare ==
Programul citește de la tastatură N.
== Date de ieșire ==
Programul afișează pe ecran numărul maxim de stive care pot construi și numărul de cutii care pot fi aranjate modulo 1.000.000.007.
== Restricții și precizări ==
*1 ≤ N ≤ 1.000.000.000
== Exemplu 1 ==
;Intrare
3
;Iesire
7 11

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

def factorial(n, mod):
result = 1
for i in range(2, n + 1):
result = (result * i) % mod
return result

def mod_inverse(x, mod):
return pow(x, mod - 2, mod)

def comb(n, k, mod):
if k > n:
return 0
num = factorial(n, mod)
denom = (factorial(k, mod) * factorial(n - k, mod)) % mod
return (num * mod_inverse(denom, mod)) % mod

def calculate_stive_and_cuts(N):
# Numărul maxim de stive este (N + 1) * N // 2
max_stive = (N + 1) * N // 2

# Numărul de moduri de a aranja cutiile
num_cuts = 1
for i in range(1, N):
num_cuts = (num_cuts * (2 * N - i) * mod_inverse(i, MOD)) % MOD

return max_stive, num_cuts

def main():
N = int(input().strip())
assert 1 <= N <= 10000007, "N nu este in parametru"
max_stive, num_cuts = calculate_stive_and_cuts(N)
print(max_stive+1, num_cuts+1)

if __name__ == "__main__":
main()

</syntaxhighlight>

0392 - Cladire

2024-06-03T01:36:15Z

Benzar Ioan:

== Cerința ==
Se consideră o clădire de formă dreptunghiulară formată din n*m camere, dispuse pe n linii și m coloane. Intrarea în clădire este în camera de coordonate (1,1), iar ieșirea în camera de coordonate (n,m). Din orice cameră (i,j) se poate ajunge numai în camerele (i+1,j) sau (i,j+1). Determinați în câte moduri se poate ajunge din camera (1,1) în camera (n,m).

Deoarece numărul de posibilități poate fi foarte mare, se cere doar restul acestui număr la împărțirea cu 9901.
== Date de intrare ==
Fişierul de intrare cladire.in conţine pe prima linie numerele n m.
== Date de ieșire ==
Fişierul de ieşire cladire.out va conţine pe prima linie numărul P, reprezentând în câte moduri se poate ajunge din camera (1,1) în camera (n,m), număr afișat modulo 9901.
== Restricții și precizări ==
*1 ≤ n , m ≤ 1000
== Exemplu 1 ==
;Intrare
3 3
;Iesire
6

== Rezolvare ==
<syntaxhighlight lang="python" line>
def count_paths(n, m):
MOD = 9901
dp = [[0] * m for _ in range(n)]
dp[0][0] = 1

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

return dp[n - 1][m - 1]

def main():
with open("cladire.in", "r") as f:
n, m = map(int, f.readline().strip().split())

result = count_paths(n, m)

with open("cladire.out", "w") as f:
f.write(f"{result}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

1187 - Roboti 1

2024-06-03T01:33:35Z

Benzar Ioan:

== Cerința ==
O firmă de construcţii imobiliare a achiziţionat recent un teren dreptunghiular de dimensiuni N×M. Terenul este împărțit în parcele de dimensiune 1x1. Pe unele dintre cele N×M parcele sunt plantați copaci. Firma dorește construirea unui grandios complex comercial și este necesară defrișarea întregului teren. În acest scop sunt utilizați roboți, fiecare robot având baza un pătrat de latură L. Suprafața defrișată de fiecare robot la un moment dat este chiar aria de acoperire a robotului, L×L. Fiecare robot pătrunde prin colțul stânga sus de coordonate (1, 1), se poate deplasa doar în dreapta și în jos și poate părăsi suprafața numai prin colțul dreapta jos, de coordonate (N, M).
Cunoscând dimensiunile N, M ale terenului și coordonatele parcelelor în care sunt plantați copaci se cere:

1. Numărul minim de roboți necesari defrișării întregului teren.
2. Să se răspundă la Q interogări de forma k, unde k este un număr natural. Pentru fiecare interogare de această formă va trebui determinată latura minimă a unui robot astfel încât să fie necesari pentru defrișare cel mult k roboți.
== Date de intrare ==
Fişierul de intrare roboti1.in conţine:

*Pe prima linie un număr natural p reprezentând varianta cerinței de rezolvare. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2.
*Pe a doua linie se află 3 numere naturale N, M, T separate prin câte un spațiu reprezentând numărul liniilor, numărul coloanelor terenului dreptunghiular, respectiv numărul copacilor plantați.
*Următoarele T linii conțin fiecare câte două numere naturale x y separate prin câte un spațiu, reprezentând linia, respectiv coloana parcelei în care este plantat un copac.
*În cazul cerinței 1, ultima linie conține un singur număr natural L, reprezentând latura unui robot.
*În cazul cerinței 2, penultima linie va conține un număr natural Q, iar ultima linie Q numere naturale k[1], k[2], …, k[Q] separate prin câte un spațiu, reprezentând numărul maxim de roboți ce pot fi utilizați în fiecare dintre cele Q interogări.
== Date de ieșire ==
*Dacă valoarea lui p este 1, se va rezolva numai cerința 1. În acest caz, în fişierul de ieşire roboti1.out se va scrie un singur număr natural n1, reprezentând numărul minim de roboți utilizați.
*Dacă valoarea lui p este 2, se va rezolva numai cerința 2. În acest caz, în fişierul de ieşire roboti1.out se vor scrie Q linii. Fiecare linie i va conţine câte un număr natural ni, reprezentând latura minimă a unui robot astfel încât pentru defrișare să fie utilizați cel mult ki roboți.
== Restricții și precizări ==
*2 ≤ N, M, L ≤ 150
*1 ≤ Q ≤ 150
*1 ≤ k[i] ≤ 150, 1 ≤ i ≤ Q
*1 ≤ T ≤ 1000
*Latura robotului nu poate fi mai mare decât dimensiunile terenului
*Pe tot parcursul deplasării, fiecare robot se va afla în interiorul suprafeţei terenului.
*În orice moment în interiorul suprafeţei terenului se va afla cel mult un robot.

== Exemplu 1 ==
;Intrare
1 
6 8 8 
4 1 
5 3 
3 5 
2 6 
5 5 
4 7 
3 8 
6 8 
4
;Iesire
1

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

def citire_date_intrare(fisier_intrare):
with open(fisier_intrare, "r") as f:
p = int(f.readline().strip())
n, m, l = map(int, f.readline().strip().split())
copaci = []
for _ in range(l):
x, y = map(int, f.readline().strip().split())
copaci.append((x - 1, y - 1)) # Corectăm indexarea la 0
if p == 2:
Q = int(f.readline().strip())
k = list(map(int, f.readline().strip().split()))
else:
Q = 0
k = []
return p, n, m, l, copaci, Q, k

def bfs(n, m, copaci, latura):
def in_bounds(x, y):
return 0 <= x < n and 0 <= y < m

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

vizitat = [[False] * m for _ in range(n)]
for x, y in copaci:
vizitat[x][y] = True

num_roboți = 0
for i in range(n):
for j in range(m):
if not vizitat[i][j]:
num_roboți += 1
q = deque([(i, j)])
vizitat[i][j] = True
while q:
x, y = q.popleft()
for d in range(4):
for k in range(1, latura + 1):
nx, ny = x + dx[d] * k, y + dy[d] * k
if in_bounds(nx, ny) and not vizitat[nx][ny]:
vizitat[nx][ny] = True
q.append((nx, ny))
return num_roboți

def defrisare_minima(n, m, copaci, max_roboți):
def numar_roboți(latura):
return bfs(n, m, copaci, latura)

stanga, dreapta = 1, min(n, m)
while stanga < dreapta:
mijloc = (stanga + dreapta) // 2
if numar_roboți(mijloc) <= max_roboți:
dreapta = mijloc
else:
stanga = mijloc + 1
return stanga

def latura_minima_robot(n, m, copaci, Q, k):
rezultate = []
for fiecare_k in k:
rezultate.append(defrisare_minima(n, m, copaci, fiecare_k))
return rezultate

def scrie_rezultate(fisier_iesire, rezultate):
with open(fisier_iesire, "w") as f:
for rezultat in rezultate:
f.write(f"{rezultat}\n")

def main():
fisier_intrare = "roboti.in"
fisier_iesire = "roboti.out"

p, n, m, l, copaci, Q, k = citire_date_intrare(fisier_intrare)

# Restricții și precizări
assert 2 <= n <= 150, "n trebuie să fie între 2 și 150"
assert 2 <= m <= 150, "m trebuie să fie între 2 și 150"
assert 1 <= l <= 150, "l trebuie să fie între 1 și 150"
for x, y in copaci:
assert 0 <= x < n, "Coordonata x trebuie să fie între 1 și n"
assert 0 <= y < m, "Coordonata y trebuie să fie între 1 și m"
if p == 2:
assert 1 <= Q <= 1000, "Q trebuie să fie între 1 și 1000"
for fiecare_k in k:
assert 1 <= fiecare_k <= 150, "k[i] trebuie să fie între 1 și 150"

if p == 1:
num_roboți = defrisare_minima(n, m, copaci, l)
rezultate = [num_roboți]
elif p == 2:
laturi_minime = latura_minima_robot(n, m, copaci, Q, k)
rezultate = laturi_minime

scrie_rezultate(fisier_iesire, rezultate)

if __name__ == "__main__":
main()

</syntaxhighlight>

1063 - Arme

2024-06-03T00:01:00Z

Benzar Ioan: /* Exemplu 1 */

== Cerința ==
Vasile joacă (din nou!) jocul său preferat cu împuşcături. Personajul său are la brâu N arme, aşezate în N huse speciale, numerotate de la 1 la N. Arma din husa i are puterea pbi (1≤i≤N).

În camera armelor a găsit M arme, aşezate pe perete, în M locaţii, numerotate de la 1 la M. Pentru fiecare armă j (1≤j≤M) este cunoscută puterea sa pcj.

Vasile poate înlocui arme pe care le are la brâu cu arme aflate pe perete în camera armelor. La o înlocuire el ia arma de pe perete din locaţia j (1≤j≤M) şi o pune la brâu în husa i (1≤i≤N), iar arma din husa i o pune pe perete în locaţia j.
Scrieţi un program care să determine suma maximă a puterilor armelor pe care le va avea la brâu Vasile după efectuarea înlocuirilor.
== Date de intrare ==
Fișierul de intrare arme.in conține pe prima linie numerele naturale N M, reprezentând numărul de arme pe care le are la brâu, respectiv numărul de arme aflate în camera armelor. Pe a doua linie se află N numere naturale pb1 pb2 … pbN reprezentând în ordine puterile armelor pe care Vasile le are la brâu. Pe a treia linie se află M numere naturale pc1 pc2 … pcM reprezentând în ordine puterile armelor aflate în camera armelor. Numerele scrise pe aceeaşi linie sunt separate prin spaţiu.
== Date de ieșire ==
Fișierul de ieșire arme.out va conține o singură linie pe care va fi scrisă suma maximă a puterilor armelor de la brâul lui Vasile, după efectuarea înlocuirilor.
== Restricții și precizări ==
*1 ≤ N, M ≤ 1000
*Puterile armelor sunt numere naturale ≤ 10.000.
* Greutatea și valoarea fiecărei arme sunt numere întregi pozitive
== Exemplu 1 ==
;Intrare
3 2 
3 1 7 
4 5

;Iesire
16

== Rezolvare ==
<syntaxhighlight lang="python" line>
def main():
with open("arme.in", "r") as f:
# Citim dimensiunile N și M
N, M = map(int, f.readline().strip().split())

# Citim puterile armelor de la brâu
puteri_brau = list(map(int, f.readline().strip().split()))

# Citim puterile armelor din camera armelor
puteri_camera = list(map(int, f.readline().strip().split()))

# Restricții și precizări
assert 1 <= N <= 1000, "N trebuie să fie între 1 și 1000"
assert 1 <= M <= 1000, "M trebuie să fie între 1 și 1000"
assert all(1 <= pb <= 10000 for pb in puteri_brau), "Puterea armelor de la brâu trebuie să fie între 1 și 10000"
assert all(1 <= pc <= 10000 for pc in puteri_camera), "Puterea armelor din cameră trebuie să fie între 1 și 10000"

# Sortăm puterile armelor de la brâu în ordine crescătoare
puteri_brau.sort()

# Sortăm puterile armelor din cameră în ordine descrescătoare
puteri_camera.sort(reverse=True)

# Înlocuim armele de la brâu cu cele din cameră
for i in range(min(N, M)):
if puteri_camera[i] > puteri_brau[i]:
puteri_brau[i] = puteri_camera[i]
else:
break

# Calculăm suma maximă a puterilor armelor de la brâu
suma_maxima = sum(puteri_brau)

with open("arme.out", "w") as f:
f.write(f"{suma_maxima}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

1063 - Arme

2024-06-03T00:00:38Z

Benzar Ioan: /* Exemplu 2 */

== Cerința ==
Vasile joacă (din nou!) jocul său preferat cu împuşcături. Personajul său are la brâu N arme, aşezate în N huse speciale, numerotate de la 1 la N. Arma din husa i are puterea pbi (1≤i≤N).

În camera armelor a găsit M arme, aşezate pe perete, în M locaţii, numerotate de la 1 la M. Pentru fiecare armă j (1≤j≤M) este cunoscută puterea sa pcj.

Vasile poate înlocui arme pe care le are la brâu cu arme aflate pe perete în camera armelor. La o înlocuire el ia arma de pe perete din locaţia j (1≤j≤M) şi o pune la brâu în husa i (1≤i≤N), iar arma din husa i o pune pe perete în locaţia j.
Scrieţi un program care să determine suma maximă a puterilor armelor pe care le va avea la brâu Vasile după efectuarea înlocuirilor.
== Date de intrare ==
Fișierul de intrare arme.in conține pe prima linie numerele naturale N M, reprezentând numărul de arme pe care le are la brâu, respectiv numărul de arme aflate în camera armelor. Pe a doua linie se află N numere naturale pb1 pb2 … pbN reprezentând în ordine puterile armelor pe care Vasile le are la brâu. Pe a treia linie se află M numere naturale pc1 pc2 … pcM reprezentând în ordine puterile armelor aflate în camera armelor. Numerele scrise pe aceeaşi linie sunt separate prin spaţiu.
== Date de ieșire ==
Fișierul de ieșire arme.out va conține o singură linie pe care va fi scrisă suma maximă a puterilor armelor de la brâul lui Vasile, după efectuarea înlocuirilor.
== Restricții și precizări ==
*1 ≤ N, M ≤ 1000
*Puterile armelor sunt numere naturale ≤ 10.000.
* Greutatea și valoarea fiecărei arme sunt numere întregi pozitive
== Exemplu 1 ==
;Intrare
4 
2 3 
3 4 
4 5 
5 6 
5

;Iesire
7
== Rezolvare ==
<syntaxhighlight lang="python" line>
def main():
with open("arme.in", "r") as f:
# Citim dimensiunile N și M
N, M = map(int, f.readline().strip().split())

# Citim puterile armelor de la brâu
puteri_brau = list(map(int, f.readline().strip().split()))

# Citim puterile armelor din camera armelor
puteri_camera = list(map(int, f.readline().strip().split()))

# Restricții și precizări
assert 1 <= N <= 1000, "N trebuie să fie între 1 și 1000"
assert 1 <= M <= 1000, "M trebuie să fie între 1 și 1000"
assert all(1 <= pb <= 10000 for pb in puteri_brau), "Puterea armelor de la brâu trebuie să fie între 1 și 10000"
assert all(1 <= pc <= 10000 for pc in puteri_camera), "Puterea armelor din cameră trebuie să fie între 1 și 10000"

# Sortăm puterile armelor de la brâu în ordine crescătoare
puteri_brau.sort()

# Sortăm puterile armelor din cameră în ordine descrescătoare
puteri_camera.sort(reverse=True)

# Înlocuim armele de la brâu cu cele din cameră
for i in range(min(N, M)):
if puteri_camera[i] > puteri_brau[i]:
puteri_brau[i] = puteri_camera[i]
else:
break

# Calculăm suma maximă a puterilor armelor de la brâu
suma_maxima = sum(puteri_brau)

with open("arme.out", "w") as f:
f.write(f"{suma_maxima}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

1063 - Arme

2024-06-03T00:00:27Z

Benzar Ioan:

== Cerința ==
Vasile joacă (din nou!) jocul său preferat cu împuşcături. Personajul său are la brâu N arme, aşezate în N huse speciale, numerotate de la 1 la N. Arma din husa i are puterea pbi (1≤i≤N).

În camera armelor a găsit M arme, aşezate pe perete, în M locaţii, numerotate de la 1 la M. Pentru fiecare armă j (1≤j≤M) este cunoscută puterea sa pcj.

Vasile poate înlocui arme pe care le are la brâu cu arme aflate pe perete în camera armelor. La o înlocuire el ia arma de pe perete din locaţia j (1≤j≤M) şi o pune la brâu în husa i (1≤i≤N), iar arma din husa i o pune pe perete în locaţia j.
Scrieţi un program care să determine suma maximă a puterilor armelor pe care le va avea la brâu Vasile după efectuarea înlocuirilor.
== Date de intrare ==
Fișierul de intrare arme.in conține pe prima linie numerele naturale N M, reprezentând numărul de arme pe care le are la brâu, respectiv numărul de arme aflate în camera armelor. Pe a doua linie se află N numere naturale pb1 pb2 … pbN reprezentând în ordine puterile armelor pe care Vasile le are la brâu. Pe a treia linie se află M numere naturale pc1 pc2 … pcM reprezentând în ordine puterile armelor aflate în camera armelor. Numerele scrise pe aceeaşi linie sunt separate prin spaţiu.
== Date de ieșire ==
Fișierul de ieșire arme.out va conține o singură linie pe care va fi scrisă suma maximă a puterilor armelor de la brâul lui Vasile, după efectuarea înlocuirilor.
== Restricții și precizări ==
*1 ≤ N, M ≤ 1000
*Puterile armelor sunt numere naturale ≤ 10.000.
* Greutatea și valoarea fiecărei arme sunt numere întregi pozitive
== Exemplu 1 ==
;Intrare
4 
2 3 
3 4 
4 5 
5 6 
5

;Iesire
7
== Exemplu 2 ==
;Intrare
3 
1 1 
3 4 
4 5 
5

;Iesire
6

== Rezolvare ==
<syntaxhighlight lang="python" line>
def main():
with open("arme.in", "r") as f:
# Citim dimensiunile N și M
N, M = map(int, f.readline().strip().split())

# Citim puterile armelor de la brâu
puteri_brau = list(map(int, f.readline().strip().split()))

# Citim puterile armelor din camera armelor
puteri_camera = list(map(int, f.readline().strip().split()))

# Restricții și precizări
assert 1 <= N <= 1000, "N trebuie să fie între 1 și 1000"
assert 1 <= M <= 1000, "M trebuie să fie între 1 și 1000"
assert all(1 <= pb <= 10000 for pb in puteri_brau), "Puterea armelor de la brâu trebuie să fie între 1 și 10000"
assert all(1 <= pc <= 10000 for pc in puteri_camera), "Puterea armelor din cameră trebuie să fie între 1 și 10000"

# Sortăm puterile armelor de la brâu în ordine crescătoare
puteri_brau.sort()

# Sortăm puterile armelor din cameră în ordine descrescătoare
puteri_camera.sort(reverse=True)

# Înlocuim armele de la brâu cu cele din cameră
for i in range(min(N, M)):
if puteri_camera[i] > puteri_brau[i]:
puteri_brau[i] = puteri_camera[i]
else:
break

# Calculăm suma maximă a puterilor armelor de la brâu
suma_maxima = sum(puteri_brau)

with open("arme.out", "w") as f:
f.write(f"{suma_maxima}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

3739 - Cafea

2024-06-02T23:56:32Z

Benzar Ioan:

== Cerința ==
Algorel a primit de la părinţi o sumă de bani, S, şi o plasă în care încap K grame de cafea. Algorel trebuie să meargă la piaţă şi să cumpere suficientă cafea încât să umple plasa. Pe de altă parte, părinţii nu îi cer înapoi restul. Dacă va reuşi să umple plasa, va putea păstra diferenţa de bani dintre suma primită S şi costul total al cafelei achiziţionate. Dacă nu va reuşi să umple plasa, atunci nu va rămâne cu niciun ban.

La piaţă există N comercianţi care vând cafea. Fiecare dintre aceştia are o cantitate de Ci grame de cafea pe care o vinde cu preţul total de Pi lei (1 ≤ i ≤ N). Comercianţii nu au monede mai mici de 1 leu, aşa că, în cazul în care clientul cumpără o cantitate de cafea al cărei preţ nu este un număr întreg, acesta va plăti suma rotunjită la cea mai apropiată valoare întreagă mai mare sau egală cu valoarea datorată. De exemplu, dacă un comerciant vinde 1000 de grame de cafea la preţul de 25 de lei şi un client vrea să cumpere 250 de grame, atunci acesta va plăti 7 lei, deşi suma datorată era de 6.25 lei.
Ajutaţi-l pe Algorel să rămână cu o sumă cât mai mare de bani, scriind un program care face acest calcul pe baza datelor corespunzătoare comercianţilor.
== Date de intrare ==
Fişierul de intrare cafea.in va conţine pe prima linie, separate prin câte un spaţiu numerele naturale K, S şi N corespunzătoare capacităţii plasei, sumei pe pare o primeşte de la părinţi şi numărului de vânzători. Pe următoarele N linii se vor afla datele corespunzătoare comercianţilor: pe linia i + 1 se vor afla numerele naturale Ci şi Pi reprezentând cantitatea maximă de cafea pe care o vinde comerciantul numărul i şi preţul total cerut de acesta.
== Date de ieșire ==
Fișierul de ieșire cafea.out va conține pe prima linie un număr natural, reprezentând suma maximă care îi rămâne lui Algorel după ce umple plasa cu cafea.
== Restricții și precizări ==
*1 ≤ K ≤ 1 000 000 000
*1 ≤ S ≤ 1 000 000 000
*1 ≤ N ≤ 100 000
*Ci ∈ [1, 100 000], pentru 1 ≤ i ≤ N
*Pi ∈ [1, 100 000], pentru 1 ≤ i ≤ N

== Exemplu 1 ==
;Intrare
1000 200 4 
500 85 
600 45 
250 35 
1000 1000
;Iesire
94
== Rezolvare ==
<syntaxhighlight lang="python" line>
def main():
with open("cafea.in", "r") as f:
k, s, n = map(int, f.readline().strip().split())
comercianti = []
for _ in range(n):
ci, pi = map(int, f.readline().strip().split())
comercianti.append((pi / ci, ci, pi)) # (preț per gram, cantitate maximă, preț total)

# Sortăm comercianții după prețul per gram
comercianti.sort()

cantitate_cumparata = 0
cost_total = 0

for pret_per_gram, cantitate_max, pret_total in comercianti:
if cantitate_cumparata + cantitate_max <= k:
cantitate_cumparata += cantitate_max
cost_total += pret_total
else:
cantitate_necesara = k - cantitate_cumparata
cost_total += cantitate_necesara * pret_per_gram
cantitate_cumparata += cantitate_necesara
break

bani_ramasi = s - cost_total

with open("cafea.out", "w") as f:
f.write(f"{int(bani_ramasi)}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

3943 - Cerc5

2024-06-02T23:52:39Z

Benzar Ioan:

== Cerința ==
Se dă numărul natural n. Determinati o modalitate de așezare a numerelor din mulțimea 1,2,…,n
pe un cerc astfel încât suma a oricare două nume învecinate să nu fie pătrat perfect.
== Date de intrare ==
Programul citește de la tastatură numărul n.
== Date de ieșire ==
Programul va afișa pe ecran cele n numere cerute, separate prin câte un spațiu.
== Restricții și precizări ==
*1 ≤ n ≤ 35
*dacă există mai multe modalități de aranjare a numerelor astfel încât să fie îndeplinită condiția, se poate afișa oricare;
*dacă nu există nicio modalitate de aranjare se va afișa mesajul nu exista

== Exemplu 1 ==
;Intrare
32

;Iesire
1 8 28 21 4 32 17 19 30 6 3 13 12 24 25 11 5 31 18 7 29 20 16 9 27 22 14 2 23 26 10 15

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

# Verifică dacă un număr este pătrat perfect
def este_patrat_perfect(x):
return int(math.isqrt(x)) ** 2 == x

# Funcție de backtracking pentru a găsi o soluție validă
def backtrack(cerc, vizitat, n):
if len(cerc) == n:
# Verifică dacă primul și ultimul element formează un pătrat perfect
return este_patrat_perfect(cerc[-1] + cerc[0])

for i in range(1, n + 1):
if not vizitat[i]:
if not cerc or este_patrat_perfect(cerc[-1] + i):
cerc.append(i)
vizitat[i] = True
if backtrack(cerc, vizitat, n):
return True
cerc.pop()
vizitat[i] = False
return False

# Funcție pentru a găsi aranjarea corectă
def gaseste_aranjare(n):
cerc = []
vizitat = [False] * (n + 1)
if backtrack(cerc, vizitat, n):
return cerc
else:
return "nu exista"

# Funcția principală
def main():
n = int(input().strip())
rezultat = gaseste_aranjare(n)
if isinstance(rezultat, list):
print(" ".join(map(str, rezultat)))
else:
print(rezultat)

if __name__ == "__main__":
main()

if __name__ == "__main__":
main()

</syntaxhighlight>

3156 - perm min max

2024-06-02T23:40:20Z

Benzar Ioan:

== Cerința ==
Se citește o mulțime cu n numere naturale. Afișați în ordine lexicografică toate permutările mulțimii citite în care elementul minim și cel maxim nu își schimbă poziția.
== Date de intrare ==
Programul citește de la tastatură numărul n, iar apoi n numere naturale distincte, separate prin spații.
== Date de ieșire ==
Programul va afișa pe ecran permutările cerute, pe rânduri separate, fiecare permutare având elementele separate prin câte un spațiu.
== Restricții și precizări ==
*1 ≤ n ≤ 10
*cele n numere citite vor fi mai mici decât 1.000.000.000 și vor fi distincte

== Exemplu 1 ==
;Intrare
6 
8 2 7 9 4 5

;Iesire
4 2 5 9 7 8 
4 2 5 9 8 7 
4 2 7 9 5 8 
4 2 7 9 8 5 
4 2 8 9 5 7 
4 2 8 9 7 5 
5 2 4 9 7 8 
5 2 4 9 8 7 
5 2 7 9 4 8 
5 2 7 9 8 4 
5 2 8 9 4 7 
5 2 8 9 7 4 
7 2 4 9 5 8 
7 2 4 9 8 5 
7 2 5 9 4 8 
7 2 5 9 8 4 
7 2 8 9 4 5 
7 2 8 9 5 4 
8 2 4 9 5 7 
8 2 4 9 7 5 
8 2 5 9 4 7 
8 2 5 9 7 4 
8 2 7 9 4 5 
8 2 7 9 5 4

== Rezolvare ==
<syntaxhighlight lang="python" line>
from itertools import permutations

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

min_value = min(arr)
max_value = max(arr)

min_index = arr.index(min_value)
max_index = arr.index(max_value)

# To store the results
results = set()

# Generate permutations
for perm in permutations(arr):
if perm[min_index] == min_value and perm[max_index] == max_value:
results.add(perm)

# Sort results lexicographically
results = sorted(results)

# Print results
for result in results:
print(" ".join(map(str, result)))

if __name__ == "__main__":
main()

</syntaxhighlight>

1176 – FListă Ștergere

2024-06-02T23:36:45Z

Benzar Ioan: Ștergerea conținutului paginii

0884 - Paznici

2024-06-02T23:35:31Z

Benzar Ioan: /* Exemplu 1 */

== Cerința ==
Se consideră o clădire de formă dreptunghiulară, formată din n*m camere dispuse sub forma unei matrice cu n linii și m coloane. Anumite camere sunt ocupate şi nu pot fi vizitate, celelalte sunt libere și pot fi vizitate. Dintr-o cameră se poate trece în altă cameră dacă ambele sunt libere și se învecinează pe linie sau pe coloană.

În anumite camere sunt paznici. Din motive de securitate, paznicii se pot deplasa din camera inițială în anumite camere libere din apropiere, dar fără a se îndepărta la o distanță mai mare decât o valoare cunoscută. Fiecare paznic va verifica periodic camerele libere în care poate ajunge.

Să se determine numărul de camere din clădire care nu sunt verificate de niciun paznic.
== Date de intrare ==
Fișierul de intrare paznici.in conține pe prima linie trei numere n m p, reprezentând dimensiunile clădirii şi numărul de paznici.

Urmează n linii cu câte m caractere, care pot fi: -, reprezentând o cameră liberă, respectiv #, reprezentând o cameră ocupată.

Urmează p linii cu câte 3 valori i j d, reprezentând informaţiile despre paznici. i j reprezintă indicii camerei, iar d reprezintă distanţa pe care se poate deplasa acel paznic.
== Date de ieșire ==
Fișierul de ieșire paznici.out va conține pe prima linie numărul C de camere care nu sunt vizitate de niciun paznic.
== Restricții și precizări ==
*1 ≤ n, m, p ≤ 200
*1 ≤ i ≤ n
*1 ≤ j ≤ m
*0 ≤ d ≤ 40

== Exemplu 1 ==
;Intrare
*4 6 3 
*--#-#- 
*--##-- 
*------ 
*-----# 
*1 1 1 
*1 6 2 
*4 1 3

;Iesire
4

== Rezolvare ==
<syntaxhighlight lang="python" line>
def in_bounds(x, y, n, m):
return 0 <= x < n and 0 <= y < m

def mark_guard_reachable(grid, visited, x, y, d, n, m):
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] # N, S, W, E
queue = [(x, y, 0)]
visited[x][y] = True

while queue:
cx, cy, dist = queue.pop(0)
if dist < d:
for dx, dy in directions:
nx, ny = cx + dx, cy + dy
if in_bounds(nx, ny, n, m) and not visited[nx][ny] and grid[nx][ny] == '-':
visited[nx][ny] = True
queue.append((nx, ny, dist + 1))

def main():
with open("paznici.in", "r") as f:
n, m, p = map(int, f.readline().strip().split())
grid = [list(f.readline().strip()) for _ in range(n)]
guards = [tuple(map(int, f.readline().strip().split())) for _ in range(p)]

visited = [[False for _ in range(m)] for _ in range(n)]

for guard in guards:
i, j, d = guard
mark_guard_reachable(grid, visited, i - 1, j - 1, d, n, m)

unvisited_count = sum(1 for i in range(n) for j in range(m) if grid[i][j] == '-' and not visited[i][j])

with open("paznici.out", "w") as f:
f.write(f"{unvisited_count}\n")

if __name__ == "__main__":
main()

if __name__ == "__main__":
main()

</syntaxhighlight>

0884 - Paznici

2024-06-02T23:35:09Z

Benzar Ioan: /* Exemplu 2 */

== Cerința ==
Se consideră o clădire de formă dreptunghiulară, formată din n*m camere dispuse sub forma unei matrice cu n linii și m coloane. Anumite camere sunt ocupate şi nu pot fi vizitate, celelalte sunt libere și pot fi vizitate. Dintr-o cameră se poate trece în altă cameră dacă ambele sunt libere și se învecinează pe linie sau pe coloană.

În anumite camere sunt paznici. Din motive de securitate, paznicii se pot deplasa din camera inițială în anumite camere libere din apropiere, dar fără a se îndepărta la o distanță mai mare decât o valoare cunoscută. Fiecare paznic va verifica periodic camerele libere în care poate ajunge.

Să se determine numărul de camere din clădire care nu sunt verificate de niciun paznic.
== Date de intrare ==
Fișierul de intrare paznici.in conține pe prima linie trei numere n m p, reprezentând dimensiunile clădirii şi numărul de paznici.

Urmează n linii cu câte m caractere, care pot fi: -, reprezentând o cameră liberă, respectiv #, reprezentând o cameră ocupată.

Urmează p linii cu câte 3 valori i j d, reprezentând informaţiile despre paznici. i j reprezintă indicii camerei, iar d reprezintă distanţa pe care se poate deplasa acel paznic.
== Date de ieșire ==
Fișierul de ieșire paznici.out va conține pe prima linie numărul C de camere care nu sunt vizitate de niciun paznic.
== Restricții și precizări ==
*1 ≤ n, m, p ≤ 200
*1 ≤ i ≤ n
*1 ≤ j ≤ m
*0 ≤ d ≤ 40

== Exemplu 1 ==
;Intrare
4 6 3 
--#-#- 
--##-- 
------ 
-----# 
1 1 1 
1 6 2 
4 1 3

;Iesire
4

== Rezolvare ==
<syntaxhighlight lang="python" line>
def in_bounds(x, y, n, m):
return 0 <= x < n and 0 <= y < m

def mark_guard_reachable(grid, visited, x, y, d, n, m):
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] # N, S, W, E
queue = [(x, y, 0)]
visited[x][y] = True

while queue:
cx, cy, dist = queue.pop(0)
if dist < d:
for dx, dy in directions:
nx, ny = cx + dx, cy + dy
if in_bounds(nx, ny, n, m) and not visited[nx][ny] and grid[nx][ny] == '-':
visited[nx][ny] = True
queue.append((nx, ny, dist + 1))

def main():
with open("paznici.in", "r") as f:
n, m, p = map(int, f.readline().strip().split())
grid = [list(f.readline().strip()) for _ in range(n)]
guards = [tuple(map(int, f.readline().strip().split())) for _ in range(p)]

visited = [[False for _ in range(m)] for _ in range(n)]

for guard in guards:
i, j, d = guard
mark_guard_reachable(grid, visited, i - 1, j - 1, d, n, m)

unvisited_count = sum(1 for i in range(n) for j in range(m) if grid[i][j] == '-' and not visited[i][j])

with open("paznici.out", "w") as f:
f.write(f"{unvisited_count}\n")

if __name__ == "__main__":
main()

if __name__ == "__main__":
main()

</syntaxhighlight>

0884 - Paznici

2024-06-02T23:34:59Z

Benzar Ioan:

== Cerința ==
Se consideră o clădire de formă dreptunghiulară, formată din n*m camere dispuse sub forma unei matrice cu n linii și m coloane. Anumite camere sunt ocupate şi nu pot fi vizitate, celelalte sunt libere și pot fi vizitate. Dintr-o cameră se poate trece în altă cameră dacă ambele sunt libere și se învecinează pe linie sau pe coloană.

În anumite camere sunt paznici. Din motive de securitate, paznicii se pot deplasa din camera inițială în anumite camere libere din apropiere, dar fără a se îndepărta la o distanță mai mare decât o valoare cunoscută. Fiecare paznic va verifica periodic camerele libere în care poate ajunge.

Să se determine numărul de camere din clădire care nu sunt verificate de niciun paznic.
== Date de intrare ==
Fișierul de intrare paznici.in conține pe prima linie trei numere n m p, reprezentând dimensiunile clădirii şi numărul de paznici.

Urmează n linii cu câte m caractere, care pot fi: -, reprezentând o cameră liberă, respectiv #, reprezentând o cameră ocupată.

Urmează p linii cu câte 3 valori i j d, reprezentând informaţiile despre paznici. i j reprezintă indicii camerei, iar d reprezintă distanţa pe care se poate deplasa acel paznic.
== Date de ieșire ==
Fișierul de ieșire paznici.out va conține pe prima linie numărul C de camere care nu sunt vizitate de niciun paznic.
== Restricții și precizări ==
*1 ≤ n, m, p ≤ 200
*1 ≤ i ≤ n
*1 ≤ j ≤ m
*0 ≤ d ≤ 40

== Exemplu 1 ==
;Intrare
4 6 3 
--#-#- 
--##-- 
------ 
-----# 
1 1 1 
1 6 2 
4 1 3

;Iesire
4

== Exemplu 2 ==
;Intrare
4 
ENQUEUE George 
DEQUEUE 
DEQUEUE 
ENQUEUE Paul

;Iesire
Eroare: coada goală
['Paul']

Datele de intrare nu corespund restricțiilor impuse.
== Rezolvare ==
<syntaxhighlight lang="python" line>
def in_bounds(x, y, n, m):
return 0 <= x < n and 0 <= y < m

def mark_guard_reachable(grid, visited, x, y, d, n, m):
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] # N, S, W, E
queue = [(x, y, 0)]
visited[x][y] = True

while queue:
cx, cy, dist = queue.pop(0)
if dist < d:
for dx, dy in directions:
nx, ny = cx + dx, cy + dy
if in_bounds(nx, ny, n, m) and not visited[nx][ny] and grid[nx][ny] == '-':
visited[nx][ny] = True
queue.append((nx, ny, dist + 1))

def main():
with open("paznici.in", "r") as f:
n, m, p = map(int, f.readline().strip().split())
grid = [list(f.readline().strip()) for _ in range(n)]
guards = [tuple(map(int, f.readline().strip().split())) for _ in range(p)]

visited = [[False for _ in range(m)] for _ in range(n)]

for guard in guards:
i, j, d = guard
mark_guard_reachable(grid, visited, i - 1, j - 1, d, n, m)

unvisited_count = sum(1 for i in range(n) for j in range(m) if grid[i][j] == '-' and not visited[i][j])

with open("paznici.out", "w") as f:
f.write(f"{unvisited_count}\n")

if __name__ == "__main__":
main()

if __name__ == "__main__":
main()

</syntaxhighlight>

3550 - liceu

2024-06-02T23:31:24Z

Benzar Ioan:

== Cerința ==
Marciuc este un băiat foarte neastâmpărat. El refuză să învețe informatică, așa că înainte de fiecare oră el pleacă pentru a explora noul său liceu. La plecare le promite colegilor lui că o să treacă pe la magazin înainte de a se întoarce în clasă, pentru a avea ce să mănânce în pauza următoare. Însă, dacă va ajunge în clasă în mai mult de T secunde, va întarza la ora așa că în acest caz va folosi o ruta directă spre clasă.

Liceul poate fi reprezentat sub forma unei matrice cu n linii și n coloane. Există 3 tipuri de celule:

*celulă liberă, pe unde băiatul poate avansa, o mutare durând o secundă;
*celulă ocupată de un zid, pe unde băiatul nu poate avansa;
*celulă în care se află o scurtătură, ce îl duce într-o secundă de la poziția, x1 y1, la poziția x2 y2 sau invers;
Fiind dat numărul n de linii și de coloane, coordonatele celulelor ocupate de zid și coordonatele scurtăturilor, se cere să se afișeze numărul minim de secunde în care Marciuc reușește să ajungă în clasă, trecând și pe la magazin. Dacă magazinul nu este accesibil sau daca va ajunge în clasă in mai mult de T secunde, atunci el nu va mai merge la magazin și se va afișa numărul minim de secunde în care acesta ajunge de la poziția lui la clasă. De asemenea, se va afișa și traseul folosit.

== Date de intrare ==
Pe prima linie a fișierului liceu.in se vor afla 4 numere naturale: n – numărul de linii și de coloane ale matricei, z – numărul de ziduri ce blochează calea băiatului, s – numărul de scurtături și t – numărul de secunde în care Marciuc poate ajunge în clasă dacă vrea să treacă și pe la magazin.

Pe următoarele Z linii se află câte 2 numere reprezentânt coordonatele celulelor ocupate de zid.

Pe următoarele S linii se află câte 4 numere naturale reprezentând coordonatele a două celule ce formează o scurtătură.

Pe ultima linie se află 2 numere ce reprezintă coordonatele magazinului.
== Date de ieșire ==
Fișierul de ieșire liceu.out va conține pe prima linie numărul minim de secunde în care băiatul ajunge în clasă, iar pe următoarele linii traseul complet al băiatului, celule fiind afișate în ordinea parcurgerii.
== Restricții și precizări ==
*1 ≤ n ≤ 400
*5 ≤ z ≤ 100000
*0 ≤ s ≤ 15500
*Poziția inițială a lui Marciuc este 1 1, iar poziția clasei este n n
*Orice traseu de durată minimă este corect. Dacă băiatul poate merge pe la magazin, în traseu trebuie să apară obligatoriu coordonatele magazinului.
*Daca numărul minim de secunde este corect dar traseul nu este curect se acordă 40% din punctaj.
*Pentru teste în valoare de 20 de puncte, s = 0.
*Pentru teste în valoare de 40 de puncte, n ≤ 100.
*Marciuc poate trece de mai multe ori prin același loc.
*O celula surtătură poate fi folosită și ca o celula libera.
*Fiecare celulă are un singur tip. Nu există scurtături spre celule blocate; celulele 1 1, n n și celula pe care este situat magazinul nu sunt blocate.
*O scurtatură poate fi traversată prin ambele sensuri.

== Exemplu 1 ==
;Intrare
5 
ENQUEUE Maria 
ENQUEUE Andrei 
DEQUEUE 
ENQUEUE Ioana 
ENQUEUE Alexandru

;Iesire
['Andrei', 'Ioana', 'Alexandru']

== Exemplu 2 ==
;Intrare
4 
ENQUEUE George 
DEQUEUE 
DEQUEUE 
ENQUEUE Ana

;Iesire
Eroare: coada goală
['Ana']

Datele de intrare nu corespund restricțiilor impuse.
== Rezolvare ==
<syntaxhighlight lang="python" line>
def citeste_date():
try:
n = int(input("Introduceți numărul de operațiuni (n): "))
operatiuni = []
for _ in range(n):
operatiune = input().strip()
operatiuni.append(operatiune)
return n, operatiuni
except ValueError:
return None, None

def valideaza_date(n, operatiuni):
if not (1 <= n <= 100):
return False
for operatiune in operatiuni:
if not (operatiune.startswith("ENQUEUE ") or operatiune == "DEQUEUE"):
return False
if operatiune.startswith("ENQUEUE ") and len(operatiune.split()) != 2:
return False
if operatiune.startswith("ENQUEUE ") and not operatiune.split()[1].isalpha():
return False
return True

def proceseaza_operatiuni(n, operatiuni):
coada = []
for operatiune in operatiuni:
if operatiune.startswith("ENQUEUE "):
_, nume = operatiune.split()
coada.append(nume)
elif operatiune == "DEQUEUE":
if coada:
coada.pop(0)
else:
print("Eroare: coada goală")
return coada

def main():
n, operatiuni = citeste_date()

if n is None or operatiuni are None or not valideaza_date(n, operatiuni):
print("Datele de intrare nu corespund restricțiilor impuse.")
return

print("Datele de intrare corespund restricțiilor impuse.")
rezultat = proceseaza_operatiuni(n, operatiuni)
print(rezultat)

if __name__ == "__main__":
main()

</syntaxhighlight>