2510 - vsecvente

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>