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 nrappin.txt 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 nrappout.txt 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

Exemplul 1:

nrappin.txt

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

nrappout.txt

Datele de intrare corespund restrictiilor impuse
0
5
4
2
1
9
8
9

Exemplul 2:

nrappin.txt

nrapp

nrappout.txt

Datele de intrare nu corespund restrictiilor impuse

Rezolvare

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

def validare(n, sir_v, q, intrebari, file_output): # functia de validare a datelor de intrare

   if not 1 <= n <= 100000:
       raise ValueError
   for val in sir_v:
       if not 1 <= val <= 1000000:    # fiecare element trebuie sa fie numar intreg intre 1 si 1.000.000
           raise ValueError
   if q < 1:
       raise ValueError
   for intrebare in intrebari:
       if len(intrebare) != 2 or not isinstance(intrebare[1], int):
           raise ValueError
   file_output.write("Datele de intrare corespund restrictiilor impuse\n")

def solve(n, sir_v, intrebari): # functia de rezolvare

   raspunsuri = []
   for intrebare in intrebari:
       if intrebare[0] == 'D':
           y = intrebare[1]
           raspuns = n + 1
           for x in range(y + 1, n + 1):
               if sir_v[x - 1] < sir_v[y - 1]:
                   raspuns = x
                   break
           raspunsuri.append(raspuns)
       elif intrebare[0] == 'S':
           y = intrebare[1]
           raspuns = 0
           for x in range(y - 1, 0, -1):
               if sir_v[x - 1] < sir_v[y - 1]:
                   raspuns = x
                   break
           raspunsuri.append(raspuns)
   return raspunsuri

if __name__ == '__main__':

   file_in = open('nrappin.txt', 'r')
   file_out = open('nrappout.txt', 'w')

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

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

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

   except ValueError:
       file_out.write("Datele de intrare nu corespund restrictiilor impuse")
   except IndexError:
       file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>