Bitnami MediaWiki - User contributions [en]

3044 - Comun 1

2024-06-03T17:53:09Z

RebecaBud: Pagină nouă: == Enunt == Tocmai ai primit un șir v de K numere naturale nenule distincte. Plecând de la acest șir, te-ai gândit să construiești un șir w de N numere naturale distincte, astfel încât un număr x este în șirul w dacă și numai dacă exista inițial în șirul v sau se pot alege cel puțin două numere din șirul v astfel încât x este cel mai mare divizor comun al acelor numere. De exemplu, dacă v = {4, 6, 7} atunci w = {1, 2, 4, 6, 7}. Uimit de proprietățile...

== Enunt ==
Tocmai ai primit un șir v de K numere naturale nenule distincte. Plecând de la acest șir, te-ai gândit să construiești un șir w de N numere naturale distincte, astfel încât un număr x este în șirul w dacă și numai dacă exista inițial în șirul v sau se pot alege cel puțin două numere din șirul v astfel încât x este cel mai mare divizor comun al acelor numere. De exemplu, dacă v = {4, 6, 7} atunci w = {1, 2, 4, 6, 7}.
Uimit de proprietățile matematice frumoase ale noului șir w, ai uitat din păcate șirul original v de la care ai pornit.
== Cerinţa ==
Dându-se șirul w, să se găsească un șir posibil inițial v având un număr minim de elemente.
== Date de intrare ==
Fișierul de intrare comun.in conține pe prima linie un număr natural N. Pe cea de-a doua linie se află N numere naturale nenule distincte, în ordine strict crescătoare, reprezentând șirul w.
== Date de ieșire ==
Fișierul de ieșire comun.out va conține pe prima linie numărul minim K de elemente ale șirului v. Pe cea de-a doua linie se vor afla K numere naturale distincte, în ordine strict crescătoare, reprezentând șirul propriu-zis.
== Restricţii şi precizări ==
* Toate valorile din fișierul de intrare sunt numere naturale nenule mai mici sau egale cu 100.000.
* Pentru teste în valoare de 15 puncte, toate valorile din fișierul de intrare sunt mai mici sau egale cu 20.
* Pentru teste în valoare de 50 de puncte, toate valorile din fișierul de intrare sunt mai mici sau egale cu 2000.
* Se garantează că există măcar o soluție.
* Dacă există mai multe șiruri inițiale cu număr minim de elemente, oricare este acceptat.
== Exemplul 1 ==
; comun.in

5
1 2 4 6 7
; comun.out

3
4 6 7
== Explicație ==
1 = cmmdc(6, 7) = cmmdc(4, 6, 7). 2 = cmmdc(4, 6). Se poate demonstra că orice alt șir cu proprietatea cerută are măcar 3 elemente.
 

== Exemplul 2 ==
; comun.in

4
2 4 8 16
; comun.out

4
2 4 8 16
== Explicație ==
Nu există niciun șir de mai puțin de 4 elemente cu proprietatea cerută.
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def gcd(a, b):
while b:
a, b = b, a % b
return a

def find_initial_sequence(w):
n = len(w)
initial_sequence = []
initial_sequence.append(w[0])
for i in range(1, n):
current_gcd = gcd(initial_sequence[-1], w[i])
if current_gcd != w[i]:
initial_sequence.append(w[i])
return initial_sequence

def main():
with open("comun.in", "r") as f:
n = int(f.readline())
w = list(map(int, f.readline().split()))

initial_sequence = find_initial_sequence(w)

with open("comun.out", "w") as f:
f.write(str(len(initial_sequence)) + "\n")
f.write(" ".join(map(str, initial_sequence)))

if __name__ == "__main__":
main()

</syntaxhighlight>

3047 - Fibo Frac

2024-06-03T17:50:47Z

RebecaBud: Pagină nouă: == Enunt == Fie șirul Fibonacci dat prin F1 = 1, F2 = 1 și relația de recurență Fk = Fk-1 + Fk-2, k ≥ 3. Se consideră un număr natural N. == Cerinţa == Să se scrie un program care determină numărul F al fracțiilor diferite ireductibile subunitare, ce se pot forma utilizând primii N termeni ai șirului Fibonacci. == Date de intrare == Fișierul de intrare fibofrac.in conține pe prima linie numărul N. == Date de ieșire == Fișierul de ieșire fibofrac.out va c...

== Enunt ==
Fie șirul Fibonacci dat prin F1 = 1, F2 = 1 și relația de recurență Fk = Fk-1 + Fk-2, k ≥ 3. Se consideră un număr natural N.
== Cerinţa ==
Să se scrie un program care determină numărul F al fracțiilor diferite ireductibile subunitare, ce se pot forma utilizând primii N termeni ai șirului Fibonacci.
== Date de intrare ==
Fișierul de intrare fibofrac.in conține pe prima linie numărul N.
== Date de ieșire ==
Fișierul de ieșire fibofrac.out va conține pe prima linie numărul F, cu semnificația de mai sus.
== Restricţii şi precizări ==
* Pentru teste în valoare de 24 puncte, 0 < N < 80
* Pentru teste în valoare de 40 puncte, 0 < N < 1101
* Pentru teste în valoare de 56 puncte, 0 < N < 50001
* Pentru teste în valoare de 100 puncte, 0 < N < 1.000.000
* Două fracții ireductibile a / b și c / d sunt diferite dacă a ≠ c sau b ≠ d.
* 0 ≤ F < 2^63
== Exemplul 1 ==
; fibofrac.in

7
; fibofrac.out

14
== Explicație ==
N = 7; Primii 7 termeni ai șirului Fibonacci sunt: 1, 1, 2, 3, 5, 8, 13. Se pot forma 14 fracții diferite ireductibile subunitare: 1/2, 1/3, 1/5, 1/8, 1/13, 2/3, 2/5, 2/13, 3/5, 3/8, 3/13, 5/8, 5/13, 8/13.
 

== Exemplul 2 ==
; fibofrac.in

2019
; fibofrac.out

1547722
 

== Exemplul 3 ==
; fibofrac.in

500000
; fibofrac.out

94988288219

 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def gcd(a, b):
while b:
a, b = b, a % b
return a

def count_fibonacci_fractions(n):
fib = [1, 1]
for i in range(2, n):
fib.append(fib[i - 1] + fib[i - 2])

count = 0
for i in range(n):
for j in range(i + 1, n):
if gcd(fib[i], fib[j]) == 1:
count += 1
return count

def main():
with open("fibofrac.in", "r") as f_in:
n = int(f_in.readline().strip())

result = count_fibonacci_fractions(n)

with open("fibofrac.out", "w") as f_out:
f_out.write(str(result))

if __name__ == "__main__":
main()

</syntaxhighlight>

3091 - Pavele

2024-06-03T17:48:09Z

RebecaBud: Pagină nouă: == Cerinţa == Avem o suprafață dreptunghiulară pătratică de dimensiune n x n (n – impar). Colțul de dimensiune 1 x 1 din stânga-sus lipsește. Se dorește pavarea a cât mai mult din suprafața sa cu dale de dimensiune 1 x 2 (sau 2 x 1). Trebuie folosite cât mai multe dale și în plus, numărul de dale orizontale folosite trebuie să fie egal cu numărul de dale verticale folosite pentru pavare. == Date de intrare == Fișierul de intrare pavele.in conține pe pr...

== Cerinţa ==
Avem o suprafață dreptunghiulară pătratică de dimensiune n x n (n – impar). Colțul de dimensiune 1 x 1 din stânga-sus lipsește. Se dorește pavarea a cât mai mult din suprafața sa cu dale de dimensiune 1 x 2 (sau 2 x 1). Trebuie folosite cât mai multe dale și în plus, numărul de dale orizontale folosite trebuie să fie egal cu numărul de dale verticale folosite pentru pavare.
== Date de intrare ==
Fișierul de intrare pavele.in conține pe prima linie numărul n.
== Date de ieșire ==
Fișierul de ieșire pavele.out conține pe prima linie un număr r, ce reprezintă numărul de dale verticale (orizontale) folosite. Următoarele n linii conțin câte n numere întregi, separate printr-un spațiu, reprezentând codificarea modului de pavare. Numerele trebuie să fie cuprinse între –r și r. Valoarea 0 semnifică faptul că acea poziție a zonei dreptunghiulare nu se pavează (sau lipsește, întrucât se afișează 0 și în contul colțului stânga sus).
Pentru codificarea dalelor orizontale se folosesc câte două numere egale, cuprinse între 1 și r, așezate unul lângă altul pe aceeași linie iar pentru codificarea dalelor verticale se folosesc câte două numere egale cuprinse, cuprinse între –r și -1, așezate unul sub altul.
== Restricţii şi precizări ==
* 5 ≤ n ≤ 299
* n – impar;
* dalele orizontale se codifică folosind valori pozitive iar cele verticale folosind valori negative;
* evident, dalele nu se pot suprapune și trebuie să fie complet incluse în zona dreptunghiulară;
== Exemplul 1 ==
; pavele.in

5
; pavele.out

6
0 1 1 -1 -2
3 -4 -5 -1 -2
-3 -4 -5 4 4
2 2 -6 5 5
3 3 -6 6 6
Aici datele sunt indentate doar pentru o mai ușoară înțelegere a exemplului.

 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def write_output(file_name, r, pave_layout):
with open(file_name, 'w') as file:
file.write(str(r) + '\n')
for row in pave_layout:
file.write(' '.join(map(str, row)) + '\n')

def pave_surface(n):
pave_layout = [[0] * n for _ in range(n)]
r = n // 2 + 1
for i in range(n):
for j in range(n):
if (i + j) % 2 == 0:
pave_layout[i][j] = r
else:
pave_layout[i][j] = -r
return r, pave_layout

def main():
with open("pavele.in", 'r') as file:
n = int(file.readline().strip())
r, pave_layout = pave_surface(n)
write_output("pavele.out", r, pave_layout)

if __name__ == "__main__":
main()

</syntaxhighlight>

3924 - Cripto 1

2024-06-03T17:46:23Z

RebecaBud: Pagină nouă: == Enunt == Se dă un limbaj format din N cuvinte și un text criptat format din M cuvinte. Spunem că un cuvânt se permută după un șir x1,x2,…,xK dacă prima literă se permută cu x1, a doua cu x2, …, iar ultima cu xK. De exemplu, după șirul 1 5 6, “abc” devine “bgi”. Permutarea se face în ordinea literelor mici din alfabetul englez. Dacă o literă ar trece de finalul alfabetului, aceasta îl reia și apoi permută și litera următoare cu 1. În cazul...

== Enunt ==
Se dă un limbaj format din N cuvinte și un text criptat format din M cuvinte. Spunem că un cuvânt se permută după un șir x1,x2,…,xK dacă prima literă se permută cu x1, a doua cu x2, …, iar ultima cu xK.
De exemplu, după șirul 1 5 6, “abc” devine “bgi”. Permutarea se face în ordinea literelor mici din alfabetul englez. Dacă o literă ar trece de finalul alfabetului, aceasta îl reia și apoi permută și litera următoare cu 1.
În cazul în care ultima literă trece de finalul alfabetului, atunci cuvântul devine invalid. De exemplu, “zza” permutat după șirul 1 2 3, devine “ace”. (adunarea se face cu transport pornind de la stânga). Dacă “zzz” s-ar permuta după șirul 1 2 3, ar deveni invalid. Cele mai “semnificative” litere sunt de la dreapta la stânga.
Vrem să decriptăm textul, folosind mai multe variante de șiruri pe care le considerăm valabile. Cel mai bun șir de decriptare este acela pentru care numărul de cuvinte din textul criptat care se găsesc, după operație, în limbaj, este maximal.
== Cerinţa ==
Să se determine șirul cel mai bun de decriptare, dintre cele date. În cazul în care există mai multe astfel de șiruri, se va afișa cel cu indicele cel mai mic.
== Date de intrare ==
Pe prima linie din fișierul cripto1.in se află patru numere naturale N, M, K, Q.
Pe următoarea linie, se găsește limbajul, format din cele N cuvinte de lungime K.
Pe a treia linie se găsesc cele M cuvinte.
În final, se găsesc cele Q șiruri, de câte K numere fiecare pe câte o linie.
== Date de ieșire ==
Fişierul de ieşire cripto1.out va conţine pe prima linie, indicele celui mai bun șir, și similitudinea acestuia.
== Restricţii şi precizări ==
* N, M, Q ≤ 105, M * Q ≤ 107
* Valorile din șiruri sunt strict mai mici decât 26.
* Pentru 30% din tese N, M, Q ≤ 100.
* K ≤ 12. Pentru alte 20% din teste K ≤ 3.
== Exemplul 1 ==
; cripto1.in

6 3 4 2
info olte niaa este inva lcea
hlck njqa hlcj
1 2 3 5
1 2 3 4
; cripto1.out

2 2
== Explicație ==
Se permută cuvintele de pe a doua linie, după fiecare șir, din cele două.
Răspunsul este al doilea șir, 1 2 3 4, pentru că input-ul devine info olte infn.
Astfel, 2 dintre cuvinte se găsesc în primul limbaj.
Dacă am folosi primul șir, rezultatul ar fi 1: infp oltf info.
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def decrypt_text(language, encrypted_text, permutation):
decrypted_text = []
for word in encrypted_text:
decrypted_word = ""
for i in range(len(word)):
decrypted_word += language[word[i] - 1]
decrypted_text.append(decrypted_word)
decrypted_text_permuted = []
for word in decrypted_text:
permuted_word = ""
for i in range(len(word)):
permuted_word += word[permutation[i] - 1]
decrypted_text_permuted.append(permuted_word)
return decrypted_text_permuted

def similarity(language, decrypted_text):
count = 0
for word in decrypted_text:
if word in language:
count += 1
return count

def read_input(file_name):
with open(file_name, 'r') as file:
N, M, K, Q = map(int, file.readline().split())
language = file.readline().split()
encrypted_text = [file.readline().split()[0] for _ in range(M)]
permutations = [list(map(int, file.readline().split())) for _ in range(Q)]
return N, M, K, Q, language, encrypted_text, permutations

def write_output(file_name, result):
with open(file_name, 'w') as file:
file.write(str(result[0]) + ' ' + str(result[1]))

def find_best_decryption(N, M, K, Q, language, encrypted_text, permutations):
max_similarity = -1
best_permutation_index = -1
for i in range(Q):
decrypted_text = decrypt_text(language, encrypted_text, permutations[i])
current_similarity = similarity(language, decrypted_text)
if current_similarity > max_similarity:
max_similarity = current_similarity
best_permutation_index = i + 1
return best_permutation_index, max_similarity

def main():
N, M, K, Q, language, encrypted_text, permutations = read_input("cripto1.in")
result = find_best_decryption(N, M, K, Q, language, encrypted_text, permutations)
write_output("cripto1.out", result)

if __name__ == "__main__":
main()

</syntaxhighlight>

3399 - Semarun

2024-06-03T17:44:25Z

RebecaBud: /* Rezolvare */

== Enunt ==
Pentru că este un bun sportiv și poate alerga constant cu x metri pe secundă, Gigel și-a propus să câștige competiția semarun. Această competiție începe la momentul 0 și constă în parcurgerea unui traseu de n metri, ce conține k semafoare.
Pentru fiecare semafor se cunosc:
- distanța la care este poziționat față de punctul de start, exprimată în metri – d;
- numărul de secunde pentru care acesta indică culoarea roșu – r;
- numărul de secunde pentru care acesta indică culoarea verde – v.
La începutul competiției toate semafoarele indică culoarea roșu, apoi alternează între roșu și verde. La întâlnirea unui semafor, participanții trebuie să aștepte dacă acesta este roșu sau își schimbă culoarea din verde în roșu, și pot trece dacă acesta este verde sau își schimbă culoarea din roșu în verde. Este desemnat câștigător cel care parcurge distanța de la linia de start pană la final în cel mai scurt timp și fără a depăși s secunde de la începutul competiției.
Este important de știut faptul că înainte de începerea competiției, fiecare participant trebuie să-și aleagă momentul (exprimat în secunde trecute de la începerea competiției) la care va începe parcurgerea traseului astfel încât să ajungă la final într-un interval de timp cat mai scurt.
== Cerinţa ==
Deoarece Gigel știe că nu este important să ajungă primul la final, ci să parcurgă traseul într-un timp cat mai scurt, vă roagă să îl ajutați cu următoarea cerință: determinați momentele de timp pe care Gigel ar putea sa le aleagă pentru a începe parcurgerea traseului astfel încât să nu se oprească la niciun semafor și atunci când ajunge la final să nu fi trecut mai mult de s secunde de la începutul competiției (momentul 0).
== Date de intrare ==
Pe prima linie a fișierului de intrare semarun.in se află numerele naturale n, x și s. Pe a doua linie se află numărul natural k, iar pe următoarele k linii se specifică pentru fiecare semafor numerele naturale d, r și v.

== Date de ieșire ==
Pe prima linie a fișierului de ieșire semarun.out se va scrie numărul de soluții pentru cerința lui Gigel, iar pe a doua linie se vor scrie soluțiile separate printr-un spațiu, ordonate crescător.

Restricții și prec
== Restricţii şi precizări ==
* 1 ≤ d ≤ n ≤ 100.000
* 1 ≤ x ≤ 12
* 1 ≤ s ≤ 864.000
* 1 ≤ k ≤ 70.000
* 1 ≤ r, v ≤ 5
* Se garantează că pentru datele din fișierul de intrare există cel puțin o soluție.
* Toate soluțiile din fișierul de ieșire trebuie să fie numere naturale pozitive.
== Exemplul 1 ==
; semarun.in

400 10 60
3
30 2 2
60 3 3
90 4 4
; semarun.out

3
3 4 11
== Explicație ==
Momentele de timp pe care Gigel le poate alege astfel încât să respecte cerința sunt: 3, 4 sau 11 secunde de la începerea competiției.
Dacă Gigel începe parcurgerea traseului după 3 secunde de la start, acesta o să ajungă la cele trei semafoare în secundele 6, 9 și 12, fix când acestea își schimbă culoarea din roșu în verde. La final acesta o sa ajungă în secunda 43, încadrându-se în limita a 60 de secunde.
Pentru orice altă alegere față de cele trei menționate mai sus, Gigel ar întâlni cel puțin un semafor care ar indica culoarea roșu sau și-ar schimba culoarea din verde în roșu la întâlnirea acestuia, ori nu s-ar încadra în limita de timp.
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def possible_start_times(n, x, s, k, semaphores):
start_times = []
for i in range(k):
d, r, v = semaphores[i]
if r >= s or v >= s:
continue
red_circles = (d // (x + r)) * r
red_start = d // (x + r) * (x + r)
green_circles = (d // (x + r)) * v
green_start = (d // (x + r) + 1) * (x + r)
if red_circles + green_circles <= s:
start_times.append(red_start + 1)
start_times.append(green_start + 1)
return start_times

def read_input(file_name):
with open(file_name, 'r') as file:
n, x, s = map(int, file.readline().split())
k = int(file.readline())
semaphores = [list(map(int, file.readline().split())) for _ in range(k)]
return n, x, s, k, semaphores

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

def main():
n, x, s, k, semaphores = read_input("semarun.in")
result = possible_start_times(n, x, s, k, semaphores)
write_output("semarun.out", result)

if __name__ == "__main__":
main()

</syntaxhighlight>

3399 - Semarun

2024-06-03T17:43:27Z

RebecaBud: Pagină nouă: == Enunt == Pentru că este un bun sportiv și poate alerga constant cu x metri pe secundă, Gigel și-a propus să câștige competiția semarun. Această competiție începe la momentul 0 și constă în parcurgerea unui traseu de n metri, ce conține k semafoare. Pentru fiecare semafor se cunosc: - distanța la care este poziționat față de punctul de start, exprimată în metri – d; - numărul de secunde pentru care acesta indică culoarea roșu – r; - numărul de s...

3679 - Consolidare

2024-06-03T17:40:52Z

RebecaBud: Pagină nouă: == Cerinţa == După consolidarea structurii de rezistență, a venit vremea refacerii zidului cetății. Acesta avea lungimea de L unități și înălțimea de H unități. El deteriorându-se în timp, acum nu mai este dreptunghiular ci, pe fiecare din cele L unități de lungime mai există Vi unități, de material, așezate una peste alta și sprijinite pe fundație, deci până la înălțimea Vi unități. Se dorește, evident, acoperirea zonelor rămase așa încâ...

== Cerinţa ==
După consolidarea structurii de rezistență, a venit vremea refacerii zidului cetății. Acesta avea lungimea de L unități și înălțimea de H unități. El deteriorându-se în timp, acum nu mai este dreptunghiular ci, pe fiecare din cele L unități de lungime mai există Vi
unități, de material, așezate una peste alta și sprijinite pe fundație, deci până la înălțimea Vi
unități. Se dorește, evident, acoperirea zonelor rămase așa încât zidul să ajungă dreptunghiular, cu înălțimea de H unități pe fiecare din cele L unități de lungime.

Se dispune de bucăți de material, dreptunghiulare, cu o dimensiune de o unitate. Așadar putem spune că bucățile sunt de dimensiuni 1 X B(1 ≤ B ≤ L) și pentru fiecare valoare B dispunem de oricâte bucăți(să le numim de tipul B). Pentru ca zidul să fie stabil, bucățile trebuie să fie dispuse orizontal, adică una de dimensiune 1 X B va ocupa B unități pe lungime și o unitate pe înălțime. Se mai cunoaște că bucățile de același tip B au aceeași culoare și diferită de culoarea bucăților de alte tipuri. Pentru a fi zidul frumos, trebuie ca la aceeași înălțime față de fundație, să se folosească bucăți de material de aceeași culoare. Determinați numărul minim de bucăți necesare refacerii zidului.
== Date de intrare ==
Fișierul de intrare consolidare.in conține pe prima linie două numere naturale L și H, separate prin spațiu, reprezentând, conform descrierii de mai sus, lungimea respectiv înălțimea pe care trebuie să o aibă zidul refăcut. Pe linia a doua se află L numere naturale nenule, separate prin câte un spațiu indicând, în ordine, înălțimea în unități a părții existente, pentru fiecare unitate de lungime.
== Date de ieșire ==
Fișierul de ieșire consolidare.out va conține pe primul rând o valoare naturală ce reprezintă numărul minim de bucăți folosite pentru a construi zidul conform restricțiilor.
== Restricţii şi precizări ==
* 1 ≤ L ≤ 100.000
* 1 ≤ H ≤ 10
* 0≤Vi≤H
* Nu este permis ca o bucată de material să iasă în afara celor L unități de lungime.
== Exemplul 1 ==
; consolidare.in

10 4
0 0 1 3 0 1 1 2 2 2
; consolidare.out

9

 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def minimum_pieces_needed(L, H, heights):
pieces_needed = 0
current_height = [0] * (H + 1)

for i in range(L):
for j in range(heights[i], H):
if current_height[j] == 0:
pieces_needed += 1
current_height[j] = 1
current_height[heights[i]] += 1

return pieces_needed

def read_input(file_name):
with open(file_name, 'r') as file:
L, H = map(int, file.readline().split())
heights = list(map(int, file.readline().split()))
return L, H, heights

def write_output(file_name, result):
with open(file_name, 'w') as file:
file.write(str(result))

def main():
L, H, heights = read_input("consolidare.in")
result = minimum_pieces_needed(L, H, heights)
write_output("consolidare.out", result)

if __name__ == "__main__":
main()

</syntaxhighlight>

3832 - A - Manhattan de Buget

2024-06-03T17:37:59Z

RebecaBud: Pagină nouă: == Cerinţa == Dându-se N puncte laticiale, care este distanța Manhattan de buget minimă dintre două puncte de coordonate a b respectiv x y cu proprietatea că a-y >= x-b? == Date de intrare == Fișierul de intrare mman.in conține pe prima linie numărul N, iar pe următoarele n linii se află câte două numere, pe linia i se află coordonatele x respectiv y ale punctului i. == Date de ieșire == Fișierul de ieșire mman.out va conține pe prima linie numărul M reprez...

== Cerinţa ==
Dându-se N puncte laticiale, care este distanța Manhattan de buget minimă dintre două puncte de coordonate a b respectiv x y cu proprietatea că a-y >= x-b?
== Date de intrare ==
Fișierul de intrare mman.in conține pe prima linie numărul N, iar pe următoarele n linii se află câte două numere, pe linia i se află coordonatele x respectiv y ale punctului i.
== Date de ieșire ==
Fișierul de ieșire mman.out va conține pe prima linie numărul M reprezentând valoarea cerută.
== Restricţii şi precizări ==
* 2 ≤ n ≤ 100.000
* coordonatele tuturor punctelor aparțin intervalului [-1.000.000.000, 1.000.000.000].
* Distanța Manhattan de buget dintre punctul cu coordonate a b si punctul de coordonate x y este a-x+b-y.
== Exemplul 1 ==
; mman.in

3
1 1
2 3
-1 -1
; mman.out

3
== Explicație ==
Distanța minimă dintre două puncte se obține din punctele cu coordonate 1 1 și 2 3.
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def minimum_manhattan_distance(n, points):
min_distance = float('inf')
points.sort(key=lambda point: point[0] - point[1])

for i in range(1, n):
distance = points[i][0] - points[i-1][0] + points[i][1] - points[i-1][1]
min_distance = min(min_distance, distance)

return min_distance

def read_input(file_name):
with open(file_name, 'r') as file:
n = int(file.readline().strip())
points = [tuple(map(int, line.strip().split())) for _ in range(n)]
return n, points

def write_output(file_name, result):
with open(file_name, 'w') as file:
file.write(str(result))

def main():
n, points = read_input("mman.in")
result = minimum_manhattan_distance(n, points)
write_output("mman.out", result)

if __name__ == "__main__":
main()

</syntaxhighlight>

3820 - Mordor Trip

2024-06-03T17:36:16Z

RebecaBud: Pagină nouă: == Cerinţa == Dr. Le Quack , fiind un mare fan al Lord Of The Rings , decide să plece în Mordor , locul unde a fost făurit inelul atotputernic . Când acesta ajunge la turnul lui Sauron , observă că intrarea are un cifru . Cifrul este un șir de numere întregi. Dr. Le Quack poate aplică următorul algoritm șirului : for(int i=1;i<n;i++){ if(a[i]<=a[i+1]){ swap(a[i], a[i+1]); } } Dr. Le Quack poate aplica acest tip de operatie de un număr n...

== Cerinţa ==
Dr. Le Quack , fiind un mare fan al Lord Of The Rings , decide să plece în Mordor , locul unde a fost făurit inelul atotputernic . Când acesta ajunge la turnul lui Sauron , observă că intrarea are un cifru . Cifrul este un șir de numere întregi. Dr. Le Quack poate aplică următorul algoritm șirului :

for(int i=1;i<n;i++){
if(a[i]<=a[i+1]){
swap(a[i], a[i+1]);
}
}
Dr. Le Quack poate aplica acest tip de operatie de un număr nelimitat de ori ( posibil 0 ). Intrarea se va deschide atunci când șirul va fi unul descrescator. Un șir este descrescător dacă pentru fiecare i din intervalul [1 , n-1] se respectă condiția a[i] ≥ a[i+1]. Dr. Le Quack fiind lacom vrea să stie care este numărul minim operații pentru a deschide intrarea. Pentru că acesta a chiulit de la orele de informatică uitat cum se rezolvă problemele de natură algoritmica , vă roaga sa îl ajutați în schimbul a 100 de puncte și asigurare medicală la cabinetul său.
== Date de intrare ==
Fișierul de intrare mordortrip.in conține pe prima linie numărul n, iar pe a doua linie n numere întregi separate prin spații.
== Date de ieșire ==
Fișierul de ieșire mordortrip.out conține pe prima linie un număr ans reprezentând numărul minim de operații ale
algoritmului specificat mai sus pentru a sorta vectorul dat la input într-unul descrescător.
== Restricţii şi precizări ==
* Numerele sunt întregi , din intervalul [ -1.000.000.000 , 1.000.000.000 ] , NU neapărat distincte.
* Se garantează că avem mereu soluție dintr-un număr finit de operații ale algoritmului descris.
* Pentru teste în valoare de 20 de puncte , N ≤ 5.000.
* Pentru restul testelor , N ≤ 1.000.000.
== Exemplul 1 ==
; mordortrip.in

5
5 1 3 2 4
; mordortrip.out

3
; mordortrip.in

4
3 1 2 2
; mordortrip.out

1
== Explicație ==
În primul exemplu , sunt necesare doar 3 aplicări ale algoritmului : 1 – 5 3 2 4 1 ; 2 – 5 3 4 2 1 ; 3 – 5 4 3 2 1
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def minimum_operations(n, arr):
operations = 0

for i in range(1, n):
if arr[i] <= arr[i-1]:
operations += arr[i-1] - arr[i] + 1
arr[i] = arr[i-1] + 1

return operations

def read_input(file_name):
with open(file_name, 'r') as file:
n = int(file.readline().strip())
arr = list(map(int, file.readline().strip().split()))
return n, arr

def write_output(file_name, result):
with open(file_name, 'w') as file:
file.write(str(result))

def main():
n, arr = read_input("mordortrip.in")
result = minimum_operations(n, arr)
write_output("mordortrip.out", result)

if __name__ == "__main__":
main()

</syntaxhighlight>

3823 - A - Flipped Cards

2024-06-03T17:33:57Z

RebecaBud: Pagină nouă: == Cerinţa == După ce Le Quack și-a pierdut toți banii dați de mama lui să cumpere pâine la Blackjack, acesta a decis să își creeze propriul joc de cărți unde își poate bate prietenii și să câștige banii înapoi. Jocul se joacă cu un pachet de N cărți. Pachetul de cărți este reprezentat că un șir binar cum va fi descris în cele ce urmează.Cărțile pot fi așezate pe față sau pe spate fără a conta culoarea sau valoarea cărții, pentru simplitat...

== Cerinţa ==
După ce Le Quack și-a pierdut toți banii dați de mama lui să cumpere pâine la Blackjack, acesta a decis să își creeze propriul joc de cărți unde își poate bate prietenii și să câștige banii înapoi. Jocul se joacă cu un pachet de N cărți. Pachetul de cărți este reprezentat că un șir binar cum va fi descris în cele ce urmează.Cărțile pot fi așezate pe față sau pe spate fără a conta culoarea sau valoarea cărții, pentru simplitate codificăm o care întoarsă prin cifra 0 și o carte pe față prin cifra 1 . Fiecare jucător poate face un număr nelimitat de operații de următorul tip: se alege un index i și se întorc toate cărțile din secvență de cărți i...n, adică o carte de valoare 0 se transformă în carte de valoare 1 și invers. Acum este rândul lui Le Quack, el va prezintă configurația curentă a cărților și voi trebuie să îl ajutați cu 2 cerințe, el va poate răsplăti cu un posibil loc I la concurs.

Cerinta 1: Stiind configuratia cartilor sunteti rugati sa aflati lungimea maxima a unei secvente de carti, astfel incat costul de a transforma aceasta secventa intr-o secventa de carti care contin doar valori de 1 este maxim K.

Certina 2: Stiind configuratia cartilor sunteti intrebati care este numarul secventelor de carti pentru care numarul minim de operatii pentru a devni o secventa care contine numai valori de 1 este fix K.

== Date de intrare ==
Pe prima linie sunt scrise valorile C, N si K, reprezentand numarul cerintei, numarul de carti respectiv valoarea K descrisa in enunt. Pe a doua linie sunt N valori binare reprezentand sirul de carti. Numerele se citesc din fisierul flipc.in.
== Date de ieșire ==
Se va tiparii un singur numar, reprezentand raspunul la cerinta aferenta. Numerele se tiparesc in fisieru flipc.out.
== Restricţii şi precizări ==
* Cerinta I:
Pentru 40/40 p : N <= 1.000.000 , K <= N
Pentru 30/40 p : N <= 200.000 , K <= N
Pentru 10/40 p : N <= 10.000 , K <= min(N , 100)
* Cerinta II:
Pentru 60/60 p : N <= 1.000.000 , K <= N
Pentru 50/60 p : N <= 200.000 , K <= N
Pentru 15/60 p : N <= 10.000 , K <= min(N , 100)
O carte NU se poate roti de 2 ori in aceasi mutare !
== Exemplul 1 ==
; flipc.in

1 5 2
10001
; flipc.out

5
; flipc.in

2 13 4
1010011111101
; flipc.out

15
= Explicație ==
Pentru primul exemplu : putem transforma tot stringul in valori de 1 in 2 operatii, prima operatie la
pozitia 2 si a doua la pozitia 5.
Pentru al doilea exemplu : niste exemple de secvente care contin doar valori de 1 si sunt formate prin
4 operatii ar avea capetele: {1,6}, {2,6}, {1,9} .....
 

== Exemplul 2 ==
;
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def max_length_of_sequence(N, K, cards):
max_len = 0
count_zeroes = 0
left, right = 0, 0

while right < N:
if cards[right] == '0':
count_zeroes += 1

while count_zeroes > K:
if cards[left] == '0':
count_zeroes -= 1
left += 1

max_len = max(max_len, right - left + 1)
right += 1

return max_len

def count_sequences(N, K, cards):
count = 0
count_zeroes = 0
left, right = 0, 0

while right < N:
if cards[right] == '0':
count_zeroes += 1

while count_zeroes > K:
if cards[left] == '0':
count_zeroes -= 1
left += 1

if count_zeroes == K:
count += N - right

right += 1

return count

def solve_problem(C, N, K, cards):
if C == 1:
return max_length_of_sequence(N, K, cards)
elif C == 2:
return count_sequences(N, K, cards)

def read_input(file_name):
with open(file_name, 'r') as file:
line = file.readline().strip().split()
C, N, K = map(int, line)
cards = file.readline().strip()
return C, N, K, cards

def write_output(file_name, result):
with open(file_name, 'w') as file:
file.write(str(result))

def main():
C, N, K, cards = read_input("flipc.in")
result = solve_problem(C, N, K, cards)
write_output("flipc.out", result)

if __name__ == "__main__":
main()

</syntaxhighlight>

4124 - Colibri

2024-06-03T17:31:11Z

RebecaBud: Pagină nouă: == Enunt == Se dau N triplete de numere naturale (ai, bi, ci), unde ai ≠ 0 și 1 ≤ i ≤ N, fiecare reprezentând câte un număr rațional qi egal cu: (−1)aibici == Cerinţa == Găsiți un subșir nevid al șirului q1, q2, …, qN al cărui produs al valorilor să fie maxim posibil. == Date de intrare == Fișierul de intrare colibri.in conține pe prima linie numărul N. Următoarele N linii descriu cele N triplete: pe linia i se află numerele naturale ai, bi, ci, sep...

== Enunt ==
Se dau N triplete de numere naturale (ai, bi, ci), unde ai ≠ 0 și 1 ≤ i ≤ N, fiecare reprezentând câte un număr rațional qi egal cu: (−1)aibici
== Cerinţa ==
Găsiți un subșir nevid al șirului q1, q2, …, qN al cărui produs al valorilor să fie maxim posibil.
== Date de intrare ==
Fișierul de intrare colibri.in conține pe prima linie numărul N. Următoarele N linii descriu cele N triplete: pe linia i se află numerele naturale ai, bi, ci, separate prin spații.
== Date de ieșire ==
Pe prima linie a fișierului de ieșire colibri.out se află un șir de N cifre. Cifra i, unde 1 ≤ i ≤ N, este 1 dacă și numai dacă qi este selectat în subșirul soluție, altfel este 0. Cifrele șirului nu se vor separa prin spații.
== Restricţii şi precizări ==
* 1 ≤ N ≤ 50.000;
* 0 ≤ ai, bi ≤ 1.000.000, oricare ar fi 1 ≤ i ≤ N;
* 1 ≤ ci ≤ 1.000.000, oricare ar fi 1 ≤ i ≤ N;
* Dacă există mai multe soluții, atunci se acceptă orice soluție corectă;
* Spunem că un șir x este subșir al unui șir y dacă și numai dacă x se poate obține din y eliminând o parte din * elementele lui y (inclusiv nici unul) fără a schimba ordinea relativă a elementelor rămase.
* Pentru 30 de puncte, N ≤ 19 și ai, ci, ci ≤ 9
* Pentru 20 de puncte, N ≤ 19
* Pentru 20 de puncte, ai, bi, ci ≤ 9
* Pentru 30 de puncte, fără restricții suplimentare
== Exemplul 1 ==
; colibri.in

5
0 0 1
2 4 2
4 7 7
1 2 3
0 3 2
; colibri.out

01001
== Explicație ==
În exemplu N=5, q1=01, q2=42, q3=77, q4=−23 și q5=32.

Produsul maxim posibil este egal cu 3. Acesta se poate obține luând fie subșirul constând din numerele q2 și q5, fie luând subșirul format din numerele q2, q3 și q5. Cu alte cuvinte, și răspunsul 01101 este corect.
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def max_product_subarray(N, triples):
max_product = float('-inf')
max_index = -1

for i in range(N):
ai, bi, ci = triples[i]
current_product = (-1) ** (ai * bi) * ci
if current_product > max_product:
max_product = current_product
max_index = i

result = ['0'] * N
result[max_index] = '1'
return ''.join(result)

def main():
N = int(input())
triples = [list(map(int, input().split())) for _ in range(N)]

result = max_product_subarray(N, triples)
print(result)

if __name__ == "__main__":
main()

</syntaxhighlight>

4115 - Investitie

2024-06-03T17:27:52Z

RebecaBud: Pagină nouă: == Enunt == După o lungă activitate în domeniul instalaţiilor sanitare, Dorel s-a hotărât să investească averea acumulată în acţiuni ale mai multor companii. Astfel, el dispune de o listă cu N companii la care vrea să cumpere acţiuni, în M zile consecutive. În prima zi, suma de bani investită în compania i este s[1][i] = a[i], pentru orice i=1..N, unde valorile a[i] sunt date. Numerele a[1], a[2], …, a[N] reprezintă o permutare a numerelor 1,2,...,N}....

== Enunt ==
După o lungă activitate în domeniul instalaţiilor sanitare, Dorel s-a hotărât să investească averea acumulată în acţiuni ale mai multor companii. Astfel, el dispune de o listă cu N companii la care vrea să cumpere acţiuni, în M zile consecutive.

În prima zi, suma de bani investită în compania i este s[1][i] = a[i], pentru orice i=1..N, unde valorile a[i] sunt date.

Numerele a[1], a[2], …, a[N] reprezintă o permutare a numerelor 1,2,...,N}.

În ziua a j-a el va investi în compania i o sumă de bani egală cu s[j][i] = s[j-1][a[i]], pentru orice zi j =2..M şi orice companie i = 1..N.
== Cerinţa ==
După finalizarea planului de investiţii, Dorel vrea să realizeze Q statistici referitoare la sumele investite. Fiind date Q seturi de valori zi, zf, cl, cr, el doreşte să afle ce sumă a investit în perioada cuprinsă între zilele zi și zf (inclusiv acestea), la companiile cu numere de ordine cuprinse între cl și cr (inclusiv acestea).
== Date de intrare ==
Pe prima linie a fişierului de intrare investitie.in se află numerele N şi M, separate prin spaţiu. Pe a doua linie se află valorile a[1], a[2], ..., a[N], separate prin spaţiu. Pe a treia linie se află valoarea lui Q. Pe următoarele Q linii se află câte patru valori, zi, zf, cl, cr, separate prin spaţiu.
== Date de ieșire ==
În fişierul de ieşire investitie.out se vor afişa, pe linii diferite, sumele investite corespunzătoare fiecăreia din cele Q statistici din fişierul de intrare.
== Restricţii şi precizări ==
* 1 ≤ N, Q ≤ 100.000
* 1 ≤ M ≤ 1.000.000.000
* 1 ≤ zi ≤ zf ≤ M
* 1 ≤ cl ≤ cr ≤ N
* 0 ≤ cr -cl ≤ 100
* Pentru 10 puncte, M = 1
* Pentru 20 de puncte, 1 ≤ N, M ≤ 100, 1 ≤ Q ≤ 1000
* Pentru 12 puncte, 101 ≤ N , M ≤ 3000
* Pentru 24 de puncte, 1 ≤ N ≤ 50
* Pentru 34 de puncte fără alte restricţii
== Exemplul 1 ==
; investitie.in

8 3
3 1 7 2 6 4 5 8
5
1 1 3 7
1 2 1 4
1 3 2 8
2 3 3 6
3 3 3 3
; investitie.out

24
29
93
24
6
== Explicație ==
Sumele investite în cele trei zile, în acţiuni ale celor opt companii, vor fi:

3 & 1 & 7 & 2 & 6 & 4 & 5 & 8
7 & 3 & 5 & 1 & 4 & 2 & 6 & 8
5 & 7 & 6 & 3 & 2 & 1 & 4 & 8

Prima statistică cere suma investită în prima zi în companiile cu numere de ordine de la 3 la 7. Suma este 7+2+6+4+5=24.
A doua statistică cere suma investită în primele două zile în companiile cu numerele de ordine de la 12 la 4. Suma este (3+1+7+2)+(7+3+5+1)=29.
Similar se calculează celelalte statistici.
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def investition(N, M, a, Q, queries):
investments = [[0] * (N + 1) for _ in range(M + 1)]
for i in range(1, N + 1):
investments[1][i] = a[i - 1]
for j in range(2, M + 1):
for i in range(1, N + 1):
investments[j][i] = investments[j - 1][a[i - 1]]

cumulative_investments = [[0] * (N + 1) for _ in range(M + 1)]
for j in range(1, M + 1):
for i in range(1, N + 1):
cumulative_investments[j][i] = cumulative_investments[j - 1][i] + investments[j][i]

results = []
for query in queries:
zi, zf, cl, cr = query
total_investment = 0
for i in range(cl, cr + 1):
total_investment += cumulative_investments[zf][i] - cumulative_investments[zi - 1][i]
results.append(total_investment)
return results

def main():
N, M = map(int, input().split())
a = list(map(int, input().split()))
Q = int(input())
queries = [list(map(int, input().split())) for _ in range(Q)]

results = investition(N, M, a, Q, queries)
for result in results:
print(result)

if __name__ == "__main__":
main()

</syntaxhighlight>

3889 - Cnt Subsir Max

2024-06-03T17:24:43Z

RebecaBud: Pagină nouă: == Cerinţa == Felicia este interesată de subșirul maxim lexicografic al unui șir de caractere. Rețineți că un șir a este considerat mai mic în ordine lexicografică decât un șir b dacă a este prefix al lui b, sau dacă există o poziție i pentru care avem a[1] = b[1], ..., a[i − 1] = b[i − 1], și a[i] < b[i]. Astfel, subșirul maxim lexicografic al unui șir de caractere este cel mai mare subșir, în ordinea lexicografică, al unui șir de caractere (de exe...

== Cerinţa ==
Felicia este interesată de subșirul maxim lexicografic al unui șir de caractere. Rețineți că un șir a este considerat mai mic în ordine lexicografică decât un șir b dacă a este prefix al lui b, sau dacă există o poziție i pentru care avem a[1] = b[1], ..., a[i − 1] = b[i − 1], și a[i] < b[i]. Astfel, subșirul maxim lexicografic al unui șir de caractere este cel mai mare subșir, în ordinea lexicografică, al unui șir de caractere (de exemplu zzxx pentru azbxazbxaax). Pentru un șir s de caractere vom nota cu m(s) subșirul maxim lexicografic al lui s, și cu v(s) = |m(s)| lungimea acestui subșir. Felicia vă dă un șir s format din caractere mici ale alfabetului englez. Considerați toate subsecvențele continue s' ale lui s. Felicia vrea să calculați suma valorilor v(s') pentru toate subsecvențele posibile s' amintite anterior.
== Date de intrare ==
Pe singura linie citită de la tastatură se va găsi șirul s.
== Date de ieșire ==
Să se afișeze suma cerută, modulo 109+7.
== Restricţii şi precizări ==
* 1≤N≤106
== Subtask ==
* N≤15
== Subtask ==
* N≤200
== Subtask ==
* N≤2000
== Subtask ==
* N≤5⋅104
== Subtask ==
* Fară restricții suplimentare.
== Exemplul 1 ==
; Intrare

cab
; Ieșire

8
== Explicație ==
Pentru primul exemplu, observăm că m(c) = c, m(a) = a, m(b) = b, m(ca) = ca, m(ab) = b, m(cab) = cb.
Astfel, răspunsul este 1 + 1 + 1 + 2 + 1 + 2 = 8.
 

== Exemplu 2 ==
; Intrare

felicia
; Ieșire

59

== Rezolvare ==
<syntaxhighlight lang="python" line>
MOD = 10**9 + 7

def max_lexicographic(s):
max_substring = s[0]
for i in range(1, len(s)):
if s[i] >= max_substring[0]:
max_substring = s[i] + max_substring
else:
max_substring += s[i]
return max_substring

def sum_of_max_substrings(s):
total_sum = 0
for i in range(len(s)):
max_substring = max_lexicographic(s[i:])
total_sum += len(max_substring)
total_sum %= MOD
return total_sum

def main():
s = input().strip()
result = sum_of_max_substrings(s)
print(result)

if __name__ == "__main__":
main()

</syntaxhighlight>

3229 - The Grade

2024-06-03T17:19:30Z

RebecaBud: /* Rezolvare */

== Enunt ==
Aleku Turcul este la ora de matematica. În timp ce el încearcă să-și dea seama dacă 1+1=2, profesorul scrie pe tablă o problemă ceva mai complicată. Se dau Q queryuri și o listă S cu P elemente egale cu 0. Notăm cu A un șir, care inițial este vid. Queryurile pot fi de forma:
- 0 x (inserează valoarea x în A)
- 1 x (șterge valoarea x din A; se garantează că există cel puțin o valoare de x în A)
Se garantează că A nu va fi niciodată vid după vreun query. După fiecare query profesorul îi pune lui Aleku următoarea întrebare: oare pot așeza în lista S toate numerele din A (nu neapărat în ordinea în care se află în A) astfel încât:

elementele din A se vor așeza în S pe poziții distincte, restul pozițiilor din S fiind ocupate de elemente cu valoarea 0
fie S[i] un element nenul din S și S[j] cel mai apropiat element nenul care se află în stânga lui S[i] în S. Atunci următoarea condiție trebuie respectată: i - j ≥ S[i]
fie f poziția celui mai din stânga element nenul din S. Atunci f ≥ S[f].
Dacă răspunsul la întrebarea profesorului este da, atunci să se spună și câte configurații diferite se pot obține. Deoarece răspunsul la întrebare poate fi foarte mare, acesta se va afișa modulo 1.000.000.007. Dacă răspunsul este nu, se va afișa -1.
== Cerinţa ==
Ajutați-l pe Aleku sa răspundă corect la întrebările profesorului pentru ca sa obțină nota 10. Media lui depinde de aceasta!
== Date dePrima linie se vor citi de la tastatură două numere naturale Q și P. Pe următoarele Q linii se află Q query-uri sub forma descrisă în enunț.
== Date de ieșire ==
Se vor afișa pe ecran răspunsurile la cele Q query-uri, câte unul pe linie.
== Restricţii şi precizări ==
* 1 ≤ Q, P ≤ 100.000
* Răspunsurile se vor afișa modulo 1.000.000.007.
* Numerele ce vor fi adăugate/șterse la un query sunt mai mici sau egale decât 1.000.000.
* ATENȚIE! În cazul în care răspunsul unui query este NU, se va afișa -1.
* Aleku nu este turc. Turcul este numele lui. El este de fapt căpitan.
== Exemplul 1 ==
; Intrare

9 8
0 3
0 3
0 2
1 2
0 1
0 1
0 1
1 3
1 1
; Ieșire

6
6
3
6
12
6
-1
60
60

 

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

def get_configurations(A):
config_count = 1
last_nonzero_pos = -1
for i in range(len(A)):
if A[i] != 0:
if i - last_nonzero_pos < A[i]:
return 0
last_nonzero_pos = i
if last_nonzero_pos + 1 < A[0]:
return 0
if last_nonzero_pos == A[0] - 1:
config_count *= 2
config_count %= MOD
return config_count

def solve(Q, P, queries):
A = []
configurations = []
result = []

for query in queries:
if query[0] == 0:
A.append(query[1])
else:
A.remove(query[1])
configurations.append(get_configurations(A))

for config in configurations:
if config == 0:
result.append(-1)
else:
result.append(config)

return result

def main():
Q, P = map(int, input().split())
queries = [list(map(int, input().split())) for _ in range(Q)]

result = solve(Q, P, queries)

for res in result:
print(res)

if __name__ == "__main__":
main()

</syntaxhighlight>

3229 - The Grade

2024-06-03T17:19:15Z

RebecaBud: Pagină nouă: == Enunt == Aleku Turcul este la ora de matematica. În timp ce el încearcă să-și dea seama dacă 1+1=2, profesorul scrie pe tablă o problemă ceva mai complicată. Se dau Q queryuri și o listă S cu P elemente egale cu 0. Notăm cu A un șir, care inițial este vid. Queryurile pot fi de forma: - 0 x (inserează valoarea x în A) - 1 x (șterge valoarea x din A; se garantează că există cel puțin o valoare de x în A) Se garantează că A nu va fi niciodată vid dup...

2654 - Sort All

2024-06-03T17:16:37Z

RebecaBud: Pagină nouă: == Enunt == Pentru un șir de numere A se definește următoarea funcție de cost: f(A)=1⋅v1+2⋅v2+…+k⋅vk , unde [v1,v2,…,vk] sunt valorile distincte ale lui A , ordonate crescător. == Cerinţa == Fiind dat un șir de N numere naturale A, să se calculeze suma aplicării funcției f pe toate subsecvențele lui A (i.e. suma după (1 ≤ i ≤ j ≤ N) din f(A[i...j]), unde A[i…j] este subsecvența de la i la j). == Date de intrare == Fișierul sortall.in conțin...

== Enunt ==
Pentru un șir de numere A
se definește următoarea funcție de cost: f(A)=1⋅v1+2⋅v2+…+k⋅vk
, unde [v1,v2,…,vk]
sunt valorile distincte ale lui A
, ordonate crescător.
== Cerinţa ==
Fiind dat un șir de N numere naturale A, să se calculeze suma aplicării funcției f pe toate subsecvențele lui A (i.e. suma după (1 ≤ i ≤ j ≤ N) din f(A[i...j]), unde A[i…j] este subsecvența de la i la j).
== Date de intrare ==
Fișierul sortall.in conține pe prima linie numărul natural N. Linia a doua conține N numere naturale separate prin spațiu, reprezentând elementele șirului A.
== Date de ieșire ==
Fișierul sortall.out va conține răspunsul modulo 1 000 000 007.
== Restricţii şi precizări ==
* 1 ≤ N ≤ 50 000
* 1 ≤ Vi ≤ N
* Pentru 10 puncte 1 ≤ N ≤ 100
* Pentru alte 15 puncte 1 ≤ N ≤ 1000
* Pentru alte 15 puncte 1 ≤ N ≤ 5000
* Pentru alte 20 de puncte se garanteză că valorile din șir sunt distincte
== Exemplul 1 ==
; sortall.in

3
1 3 2
; sortall.out

35

 

== Exemplul 2 ==
; sortall.in

8
4 3 4 4 7 1 2 1
; sortall.out

864
 

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

def solve(N, A):
freq = {}
total_sum = 0

for i in range(N):
curr_sum = 0

for num in freq:
if num <= A[i]:
curr_sum += (i - freq[num] + 1) * num * (freq[num] - freq.get(num - 1, 0))
curr_sum %= MOD

total_sum += curr_sum
total_sum %= MOD

freq[A[i]] = i + 1

return total_sum

def main():
with open("sortall.in", "r") as fin:
N = int(fin.readline())
A = list(map(int, fin.readline().split()))

result = solve(N, A)

with open("sortall.out", "w") as fout:
fout.write(str(result) + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

4026 - Order

2024-06-03T17:14:22Z

RebecaBud: Pagină nouă: == Enunt == Se consideră toate şirurile finite de numere naturale nenule ordonate astfel: [1]; [1,1]; [2]; [1,1,1]; [1,2]; [2,1]; [3]; [1,1,1,1]; [1,1,2]; [1,2,1]; [1,3]; ... Ordonarea se face după următoarea regulă: dacă avem două şiruri cu sumele termenilor diferite, atunci şirul cu suma termenilor mai mică se găseşte pe o poziţie mai mică. Dacă avem două şiruri cu sumele termenilor egale atunci se compară termen cu termen şirurile până când se găse...

== Enunt ==
Se consideră toate şirurile finite de numere naturale nenule ordonate astfel:
[1]; [1,1]; [2]; [1,1,1]; [1,2]; [2,1]; [3]; [1,1,1,1]; [1,1,2]; [1,2,1]; [1,3]; ...
Ordonarea se face după următoarea regulă: dacă avem două şiruri cu sumele termenilor diferite, atunci şirul cu suma termenilor mai mică se găseşte pe o poziţie mai mică.
Dacă avem două şiruri cu sumele termenilor egale atunci se compară termen cu termen şirurile până când se găseşte un termen diferit.
Şirul care are termenul mai mic se găseşte pe poziţie mai mică. Cu alte cuvinte, primul criteriu de ordonare este suma termenilor, iar în caz de egalitate, al doilea criteriu de sortare este ordinea lexicografică.
Oricărui şir i se asociază o poziţie (număr natural nenul) şi invers, oricărei poziţii i se asociază un şir.

De exemplu:

* Şirului [1,1,2] i se asociază poziţia 9.
* Poziţiei 14 i se asociază şirul [3,1].
== Cerinţa ==
Să se răspundă la un număr de interogări de tipul:
1. Cunoscând un şir de numere naturale nenule să se determine poziţia asociată şirului.
2. Cunoscând un număr natural reprezentând o poziţie asociată unui şir să se determine şirul corespunzător.
== Date de intrare ==
Fişierul de intrare order3.in conţine pe prima linie un număr natural Q reprezentând numărul de interogări.
Pe următoarele Q linii vor fi descrise interogările.
Dacă interogarea este de tip 1 linia va conţine numărul 1, apoi un număr natural N reprezentând numărul de termeni ai şirului urmat de N numere naturale separate prin cűte un spaţiu reprezentând termenii şirului.
Dacă interogarea este de tip 2 linia va conţine numărul 2 urmat de un număr natural nenul P reprezentând poziţia şirului solicitat.
== Date de ieșire ==
Fişierul de ieşire order3.out va conţine Q linii. Pe fiecare linie este descris răspunsul la interogarea corespunzătoare din fişierul de intrare.
Dacă interogarea este de tip 1, pe linia corespunzătoare se va afişa un singur număr P reprezentând poziţia şirului descris în interogare.
Dacă interogarea este de tip 2, linia corespunzătoare va conţine un număr natural N@ reprezentând numărul de termeni pentru şirul solicitat, urmat de N numere naturale nenule reprezentând termenii şirului. Numerele de pe aceste linii trebuie sa fie separate prin câte un spaţiu.
== Restricţii şi precizări ==
* 1 ≤ P ≤ 1015 (mai precis se asigură ca pentru ambele tipuri de interogări poziţia asociată şirului considerat nu depăşeşte 1015).
* 1 ≤ Q ≤ 105.
* Pentru 40 de puncte testele vor conţine doar interogări de tip 1.
* Pentru 40 de puncte testele vor conţine doar interogări de tip 2.
* Pentru 20 de puncte testele vor conţine interogări de ambele tipuri.
== Exemplul 1 ==
; order.in

2
1 3 1 1 2
2 14
; order.out

9
2 3 1
== Explicație ==
Fişierul de intrare conţine două interogări. Prima este de tip 1 şi cere determinarea poziţiei şirului [1,1,2] care are lungimea 3. Acest şir este pe poziţia a 9-a conform ordinii descrise în enunţ. A doua interogare cere determinarea şirului aflat pe poziţia 14. Acest şir este şirul [3,1] de lungime 2.
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def fibonacci(n):
fib = [1, 1]
while len(fib) < n:
fib.append(fib[-1] + fib[-2])
return fib

def find_position(sequence):
n = len(sequence)
fib = fibonacci(n + 2)
prefix_sum = [0] * (n + 1)
for i in range(1, n + 1):
prefix_sum[i] = prefix_sum[i - 1] + fib[i]
position = prefix_sum[n]
for i in range(n):
position += sequence[i] - 1
for j in range(1, sequence[i]):
position += fib[n - i - 1]
return position

def find_sequence(position):
fib = fibonacci(100)
n = len(fib)
sequence = []
for i in range(n - 1, -1, -1):
if position > fib[i]:
sequence.append(i + 1)
position -= fib[i]
return sequence

def main():
with open("order3.in", "r") as fin:
Q = int(fin.readline())
queries = [list(map(int, line.split())) for line in fin.readlines()]

with open("order3.out", "w") as fout:
for query in queries:
if query[0] == 1:
sequence = query[2:]
position = find_position(sequence)
fout.write(str(position) + "\n")
elif query[0] == 2:
position = query[1]
sequence = find_sequence(position)
fout.write(f"{len(sequence)} {' '.join(map(str, sequence))}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

2053 - Fibo Div

2024-06-03T17:12:25Z

RebecaBud: Pagină nouă: == Enunt == Fie șirul Fibonacci, dat prin F[1] = 1, F[2] = 1 și relația de recurență F[k] = F[k-1] + F[k-2], k ≥ 3 . Se consideră un număr natural N și un șir A[1], A[2],...,A[N] de N numere naturale distincte. Se consideră de asemenea și un număr natural T. == Cerinţa == Să se scrie un program care determină o valoare D ce reprezintă numărul termenilor din șirul Fibonacci F[1], F[2] ,..., F[T] care sunt divizibili cu cel puțin unul dintre numerele A[1],...

== Enunt ==
Fie șirul Fibonacci, dat prin F[1] = 1, F[2] = 1 și relația de recurență F[k] = F[k-1] + F[k-2], k ≥ 3 . Se consideră un număr natural N și un șir A[1], A[2],...,A[N] de N numere naturale distincte. Se consideră de asemenea și un număr natural T.
== Cerinţa ==
Să se scrie un program care determină o valoare D ce reprezintă numărul termenilor din șirul Fibonacci F[1], F[2] ,..., F[T] care sunt divizibili cu cel puțin unul dintre numerele A[1], A[2],...,A[N].
== Date de intrare ==
Fișierul de intrare fibodiv.in conţine pe prima linie numerele N și T separate printr-un spațiu, iar pe a doua linie N numere naturale, A[1], A[2],...,A[N], separate prin câte un spațiu.
== Date de ieșire ==
Fișierul de ieșire fibodiv.out va conţine pe prima linie numărul natural D,cu semnificația de mai sus.
== Restricţii şi precizări ==
* '''1 ≤ N ≤ 15'''
* '''2 ≤ T ≤ 1018'''
* '''2 ≤ A[i] ≤ 50, 1 ≤ i ≤ N'''
== Exemplul 1 ==
; fibodiv.in

3 20
3 6 10
; fibodiv.out

6
== Explicație ==
N = 3; T = 20; A1 = 3, A2 = 6, A3 = 10. Primii 20 de termeni ai șirului Fibonacci sunt: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765. Printre aceștia se găsesc 6 termeni divizibili cu cel puțin unul dintre numerele 3, 6, 10 și anume: 3, 21, 144, 610, 987, 6765.
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def fibonacci_sequence(n):
fib = [1, 1]
for i in range(2, n):
fib.append(fib[i - 1] + fib[i - 2])
return fib

def count_divisible_terms(fib_sequence, divisors):
count = 0
for term in fib_sequence:
for divisor in divisors:
if term % divisor == 0:
count += 1
break
return count

def main():
with open("fibodiv.in", "r") as fin:
N, T = map(int, fin.readline().split())
divisors = list(map(int, fin.readline().split()))

fib_sequence = fibonacci_sequence(T)
count = count_divisible_terms(fib_sequence, divisors)

with open("fibodiv.out", "w") as fout:
fout.write(str(count) + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

1896 - K Sir

2024-06-03T17:10:31Z

RebecaBud: Pagină nouă: == Cerinţa == Fie S un șir de caractere cu litere mici și litere mari. Se sortează în ordine lexicografică toate subsecvențele distincte ale lui S. Se dă un număr K și un vector k cu K numere întregi, se cere pentru fiecare număr cel de ki -lea subșir lexicografic. == Date de intrare == Fișierul de intrare ksir.in conține pe prima linie un șir S, pe a doua linie un număr K, iar pe următoarea linie K numere naturale separate prin spații. == Date de ieșire...

== Cerinţa ==
Fie S un șir de caractere cu litere mici și litere mari. Se sortează în ordine lexicografică toate subsecvențele distincte ale lui S. Se dă un număr K și un vector k cu K numere întregi, se cere pentru fiecare număr cel de ki -lea subșir lexicografic.
== Date de intrare ==
Fișierul de intrare ksir.in conține pe prima linie un șir S, pe a doua linie un număr K, iar pe următoarea linie K numere naturale separate prin spații.
== Date de ieșire ==
Fișierul de ieșire ksir.out va conține cele K șiruri de caractere, câte unul pe fiecare linie.
== Restricţii şi precizări ==
* |S| ≤ 200000
* suma |ki | ≤ 200000
== Exemplul 1 ==
; ksir.in

FORR
6
1 1 2 3 4 5
; ksir.out

F
F
FO
FOR
FORR
O
== Explicație ==
Subsecvențele pentru FORR sunt {'F', 'FO', 'FOR', 'FORR', 'O', 'OR', 'ORR', 'R', 'RR'}.
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def generate_subsequences(s):
subsequences = set()
n = len(s)
for i in range(n):
for j in range(i+1, n+1):
subsequences.add(s[i:j])
return sorted(subsequences)

def main():
with open("ksir.in", "r") as fin:
s = fin.readline().strip()
K = int(fin.readline().strip())
k_values = list(map(int, fin.readline().split()))

subsequences = generate_subsequences(s)

with open("ksir.out", "w") as fout:
for k in k_values:
fout.write(subsequences[k - 1] + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

1648 - Diez

2024-06-03T17:08:46Z

RebecaBud: Pagină nouă: == Enunt == Negrimon a găsit într-o culegere această problemă #legendară: peste un şir de caractere de lungime N, alcătuit din litere mici ale alfabetului englez, se efectuează M operaţii de următoarele tipuri: Se inserează în şir caracterul x, pe poziţia p, după deplasarea cu o poziţie la dreapta a caracterelor situate pe poziţiile mai mari sau egale cu p. Dacă valoarea p este egală cu lungimea şirului, x este alipit la finalul şirului. Se răspunde cu...

== Enunt ==

Negrimon a găsit într-o culegere această problemă #legendară: peste un şir de caractere de lungime N, alcătuit din litere mici ale alfabetului englez, se efectuează M operaţii de următoarele tipuri:

Se inserează în şir caracterul x, pe poziţia p, după deplasarea cu o poziţie la dreapta a caracterelor situate pe poziţiile mai mari sau egale cu p. Dacă valoarea p este egală cu lungimea şirului, x este alipit la finalul şirului.
Se răspunde cu 1 dacă secvenţa de litere care începe la poziţia q1 şi are lungimea lg coincide literă cu literă, cu secvenţa care începe la poziţia q2 şi are aceeaşi lungime lg şi se răspunde cu 0 în caz contrar. Este posibil ca cele două secvenţe să se suprapună complet sau parţial în şirul din care ele fac parte.
== Cerinţa ==
Fiind dat un şir de N litere mici şi o listă de M operaţii, să se afişeze răspunsurile la operaţiile de tip 2, respectând ordinea din succesiunea de operaţii date.
== Date de intrare ==
Fișierul de intrare diez.in conține pe prima linie valorile N şi M, separate printr-un spaţiu cu semnificaţia din enunţ. Pe a doua linie se află un şir de N litere mici ale alfabetului englez iar următoarele M linii conţin câte o operaţie în unul dintre formatele:

* 1 p x – Datele pentru operaţia de tipul 1.
* 2 q1 q2 lg – Datele pentru operaţia de tipul 2.
== Date de ieșire ==
În fișierul de ieșire diez.out se vor scrie valori egale cu 0 sau 1, câte una pe o linie, reprezentând răspunsurile date, în ordine, la operaţiile de tipul 2 existente în fişierul de intrare.
== Restricţii şi precizări ==
* 1 ≤ N, M ≤ 250 000
* 0 ≤ p ≤ lungimea şirului la momentul inserării
* x este literă mică a alfabetului englez
* q1, q2 ≥ 0; se garantează că pentru fiecare operaţie de tipul 2 există lg caractere în şir începând atât cu *poziţia q1 cât şi cu poziţia q2
* 1 < lg ≤ lungimea şirului la momentul efectuării operaţiei de tipul 2
* Numerotarea caracterelor din şir începe de la poziţia 0
== Exemplul 1 ==
; diez.in

8 6
abcasfas
2 0 5 3
1 3 d
2 4 7 2
1 1 s
1 10 b
2 0 8 3
; diez.out

0
1
1
== Explicație ==
Se compară secvenţele abc şi fas care sunt diferite → se afişează 0
Caracterul d este inserat înainte de poziţia 3 şi se obţine şirul abcdasfas
Se compară subşirurile as şi as, sunt identice → se afişează 1
Caracterul s este inserat înainte de poziţia 1, se obţine şirul asbcdasfas
Caracterul b este inserat pe poziţia 10, poziţia este egală cu lungimea şirului, se obţine şirul asbcdasfasb
Se compară subşirurile asb si asb , sunt identice → se afişează 1
 

== Exemplul 2 ==
; diez.in

6 3
atmatm
2 0 2 4
1 6 a
2 0 3 4
; diez.out

0
1
== Explicație ==
Se compară subşirurile atma şi matm, sunt diferite → se afişează 0
Caracterul a se alipeşte la final, se obţine şirul atmatma
Se compară subşirurile atma atma, sunt identice → se afişează 1
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def compare_substrings(string, q1, q2, lg):
return string[q1:q1+lg] == string[q2:q2+lg]

def main():
with open("diez.in", "r") as fin:
N, M = map(int, fin.readline().split())
string = fin.readline().strip()
operations = [list(map(str, fin.readline().split())) for _ in range(M)]

for op in operations:
if op[0] == '2':
q1, q2, lg = map(int, op[1:])
result = compare_substrings(string, q1, q2, lg)
print(result)

if __name__ == "__main__":
main()

</syntaxhighlight>

1829 - Cuvinte Ascunse

2024-06-03T17:05:59Z

RebecaBud: /* Enunt */

== Enunt ==
Programatoarea Petra a început un curs de criptografie. Fiind un spirit creativ, Petra a creat deja o metodă elaborată de criptare a unei parole sub forma unei perechi (tabel de litere aparţinând mulţimii {‘a’...’z’}, dicţionar de cuvinte). Din păcate pentru Petra, metoda ei de criptare a parolei, poate fi decriptată de oricine astfel:
* se iau tabelul de litere şi dicţionarul de cuvinte permise
* se listează, sortează şi numără toate cuvintele care se găsesc în tabel. Un cuvânt c1c2…ckcare există în dicţionar există şi în tabel dacă fiecare literă ci apare în tabel şi pentru i>1, cieste vecină în tabel cu litera ci−1.
* din lista sortata de T perechi (cuvânti, ai), unde cuvântieste un cuvânt iar ai este numărul de apariţii în tabel, reconstituie litera pi a parolei astfel: pi=‘a’ + ( aimod 26). Încercând să îmbunătăţească algoritmul, Petra a decis să înlocuiască unele litere din tabel cu semnul întrebării '?'. Un semn '?' poate fi înlocuit cu orice literă când se parcurge tabelul. Convinge-o pe Petra că, în ciuda îmbunătăţirii, îi poţi găsi parola pornind de la orice pereche de (dicţionar, tabel de litere) dată.

== Cerinţa ==
Dat fiind un tabel de litere de dimensiuni N x M, şi o listă a cuvintelor din dicţionar, să se afişeze lista sortată de T perechi de forma 'ci: ai' şi parola Petrei.
== Date de intrare ==
Fişierul cuvinteascunse.in va conţine N + C + 1 linii. Pe prima linie N, M, C – dimensiunile tabelului, şi numărul de cuvinte din dicţionar. Apoi cele N linii ale tabelului:
t1,1 ...t1,m
t2,1 ...t2,m
. . .
tn,1 ...tn,m
urmate de cele C cuvinte din dicţionar, fiecare pe o linie:
cuvânt1
cuvânt2
. . .
cuvântC
== Date de ieșire ==
Fişierul cuvinteascunse.out va conţine pe prima linie T, numărul de cuvinte distincte găsite în tabel. Pe următoarele T linii se vor afla perechi cuvânti ai separate printr-un spaţiu. Pe ultima linie se va afla un şir de caractere reprezentand parola Petrei.
== Restricţii şi precizări ==
* O secvenţă de litere reprezintă un cuvânt dacă se află în dicţionarul dat ca date de intrare. Dicţionarul conţine cuvinte formate din litere aparţinând mulţimii {‘a’...’z’}U{‘A’...’Z’}. Literele mici şi cele mari se consideră egale. Două litere sunt vecine în tabel, dacă celulele lor au o latura sau un colţ comun. Aceeaşi litera din tabel se poate folosi de mai multe ori într-un cuvânt. Dacă acelaşi semn '?' este folosit de mai multe ori într-un cuvânt, trebuie să reprezinte aceeaşi literă de fiecare dată.
* 0 < N < 6
* 0 < M < 6
* 0 < C < 20000
== Exemplul 1 ==
; cuvinteascunse.in

2 2 3
e a
l ?
ea
elena
arc
; cuvinteascunse.out

2
ea 3
elena 1
db
== Explicație ==
Am gasit cuvântul “ea” de 3 ori: o data pe prima linie a tabelului, o data pe diagonala principală, inlocuind '?' cu 'a', şi o data ca “?a" inlocuind '?' cu 'e'. Am gasit cuvântul “elena” o data, inlocuind '?' cu 'n'.
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def is_valid_cell(i, j, n, m):
return 0 <= i < n and 0 <= j < m

def search_word(grid, word, n, m, visited, i, j, idx):
if idx == len(word):
return True
if not is_valid_cell(i, j, n, m) or visited[i][j] or grid[i][j] != word[idx]:
return False
visited[i][j] = True
for di in [-1, 0, 1]:
for dj in [-1, 0, 1]:
if (di, dj) != (0, 0) and search_word(grid, word, n, m, visited, i + di, j + dj, idx + 1):
return True
visited[i][j] = False
return False

def count_word_occurrences(grid, word, n, m):
count = 0
for i in range(n):
for j in range(m):
if grid[i][j] == word[0]:
visited = [[False] * m for _ in range(n)]
if search_word(grid, word, n, m, visited, i, j, 0):
count += 1
return count

def main():
with open("cuvinteascunse.in", "r") as fin:
n, m, c = map(int, fin.readline().split())
grid = [fin.readline().split() for _ in range(n)]
words = [fin.readline().strip() for _ in range(c)]

word_counts = {}
for word in words:
count = count_word_occurrences(grid, word, n, m)
if count > 0:
word_counts[word] = count

sorted_words = sorted(word_counts.items(), key=lambda x: x[1], reverse=True)

with open("cuvinteascunse.out", "w") as fout:
fout.write(str(len(sorted_words)) + "\n")
for word, count in sorted_words:
fout.write(f"{word} {count}\n")
password = ""
for i in range(n):
for j in range(m):
if grid[i][j] != "?":
password += chr(ord("a") + (count_word_occurrences(grid, grid[i][j], n, m) % 26))
fout.write(password + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

1829 - Cuvinte Ascunse

2024-06-03T17:05:32Z

RebecaBud: /* Enunt */

== Enunt ==
Programatoarea Petra a început un curs de criptografie. Fiind un spirit creativ, Petra a creat deja o metodă elaborată de criptare a unei parole sub forma unei perechi (tabel de litere aparţinând mulţimii {‘a’...’z’}, dicţionar de cuvinte). Din păcate pentru Petra, metoda ei de criptare a parolei, poate fi decriptată de oricine astfel:
* se iau tabelul de litere şi dicţionarul de cuvinte permise
* se listează, sortează şi numără toate cuvintele care se găsesc în tabel. Un cuvânt c1c2…ck
care există în dicţionar există şi în tabel dacă fiecare literă ci
apare în tabel şi pentru i>1, ci
este vecină în tabel cu litera ci−1.
din lista sortata de T perechi (cuvânti, ai), unde cuvântieste un cuvânt iar ai este numărul de apariţii în tabel, reconstituie litera pi a parolei astfel: pi=‘a’ + ( aimod 26). Încercând să îmbunătăţească algoritmul, Petra a decis să înlocuiască unele litere din tabel cu semnul întrebării '?'. Un semn '?' poate fi înlocuit cu orice literă când se parcurge tabelul. Convinge-o pe Petra că, în ciuda îmbunătăţirii, îi poţi găsi parola pornind de la orice pereche de (dicţionar, tabel de litere) dată.

== Cerinţa ==
Dat fiind un tabel de litere de dimensiuni N x M, şi o listă a cuvintelor din dicţionar, să se afişeze lista sortată de T perechi de forma 'ci: ai' şi parola Petrei.
== Date de intrare ==
Fişierul cuvinteascunse.in va conţine N + C + 1 linii. Pe prima linie N, M, C – dimensiunile tabelului, şi numărul de cuvinte din dicţionar. Apoi cele N linii ale tabelului:
t1,1 ...t1,m
t2,1 ...t2,m
. . .
tn,1 ...tn,m
urmate de cele C cuvinte din dicţionar, fiecare pe o linie:
cuvânt1
cuvânt2
. . .
cuvântC
== Date de ieșire ==
Fişierul cuvinteascunse.out va conţine pe prima linie T, numărul de cuvinte distincte găsite în tabel. Pe următoarele T linii se vor afla perechi cuvânti ai separate printr-un spaţiu. Pe ultima linie se va afla un şir de caractere reprezentand parola Petrei.
== Restricţii şi precizări ==
* O secvenţă de litere reprezintă un cuvânt dacă se află în dicţionarul dat ca date de intrare. Dicţionarul conţine cuvinte formate din litere aparţinând mulţimii {‘a’...’z’}U{‘A’...’Z’}. Literele mici şi cele mari se consideră egale. Două litere sunt vecine în tabel, dacă celulele lor au o latura sau un colţ comun. Aceeaşi litera din tabel se poate folosi de mai multe ori într-un cuvânt. Dacă acelaşi semn '?' este folosit de mai multe ori într-un cuvânt, trebuie să reprezinte aceeaşi literă de fiecare dată.
* 0 < N < 6
* 0 < M < 6
* 0 < C < 20000
== Exemplul 1 ==
; cuvinteascunse.in

2 2 3
e a
l ?
ea
elena
arc
; cuvinteascunse.out

2
ea 3
elena 1
db
== Explicație ==
Am gasit cuvântul “ea” de 3 ori: o data pe prima linie a tabelului, o data pe diagonala principală, inlocuind '?' cu 'a', şi o data ca “?a" inlocuind '?' cu 'e'. Am gasit cuvântul “elena” o data, inlocuind '?' cu 'n'.
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def is_valid_cell(i, j, n, m):
return 0 <= i < n and 0 <= j < m

def search_word(grid, word, n, m, visited, i, j, idx):
if idx == len(word):
return True
if not is_valid_cell(i, j, n, m) or visited[i][j] or grid[i][j] != word[idx]:
return False
visited[i][j] = True
for di in [-1, 0, 1]:
for dj in [-1, 0, 1]:
if (di, dj) != (0, 0) and search_word(grid, word, n, m, visited, i + di, j + dj, idx + 1):
return True
visited[i][j] = False
return False

def count_word_occurrences(grid, word, n, m):
count = 0
for i in range(n):
for j in range(m):
if grid[i][j] == word[0]:
visited = [[False] * m for _ in range(n)]
if search_word(grid, word, n, m, visited, i, j, 0):
count += 1
return count

def main():
with open("cuvinteascunse.in", "r") as fin:
n, m, c = map(int, fin.readline().split())
grid = [fin.readline().split() for _ in range(n)]
words = [fin.readline().strip() for _ in range(c)]

word_counts = {}
for word in words:
count = count_word_occurrences(grid, word, n, m)
if count > 0:
word_counts[word] = count

sorted_words = sorted(word_counts.items(), key=lambda x: x[1], reverse=True)

with open("cuvinteascunse.out", "w") as fout:
fout.write(str(len(sorted_words)) + "\n")
for word, count in sorted_words:
fout.write(f"{word} {count}\n")
password = ""
for i in range(n):
for j in range(m):
if grid[i][j] != "?":
password += chr(ord("a") + (count_word_occurrences(grid, grid[i][j], n, m) % 26))
fout.write(password + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

1829 - Cuvinte Ascunse

2024-06-03T17:04:55Z

RebecaBud: Pagină nouă: == Enunt == Programatoarea Petra a început un curs de criptografie. Fiind un spirit creativ, Petra a creat deja o metodă elaborată de criptare a unei parole sub forma unei perechi (tabel de litere aparţinând mulţimii {‘a’...’z’}, dicţionar de cuvinte). Din păcate pentru Petra, metoda ei de criptare a parolei, poate fi decriptată de oricine astfel: * se iau tabelul de litere şi dicţionarul de cuvinte permise * se listează, sortează şi numără toate cuvin...

== Enunt ==
Programatoarea Petra a început un curs de criptografie. Fiind un spirit creativ, Petra a creat deja o metodă elaborată de criptare a unei parole sub forma unei perechi (tabel de litere aparţinând mulţimii {‘a’...’z’}, dicţionar de cuvinte). Din păcate pentru Petra, metoda ei de criptare a parolei, poate fi decriptată de oricine astfel:
* se iau tabelul de litere şi dicţionarul de cuvinte permise
* se listează, sortează şi numără toate cuvintele care se găsesc în tabel. Un cuvânt c1c2…ck
care există în dicţionar există şi în tabel dacă fiecare literă ci
apare în tabel şi pentru i>1, ci
este vecină în tabel cu litera ci−1.
din lista sortata de T perechi (cuvânti, ai
), unde cuvânti
este un cuvânt iar ai
este numărul de apariţii în tabel, reconstituie litera pi
a parolei astfel: pi=
‘a’ + ( ai
mod 26). Încercând să îmbunătăţească algoritmul, Petra a decis să înlocuiască unele litere din tabel cu semnul întrebării '?'. Un semn '?' poate fi înlocuit cu orice literă când se parcurge tabelul. Convinge-o pe Petra că, în ciuda îmbunătăţirii, îi poţi găsi parola pornind de la orice pereche de (dicţionar, tabel de litere) dată.
== Cerinţa ==
Dat fiind un tabel de litere de dimensiuni N x M, şi o listă a cuvintelor din dicţionar, să se afişeze lista sortată de T perechi de forma 'ci: ai' şi parola Petrei.
== Date de intrare ==
Fişierul cuvinteascunse.in va conţine N + C + 1 linii. Pe prima linie N, M, C – dimensiunile tabelului, şi numărul de cuvinte din dicţionar. Apoi cele N linii ale tabelului:
t1,1 ...t1,m
t2,1 ...t2,m
. . .
tn,1 ...tn,m
urmate de cele C cuvinte din dicţionar, fiecare pe o linie:
cuvânt1
cuvânt2
. . .
cuvântC
== Date de ieșire ==
Fişierul cuvinteascunse.out va conţine pe prima linie T, numărul de cuvinte distincte găsite în tabel. Pe următoarele T linii se vor afla perechi cuvânti ai separate printr-un spaţiu. Pe ultima linie se va afla un şir de caractere reprezentand parola Petrei.
== Restricţii şi precizări ==
* O secvenţă de litere reprezintă un cuvânt dacă se află în dicţionarul dat ca date de intrare. Dicţionarul conţine cuvinte formate din litere aparţinând mulţimii {‘a’...’z’}U{‘A’...’Z’}. Literele mici şi cele mari se consideră egale. Două litere sunt vecine în tabel, dacă celulele lor au o latura sau un colţ comun. Aceeaşi litera din tabel se poate folosi de mai multe ori într-un cuvânt. Dacă acelaşi semn '?' este folosit de mai multe ori într-un cuvânt, trebuie să reprezinte aceeaşi literă de fiecare dată.
* 0 < N < 6
* 0 < M < 6
* 0 < C < 20000
== Exemplul 1 ==
; cuvinteascunse.in

2 2 3
e a
l ?
ea
elena
arc
; cuvinteascunse.out

2
ea 3
elena 1
db
== Explicație ==
Am gasit cuvântul “ea” de 3 ori: o data pe prima linie a tabelului, o data pe diagonala principală, inlocuind '?' cu 'a', şi o data ca “?a" inlocuind '?' cu 'e'. Am gasit cuvântul “elena” o data, inlocuind '?' cu 'n'.
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def is_valid_cell(i, j, n, m):
return 0 <= i < n and 0 <= j < m

def search_word(grid, word, n, m, visited, i, j, idx):
if idx == len(word):
return True
if not is_valid_cell(i, j, n, m) or visited[i][j] or grid[i][j] != word[idx]:
return False
visited[i][j] = True
for di in [-1, 0, 1]:
for dj in [-1, 0, 1]:
if (di, dj) != (0, 0) and search_word(grid, word, n, m, visited, i + di, j + dj, idx + 1):
return True
visited[i][j] = False
return False

def count_word_occurrences(grid, word, n, m):
count = 0
for i in range(n):
for j in range(m):
if grid[i][j] == word[0]:
visited = [[False] * m for _ in range(n)]
if search_word(grid, word, n, m, visited, i, j, 0):
count += 1
return count

def main():
with open("cuvinteascunse.in", "r") as fin:
n, m, c = map(int, fin.readline().split())
grid = [fin.readline().split() for _ in range(n)]
words = [fin.readline().strip() for _ in range(c)]

word_counts = {}
for word in words:
count = count_word_occurrences(grid, word, n, m)
if count > 0:
word_counts[word] = count

sorted_words = sorted(word_counts.items(), key=lambda x: x[1], reverse=True)

with open("cuvinteascunse.out", "w") as fout:
fout.write(str(len(sorted_words)) + "\n")
for word, count in sorted_words:
fout.write(f"{word} {count}\n")
password = ""
for i in range(n):
for j in range(m):
if grid[i][j] != "?":
password += chr(ord("a") + (count_word_occurrences(grid, grid[i][j], n, m) % 26))
fout.write(password + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

0711 - Desc

2024-06-03T17:00:44Z

RebecaBud: Pagină nouă: == Enunt == Fie n un număr natural nenul, n > 1. Definim n(p) ca fiind descompunerea lui n în sumă de puteri naturale distincte ale numărului prim p. Exemple: * pentru n=10 toate n(p) descompunerile posibile sunt: 10(2)=21+23 şi 10(3)=30+32 * pentru n=11 toate n(p) descompunerile posibile sunt: 11(2)=20+21+23 şi 11(11)=111 == Cerinţa == Să se scrie un program care citeşte un număr natural n şi determină toate n(p) descompunerile numărului n. == Date de intrare...

== Enunt ==
Fie n un număr natural nenul, n > 1. Definim n(p) ca fiind descompunerea lui n în sumă de puteri naturale distincte ale numărului prim p.

Exemple:

* pentru n=10 toate n(p) descompunerile posibile sunt: 10(2)=21+23 şi 10(3)=30+32
* pentru n=11 toate n(p) descompunerile posibile sunt: 11(2)=20+21+23 şi 11(11)=111
== Cerinţa ==
Să se scrie un program care citeşte un număr natural n şi determină toate n(p) descompunerile numărului n.
== Date de intrare ==
Fișierul de intrare desc.in conține pe prima linie numărul n.
== Date de ieșire ==
Fișierul de ieșire desc.out va conține pe linii separate toate n(p) descompunerile numărului n. Fiecare linie va conţine în ordine:
* o valoare naturală p reprezentând numărul prim asociat descompunerii;
* o valoare naturală k, reprezentând numărul de termeni ai descompunerii;
* Următoarele k valori, numere naturale, reprezintă exponenţii puterilor din descompunere, scrise în ordine crescătoare.
== Restricţii şi precizări ==
* '''2 ≤ n ≤ 10 000 000'''
* Pentru un număr prim p fixat, există o singură n(p) descompunere a unui număr natural n;
* Descompunerile vor fi afişate în ordinea crescătoare a valorilor identificate pentru p;
* Pe fiecare linie a fişierului de ieşire, valorile vor fi despărţite prin câte un spaţiu.
== Exemplul 1 ==
; desc.in

10
; desc.out

2 2 1 3
3 2 0 2
== Explicație ==
10(2)=21+23; 10(3)=30+32. Prima descompunere s-a făcut după numărul prim p=2 şi conţine 2 termeni cu puterile 1 şi 3. A doua descompunere s-a făcut după numărul prim p=3 şi conţine 2 termeni cu puterile 0 şi 2.
 

== Exemplul 2 ==
; desc.in

11
; desc.out

2 3 0 1 3
11 1 1
== Explicație ==
11(2)=20+21+23; 11(11)=111. Prima descompunere s-a făcut după numărul prim p=2 şi conţine 3 termeni cu puterile 0, 1 şi 3. A doua descompunere s-a făcut după numărul prim p=11 şi conţine un termen cu puterea 1.
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def prime_factors(n):
factors = []
d = 2
while d * d <= n:
while n % d == 0:
factors.append(d)
n //= d
d += 1
if n > 1:
factors.append(n)
return factors

def decompose(n):
primes = prime_factors(n)
decompositions = []
for p in set(primes):
exponents = []
count = primes.count(p)
for i in range(count):
exponents.append(i)
decompositions.append((p, count, exponents))
return sorted(decompositions)

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

decompositions = decompose(n)

with open("desc.out", "w") as fout:
for decomposition in decompositions:
p, k, exponents = decomposition
fout.write(f"{p} {k} {' '.join(map(str, exponents))}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

1022 - Fractii 2

2024-06-03T16:57:49Z

RebecaBud: Pagină nouă: == Enunt == Numărul 1 poate fi scris în diverse moduri ca sumă de fracţii cu numărătorul 1 şi numitorul o putere a lui 2. De exemplu: '''1 = 1/2 + 1/2 = 1/2 + 1/4 + 1/8 + 1/8 = 1/8 + 1/4 + 1/2 + 1/8''' Două scrieri nu sunt considerate distincte dacă folosesc aceleaşi fracţii scrise în altă ordine. În exemplul de mai sus ultimele două scrieri nu sunt distincte. == Cerinţa == Pentru N – număr natural nenul să se determine: a) O modalitate de scriere a num...

== Enunt ==
Numărul 1 poate fi scris în diverse moduri ca sumă de fracţii cu numărătorul 1 şi numitorul o putere a lui 2. De exemplu:

'''1 = 1/2 + 1/2 = 1/2 + 1/4 + 1/8 + 1/8 = 1/8 + 1/4 + 1/2 + 1/8'''

Două scrieri nu sunt considerate distincte dacă folosesc aceleaşi fracţii scrise în altă ordine. În exemplul de mai sus ultimele două scrieri nu sunt distincte.
== Cerinţa ==
Pentru N – număr natural nenul să se determine:
a) O modalitate de scriere a numărului 1 ca sumă de exact N fracţii cu numărătorul 1 şi numitorul o putere a lui 2.
b) Numărul de scrieri distincte a numărului 1 ca sumă de exact N fracţii cu numărătorul 1 şi numitorul o putere a lui 2. Deoarece acest număr poate fi foarte mare acest număr trebuie calculat modulo 100003.
== Date de intrare ==
Fişierul de intrare fractii2.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 găseşte un singur număr N natural – reprezentând numărul de fracţii
== 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 fractii2.out se vor scrie, pe o singură linie, N numere naturale separate prin câte un spaţiu reprezentând cei N exponenţi ai lui 2 din scrierea solicitată în prima cerinţă. Astfel, dacă numerele afişate sunt m1,m2,…,mn
atunci există scrierea 1=12m1+12m2+…+12mn
.
Dacă valoarea lui p este 2, se va rezolva numai punctul b) din cerinţă. În acest caz, în fişierul de ieşire fractii2.out se va scrie un număr natural reprezentând răspunsul la a doua cerinţă, adică numărul de scrieri distincte a numărului 1 ca sumă de N fracţii cu numărătorul 1 şi numitorul o putere a lui 2 (modulo 100003).

Restricţii
== Restricţii şi precizări ==
* '''2 ≤ N ≤ 2000'''
* Pentru prima cerinţă se acordă 20% din punctaj.
* Pentru a doua cerinţă de acordă 80% din punctaj.
* Rezultatul pentru a doua cerinţă trebuie afişat modulo 100003
== Exemplul 1 ==
; fractii2.in

1
4
; fractii2.out

2 2 2 2
 

== Exemplul 2 ==
; fractii2.in

2
4
; fractii2.out

2
== Explicaţie ==
Primul exemplu:

1 = 1/2 + 1/4 + 1/8 + 1/8 = 1/4 + 1/4 + 1/4 + 1/4
Răspunsul corespunde celei de-a doua scrieri dar există şi alte variante corecte de răspuns. De exemplu, 3 1 2 3 se consideră răspuns corect.
Atenţie! Pentru acest test se va afişa doar rezultatul la cerinţa a).

Al doilea exemplu:

1 = 1/2 + 1/4 + 1/8 + 1/8 = 1/4 + 1/4 + 1/4 + 1/4

Acestea sunt singurele scrieri distincte.
Atenţie! Pentru acest test se va afişa doar rezultatul la cerinţa b).
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def write_fractions(N):
exponents = [1] * N
return exponents

def count_distinct_writings(N):
MOD = 100003
if N == 2:
return 1

dp = [0] * (N + 1)
dp[0] = 1
for i in range(1, N):
for j in range(i, N + 1):
dp[j] = (dp[j] + dp[j - i]) % MOD

return dp[N]

def main():
with open("fractii2.in", "r") as fin:
p = int(fin.readline())
N = int(fin.readline())

if p == 1:
with open("fractii2.out", "w") as fout:
exponents = write_fractions(N)
fout.write(" ".join(map(str, exponents)))
elif p == 2:
with open("fractii2.out", "w") as fout:
distinct_writings = count_distinct_writings(N)
fout.write(str(distinct_writings % 100003))

if __name__ == "__main__":
main()

</syntaxhighlight>

1203 - K Secv

2024-06-03T16:54:50Z

RebecaBud: Pagină nouă: == Enunt == Fie un vector V cu N elemente și un număr K. Vectorul V trebuie împărțit în exact K subsecvențe nevide, astfel încât fiecare element din vector să aparțină exact unei subsecvențe. Această împărțire trebuie făcută astfel încât maximul șmecheriei fiecărei subsecvențe să fie cât mai mic. (Această problemă concepe greșit sistemul de șmecherie și valoare). Șmecheria fiecărei subsecvențe se definește ca fiind parte întreagă din ((V...

== Enunt ==
Fie un vector V cu N elemente și un număr K. Vectorul V trebuie împărțit în exact K subsecvențe nevide, astfel încât fiecare element din vector să aparțină exact unei subsecvențe. Această împărțire trebuie făcută astfel încât maximul șmecheriei fiecărei subsecvențe să fie cât mai mic. (Această problemă concepe greșit sistemul de șmecherie și valoare). Șmecheria fiecărei subsecvențe se definește ca fiind parte întreagă din ((Vmax – Vmin + 1) / 2), unde Vmax este valoarea maximă din subsecvență, iar Vmin este valoarea minimă.

Vectorul V de N elemente va fi generat în felul următor: se dă un număr M și 2 vectori A și B de lungime M (indexați de la 0 la M - 1). Fiecare element i, 0 ≤ i < N, din vectorul V va fi calculat cu următoarea formulă: V[i] = (A[i % M] ^ B[i / M]), unde x % y reprezintă restul lui x la împărțirea cu y, x / y reprezintă câtul împărțirii lui x la y și x ^ y reprezintă rezultatul operației xor (sau exclusiv pe biți) dintre x și y.

== Date de intrare ==
Pe prima linie a fișierului ksecv.in se află 3 numere naturale N, K și M, cu semnificația din enunț, separate prin câte un spațiu. Pe a doua linie a fișierului se află M numere naturale separate prin câte un spațiu, reprezentând vectorul A. Pe a treia linie se află M numere naturale separate prin câte un spațiu, reprezentând vectorul B.
== Date de ieșire ==
Pe prima linie a fișierului de ieșire ksecv.out se va afișa cel mai mic număr natural S pentru care vectorul V poate fi împărțit în exact K subsecvențe nevide, fiecare având șmecheria mai mică sau egală cu S.
== Restricţii şi precizări ==
* 1 ≤ N ≤ 1 000 000
* 1 ≤ K ≤ 1 000
* 1 ≤ M ≤ 2 048
* N < M*M
* 1 ≤ K < N
* Valorile vectorilor A și B vor fi din intervalul [0, 260 - 1]
* Fiecare din cele K subsecvențe trebuie să aibă cel puțin un element.
* Pentru 20% din teste N ≤ 100, K ≤ 50.
* Pentru alte 20% din teste N ≤ 100 000, K ≤ 1000.
* Pentru alte 20% din teste N ≤ 1 000 000, K ≤ 50.
* Vectorul V are indicii indexați de la 0 la N - 1.
* Vectorii A și B au indicii indexați de la 0 la M - 1.
== Exemplul 1 ==
; ksecv.in

6 3 6
13 4 6 19 4 10
0 0 0 0 0 0
; ksecv.out

5
== Explicație ==
Valorile vectorului V sunt 13 4 6 19 4 10.

Dacă împărțim șirul în subsecvențele [0,2] [3,3] [4,5] obținem șmecheriile 5, 0 și 3. Șmecheria maxima este 5.

Nu putem împărți vectorul V astfel încât șmecheria maximă a unei subsecvențe să fie mai mică decât 5.
 

== Exemplul 2 ==
; ksecv.in

6 4 6
13 4 6 19 4 10
0 0 0 0 0 0
; ksecv.out

3
== Explicație ==
Valorile vectorului V sunt 13 4 6 19 4 10.
O posibilă împărțire este: [0,0] [1,2] [3,3] [4,5]. Șmecheriile fiecărei subsecvențe sunt 0, 1, 0 și 3.
 

== Exemplul 3 ==
; ksecv.in

6 3 3
3 4 2
4 5 3
; ksecv.out

3
== Explicație ==
Valorile vectorului V sunt 7 0 6 6 1 7.

Dacă împărțim în subsecvențele [0,0] [1,4] [5,5], obținem șmecheriile 0, 3 și 0.
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def calculate_smek(X):
return (max(X) - min(X) + 1) // 2

def check_feasibility(N, K, M, A, B, S):
count = 1
min_smek = max_smek = calculate_smek([A[i % M] ^ B[i // M] for i in range(N)])

for i in range(1, N):
max_smek = max(max_smek, calculate_smek([A[i % M] ^ B[i // M] for i in range(N - i)]))
if max_smek <= S:
count += 1

return count >= K

def binary_search(N, K, M, A, B):
left = 0
right = calculate_smek([A[i % M] ^ B[i // M] for i in range(N)])

while left < right:
mid = (left + right) // 2
if check_feasibility(N, K, M, A, B, mid):
right = mid
else:
left = mid + 1

return left

def main():
with open("ksecv.in", "r") as fin:
N, K, M = map(int, fin.readline().split())
A = list(map(int, fin.readline().split()))
B = list(map(int, fin.readline().split()))

with open("ksecv.out", "w") as fout:
fout.write(str(binary_search(N, K, M, A, B)))

if __name__ == "__main__":
main()

</syntaxhighlight>

0694 - Sam

2024-06-03T16:51:08Z

RebecaBud: Pagină nouă: == Enunt == Aranjăm primele N numere naturale nenule sub forma unui șir A[1], A[2], ..., A[N]. Fie X[1], X[2],...,X[K] (K ≥ 3), un subșir al șirului A. Numim extrem local al subșirului X termenul din mijlocul unei secvențe de lungime trei din subșir, X[i-1], X[i], X[i+1], cu proprietatea: X[i-1]<X[i]>X[i+1], 1<i<K sau X[i-1]>X[i]<X[i+1], 1<i<K. Vom nota cu nrex(X) numărul de extreme locale ale subșirului X. Spunem că un subșir X[1], X[2],...,X[K] (K≥2) al...

== Enunt ==

Aranjăm primele N numere naturale nenule sub forma unui șir A[1], A[2], ..., A[N].

Fie X[1], X[2],...,X[K] (K ≥ 3), un subșir al șirului A. Numim extrem local al subșirului X termenul din mijlocul unei secvențe de lungime trei din subșir, X[i-1], X[i], X[i+1], cu proprietatea: X[i-1]<X[i]>X[i+1], 1<i<K sau X[i-1]>X[i]<X[i+1], 1<i<K.

Vom nota cu nrex(X) numărul de extreme locale ale subșirului X.

Spunem că un subșir X[1], X[2],...,X[K] (K≥2) al șirului A este subșir alternant dacă nrex(X)=K-2, adică exceptând primul și ultimul termen din subșir toți ceilalți termeni sunt extreme locale ale subșirului X.

Dintre toate subșirurile alternante ale șirului A ne interesează cele de lungime maximă pe care le vom numi subșiruri alternante maximale.
== Cerinţa ==
Cunoscând N și tabloul A se cere să se determine restul obținut la împărțirea dintre numărul M al subșirurilor alternante maximale ale tabloului A și numărul 1000003.
== Date de intrare ==
Fișierul de intrare sam.in conţine pe prima linie numărul natural N. Pe linia a doua se găsesc cele N numere ale șirului dat separate prin câte un spațiu.
== Date de ieșire ==
În fişierul de ieşire sam.out se va scrie numărul obţinut ca rest la împărţirea dintre numărul M, având semnificația descrisă mai sus, şi numărul 1000003.
== Restricţii şi precizări ==
* '''3 ≤ N ≤ 100 000'''
== Exemplul 1 ==
; sam.in

7
1 3 5 4 7 6 2
; sam.out

6
== Explicație ==
Șirul dat conține trei extreme locale , valorile 5, 4 și 7. Cele șase subșiruri alternante maximale cu șirul dat sunt: (1 5 4 6 2), (1 5 4 7 2), (1 5 4 7 6), (3 5 4 6 2), (3 5 4 7 2), (3 5 4 7 6)
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def count_alternating_subsequences(N, A):
count = 0

for i in range(1, N - 1):
if (A[i - 1] < A[i] > A[i + 1]) or (A[i - 1] > A[i] < A[i + 1]):
count += 1

return count

def main():
with open("sam.in", "r") as fin:
N = int(fin.readline())
A = list(map(int, fin.readline().split()))

M = count_alternating_subsequences(N, A)

with open("sam.out", "w") as fout:
fout.write(str(M % 1000003))

if __name__ == "__main__":
main()

</syntaxhighlight>

3649 - CMMDC 4

2024-06-03T16:45:20Z

RebecaBud: /* Rezolvare */

== Enunt ==
== Cerinţa ==
Dându-se N, determinați valoarea expresiei: a1•b1•c1 + a2•b2•c2 + ... + ak•bk•ck
unde (a1,b1,c1), (a2,b2,c2), …, (ak,bk,ck) sunt toate tripletele care îndeplinesc condițiile de mai sus. Întrucât rezultatul poate fi foarte mare, afișați resul împărțirii valorii expresiei la numărul 1.000.000.007.
== Date de intrare ==
De la tastatură se citește numărul N.
== Date de ieșire ==
Pe ecran se va afișa un singur număr natural R reprezentând restul împărțirii rezultatului expresiei descrise anterior la numărul 1.000.000.007.
== Restricţii şi precizări ==
* '''1 ≤ n ≤ 1.000.000'''
== Exemplul 1 ==
; Intrare

4
; Ieșire

36
== Explicație ==
Tripletele valide sunt: (2, 3, 1), (3, 4, 1), (3, 2, 1), (4, 3, 1).
2*3*1 + 3*4*1 +3*2*1 + 4*3*1 = 36. Restul împărțirii numărului 36 la 1.000.000.007 este 36.
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def gcd(a, b):
while b:
a, b = b, a % b
return a

def euler_totient(N):
phi = [i for i in range(N + 1)]
for i in range(2, N + 1):
if phi[i] == i: # i este prim
for j in range(i, N + 1, i):
phi[j] -= phi[j] // i
return phi

def main():
N = int(input("Introduceți valoarea lui N: "))

totient = euler_totient(N)

result = 0
mod = 10**9 + 7

for p in range(2, N + 1):
for k in range(1, N // p + 1):
a = p * k
b = p * k + 1
if b > N:
break
c = p
result += a * b * c * totient[p] % mod
result %= mod

print(result)

if __name__ == "__main__":
main()

</syntaxhighlight>

3649 - CMMDC 4

2024-06-03T16:44:43Z

RebecaBud: /* Rezolvare */

== Enunt ==
== Cerinţa ==
Dându-se N, determinați valoarea expresiei: a1•b1•c1 + a2•b2•c2 + ... + ak•bk•ck
unde (a1,b1,c1), (a2,b2,c2), …, (ak,bk,ck) sunt toate tripletele care îndeplinesc condițiile de mai sus. Întrucât rezultatul poate fi foarte mare, afișați resul împărțirii valorii expresiei la numărul 1.000.000.007.
== Date de intrare ==
De la tastatură se citește numărul N.
== Date de ieșire ==
Pe ecran se va afișa un singur număr natural R reprezentând restul împărțirii rezultatului expresiei descrise anterior la numărul 1.000.000.007.
== Restricţii şi precizări ==
* '''1 ≤ n ≤ 1.000.000'''
== Exemplul 1 ==
; Intrare

4
; Ieșire

36
== Explicație ==
Tripletele valide sunt: (2, 3, 1), (3, 4, 1), (3, 2, 1), (4, 3, 1).
2*3*1 + 3*4*1 +3*2*1 + 4*3*1 = 36. Restul împărțirii numărului 36 la 1.000.000.007 este 36.
 

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

</syntaxhighlight><nowiki><syntaxhighlight lang="python" line></nowiki>

def gcd(a, b):

while b:

a, b = b, a % b

return a

def euler_totient(N):

phi = [i for i in range(N + 1)]

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

if phi[i] == i: # i este prim

for j in range(i, N + 1, i):

phi[j] -= phi[j] // i

return phi

def main():

N = int(input("Introduceți valoarea lui N: "))

totient = euler_totient(N)

result = 0

mod = 10**9 + 7

for p in range(2, N + 1):

for k in range(1, N // p + 1):

a = p * k

b = p * k + 1

if b > N:

break

c = p

result += a * b * c * totient[p] % mod

result %= mod

print(result)

if __name__ == "__main__":

main()

<nowiki></syntaxhighlight></nowiki>

3649 - CMMDC 4

2024-06-03T16:44:00Z

RebecaBud: Pagină nouă: == Enunt == == Cerinţa == Dându-se N, determinați valoarea expresiei: a1•b1•c1 + a2•b2•c2 + ... + ak•bk•ck unde (a1,b1,c1), (a2,b2,c2), …, (ak,bk,ck) sunt toate tripletele care îndeplinesc condițiile de mai sus. Întrucât rezultatul poate fi foarte mare, afișați resul împărțirii valorii expresiei la numărul 1.000.000.007. == Date de intrare == De la tastatură se citește numărul N. == Date de ieșire == Pe ecran se va afișa un singur număr natura...

3385 - Lumini 1

2024-06-03T16:41:36Z

RebecaBud: Pagină nouă: == Enunt == Nicoleta, o fată curioasă, dorește să afle cine dintre colegii de clasă are bradul cu cele mai multe luminițe, cât și numărul de luminițe din acest brad. Fiind olimpică la informatică și iubind provocările, colegii i-au comunicat prin SMS doar numărul de divizori corespunzător numărului de luminițe din brad, acesta fiind și cel mai mic număr cu această proprietate. De exemplu, George, colegul de bancă, i-a dat numărul 5, corespunzător unui...

== Enunt ==
Nicoleta, o fată curioasă, dorește să afle cine dintre colegii de clasă are bradul cu cele mai multe luminițe, cât și numărul de luminițe din acest brad. Fiind olimpică la informatică și iubind provocările, colegii i-au comunicat prin SMS doar numărul de divizori corespunzător numărului de luminițe din brad, acesta fiind și cel mai mic număr cu această proprietate. De exemplu, George, colegul de bancă, i-a dat numărul 5, corespunzător unui număr de 16 luminițe, mai exact D16 = {1, 2, 4, 8, 16}, iar 16 este numărul cel mai mic cu exact 5 divizori. Mesajele colegilor vor fi de forma: NrDiv Nume, unde NrDiv reprezintă numărul de divizori, iar Nume reprezintă numele colegului care a trimis mesajul.
== Cerinţa ==
Scrieţi un program care să determine:
1) Numărul de luminițe din bradul cu cele mai multe luminițe.
2) Numele colegului care are bradul cu cele mai multe luminițe.
== Date de intrare ==
Fișierul de intrare lumini.in conţine pe prima linie cerința 1 sau 2. Pe a doua linie numărul n, reprezentând numărul colegilor Nicoletei, iar pe următoarele n linii vor fi mesajele colegilor, sub forma descrisă în enunţ, câte un mesaj pe o linie.

Date de ieșire
== Date de ieșire ==
Fișierul de ieșire lumini.out va conţine o singură linie pe care va fi scris numărul de luminițe al bradului cu cele mai multe luminițe (cerința 1) sau numele primului coleg din lista primită care are bradul cu cele mai multe luminițe (cerința 2).
== Restricţii şi precizări ==
* 1 ≤ n ≤ 5000, n număr natural;
* 1 < NrDiv ≤ 120, NrDiv este număr natural;
* numele oricărui coleg are maximum 23 de caractere alfabetice;
* numărul maxim de luminițe din instalația de brad va fi 65536 (216).
== Exemplul 1 ==
; lumini.in

1
3
12 Tryp
13 Mike
14 Gymi
; lumini.out

4096
== Explicație ==
Tryp are o instalație cu 60 de luminițe.
Mike are o instalație cu 4096 de luminițe.
Gymi are o instalație cu 192 de luminițe.
 

== Exemplul 2 ==
; lumini.in

2
6
22 Andreea
26 Iustina
40 Iuliana
26 Andreia
27 Corina
30 Raluca
; lumini.out

Iustina
== Explicație ==
Iustina și Andreia, au fiecare câte o instalație cu 12288 de luminițe. Iustina apare prima în listă.
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def calculate_lights(N, messages):
max_divisors = 0
max_lights = 0
owner = ""

for message in messages:
divisors, name = message.split()
divisors = int(divisors)
lights = divisors * (divisors + 1) // 2
if divisors > max_divisors or (divisors == max_divisors and lights > max_lights):
max_divisors = divisors
max_lights = lights
owner = name

return max_lights if N == 1 else owner

def main():
with open("lumini.in", "r") as fin:
choice = int(fin.readline().strip())
N = int(fin.readline().strip())
messages = [fin.readline().strip() for _ in range(N)]

result = calculate_lights(N, messages)

with open("lumini.out", "w") as fout:
fout.write(str(result))

if __name__ == "__main__":
main()

</syntaxhighlight>

3108 - Dss

2024-06-03T16:37:52Z

RebecaBud: Pagină nouă: == Enunt == Se dau N numere naturale s[1], s[2], …, s[N] și Q interogări de forma a b. == Cerinţa == Să se determine pentru fiecare interogare [a;b] numărul de subșiruri formate din elemente distincte ale secvenței s[a], s[a+1], s[a+2], …, s[b]. Prin secvență a șirului s se înțelege orice succesiune de elemente aflate pe poziții consecutive s[a], s[a+1], …, s[b], cu 1 ≤ a ≤ b ≤ N. Prin subșir al șirului s se înțelege orice succesiune de elemente a...

== Enunt ==
Se dau N numere naturale s[1], s[2], …, s[N] și Q interogări de forma a b.
== Cerinţa ==
Să se determine pentru fiecare interogare [a;b] numărul de subșiruri formate din elemente distincte ale secvenței s[a], s[a+1], s[a+2], …, s[b].
Prin secvență a șirului s se înțelege orice succesiune de elemente aflate pe poziții consecutive s[a], s[a+1], …, s[b], cu 1 ≤ a ≤ b ≤ N.
Prin subșir al șirului s se înțelege orice succesiune de elemente aflate pe poziții în ordine strict crescătoare, dar nu neapărat consecutive, sa1, sa2, …, sak cu 1 ≤ a1 < a2 < ... < ak ≤ N.
== Date de intrare ==
Fișierul de intrare dss.in conține pe primul rând numerele N și Q. Pe linia a doua sunt scrise N numere naturale separate prin câte un spațiu. Pe următoarele Q rânduri sunt scrise câte două numere naturale a b@, separate prin spațiu, reprezentând capetele intervalelor de interogare date.
== Date de ieșire ==
În fișierul de ieșire dss.out pe fiecare dintre primele Q rânduri este scris câte un număr natural reprezentând numărul tuturor subșirurilor formate din elemente distincte conținute în secvența din interogarea corespunzătoare.
== Restricţii şi precizări ==
* '''1 ≤ N ≤ 400.000'''
* '''1 ≤ Q ≤ 10.000'''
* '''1 ≤ s[k] ≤ N'''
* '''1 ≤ a ≤ b ≤ N'''
Numărul de subșiruri pentru fiecare interogare vor fi calculate modulo 1.000.000.007
== Exemplul 1 ==
; dss.in

5 3
1 2 3 2 3
1 4
2 5
1 3
; dss.out

11
8
7
== Explicație ==
* - Subșirurile formate din elemente distincte din secvența s[1..4]=(1 2 3 2) sunt 1, 2, 3, 2, 1 2, 1 3, 1 2, 2 3, 3 2, 1 2 3, 1 3 2, deci în total 11 subșiruri.
* - Subșirurile formate din elemente distincte din secvența s[2..5]=(2 3 2 3) sunt 2, 3, 2, 3, 2 3, 2 3, 3 2, 2 3, deci 8 subșiruri.
* - Subșirurile formate din elemente distincte din secvența s[1..3]=(1 2 3) sunt 1, 2, 3, 1 2, 1 3, 2 3, 1 2 3, deci 7 subșiruri.
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def count_subsequences(s, a, b):
MOD = 1000000007
n = len(s)
dp = [0] * (n + 1)
last_seen = [-1] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
dp[i] = (dp[i - 1] * 2) % MOD
if last_seen[s[i - 1]] != -1:
dp[i] = (dp[i] - dp[last_seen[s[i - 1]] - 1] + MOD) % MOD
last_seen[s[i - 1]] = i
return (dp[b] - dp[a - 1] + MOD) % MOD

def main():
with open("dss.in", "r") as fin:
N, Q = map(int, fin.readline().split())
s = list(map(int, fin.readline().split()))
queries = [list(map(int, line.split())) for line in fin]

with open("dss.out", "w") as fout:
for a, b in queries:
fout.write(str(count_subsequences(s, a, b)) + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

3087 - Lego

2024-06-03T16:35:19Z

RebecaBud: Pagină nouă: == Enunt == Crina și Rareș pornesc în călătoria imaginară spre Deva și pentru aceasta fiecare își construiește câte un autocar din piese de lego. Pentru a nu crea blocaje în trafic, intrarea autocarelor în oraș este gestionată de un semnal pe care este scris un număr natural S. Astfel, fiecare autocar ce ajunge în dreptul semnalului, trebuie să aștepte, un număr de minute egal cu valoarea absolută a diferenței dintre S și numărul de identificare al aut...

== Enunt ==
Crina și Rareș pornesc în călătoria imaginară spre Deva și pentru aceasta fiecare își construiește câte un autocar din piese de lego. Pentru a nu crea blocaje în trafic, intrarea autocarelor în oraș este gestionată de un semnal pe care este scris un număr natural S. Astfel, fiecare autocar ce ajunge în dreptul semnalului, trebuie să aștepte, un număr de minute egal cu valoarea absolută a diferenței dintre S și numărul de identificare al autocarului său.

Cei doi copii își împart în mod egal piesele de lego pe care sunt scrise cifre (fiecare copil are același număr de piese ca și celălalt, pentru fiecare cifră în parte), cu care formează numerele de identificare ale celor două autocare. Crina aranjează una lângă alta toate piesele sale și formează cifră cu cifră, numărul N1 de identificare al autocarului ei iar Rareș procedează la fel și formează numărul N2 pentru autocarul său. Pentru ca cele două numere să nu fie identice, copiii stabilesc ca N1 să fie strict mai mic decât numărul S al semnalului, iar numărul N2 strict mai mare decât S. În cazul în care vreunul din cele două numere nu poate fi construit din piesele împărțite, atunci autocarul respectiv va avea identificatorul 0 și va aștepta la semnal până trece celălalt autocar.
== Cerinţa ==
1. Determinați numerele N1 și N2 astfel încât, autocarul fiecărui copil să aștepte cât mai puține minute la semnal.
2. Știind că autocarele celor doi copii au ajuns în același timp în fața semnalului, determinați numărul minim de minute de așteptare ale autocarului care va trece primul de semnal.
== Date de intrare ==
Fișierul de intrare '''lego.in''' conține:
pe prima linie numărul natural C ce poate avea valorile 1 sau 2, reprezentând numărul cerinței;
pe cea de-a doua linie un singur număr natural S cu semnificația din enunț;
pe următoarele linii câte două numere naturale ni și ci, despărțite prin câte un spațiu, cu următoarea semnificație: ni reprezintă numărul pieselor cu cifra ci, pe care le are fiecare copil.
== Date de ieșire ==
Pentru C = 1, fișierul de ieșire lego.out va conține pe prima linie două numere naturale N1 și N2, în această ordine, despărțite printr-un spațiu, determinate conform cerinței 1.
Pentru C = 2, fișierul de ieșire lego.out va conține pe prima linie, un singur număr natural determinat conform cerinței 2.
== Restricţii şi precizări ==
* '''1 ≤ S ≤ 1018''';
* fiecare copil are cel mult 19 piese;
* cifrele ci sunt distincte;
* pentru rezolvarea corectă a cerinței 1 se acordă 60 de puncte iar pentru rezolvarea corectă a cerinței 2 se acordă 40 de puncte.
== Exemplul 1 ==
; lego.in

1
153
1 7
3 4
; lego.out

0 4447
== Explicație =
Se rezolvă doar cerința 1. Pe semnal este scris numărul 153. Fiecare copil are 3 piese cu cifra 4 și o piesă cu cifra 7. Crina nu poate construi cu aceste piese un număr mai mic decât 153, de aceea autocarul său este identificat cu numărul 0. Rareș construiește numărul N2 = 4447.
 

== Exemplul 2 ==
; lego.in

2
42
1 3
1 5
; lego.out

7
== Explicație ==
Se rezolvă doar cerința 2. Pe semnal este scris numărul 42. Fiecare copil are o cifră de 3 și o cifră de 5. Crina construiește numărul N1 = 35 și așteaptă la semnal 42 - 35 = 7 minute. Rareș construiește numărul N2 = 53 și așteaptă la semnal 53 - 42 = 11 minute. Numărul minim al minutelor de așteptare este 7.
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def build_number(pieces):
number = 0
for i, piece in enumerate(pieces):
number += piece * 10 ** i
return number

def main():
with open("lego.in", "r") as fin:
c = int(fin.readline())
s = int(fin.readline())
pieces = [list(map(int, fin.readline().split())) for _ in range(2)]

if c == 1:
n1_pieces = [min(pieces[0][i], s) for i in range(10)]
n2_pieces = [min(pieces[1][i], s) for i in range(10)]

n1 = build_number(n1_pieces)
n2 = build_number(n2_pieces)

print(n1, n2)

elif c == 2:
min_wait = float('inf')
for i in range(1, s):
n1_pieces = [min(pieces[0][j], i) for j in range(10)]
n2_pieces = [min(pieces[1][j], s - i) for j in range(10)]
n1 = build_number(n1_pieces)
n2 = build_number(n2_pieces)
wait = abs(s - n1) + abs(s - n2)
min_wait = min(min_wait, wait)

print(min_wait)

if __name__ == "__main__":
main()

</syntaxhighlight>

2438 - Pal

2024-06-03T16:30:18Z

RebecaBud: Pagină nouă: == Enunt == Micul Prinț a ajuns în țara numerelor palindrom cu număr impar de cifre unde a primit de la sfetnicul regelui o listă care conține N numere naturale, fiecare cu număr impar de cifre. Un număr este palindrom dacă prima lui cifră este egală cu ultima, a doua cu penultima, ș.a.m.d. Acesta i-a transmis că regele este foarte bolnav. Odată cu regele, numerele din listă s-au îmbolnăvit și ele. Sfetnicul i-a spus că lista corectă poate fi obținută p...

== Enunt ==

Micul Prinț a ajuns în țara numerelor palindrom cu număr impar de cifre unde a primit de la sfetnicul regelui o listă care conține N numere naturale, fiecare cu număr impar de cifre. Un număr este palindrom dacă prima lui cifră este egală cu ultima, a doua cu penultima, ș.a.m.d. Acesta i-a transmis că regele este foarte bolnav. Odată cu regele, numerele din listă s-au îmbolnăvit și ele. Sfetnicul i-a spus că lista corectă poate fi obținută prin înlocuirea fiecărui număr din ea cu cel mai mic palindrom mai mare sau egal cu numărul respectiv.
După ce a urmat recomandarea sfetnicului, Micul Prinț a constatat că în lista corectă obținută toate palindromurile sunt distincte. Uitându-se mai cu atenție la palindromurile din această listă, a observat că există perechi de palindromuri în care cel mai mic se poate obține din cel mai mare prin ștergerea aceluiași număr de cifre de la ambele capete. De exemplu pentru perechea 7531357 și 313 palindromul 313 se obține din 7531357 prin eliminarea a câte două cifre de la ambele capete ale sale.
Considerăm un șir de palindromuri din lista corectă și notăm cu X valoarea maximă a acestui șir. Vom spune că șirul este magic dacă toate palindromurile din el se pot obține după metoda descrisă mai sus, din palindromul de valoare X. Un exemplu de șir magic este 4, 53435, 7534357, 89753435798, presupunând că toate aceste numere se regăsesc în lista corectă.
== Cerinţa ==
Scrieți un program care citește numerele din lista primită de la sfetnicul regelui și afișează:
1) Lista corectă obținută de Micul Prinț;
2) Numărul de elemente ale celui mai lung șir magic care se poate obține din lista corectă;
3) Palindromurile din care este format cel mai lung șir magic, afișate în ordine crescătoare. Dacă există mai multe astfel de șiruri în lista corectă a Micului Prinț, se va afișa cel în care ultimul număr este cel mai mare.
== Date de intrare ==
Fișierul de intrare '''pal.in''' conţine pe prima linie numărul natural P, care nu poate avea decât valorile 1, 2 sau 3 și indică numărul cerinței care va fi rezolvată. Pe a doua linie numărul natural N de numere de pe lista primită de la sfetnicul regelui. Pe a treia linie se află numerele naturale din lista primită de la sfetnic, separate prin câte un spațiu.
== Date de ieșire ==
Fișierul de ieșire '''pal.out''' va conţine pe prima linie răspunsul la cerința rezolvată. Dacă s-a rezolvat prima cerință, fișierul de ieșire va conține un șir de N numere naturale, separate prin câte un spațiu, reprezentând numerele din lista corectă, în ordinea corespunzătoare listei inițiale. Dacă s-a rezolvat cerința 2, pe prima linie a fișierului de ieșire se va scrie lungimea celui mai lung șir magic. Dacă s-a rezolvat cerința 3, fișierul de ieșire va conține numerele determinate și afișate conform cerinței.
== Restricţii şi precizări ==
* '''0 < N ≤ 50.000''';
* Numerele de pe lista sfetnicului sunt naturale nenule și fiecare are cel mult 17 cifre;
* Pentru rezolvarea corectă a primei cerinţe se acordă 20 de puncte, pentru rezolvarea corectă a celei de a doua cerințe se acordă 20 de puncte, iar pentru rezolvarea corectă a celei de a treia cerințe se acordă 50 de puncte.
* În concurs s-au acordat 10 puncte din oficiu. Aici se vor acorda pentru exemplele din enunț.
== Exemplul 1 ==
; pal.in

1
3
345 214 64325
; pal.out

353 222 64346
== Explicație ==
Șirul palindromurilor de pe lista corectă obținută de Micul Prinț.
 

== Exemplul 2 ==
; pal.in

2
8
2 3 120 4 432 5643461 7 21211
; pal.out

3
== Explicație ==
Lista corectă conține palindromurile 2 3 121 4 21212 434 5643465 7 și cel mai lung șir magic este 3 434 5643465.
 

== Exemplul 3 ==
; pal.in

3
8
2 3 5643461 7 120 4 21211 432
; pal.out

3 434 5643465
== Explicație ==
Șirul magic 2 121 21212 are aceeași lungime dar se termină într-un număr mai mic.
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def is_palindrome(num):
return str(num) == str(num)[::-1]

def next_palindrome(num):
num += 1
while not is_palindrome(num):
num += 1
return num

def prev_palindrome(num):
num -= 1
while not is_palindrome(num):
num -= 1
return num

def find_longest_magic_sequence(palindromes):
n = len(palindromes)
dp = [[0] * n for _ in range(n)]
max_length = 1

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

for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if length == 2 and palindromes[i] == palindromes[j]:
dp[i][j] = 2
max_length = max(max_length, 2)
elif palindromes[i] == palindromes[j] and dp[i + 1][j - 1] == length - 2:
dp[i][j] = length
max_length = max(max_length, length)

return max_length

def main():
with open("pal.in", "r") as fin:
p = int(fin.readline())
n = int(fin.readline())
numbers = list(map(int, fin.readline().split()))

if p == 1:
correct_numbers = [next_palindrome(num) for num in numbers]
with open("pal.out", "w") as fout:
fout.write(" ".join(map(str, correct_numbers)))
elif p == 2:
max_length = find_longest_magic_sequence(numbers)
with open("pal.out", "w") as fout:
fout.write(f"{max_length}\n")
elif p == 3:
max_length = find_longest_magic_sequence(numbers)
max_palindromes = []
for i in range(n):
for j in range(i + 1, n):
if numbers[i] == numbers[j]:
palindromes = [numbers[k] for k in range(i, j + 1)]
if find_longest_magic_sequence(palindromes) == max_length:
max_palindromes = palindromes
with open("pal.out", "w") as fout:
fout.write(" ".join(map(str, max_palindromes)))

if __name__ == "__main__":
main()

</syntaxhighlight>

2157 - Bomboane 3

2024-06-03T16:26:33Z

RebecaBud: Pagină nouă: == Enunt == Zeno are n cutii cu bomboane, iar în fiecare cutie se găsește un număr natural nenul de bomboane. Zeno poate împărți bomboanele din toate cutiile colegilor în două moduri: frățește sau diferențiat. Împărțirea frățească se realizează astfel: numărul de colegi care primesc bomboane din fiecare cutie este același (dacă din prima cutie primesc bomboane k colegi și din cutia 2 vor primi tot k colegi, și din cutia 3 tot k colegi etc). bomboanel...

== Enunt ==
Zeno are n cutii cu bomboane, iar în fiecare cutie se găsește un număr natural nenul de bomboane. Zeno poate împărți bomboanele din toate cutiile colegilor în două moduri: frățește sau diferențiat. Împărțirea frățească se realizează astfel:

numărul de colegi care primesc bomboane din fiecare cutie este același (dacă din prima cutie primesc bomboane k colegi și din cutia 2 vor primi tot k colegi, și din cutia 3 tot k colegi etc).
bomboanele din fiecare cutie se împart în mod egal între cei k colegi, aceștia primind un număr nenul de bomboane;
în final în fiecare cutie trebuie să rămână un număr identic de bomboane (posibil zero) care îi revin lui Zeno. De exemplu dacă n = 3, iar în cutii se găsesc 14, 23 respectiv 17 bomboane, din prima cutie oferă câte 4 bomboane pentru 3 colegi, din a doua cutie câte 7 bomboane pentru 3 colegi, iar din ultima cutie câte 5 bomboane pentru 3 colegi, iar în fiecare cutie rămân 2 bomboane.
Împărțirea diferențiată se realizează în felul următor:

dintre colegii care primesc bomboane din aceeași cutie fiecare coleg primește un număr diferit de bomboane (număr nenul), neexistând doi colegi care primesc număr identic de bomboane din aceeași cutie;
din fiecare cutie Zeno oferă bomboane unui număr cât mai mare de colegi.
diferențele în modul dintre numărul de bomboane primite consecutiv de doi colegi sunt distincte două câte două. De exemplu dacă n = 3, iar în cutii se găsesc 14, 23 respectiv 17 bomboane, bomboanele din prima cutie se pot împărți astfel (3, 4, 6, 1), bomboanele din a doua cutie (6, 2, 7, 1, 3, 4), iar bomboanele din a treia cutie se pot împărți astfel (2, 1, 3, 7, 4).
== Cerinţa ==
Cunoscând n numărul de cutii și numărul de bomboane din fiecare cutie să se scrie un program care determină:

a) Numărul maxim de colegi care pot primi bomboane, dacă Zeno alege împărțirea frățească.
b) O modalitate de împărțire a bomboanelor din fiecare cutie, dacă se face împărțirea diferențiată.
== Date de intrare ==
Fișierul de intrare '''bomboane3.in''' conține pe prima linie două numere naturale p (numărul cerinței de rezolvat), și n (numărul de cutii), despărțite printr-un spațiu. Pe următoarea linie se găsesc n valori naturale, separate prin câte un spațiu, reprezentând numărul de bomboane din fiecare cutie.
== Date de ieșire ==
Dacă p = 1 se va rezolva numai punctul a) din cerință. În acest caz fișierul de ieșire bomboane3.out va conține o valoare naturală reprezentând numărul maxim de colegi care pot primi bomboane, dacă Zeno alege împărțirea frățească.
Dacă p = 2 se rezolvă numai punctul b). Fișierul de ieșire bomboane3.out va conține n linii. Pe fiecare linie i, prima valoare nri reprezintă numărul maxim de colegi care pot primi bomboane din cutia i, urmată de nri valori separate prin câte un spațiu reprezentând o modalitate de împărțire a bomboanelor din cutia i, dacă Zeno alege împărțirea diferențiată.
== Restricţii şi precizări ==
* '''1 ≤ p ≤ 2''';
* Dacă p = 1 atunci 1 ≤ n ≤ 10 000 și 1 ≤ numărul de bomboane din cutii ≤ 106.
* Dacă p = 2 atunci 1 ≤ n ≤ 200 și 1 ≤ numărul de bomboane din cutii ≤ 100 000.
* Dacă există mai multe soluții se poate afișa oricare.
* Pentru rezolvarea fiecărei cerințe se acordă 50% din punctaj.
== Exemplul 1 ==
; bomboane3.in

1 3
14 23 17
; bomboane3.out

3
== Explicație ==
Se rezolvă numai punctul a). Numărul maxim de colegi care pot primi bomboane dacă Zeno alege împărțirea frățească e 3.

 

== Exemplul 2 ==
; bomboane3.in

2 3
14 23 17
; bomboane3.out

4 3 4 6 1
6 6 2 7 1 3 4
5 2 1 3 7 4
== Explicație ==
Se rezolvă numai punctul b). Din prima cutie pot primi bomboane maxim 4 colegi. O modalitate de împărțire astfel încât fiecare coleg să primească un număr diferit de bomboane, iar diferențele dintre bomboanele primite de doi colegi consecutivi să fie distincte două câte două este (3,4,6,1). Este corectă și soluția (1, 2, 7, 4).
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def max_colleagues_fraternally(boxes):
min_bombs = min(boxes)
max_colleagues = 0
for i in range(1, min_bombs + 1):
valid = True
for box in boxes:
if box % i != 0:
valid = False
break
if valid:
max_colleagues = max(max_colleagues, i)
return max_colleagues

def division_differently(boxes):
min_bombs = min(boxes)
max_colleagues = min_bombs
result = []
for box in boxes:
diff = max_colleagues - min_bombs
curr_division = [min_bombs + i * (diff + 1) for i in range(min_bombs)]
result.append((max_colleagues, curr_division))
return result

def main():
with open("bomboane3.in", "r") as fin:
p, n = map(int, fin.readline().split())
boxes = list(map(int, fin.readline().split()))

if p == 1:
max_colleagues = max_colleagues_fraternally(boxes)
with open("bomboane3.out", "w") as fout:
fout.write(f"{max_colleagues}\n")
elif p == 2:
divisions = division_differently(boxes)
with open("bomboane3.out", "w") as fout:
for division in divisions:
fout.write(f"{division[0]} {' '.join(map(str, division[1]))}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

1969 - P Digit

2024-06-03T16:23:06Z

RebecaBud: Pagină nouă: == Enunt == Fie a un număr natural scris în baza 10. Notăm cu b, baza minimă în care poate fi scris a. Astfel, dacă a=21756, atunci baza minimă în care acesta poate fi scris este b=8. Definim ''''cifra de control''' a numărului a scris în baza b, notată cu c=digit(a)b, ca fiind numărul de o cifră obținut prin adunarea în baza b a cifrelor numărului a. Dacă rezultatul obținut este de o cifră, atunci acesta reprezintă valoarea lui c, dacă nu, se aplică re...

== Enunt ==
Fie a un număr natural scris în baza 10. Notăm cu b, baza minimă în care poate fi scris a. Astfel, dacă a=21756, atunci baza minimă în care acesta poate fi scris este b=8.

Definim ''''cifra de control''' a numărului a scris în baza b, notată cu c=digit(a)b, ca fiind numărul de o cifră obținut prin adunarea în baza b a cifrelor numărului a. Dacă rezultatul obținut este de o cifră, atunci acesta reprezintă valoarea lui c, dacă nu, se aplică repetat asupra rezultatului procedeul de însumare a cifrelor în baza b până când se obține o cifră.

De exemplu:

c=digit(21756)8=digit(2+1+7+5+6)8=25, întrucât c>8 procedeul continuă
c=digit(25)8=digit(2+5)8=7.
== Cerinţa ==
Se consideră un interval închis [x,y]. Să se determine:

* a – primul număr prim mai mare sau egal ca x
* b – baza minimă în care poate fi scris numărul prim a
* c – cifra de control a numărului prim a
* n – numărul de numere prime din intervalul [x,y] ce pot fi scrise în baza b și au cifra de control egală cu c.
== Date de intrare ==
Fișierul de intrare '''pdigit.in''' conține pe o singură linie două valori natural x și y cu semnificația din enunț.
== Date de ieșire ==
Fișierul de ieșire '''pdigit.out''' va conține patru valori naturale a, b, c și n, scrise fiecare pe câte o linie, valori ce reprezintă în ordine: primul număr prim strict mai mare sau egal ca x, baza minimă în care poate fi scris numărul prim a, cifra de control a numărului prim a, numărul de numere prime scrise în baza b din intervalul [x,y] care au cifra de control egală cu c.
== Restricţii şi precizări ==
* '''1 ≤ x ≤ y ≤ 5000000'''
* intervalul [x,y] conține cel puțin un număr prim
* rezolvarea primei cerințe asigură 10% din punctaj
* rezolvarea cerinței a doua asigură 10% din punctaj
* rezolvarea cerinței a treia asigură 20% din punctaj
* Rezolvarea ultimei cerințe asigură 60% din punctaj
== Exemplul 1 ==
; pdigit.in

15 75
; pdigit.out

17
8
1
3
== Explicație ==
Primul număr prim din interval este 17. Baza minimă în care poate fi scris numărul prim este 8.
* Cifra de contro a numărului prim este 1. Sunt 3 numere prime în intervalul dat ce pot fi scrise în baza 8, și au cifra de control egală cu 1: 17, 53, 71.
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def is_prime(n):
if n <= 1:
return False
if n <= 3:
return True
if n % 2 == 0 or n % 3 == 0:
return False
i = 5
while i * i <= n:
if n % i == 0 or n % (i + 2) == 0:
return False
i += 6
return True

def digit_sum(num, base):
result = sum(int(digit, base=base) for digit in str(num))
while result >= base:
result = sum(int(digit, base=base) for digit in str(result))
return result

def prime_in_interval(x, y):
for num in range(x, y+1):
if is_prime(num):
return num
return None

def minimum_base(prime):
return min(prime, 8)

def control_digit(prime, base):
return digit_sum(prime, base)

def primes_with_control_digit(x, y, base, control_digit):
count = 0
for num in range(x, y+1):
if is_prime(num):
if digit_sum(num, base) == control_digit:
count += 1
return count

def main():
with open("pdigit.in", "r") as fin:
x, y = map(int, fin.readline().split())

prime = prime_in_interval(x, y)
base = minimum_base(prime)
control = control_digit(prime, base)
count = primes_with_control_digit(x, y, base, control)

with open("pdigit.out", "w") as fout:
fout.write(f"{prime}\n")
fout.write(f"{base}\n")
fout.write(f"{control}\n")
fout.write(f"{count}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

1968 - Bloc

2024-06-03T16:19:27Z

RebecaBud: Pagină nouă: == Cerinţa == Cifrele de la 1 la K se scriu într-un şir, iar secvenţa obţinută se repetă la nesfârşit. De exemplu, pentru K=9 se obţine şirul: 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 …. Asupra unui asemenea şir se aplică succesiv operaţia de rostogolire de lungime P, ce presupune ca blocul format cu cifrele de pe primele P poziţii să se rotească cu 1800 şi să se scrie deasupra următoarei secvenţe de lungime P. În cazul exemplului anterior...

== Cerinţa ==
Cifrele de la 1 la K se scriu într-un şir, iar secvenţa obţinută se repetă la nesfârşit. De exemplu, pentru K=9 se obţine şirul: 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 …. Asupra unui asemenea şir se aplică succesiv operaţia de rostogolire de lungime P, ce presupune ca blocul format cu cifrele de pe primele P poziţii să se rotească cu 1800 şi să se scrie deasupra următoarei secvenţe de lungime P. În cazul exemplului anterior, pentru P=3, vom obţine după 4 operaţii de rostogolire de lungime 3:
Pas 1: 3 2 1
4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9…

Pas 2: 6 5 4
1 2 3
7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9…

Pas 3: 9 8 7
3 2 1
4 5 6
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9…

Pas 4: 3 2 1
6 5 4
1 2 3
7 8 9
4 5 6 7 8 9 1 2 3 4 5 6 7 8 9…
Astfel pe primele P poziţii se formează un bloc având la bază P cifre şi înălţimea N+1, unde N este numărul de rostogoliri de lungime P.
Pentru K, P şi N date se cer următoarele:
a) Suma elementelor blocului după N rostogoliri de lungime P.
b) Suma maximă a elementelor de pe o coloană a blocului după N rostogoliri de lungime P.
c) Dacă liniile blocului le privim ca pe nişte numere cu P cifre, să se afle cel mai mic dintre aceste numere ale blocului obţinut după N rostogoliri de lungime P.
== Date de intrare ==
Fişierul de intrare bloc.in conţine pe prima linie numerele K, P şi N ce reprezintă cifra maximă din şirul iniţial, lungimea secvenţei care se rostogoleşte, respectiv numărul de rostogoliri.
== Date de ieșire ==
Fişierul de ieşire bloc.out va conţine pe prima linie suma elementelor blocului după N rostogoliri, pe a doua linie suma maximă a elementelor unei coloane a blocului după N rostogoliri, iar pe a treia linie numărul minim format din cifrele unei linii a blocului după N rostogoliri.
== Restricţii şi precizări ==
* '''1 ≤ K ≤ 9'''
* '''1 ≤ P ≤ 100'''
* '''1 ≤ N ≤ 1.000.000'''
* Prima cerinţă se notează cu 40p, a doua cu 40p, iar a treia cu 20p
== Exemplul 1 ==
; bloc.in

9 3 4
; bloc.out

66
23
123
== Explicație ==
Datele corespund exemplului de mai sus. La pasul 4 suma elementelor blocului este 66, coloana a treia a blocului are suma 1+4+3+9+6=23 care este maximă, iar cifrele de pe linia a treia a blocului formează numărul minim 123.
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def rotate_sequence(sequence, P):
return sequence[P-1::-1] + sequence[P:]

def rotate_block(block, P):
return [rotate_sequence(row, P) for row in block]

def sum_block(block):
return sum(sum(row) for row in block)

def max_column_sum(block):
max_sum = 0
for j in range(len(block[0])):
column_sum = sum(block[i][j] for i in range(len(block)))
max_sum = max(max_sum, column_sum)
return max_sum

def min_line_number(block):
min_number = int(''.join(map(str, block[0])))
for row in block[1:]:
number = int(''.join(map(str, row)))
min_number = min(min_number, number)
return min_number

def main():
with open("bloc.in", "r") as fin:
K, P, N = map(int, fin.readline().split())

sequence = [i % K + 1 for i in range(K * 2)]
block = [sequence[i:i+P] for i in range(0, P*(N+1), P)]

for _ in range(N):
block = rotate_block(block, P)

sum_elements = sum_block(block)
max_column = max_column_sum(block)
min_line = min_line_number(block)

with open("bloc.out", "w") as fout:
fout.write(f"{sum_elements}\n")
fout.write(f"{max_column}\n")
fout.write(f"{min_line}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

1499 - Broscute

2024-06-03T16:16:49Z

RebecaBud: Pagină nouă: == Enunt == Pe un lac cu apă termală se află n+1 frunze de nuferi. Pe n dintre ele stau la soare n broscuțe. Evident, o frunză este liberă și broscuţele au început să se joace. În fiecare moment o broscuță sare de pe frunza ei pe frunza liberă din acel moment. == Cerinţa == Numerotând frunzele de la 1 la n+1, broscuțele de la 1 la n, şi cunoscându-se ordinea inițială a broscuțelor pe cele n+1 frunze, să se determine numărul minim de sărituri ale brosc...

== Enunt ==
Pe un lac cu apă termală se află n+1 frunze de nuferi. Pe n dintre ele stau la soare n broscuțe. Evident, o frunză este liberă și broscuţele au început să se joace. În fiecare moment o broscuță sare de pe frunza ei pe frunza liberă din acel moment.
== Cerinţa ==
Numerotând frunzele de la 1 la n+1, broscuțele de la 1 la n, şi cunoscându-se ordinea inițială a broscuțelor pe cele n+1 frunze, să se determine numărul minim de sărituri ale broscuțelor de pe o frunză pe alta, astfel încât ele să se găsească într-o ordine finală, dată, precum şi săriturile realizate.
== Date de intrare ==
Fișierul de intrare '''broscute.in''' conține pe prima linie un număr natural n reprezentând numărul de broscuțe separat printr-un spațiu de un număr natural t, care reprezintă cerința: 1, dacă se cere numărul de sărituri, respectiv 2 dacă se cere ordinea săriturilor. Linia a doua conține n+1 numere naturale reprezentând configurația inițială a broscuțelor pe cele n+1 frunze, iar linia a treia conține n+1 numere naturale reprezentând configurația finală a broscuțelor pe cele n+1 frunze.
== Date de ieșire ==
Fișierul de ieșire '''broscute.out''' va conține pe prima linie un număr natural k ce reprezintă numărul minim de sărituri, dacă cerința este 1. Dacă cerința este 2 fișierul de ieșire va conține mai multe linii, pe fiecare dintre ele existând 3 numere naturale b s d, separate prin câte un spațiu, care descriu săritura, reprezentând numărul broscuței b, frunza de pe care sare s și frunza pe care sare d. În cazul în care la cerința 2 broscuțele nu fac nici o săritură se va afișa pe prima linie mesajul ''''broscutele nu se joaca'''.
== Restricţii şi precizări ==
* '''2 ≤ n ≤ 1000'''
* În descrierea configurațiilor din fișierul de intrare frunza liberă este reprezentată prin valoarea 0
* Pentru cerința 1 se acordă 50% din punctaj, iar pentru cerința 2 tot 50% din punctaj.
* În cazul în care cerința este 2 și numărul de sărituri afișate nu este minim dar realizează ajungerea la configurația finală se acordă doar 30% din punctaj.
== Exemplul 1 ==
; broscute.in

4 2
3 2 0 1 4
1 2 3 4 0
; broscute.out

3 1 3
1 4 1
4 5 4
== Explicație ==
Sunt 4 broscuţe, deci 5 frunze de nufăr. Cerinţa este 2.

* Broscuţele vor face 3 sărituri:
* broscuţa 3 sare de pe frunza 1 pe frunza 3
* broscuţa 1 sare de pe frunza 4 pe frunza 1
* broscuţa 4 sare de pe frunza 5 pe frunza 4
 

== Exemplul 2 ==
; broscute.in

4 1
3 2 0 1 4
1 2 3 4 0
; broscute.out

3

 

== Exemplul 3 ==
; broscute.in

4 2
3 2 0 1 4
3 2 0 1 4
; broscute.out

broscutele nu se joaca

 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def min_jumps_or_order(n, initial_config, final_config, request):
if request == 1:
return min_jumps(n, initial_config, final_config)
elif request == 2:
return min_jumps_order(n, initial_config, final_config)

def min_jumps(n, initial_config, final_config):
jumps = 0
for i in range(n+1):
if initial_config[i] != final_config[i]:
jumps += 1
return jumps

def min_jumps_order(n, initial_config, final_config):
jumps = []
for i in range(n+1):
if initial_config[i] != final_config[i]:
for j in range(i+1, n+1):
if final_config[i] == initial_config[j]:
jumps.append((j, initial_config.index(final_config[i]), i))
initial_config[j], initial_config[i] = initial_config[i], initial_config[j]
break
if not jumps:
return "broscutele nu se joaca"
return jumps

def main():
with open("broscute.in", "r") as fin:
n, request = map(int, fin.readline().split())
initial_config = list(map(int, fin.readline().split()))
final_config = list(map(int, fin.readline().split()))

result = min_jumps_or_order(n, initial_config, final_config, request)

with open("broscute.out", "w") as fout:
if request == 1:
fout.write(f"{result}\n")
elif request == 2:
if isinstance(result, str):
fout.write(result)
else:
fout.write('\n'.join([' '.join(map(str, jump)) for jump in result]))

if __name__ == "__main__":
main()

</syntaxhighlight>

0141 - Compuneri

2024-06-03T16:12:32Z

RebecaBud: Pagină nouă: == Enunt == După descoperirea vieţii pe planeta Marte, cercetătorii pământeni au început activitatea de studiere a fiinţelor vii marţiene. Prima constatare a fost că este o legătură strânsă între modul de formare a acestora şi numerele naturale. Astfel, unei specii i s-a asociat un număr natural mai mare decât 1. Mai mult, oricare două specii se pot compune, rezultând altă specie. Numărul asociat noii specii este dat de produsul numerelor asociate celor...

== Enunt ==

După descoperirea vieţii pe planeta Marte, cercetătorii pământeni au început activitatea de studiere a fiinţelor vii marţiene. Prima constatare a fost că este o legătură strânsă între modul de formare a acestora şi numerele naturale. Astfel, unei specii i s-a asociat un număr natural mai mare decât 1. Mai mult, oricare două specii se pot compune, rezultând altă specie. Numărul asociat noii specii este dat de produsul numerelor asociate celor două specii care se compun. Astfel, modalitatea de obţinere a unei specii nu este unică (o specie ce are asociat numărul 12 se poate obţine compunând specia 2 cu specia 6, sau specia 3 cu specia 4). Evident, unele specii se pot obţine prin compunerea altora (ex. 12) dar unele nu se pot obţine prin compunere. Pe acestea din urmă le vom numi atomi (de exemplu specia ce are asociat codul 7 este atom, şi mai sunt şi altele). O specie se poate compune cu ea însăşi rezultând altă specie (de exemplu, prin compunerea speciei 3 cu ea însăşi se obţine specia 9). De asemenea, dacă specia X se poate obţine prin compunerea speciilor Y şi Z spunem că X are în compoziţie pe Y şi pe Z. Mai mulţi cercetători au recoltat probe obţinând astfel o listă de coduri ale speciilor pe care le-au observat.
== Cerinţa ==
Scrieţi un program care, pe baza codurilor din lista formată, să determine:
a) numărul de atomi din listă;
b) numărul de specii din listă care nu pot avea în compoziţie niciun atom dintre cei aflaţi în listă;
== Date de intrare ==
Fişierul compuneri.in conţine pe prima linie un număr natural N. Pe linia a doua se află N numere naturale separate prin câte un spaţiu. Acestea reprezintă codurile speciilor din listă.
== Date de ieșire ==
Fişierul compuneri.out va conţine pe prima linie două valori naturale separate printr-un spaţiu, ce reprezintă numerele din cerinţă: (primul număr va fi valoarea calculată pentru cerinţa a) ).
== Restricţii şi precizări ==
* 1 <= N <= 100000;
* 2 <= numerele din listă ≤ 100000;
* Numerele din listă se pot repeta iar la rezultat se va contoriza fiecare apariţie;
== Exemplul 1 ==
; compuneri.in

10
7 7 121 11 3 29 32 3 1300 17
; compuneri.out

7 2
== Explicație ==

În listă sunt 7 atomi: 7, 7, 11, 3, 29, 3, 17

Dintre celelalte trei valori, 121 se formează prin compunerea atomului existent 11 cu el însuşi iar celelalte două nu se pot obţine prin compuneri ale atomilor existenţi.
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def count_atoms_and_species(species_codes):
atoms = set()
for code in species_codes:
factors = set()
for i in range(2, int(code**0.5) + 1):
if code % i == 0:
factors.add(i)
factors.add(code // i)
if len(factors) == 0:
atoms.add(code)
return len(atoms), len(species_codes) - len(atoms)

def main():
with open("compuneri.in", "r") as fin:
N = int(fin.readline().strip())
species_codes = list(map(int, fin.readline().split()))

atom_count, species_count = count_atoms_and_species(species_codes)

with open("compuneri.out", "w") as fout:
fout.write(f"{atom_count} {species_count}")

if __name__ == "__main__":
main()

</syntaxhighlight>

1086 - Submit

2024-06-03T16:08:32Z

RebecaBud: Pagină nouă: == Enunt == Vasilică se antrenează pe un site de probleme cu evaluare online. Când el trimite pe site soluţia la o problemă, aceasta este evaluată pe un anumit număr de teste. Punctajul obţinut la problema respectivă va fi egal cu suma punctajelor obţinute la fiecare test. Punctajele asociate testelor pot fi diferite. În plus, dacă problema a fost complet rezolvată (a obţinut punctaj maxim la toate testele), Vasilică primeşte şi un bonus. Vasilică poate tri...

== Enunt ==
Vasilică se antrenează pe un site de probleme cu evaluare online. Când el trimite pe site soluţia la o problemă, aceasta este evaluată pe un anumit număr de teste. Punctajul obţinut la problema respectivă va fi egal cu suma punctajelor obţinute la fiecare test. Punctajele asociate testelor pot fi diferite. În plus, dacă problema a fost complet rezolvată (a obţinut punctaj maxim la toate testele), Vasilică primeşte şi un bonus.

Vasilică poate trimite soluţia la o problemă de mai multe ori. Când trimite soluţia prima dată, punctajul se calculează în modul prezentat anterior. Când trimite soluţia a doua oară, Vasilică va fi penalizat cu două puncte (adică din punctajul total obţinut la problemă se scad două puncte). Când trimite soluţia a treia oară penalizarea este de 4 puncte, a patra oară de 6 puncte ş.a.m.d. Observaţi că la fiecare nouă încercare penalizarea creşte cu două puncte.
== Cerinţa ==
Date fiind rezultatele obţinute pe teste de Vasilică la fiecare soluţie trimisă, să se determine punctajul maxim pe care el l-a obţinut la problema respectivă.
== Date de intrare ==
Fișierul de intrare '''submit.in''' conține pe prima linie numărul natural N reprezentând numărul de teste pe care este evaluată soluţia. Pe cea de a doua linie se află N numere naturale separate prin spaţii P1 P2 … PN, reprezentând în ordine punctajul acordat pentru fiecare dintre cele N teste. Pe cea de a treia linie se află numărul natural B reprezentând bonusul (numărul de puncte acordate în cazul în care pentru toate testele soluţia obţine punctaj pe toate testele). Pe a patra linie este scris un număr natural M reprezentând numărul de soluţii trimise de Vasilică la problemă. Urmează M linii, fiecare linie conţinând rezultatele obţinute pe teste la cele M soluţii trimise de Vasilică, în ordinea trimiterii lor. Pe cea de a i-a linie (1≤i≤M) dintre cele M sunt scrise N valori din mulţimea {0, 1}, separate prin spaţii; a j-a valoare (1≤j≤N) este 0 dacă testul j nu a fost rezolvat corect, respectiv 1 dacă testul j a fost corect rezolvat (obţinând punctajul maxim alocat pe test).
== Date de ieșire ==
Fișierul de ieșire '''submit.out''' va conţine o singură linie pe care va fi scris punctajul maxim obţinut de Vasilică la problema respectivă.
== Restricţii şi precizări ==
* '''1 ≤ N, M ≤ 100'''
* '''0 ≤ Pi ≤ 100''', pentru orice 1 ≤ i ≤ N
* '''0 ≤ B ≤ 100'''
== Exemplul 1 ==
; submit.in

4
10 5 5 20
13
3
0 0 0 0
1 1 1 1
0 1 0 1
; submit.out

51
== Explicație==

Problema este evaluată pe 4 teste. Punctajele acordate pe teste sunt 10, 5, 5 şi respectiv 20. În cazul în care toate testele sunt rezolvate corect, se acordă 13 puncte bonus.

La această problemă Vasilică trimite 3 surse.

Prima sursă trimisă nu rezolvă corect niciun test, deci obţine 0 puncte.

A doua sursă trimisă rezolvă corect toate testele, primind 10+5+5+20=40 puncte pe teste, la care se adaugă 13 puncte bonus; dar fiind a doua soluţie trimisă se aplică o penalizare de două puncte. În total 40+13-2=51 puncte.

A treia sursă trimisă rezolvă numai teste 2 şi 4 deci obţine 5+20=25 puncte şi este penalizată cu 4 puncte, deci punctajul total este 21.

Punctajul maxim obţinut de Vasilică este prin urmare 51.
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def max_score(N, points, bonus, M, solutions):
max_score = 0
penalty = 0

for i in range(M):
correct_tests = sum(solutions[i])
score = sum(points[j] for j in range(N) if solutions[i][j] == 1)
score += bonus if correct_tests == N else 0
score -= penalty
max_score = max(max_score, score)
penalty += 2

return max_score

def main():
with open("submit.in", "r") as fin:
N = int(fin.readline().strip())
points = list(map(int, fin.readline().split()))
bonus = int(fin.readline().strip())
M = int(fin.readline().strip())
solutions = [list(map(int, fin.readline().split())) for _ in range(M)]

max_score_value = max_score(N, points, bonus, M, solutions)

with open("submit.out", "w") as fout:
fout.write(str(max_score_value))

if __name__ == "__main__":
main()

</syntaxhighlight>

1213 - Iepuras

2024-06-03T16:04:38Z

RebecaBud: Pagină nouă: == Enunt == Iepurașul Coconaș vrea să ajungă la grădina cu morcovi. Pentru aceasta el trebuie să traverseze prin salturi o zonă cu proprietăți speciale. Zona este formată din N căsuțe numerotate de la 1 la N, dispuse una după cealaltă, iar fiecare căsuță conține un număr natural ce reprezintă cantitatea de energie necesară iepurașului pentru a sări într-o altă căsuță. Iepurașul pleacă dintr-o anumită căsuță și se deplasează, de la stânga...

== Enunt ==

Iepurașul Coconaș vrea să ajungă la grădina cu morcovi. Pentru aceasta el trebuie să traverseze prin salturi o zonă cu proprietăți speciale. Zona este formată din N căsuțe numerotate de la 1 la N, dispuse una după cealaltă, iar fiecare căsuță conține un număr natural ce reprezintă cantitatea de energie necesară iepurașului pentru a sări într-o altă căsuță.

Iepurașul pleacă dintr-o anumită căsuță și se deplasează, de la stânga la dreapta, spre grădina cu morcovi după următoarele reguli:

* numărul înscris în căsuța în care se află iepurașul reprezintă numărul de căsuțe peste care el va sări;
dacă numărul înscris în căsuța în care se află iepurașul este număr prim, atunci energia lui se dublează şi va sări peste un număr dublu de căsuţe;
numărarea căsuțelor peste care va sări se face de la stânga la dreapta și începe cu căsuța imediat următoare.
* Astfel, dacă iepurașul se află în căsuța a treia și numărul înscris în această căsuță este 5, iepurașul va ajunge în căsuța cu numărul de ordine 13 (13=3+2*5).
dacă iepurașul ajunge într-o căsuță care conține numărul 0, el rămâne acolo pentru că nu mai are energie să sară mai departe, altfel el continuă să sară după regulile descrise mai sus;
iepurașul ajunge la grădina cu morcovi dacă ultimul salt pe care îl face depășește căsuța N.
== Cerinţa ==
Scrieți un program care citește trei numere naturale P, N și K iar apoi N numere naturale și determină:

1) dacă iepurașul poate ajunge sau nu, la grădina cu morcovi pornind din căsuța K și numărul de salturi pe care le face iepurașul pornind din căsuța K;
2) căsuța de pornire a iepurașului, astfel încât drumul parcurs de el să traverseze un număr maxim de căsuțe. Pentru a determina numărul de căsuțe se vor lua în calcul: căsuța de pornire, toate căsuțele peste care iepurașul a sărit și toate căsuțele în care a ajuns în urma salturilor. Iepurașul poate porni din oricare căsuță. În cazul în care există două sau mai multe căsuțe de pornire care conduc la același număr maxim de căsuțe traversate se va lua în considerare căsuța cu numărul de ordine cel mai mic.
== Date de intrare ==
Fişierul de intrare '''iepuras.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 a fișierului '''iepuras.in''' se găsesc, în această ordine, numerele naturale N și K, separate prin câte un spațiu. Pe a treia linie se găsesc N numere naturale separate prin câte un spațiu, reprezentând valorile din fiecare căsuță în ordine de la 1 la N.
== Date de ieșire ==
Dacă valoarea lui P este 1, se va rezolva numai punctul 1) din cerințe. În acest caz, fişierul de ieşire iepuras.out va conține pe prima linie cuvântul DA în cazul în care iepurașul a ajuns în grădina cu morcovi , respectiv cuvântul NU în caz contrar, iar pe a doua linie va conține un număr natural reprezentând numărul de salturi pe care le face iepurașul pornind din căsuța K.

Dacă valoarea lui P este 2, se va rezolva numai punctul 2) din cerințe. În acest caz, fişierul de ieşire iepuras.out va conține pe prima linie două numere naturale separate printr-un spaţiu reprezentând, în ordine, căsuța de pornire și numărul maxim de căsuțe determinat, iar pe a doua linie, un șir de numere naturale separate prin câte un spațiu reprezentând numerele din căsuțele în care iepurașul nu s-a aflat sau nu a sărit pe parcursul drumului, de la stânga la dreapta, începând cu căsuța 1. Dacă numărul maxim de căsuțe traversate este chiar N linia a doua nu va conține niciun număr.
== Restricţii şi precizări ==
* '''1 ≤ N ≤ 7000'''
* '''1 ≤ K ≤ N'''
* 0 ≤ numerele conţinute în căsuţe ≤ 100
* Pentru rezolvarea corectă a primei cerinţe se acordă 30 de puncte, pentru rezolvarea corectă a celei de a doua cerințe se acordă 70 de puncte.
== Exemplul 1 ==
; iepuras.in

1
14 3
2 3 4 0 1 1 2 1 4 0 0 2 1 1
; iepuras.out

NU
2
== Explicație ==
* P = 1, pentru acest test, se rezolva cerința 1).
 

== Exemplul 2 ==
; iepuras.in

2
14 3
2 3 6 0 1 1 2 1 4 0 0 2 3 1
; iepuras.out

2 13
2 6 0 1 1 2 0 0 2 1
== Explicație ==
* P = 2, pentru acest test, se rezolvă cerința 2).

Pentru a traversa un număr maxim de căsuțe, iepurașul pleacă din căsuța cu numărul de ordine 2 și sare, pe rând, în căsuțele cu numerele de ordine 8, 9, 13, și apoi în grădină, traversând astfel 13 căsuţe (de la căsuța 2 la căsuța 14).

Iepurașul nu s-a aflat sau nu a sărit în căsuţele de pe poziţiile 1, 3, 4, 5, 6, 7, 10, 11, 12 și 14.
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def can_reach_garden(N, K, houses):
energy = houses[K - 1]
jumps = 0

while K <= N:
jumps += 1
K += energy
if K > N:
return True, jumps
energy = houses[K - 1] if houses[K - 1] > 1 else energy * 2

return False, jumps

def find_starting_house(N, houses):
max_houses = 0
starting_house = 0

for i in range(1, N + 1):
energy = houses[i - 1]
jumps = 1
current_house = i

while current_house + energy <= N:
jumps += 1
current_house += energy
energy = houses[current_house - 1] if houses[current_house - 1] > 1 else energy * 2

if jumps > max_houses:
max_houses = jumps
starting_house = i

return starting_house, max_houses

def main():
with open("iepuras.in", "r") as fin:
P = int(fin.readline().strip())
N, K = map(int, fin.readline().split())
houses = list(map(int, fin.readline().split()))

if P == 1:
can_reach, jumps = can_reach_garden(N, K, houses)
with open("iepuras.out", "w") as fout:
fout.write("DA\n" if can_reach else "NU\n")
fout.write(str(jumps))
elif P == 2:
starting_house, max_houses = find_starting_house(N, houses)
not_visited_houses = [i for i in range(1, N + 1) if i != starting_house]

with open("iepuras.out", "w") as fout:
fout.write(f"{starting_house} {max_houses}\n")
fout.write(" ".join(map(str, not_visited_houses)))

if __name__ == "__main__":
main()

</syntaxhighlight>

1739 - Proiecte 1

2024-06-03T16:00:14Z

RebecaBud: Pagină nouă: == Enunt == În oraşul Iaşi, cele N firme IT derulează în prezent M proiecte din acest domeniu (printre care şi ONI 2012). Firmele sunt identificate prin numere naturale de la 1 la N, iar proiectele sunt identificate prin numere naturale de la 1 la M. Fiecare proiect are una sau mai multe etape, o etapă fiind executată de o singură firmă IT. Spunem că o firmă coordonează un proiect dacă execută mai mult de jumătate din etapele proiectului. == Cerinţa == Cunosc...

== Enunt ==
În oraşul Iaşi, cele N firme IT derulează în prezent M proiecte din acest domeniu (printre care şi ONI 2012). Firmele sunt identificate prin numere naturale de la 1 la N, iar proiectele sunt identificate prin numere naturale de la 1 la M. Fiecare proiect are una sau mai multe etape, o etapă fiind executată de o singură firmă IT. Spunem că o firmă coordonează un proiect dacă execută mai mult de jumătate din etapele proiectului.
== Cerinţa ==
Cunoscând numărul firmelor IT, numărul proiectelor, numărul de etape ale fiecărui proiect şi firmele ce execută fiecare etapă, să se determine firma/firmele care coordonează cel mai mare număr de proiecte.
== Date de intrare ==
Fişierul de intrare '''proiecte.in''' conţine, pe prima linie, numerele naturale N şi M, separate printr-un spaţiu, cu semnificaţia de mai sus. Pe fiecare dintre următoarele M linii se află informaţii despre câte un proiect, în ordinea numerelor de identificare a acestora. Astfel, pe linia corespunzătoare proiectului i (1≤i≤M), se află un număr natural nri, urmat de nri numere naturale f1f2…fnri
, reprezentând numărul de etape ale acestui proiect, respectiv firmele care execută fiecare etapă din proiect (firma fk
execută etapa k, 1≤k≤nri). Numerele de pe aceeaşi linie sunt separate prin câte un spaţiu.
== Date de ieșire ==
Fişierul de ieşire '''proiecte.out''' va conţine o singură linie, pe care va fi scris numărul de identificare al firmei/firmelor care coordonează cel mai mare număr de proiecte. Dacă sunt mai multe astfel de firme, numerele de identificare ale acestora se vor afişa pe aceeaşi linie, în ordine crescătoare, separate prin câte un spaţiu.
== Restricţii şi precizări ==
* 1 ≤ M ≤ 200
* 1 ≤ N ≤ 1000000
* 1 ≤ nri ≤ 200000 (1≤i≤M)
* 1 ≤ M*nri ≤ 320000 (1≤i≤M)
* 1 ≤ fk≤ N, (1≤k≤nri)
* există întotdeauna cel puţin un proiect coordonat de o firmă.
== Exemplul 1 ==
; proiecte.in

5 4
2 3 3
3 1 2 1
5 3 4 3 3 1
1 1
; proiecte.out

1 3
== Explicație ==
Numărul maxim de proiecte coordonate de aceeaşi firmă este 2: firma 1 coordonează proiectele 2 şi 4, iar firma 3 coordonează proiectele 1 şi 3.
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def main():
with open("proiecte.in", "r") as fin:
N, M = map(int, fin.readline().split())
projects = [list(map(int, fin.readline().split()))[1:] for _ in range(M)]

project_count = {i: 0 for i in range(1, N + 1)}

for project in projects:
firms_count = {f: 0 for f in project}
for firm in project:
firms_count[firm] += 1
max_count = max(firms_count.values())
for firm, count in firms_count.items():
if count > len(project) / 2:
project_count[firm] += 1

max_projects = max(project_count.values())
coordinating_firms = [firm for firm, count in project_count.items() if count == max_projects]

with open("proiecte.out", "w") as fout:
fout.write(" ".join(map(str, coordinating_firms)))

if __name__ == "__main__":
main()

</syntaxhighlight>

3566 - Templu

2024-06-03T15:56:35Z

RebecaBud: Pagină nouă: == Cerinţa == Copa ajunse în Orintia unde există un templu cu mai multe nivele, baza fiind un pătrat de lungime L. Primul nivel are înălţimea egală cu N, iar celelalte nivele au înălţimea mai mare cu o unitate faţă de cel anterior. Spre exemplu pentru L = 5 şi N = 3 din stâncă răsări templul (imagine din avion şi de la sol): 3 3 3 3 3 3 4 4 4 3 3 4 5 4 3 3 4 4 4 3 3 3 3 3 3 5 4 4 4 3 3 3 3 3 Copa deschise un document vechi...

== Cerinţa ==
Copa ajunse în Orintia unde există un templu cu mai multe nivele, baza fiind un pătrat de lungime L. Primul nivel are înălţimea egală cu N, iar celelalte nivele au înălţimea mai mare cu o unitate faţă de cel anterior. Spre exemplu pentru L = 5 şi N = 3 din stâncă răsări templul (imagine din avion şi de la sol):

3 3 3 3 3
3 4 4 4 3
3 4 5 4 3
3 4 4 4 3
3 3 3 3 3

5
4 4 4
3 3 3 3 3
Copa deschise un document vechi şi citi: „Ca să afli cât aur este în templu, trebuie să însumezi numărul de metri de pe fiecare orizontală…”. Şi Copa socoti: 3 + 3 + 3 + 3 + 3 = 15 ; 3 + 4 + 4 + 4 + 3 = 18 ; 3 + 4 + 5 + 4 + 3 = 19 ; celelalte 18 şi 15. „Apoi, trebuie să afli suma numerelor obţinute…”. Iar Copa îşi notă numărul 85. „Toate numerele obţinute se lipesc pentru a forma cel mai mic număr posibil…”. Şi Copa obţinu numărul: 151518181985 . „Din numărul acesta se caută cel mai mare număr de două cifre alăturate. Aceasta este cantitatea de aur din templu.”. Şi Copa ţipă de bucurie: 98!.

Plecaţi în Orintia! Veţi primi cele două numere N şi L şi vi se cere să determinaţi numărul obţinut din sume şi cantitatea de aur.
== Date de intrare ==
Fişierul de intrare '''templu.in''' conţine pe prima linie numerele N şi L separate printr-un spaţiu.
== Date de ieșire ==
Fişierul de iesire '''templu.out''' va conţine două linii. Pe câte o linie se va scrie câte un număr. Pe prima linie numărul obţinut din sume, iar pe a doua linie cantitatea de aur.
== Restricţii şi precizări ==
* 2≤L≤10
* 1≤N≤50
== Exemplul 1 ==
; templu.in

3 5
; templu.out

151518181985
98

 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def calculate_gold_quantity(N, L):
total_sum = 0
gold_number = ""

for i in range(N):
level_sum = 0
for j in range(L):
level_sum += N + j
gold_number += str(N + j)
total_sum += level_sum

gold_quantity = max(int(gold_number[i:i+2]) for i in range(len(gold_number) - 1))

return total_sum, gold_quantity

def main():
with open("templu.in", "r") as fin:
N, L = map(int, fin.readline().split())

total_sum, gold_quantity = calculate_gold_quantity(N, L)

with open("templu.out", "w") as fout:
fout.write(str(total_sum) + "\n")
fout.write(str(gold_quantity))

if __name__ == "__main__":
main()

</syntaxhighlight>

3845 - Ciurulet

2024-06-03T15:52:41Z

RebecaBud: Pagină nouă: == Cerinţa == Popel, elev de liceu calificat la barajul pentru Lotul Național de Informatică, tocmai a învățat ciurul lui Eratostene, pentru aflarea numerelor prime, al cărui algoritm este descris astfel: prim[i]=1, oricare ar fi i de la 2 la N pentru i de la 2 la N: dacă prim[i] este 1: pentru j de la 2*i la N din i în i: prim[j] = 0 Din cauza oboselii și a stresului, Popel a inițializat greșit șirul prim, punând pe unele pozi...

== Cerinţa ==
Popel, elev de liceu calificat la barajul pentru Lotul Național de Informatică, tocmai a învățat ciurul lui Eratostene, pentru aflarea numerelor prime, al cărui algoritm este descris astfel:

prim[i]=1, oricare ar fi i de la 2 la N
pentru i de la 2 la N:
dacă prim[i] este 1:
pentru j de la 2*i la N din i în i:
prim[j] = 0
Din cauza oboselii și a stresului, Popel a inițializat greșit șirul prim, punând pe unele poziții 0 în loc de 1. După ce a executat algoritmul pe șirul prim greșit inițializat, a obținut un nou șir pe care l-a notat pe o foaie de hârtie. Mai târziu, nu își mai amintea șirul inițial prim, dar mai avea șirul final pe care l-a obținut. În plus, nu mai era sigur dacă unele valori din șirul final le-a notat corect, așa că le-a marcat cu caracterul "?". Popel vă roagă să aflați un șir inițial cu proprietatea că dacă ar executa algoritmul de mai sus asupra lui, ar obține un șir care s-ar potrivi cu șirul final notat pe foaie. De asemenea, el își dorește ca șirul inițial să aibă un număr cât mai mare de cifre de 1.
== Date de intrare ==
Pe prima linie a fișierului ciurulet.in se va afla numărul N reprezentând valoarea până la care se
execută algoritmul.
Următoarea linie conține N-1 caractere din mulțimea {0, 1, ?}, fără spații între ele, reprezentând șirul notat pe foaie. Caracterul ? indică un caracter pe care Popel nu și-l mai amintește (adică Popel nu mai știe dacă acolo era 0 sau 1). Al i-lea caracter dintre acestea reprezintă valoarea lui prim[i+1]. Dacă aceasta este diferită de ?, atunci Popel și-o amintește exact. Altfel, acolo ar fi putut fi orice (0 sau 1).
== Date de ieșire ==
Pe prima linie a fișierului ciurulet.out se va afla numărul maxim de cifre de 1 care pot apărea într-un șir
inițial din care se obține un șir final care se potrivește cu cel notat pe foaie.
Pe a doua linie se vor afișa N-1 caractere din mulțimea {0, 1}, fără spații între ele, care reprezintă șirul inițial folosit.
== Restricţii şi precizări ==
* '''2 ≤ N ≤ 1.000.000.'''
* Pentru 30% din teste, șirul din fișierul de intrare nu conține caracterul ?.
* Pentru ca două șiruri A și B să se potrivească, trebuie ca A[i] și B[i] să fie egale, oricare ar fi i de la 2 la N cu B[i] diferit de ?. Cu alte cuvinte, peste 0 se potrivește 0, peste 1 se potrivește 1, iar peste ? se potrivesc atât 0, cât și 1.
* Se garantează faptul că șirul final obținut notat pe foaie este unul valid.
== Exemplu 1 ==
; ciurulet.in

9
??10?00?
;ciurulet.out

5
01101011
== Explicație ==
Aplicând algoritmul de mai sus asupra șirului 01101011 se obține în final șirul '''01100000''', care se potrivește cu ce și-a notat Popel pe foaie.
== Exemplul 2 ==
; ciurulet.in

9
??10?00?
; ciurulet.out

5
01101011
== Explicație ==
Aplicând algoritmul de mai sus asupra șirului 01101011 se obține în final șirul '''01100000''', care se potrivește cu ce și-a notat Popel pe foaie.
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def find_max_ones(N, sequence):
max_ones = 0
max_ones_index = 0
current_ones = 0
current_index = 0

for i in range(N - 1):
if sequence[i] == '1':
current_ones += 1
elif sequence[i] == '0':
current_ones -= 1

if current_ones > max_ones:
max_ones = current_ones
max_ones_index = current_index

current_index += 1

return max_ones, max_ones_index

def generate_initial_sequence(N, sequence):
initial_sequence = ['0'] * N
max_ones, max_ones_index = find_max_ones(N, sequence)

current_ones = max_ones
for i in range(max_ones_index, -1, -1):
if sequence[i] == '?':
initial_sequence[i] = '1'
current_ones -= 1
elif sequence[i] == '0':
current_ones += 1

for i in range(max_ones_index + 1, N):
if sequence[i - 1] == '?':
initial_sequence[i] = '1'
elif sequence[i - 1] == '1':
initial_sequence[i] = '1' if current_ones > 0 else '0'
current_ones -= 1

return ''.join(initial_sequence)

def main():
with open("ciurulet.in", "r") as fin:
N = int(fin.readline())
sequence = fin.readline().strip()

max_ones, _ = find_max_ones(N, sequence)
initial_sequence = generate_initial_sequence(N, sequence)

with open("ciurulet.out", "w") as fout:
fout.write(str(max_ones) + "\n")
fout.write(initial_sequence)

if __name__ == "__main__":
main()

</syntaxhighlight>

0976 - Sir 3

2024-06-03T15:47:04Z

RebecaBud: Pagină nouă: == Enunt == Se consideră şirul de numere naturale ai cărui primi termeni sunt, în această ordine: 1, 5, 3, 7, 9, 11, 19, 17, 15, 13, 21,... Se grupează numerele din şir astfel: * prima grupă, numerotată cu 1, conţine primul termen al şirului (1) * a doua grupă, numerotată cu 2, conţine următorii doi termeni ai şirului (5,3) * a treia grupă, numerotată cu 3, conţine următorii trei termeni ai şirului (7,9,11) ………………………. * a n-a grupă din...

== Enunt ==
Se consideră şirul de numere naturale ai cărui primi termeni sunt, în această ordine:

1, 5, 3, 7, 9, 11, 19, 17, 15, 13, 21,...
Se grupează numerele din şir astfel:
* prima grupă, numerotată cu 1, conţine primul termen al şirului (1)
* a doua grupă, numerotată cu 2, conţine următorii doi termeni ai şirului (5,3)
* a treia grupă, numerotată cu 3, conţine următorii trei termeni ai şirului (7,9,11)
……………………….
* a n-a grupă din şir, numerotată cu n, conţine următorii n termeni ai şirului
etc.
== Cerinţa ==
Deduceţi regula după care sunt generaţi termenii şirului şi scrieţi un program care să citească numerele naturale p, n şi k şi care să determine:

a) termenul de pe poziţia p din şirul din enunţ;
b) cel mai mare număr natural palindrom care poate fi obţinut folosindu-se cifrele tuturor numerelor din grupa a n-a a şirului dat, nu neapărat toate aceste cifre;
c) numărul grupei ce conţine un număr maxim de termeni şi are proprietatea că suma acestor termeni este cel mult egală cu k.
== Date de intrare ==
Programul citește de la tastatură cele trei numere, '''p n k'''.
== Date de ieșire ==
Programul va afișa pe ecran trei numere, reprezentând, în ordine:

* termenul de pe poziţia p din şirul din enunţ;
* cel mai mare număr natural palindrom care poate fi obţinut folosindu-se cifrele din scrierea zecimală a
* tuturor termenilor din grupa a n-a a şirului dat, nu neapărat toate aceste cifre;
* pe a treia linie se va scrie numărul grupei ce conţine un număr maxim de termeni şi are proprietatea că suma
* acestora este cel mult egală cu k.
== Restricţii şi precizări ==
* Numerele p, n şi k sunt naturale
* '''1 ≤ p ≤ 1000000000'''
* '''1 ≤ n ≤ 50'''
* '''1 ≤ k ≤ 2000000000'''
* un număr natural este palindrom dacă este egal cu numărul obţinut prin scrierea cifrelor sale în ordine inversă
* Pentru rezolvarea cerinţei a) se acordă 40% din punctaj, pentru cerinţa b) 30% din punctaj şi pentru cerinţa c) 30% din punctaj.
== Exemplul 1 ==
; Intrare

7 5 127
; Ieșire

19
22922
5
== Explicație ==
* Primii 7 termeni ai şirului sunt: 1,5,3,7,9,11,19. Termenul căutat are valoarea 19.
* Numerele din grupa a 5-a sunt scrise cu ajutorul a cinci cifre de 2, o cifră de 3, una de 5, una de 7, una de 9.
* Cel mai mare palindrom care se poate scrie cu aceste cifre este 22922.
* Grupele a căror sumă este cel mult egală cu k=127 sunt: 1,2,3,4,5. Grupa cu cei mai mulţi termeni şi cu suma maximă (=125) este grupa 5.
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def generate_sequence(n):
sequence = [1]
current = 5
for i in range(2, n + 1):
sequence.extend(range(current, current + i))
current += i + 1
return sequence

def find_term(p, n):
sequence = generate_sequence(n)
return sequence[p - 1]

def is_palindrome(num):
return str(num) == str(num)[::-1]

def find_largest_palindrome(numbers):
palindromes = [int(str(num)[::-1]) for num in numbers if is_palindrome(num)]
return max(palindromes)

def find_max_group(p, n, k):
max_sum = 0
max_group = 0
sequence = generate_sequence(n)
for i in range(1, n + 1):
group = sequence[sum(range(i)) : sum(range(i + 1))]
group_sum = sum(group)
if group_sum <= k and len(group) > max_group:
max_group = len(group)
max_sum = group_sum
return max_group

p, n, k = map(int, input().split())

# a)
term = find_term(p, n)
print(term)

# b)
group_n = generate_sequence(n)[sum(range(n)): sum(range(n + 1))]
largest_palindrome = find_largest_palindrome(group_n)
print(largest_palindrome)

# c)
max_group = find_max_group(p, n, k)
print(max_group)

</syntaxhighlight>

3607 - Run

2024-06-03T15:40:47Z

RebecaBud: Pagină nouă: == Cerinţa == În această dimineață Aky, un băiat sportiv, s-a hotărât să meargă la alergat. Acesta vrea după ce ajunge acasă să își rezolve tema la informatică și pentru asta trebuie să nu fie foarte obosit în urma antrenamentului, deci vrea să își aleagă un traseu cât mai ușor pe care să alerge, iar pentru asta și-a pus la punct un plan foarte exact. Acesta are în orașul său o distanță N kilometri legați, numerotați de la 1 la N, iar fiec...

== Cerinţa ==
În această dimineață Aky, un băiat sportiv, s-a hotărât să meargă la alergat. Acesta vrea după ce ajunge acasă să își rezolve tema la informatică și pentru asta trebuie să nu fie foarte obosit în urma antrenamentului, deci vrea să își aleagă un traseu cât mai ușor pe care să alerge, iar pentru asta și-a pus la punct un plan foarte exact.

Acesta are în orașul său o distanță N kilometri legați, numerotați de la 1 la N, iar fiecărui kilometru i din cele N(1 ≤ i ≤ N) îi cunoaște gradul de dificultate a[i]. Băiatul a întocmit o listă cu M intervale diferite de kilometri de forma [l, r], fiecare interval având un anumit grad de oboseală asociat acestuia. Gradul de oboseală G asociat unui interval [l, r] de lungime L = r - l + 1 se calculează astfel: G = a[l] * L + a[l + 1] * (L - 1) + ... + a[r - 1] * 2 + a[r] * 1 și reprezintă cu cât va crește valoarea de oboseală a lui Aky dupa ce va alerga kilometrii intervalului respectiv. Acum Aky vă cere vouă să-l ajutați să-și ducă planul la sfârșit, aflând care este valoarea minimă de oboseală pe care o poate avea la finalul antrenamentului său, știind că trebuie sa alerge kilometrii a exact K din intervalele din lista sa.
== Date de intrare ==
Fişierul de intrare '''run.in''' are pe prima linie numerele N M K, reprezentând numărul de kilometri din orașul lui Aky, numărul de intervale din lista sa, respectiv câte dintre intervale trebuie să aleagă pentru alergat, pe a 2-a linie N numere naturale a[1], a[2], ..., a[N], reprezentând gradele de dificultate ale celor N kilometri, iar pe următoarele M linii câte 2 numere l r reprezentând intervalele din lista lui Aky.
== Date de ieșire ==
Fişierul de ieşire '''run.out''' va conţine pe prima linie numărul natural V, reprezentând valoarea minimă de oboseală pe care o poate avea băiatul la finalul antrenamentului său.
== Restricţii şi precizări ==
* '''1 ≤ N, M ≤ 100.000'''
* '''1 ≤ K ≤ M'''
* '''1 ≤ a[i] ≤ 10.000'''
* '''1 ≤ l ≤ r ≤ n'''
* pentru teste în valoare de 50 de puncte '''N ≤ 5.000''' și '''M ≤ 5.000'''
== Exemplul 1 ==
; run.in

5 5 3
2 3 1 5 6
1 3
1 4
3 4
2 5
4 5
; run.out

36
== Explicație ==
Vom lua fiecare interval și vom calcula gradul său de oboseală:
* [1, 3]: G = 2 * 3 + 3 * 2 + 1 * 1 = 13
* [1, 4]: G = 2 * 4 + 3 * 3 + 1 * 2 + 5 * 1 = 24
* [3, 4]: G = 1 * 2 + 5 * 1 = 7
* [2, 5]: G = 3 * 4 + 1 * 3 + 5 * 2 + 6 * 1 = 31
* [4, 5]: G = 5 * 2 + 6 * 1 = 16

Obținem în final gradele de oboseală 13 24 7 31 16 din care Aky trebuie să aleagă 3 astfel încât valoarea sa de oboseală să fie minimă. Acesta elege primul, al treilea, respectiv ultimul interval obținând valoarea de oboseală minimă '''13 + 7 + 16 = 36'''.
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
with open("run.in", "r") as fin:
N, M, K = map(int, fin.readline().split())
difficulties = list(map(int, fin.readline().split()))
intervals = [tuple(map(int, fin.readline().split())) for _ in range(M)]

def fatigue(interval, difficulties):
l, r = interval
fatigue_value = 0
for i in range(l, r + 1):
fatigue_value += difficulties[i - 1] * (r - i + 1)
return fatigue_value

sorted_intervals = sorted(intervals, key=lambda interval: fatigue(interval, difficulties))
min_fatigue = sum(fatigue(interval, difficulties) for interval in sorted_intervals[:K])

with open("run.out", "w") as fout:
fout.write(str(min_fatigue))

</syntaxhighlight>

4196 - MPF

2024-06-03T15:26:52Z

RebecaBud: Pagină nouă: == Enunt == Fie '''X''' un număr natural nenul și '''p''' cel mai mare factor prim din descompunerea în factori primi a lui '''X'''. Pentru '''X = 1''', considerăm '''p = 1'''. Asupra lui '''X''' se pot efectua următoarele două operații: Operația 1: '''X''' se împarte la '''p''' și devine '''X / p'''; Operația 2: '''X''' devine '''X * k''', unde '''k''' este un număr prim și mai mare sau egal decât '''p'''. == Cerinţa == Se dau '''Q''' perechi de numere natura...

== Enunt ==
Fie '''X''' un număr natural nenul și '''p''' cel mai mare factor prim din descompunerea în factori primi a lui '''X'''. Pentru '''X = 1''', considerăm '''p = 1'''. Asupra lui '''X''' se pot efectua următoarele două operații:

Operația 1: '''X''' se împarte la '''p''' și devine '''X / p''';
Operația 2: '''X''' devine '''X * k''', unde '''k''' este un număr prim și mai mare sau egal decât '''p'''.
== Cerinţa ==
Se dau '''Q''' perechi de numere naturale nenule '''(X, Y)'''. Să se determine, pentru fiecare pereche, numărul minim de operații necesare pentru a-l transforma pe '''X''' în '''Y'''.
== Date de intrare ==
Datele de intrare conțin '''Q + 1''' linii. Pe prima linie se găsește '''Q''' reprezentând numărul de perechi '''(X, Y)'''.
Pe următoarele '''Q''' linii, câte o pereche de numere naturale nenule '''X''' și '''Y''', despărțite printr-un singur spațiu.
== Date de ieșire ==
Ieșirea va conține '''Q''' linii. Pe fiecare linie '''i''' se va scrie câte un număr natural reprezentând, numărul de operații determinat pentru a i-a pereche.
== Restricţii şi precizări ==
* '''1 ≤ Q ≤ 1.000.000'''
* '''1 ≤ X, Y ≤ 4.000.000'''
Datorită dimensiunii mari a datelor de intrare și de ieșire, doar unele teste au fost adăugate.
== Exemplul 1 ==
; Intrare

4
4 10
2 9
6 2
12 12
; Ieșire

2
3
1
0
== Explicație ==
Pentru (4, 10): 4 devine 2 utilizând o Operație 1, apoi devine 10 utilizând o Operație 2.
Pentru (2, 9): 2 devine 1 utilizând o Operație 1, apoi devine 3 folosind o Operație 2 și devine 9 folosind o Operație 2.
Pentru (6, 2): 6 devine 2 folosind o Operație de tip 1.
Pentru (12, 12): Numerele sunt egale, nu este necesară nicio operație.
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def max_prime_factor(x):
factor = 2
while factor * factor <= x:
if x % factor == 0:
x //= factor
else:
factor += 1
return x

with open("input.in", "r") as fin:
q = int(fin.readline())
pairs = [tuple(map(int, line.split())) for line in fin]

with open("output.out", "w") as fout:
for pair in pairs:
x, y = pair
if x == y:
fout.write("0\n")
elif max_prime_factor(x) == max_prime_factor(y):
fout.write("1\n")
else:
fout.write("2\n")

</syntaxhighlight>

3468 - weekend

2024-06-03T15:20:54Z

RebecaBud: Pagină nouă: == Enunt == În acest weekend tocmai s-au pus în vânzare bilete pentru concertul celui mai în vogă artist. Cum acesta este extrem de popular, un număr de n persoane s-au așezat la coadă la casa de bilete. Pentru simplitate, prima persoană așezată la coadă va avea indicele 1, a doua va avea indicele 2 și așa mai departe. Deoarece statul la coadă este extrem de plictisitor, fiecare om a început să numere câte persoane mai scunde decât el se află în fața s...

== Enunt ==

În acest weekend tocmai s-au pus în vânzare bilete pentru concertul celui mai în vogă artist. Cum acesta este extrem de popular, un număr de n persoane s-au așezat la coadă la casa de bilete. Pentru simplitate, prima persoană așezată la coadă va avea indicele 1, a doua va avea indicele 2 și așa mai departe.

Deoarece statul la coadă este extrem de plictisitor, fiecare om a început să numere câte persoane mai scunde decât el se află în fața sa. Se cunoaște că înălțimile oamenilor sunt reprezentate cu numere naturale nenule.

Din lipsă de imaginație, oamenii care stau la coadă nu au reușit sa ducă jocul până la capăt, așa că o vom face noi. Cunoscând câte persoane mai scunde decât el are în față fiecare om care stă la coadă, se cere să se determine înălțimea fiecărui om din șir.

Dacă există mai multe soluții valide, se cere afișată soluția minim lexicografică. Dacă există două șiruri valide de înălțimi ale celor n persoane A1, A2 ,…, An și B1, B2, …, Bn spunem că șirul A este mai mic lexicografic decât B dacă există un număr natural i mai mic sau egal decât n astfel încât Ai < Bi și Aj = Bj, oricare ar fi j = 1..i-1.
== Cerinţa ==
Fiind dat șirul inițial de observații ale oamenilor care stau la coadă, să se reconstruiască șirul minim lexicografic care poate reprezenta înălțimile acestora.
== Date de intrare ==
Fișierul de intrare '''weekend.in''' va avea pe prima linie numărul '''n'''. Pe linia a doua se va afla un șir de '''n''' numere naturale despărțite printr-un spațiu, valoarea aflată pe poziția '''i''' semnificând numărul de persoane strict mai scunde decât persoana '''i''' și cu indice mai mic decât '''i'''.

== Date de ieșire ==
În fișierul de ieșire '''weekend.out''' se va afișa șirul înălțimilor. Pe linia a i-a din fișierul de ieșire se va afla înălțimea persoanei cu indicele i.
== Restricţii şi precizări ==
* Se garantează că setul de date este corect și va exista mereu cel puțin o soluție.
* Două sau mai multe persoane NU pot avea aceeași înălțime.
* '''1 ≤ N ≤ 200.000'''
* Pentru 40% din teste, N <= 5.000

== Exemplul 1 ==
; weekend.in

4
0 1 1 0
; weekend.out

2
4
3
1
== Explicație ==
Observăm că acesta este cel mai mic șir lexicografic care satisface șirul de observații din input. O altă soluție ar fi fost șirul 2 5 3 1, dar acesta este mai mare lexicografic.
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
with open("weekend.in", "r") as fin:
n = int(fin.readline().strip())
observations = list(map(int, fin.readline().split()))

heights = [0] * n

for i in range(n - 1, -1, -1):
taller_count = observations[i]
height = 1
for j in range(taller_count):
height = max(heights[i + j + 1] + 1, height)
heights[i] = height

with open("weekend.out", "w") as fout:
for height in heights:
fout.write(str(height) + "\n")

</syntaxhighlight>

1950 - PXP

2024-06-03T15:10:49Z

RebecaBud: Pagină nouă: == Cerinţa == Se dă un şir format din '''N''' numere naturale nenule. Spunem că un număr e fericit dacă se poate scrie ca suma pătratelor a două numere naturale. Notăm cu '''K''' numărul numerelor fericite din şir şi cu '''P''' produsul acestora. Aflaţi numărul '''K''' precum şi două numere naturale care au suma pătratelor egală cu '''PE''', unde '''E''' este un număr natural dat. == Date de intrare == Fișierul de intrare '''pxp.in''' conține pe prima lin...

== Cerinţa ==
Se dă un şir format din '''N''' numere naturale nenule. Spunem că un număr e fericit dacă se poate scrie ca suma pătratelor a două numere naturale. Notăm cu '''K''' numărul numerelor fericite din şir şi cu '''P''' produsul acestora. Aflaţi numărul '''K''' precum şi două numere naturale care au suma pătratelor egală cu '''PE''', unde '''E''' este un număr natural dat.
== Date de intrare ==
Fișierul de intrare '''pxp.in''' conține pe prima linie numerele N şi E , iar pe a doua linie N numere naturale separate prin spațiu.
== Date de ieșire ==
Fișierul de ieșire '''pxp.out''' va conține pe prima linie numărul K, reprezentând numărul numerelor fericite din şir iar pe a doua linie cele două numere care au suma pătratelor egală cu PE.
== Restricţii şi precizări ==
* 1 ≤ N ≤ 100.000
* 1 ≤ E ≤ 3
* numerele din şir sunt mai mici decât 1.000.001 şi cel puţin un număr din şir este fericit
* 1 ≤ P ≤ 1036
* pentru a doua cerinţă se va afişa orice soluţie, fiecare test având soluţie
* pentru prima cerinţă se acordă 40p, iar pentru a doua 60p
* 0% din teste au P ≤ 1000000, iar alte 40% au P ≤ 1018

== Exemplul 1 ==
; pxp.in

5 1
11 2 13 7 5
; pxp.out

3
3 11
== Explicație ==
Avem '''N=5''' şi '''E=1'''. În şir sunt 3 numere fericite, 2, 13 şi 5, deoarece 2=12+12 , 13=22+32 şi 5=12+22. Produsul lor este 130=32+112, deci două numere pentru care suma pătratelor este P1 sunt 3 şi 11.
 

== Rezolvare ==
<syntaxhighlight lang="python" line>
def is_happy_number(num):
i = 1
while i * i <= num:
if num - i * i == int((num - i * i) ** 0.5) ** 2:
return True
i += 1
return False

with open("pxp.in", "r") as fin:
N, E = map(int, fin.readline().split())
numbers = list(map(int, fin.readline().split()))

happy_numbers = []
product = 1
for num in numbers:
if is_happy_number(num):
happy_numbers.append(num)
product *= num

K = len(happy_numbers)

target_sum = product * E
found = False
for i in range(len(happy_numbers)):
for j in range(i + 1, len(happy_numbers)):
if happy_numbers[i] ** 2 + happy_numbers[j] ** 2 == target_sum:
result = (happy_numbers[i], happy_numbers[j])
found = True
break
if found:
break

with open("pxp.out", "w") as fout:
fout.write(str(K) + "\n")
fout.write(" ".join(map(str, result)))

</syntaxhighlight>

3034 - Drept 1

2024-06-03T15:01:37Z

RebecaBud: Pagină nouă: == Enunt == Numim '''poligon drept''' un poligon cu laturile consecutive perpendiculare și lungimile laturilor numere naturale nenule. Un poligon drept cu n laturi este descris de un șir de n numere întregi nenule în care lungimile laturilor sunt date de valoarea absolută a numerelor din șir, iar semnul precizează poziția laturilor, un număr pozitiv însemnând latură spre dreapta sau în sus față de extremitatea laturii precedente, iar un număr negativ însemnâ...

== Enunt ==
Numim '''poligon drept''' un poligon cu laturile consecutive perpendiculare și lungimile laturilor numere naturale nenule. Un poligon drept cu n laturi este descris de un șir de n numere întregi nenule în care lungimile laturilor sunt date de valoarea absolută a numerelor din șir, iar semnul precizează poziția laturilor, un număr pozitiv însemnând latură spre dreapta sau în sus față de extremitatea laturii precedente, iar un număr negativ însemnând latură în jos sau spre stânga față de extremitatea laturii precedente; de exemplu șirul 1, 1, -1, -1 reprezintă un pătrat de latură 1 (prima latură spre dreapta, a doua în sus, a treia spre stânga, a patra în jos). Vom considera laturile ca fiind orizontale sau verticale, prima latură enumerată fiind orizontală spre dreapta, dacă numărul este pozitiv, sau spre stânga, dacă numărul este negativ.
== Cerinţa ==
Se dau unul sau mai multe șiruri de numere întregi nenule.
1. Să se stabilească, pentru fiecare dintre ele, dacă reprezintă un poligon drept.
2. Știind că șirurile date reprezintă poligoane drepte, să se determine aria fiecăruia.
== Date de intrare ==
Fișierul de intrare '''drept.in''' conține pe prima linie, separate prin spațiu, un număr natural C și un număr natural T. Următoarele 2 * T linii vor descrie testele, câte două linii pentru fiecare test. Pe prima linie corespunzătoare unui test se află un număr natural n, iar pe a doua linie un șir de n numere întregi, separate prin câte un spațiu.
== Date de ieșire ==
Fișierul de ieșire '''drept.out''' va conține pe o singură linie rezultatele corespunzătoare celor T teste, separate prin câte un spațiu. Dacă C = 1 pentru fiecare șir rezultatul este 1, dacă acesta reprezintă un poligon drept, sau 0 altfel. Dacă C = 2 pentru fiecare șir rezultatul este aria poligonului drept corespunzător.
== Restricţii şi precizări ==
* '''1 ≤ T ≤ 10'''
* '''4 ≤ n ≤ 100'''
*Pentru teste în valoare de 45 de puncte C = 1, pentru restul de 55 de puncte C = 2
*Pentru teste în valoare de 30 de puncte C = 1 și numerele ce descriu figura sunt întregi nenule aparținând intervalului [-100, 100]
*Pentru celelalte 15 puncte și C = 1 numerele ce descriu figura sunt întregi nenule aparținând intervalului [-1.000.000.000, 1.000.000.000]
*Pentru teste în valoare de 33 de puncte se garantează că avem C = 2 și intersecția dintre orice orizontală cu poligonul este fie vidă, fie formată dintr-un singur segment.
*Pentru testele în care valoarea lui C este 2, numerele din șirul ce descrie poligonul sunt întregi nenule din intervalul [-100, 100] și se garantează că aceste șiruri reprezintă poligoane drepte.
*Într-un poligon drept laturile nu au puncte comune, exceptând capetele laturilor adiacente.
*Prima și ultima latură ale unui poligon drept sunt perpendiculare.
== Exemplul 1 ==
; drept.in

1 2
8
5 3 -3 -1 2 -1 -4 -1
8
-2 1 3 1 -4 -3 2 1
; drept.out

1 0
Explicație
 

== Exemplul 2 ==
; drept.in

2 2
8
5 3 -3 -1 2 -1 -4 -1
4
1 1 -1 -1
; drept.out

9 1

 

== Rezolvare ==
<syntaxhighlight lang="python" line>
with open("drept.in", "r") as fin:
C, T = map(int, fin.readline().split())
results = []
for _ in range(T):
n = int(fin.readline().strip())
polygon = list(map(int, fin.readline().split()))

is_polygon = True
for i in range(n):
if polygon[i] == 0:
is_polygon = False
break
if i % 2 == 0:
if polygon[i] < 0:
is_polygon = False
break
else:
if polygon[i] > 0:
is_polygon = False
break

if C == 1:
results.append(1 if is_polygon else 0)
elif C == 2:
area = 0
for i in range(0, n, 2):
area += abs(polygon[i]) * abs(polygon[i + 1])
results.append(area)

with open("drept.out", "w") as fout:
fout.write(" ".join(map(str, results)))

</syntaxhighlight>