2733 - nrapp

Cerința

Se dă un număr natural N si un șir v de N numere naturale. Sa se răspundă la Q întrebări de tipul:

D y: Care este cea mai mică poziție x, unde x > y, pentru care v[x] < v[y]? Dacă nu există o astfel de poziție, răspunsul acestei întrebări va fi N + 1. S y: Care este cea mai mare poziție x, unde x < y, pentru care v[x] < v[y]? Dacă nu există o astfel de poziție, răspunsul acestei întrebări va fi 0.

Date de intrare

Fișierul de intrare nrapp.in conține pe prima linie numărul natural N, iar pe a doua linie N numere naturale separate prin spații. A treia linie va conține numărul natural nenul Q și apoi Q întrebări precum cele descrise anterior.

Date de ieșire

Fișierul de ieșire nrapp.out va conține Q linii, anume răspunsul pentru fiecare întrebare în parte.

Restricții și precizări

• 1 ≤ N ≤ 100.000
• 1 ≤ v[i] ≤ 1.000.000

Exemplu:

nrapp.in

8

1 3 6 5 2 1 9 6

8

S 1

D 2

D 3

S 4

S 5

D 6

D 7

D 8

nrapp.out

0

5

4

2

1

9

8

9

Rezolvare

<syntaxhighlight lang="python" line="1" start="1">

1. Functia solve care rezolva problema

def solve(N, v, Q, queries):

   # Initializam lista de raspunsuri
   answers = []
   # Parcurgem fiecare interogare
   for query in queries:
       # Daca interogarea este de tip 'D'
       if query[0] == 'D':
           y = query[1]
           # Initializam raspunsul cu N + 1
           answer = N + 1
           # Cautam cea mai mica pozitie x > y pentru care v[x] < v[y]
           for x in range(y + 1, N + 1):
               if v[x - 1] < v[y - 1]:
                   answer = x
                   break
           # Adaugam raspunsul in lista de raspunsuri
           answers.append(answer)
       # Daca interogarea este de tip 'S'
       elif query[0] == 'S':
           y = query[1]
           # Initializam raspunsul cu 0
           answer = 0
           # Cautam cea mai mare pozitie x < y pentru care v[x] < v[y]
           for x in range(y - 1, 0, -1):
               if v[x - 1] < v[y - 1]:
                   answer = x
                   break
           # Adaugam raspunsul in lista de raspunsuri
           answers.append(answer)
   # Returnam lista de raspunsuri
   return answers

1. Citirea datelor de intrare din fisierul nrapp.in

with open('nrapp.in', 'r') as file:

   N = int(file.readline())
   v = list(map(int, file.readline().split()))
   Q = int(file.readline())
   queries = []
   for _ in range(Q):
       query = file.readline().split()
       queries.append((query[0], int(query[1])))

1. Rezolvarea problemei

answers = solve(N, v, Q, queries)

1. Scrierea raspunsurilor in fisierul nrapp.out

with open('nrapp.out', 'w') as file:

   for answer in answers:
       file.write(str(answer) + '\n')

</syntaxhighlight>