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

2024-06-03T03:24:06Z

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

New page

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

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

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

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

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

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

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

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

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

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

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

rezultate = []

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

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

if __name__ == "__main__":
main()

</syntaxhighlight>

2510 - vsecvente - Revision history