Editing 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">

# 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

# 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])))

# Rezolvarea problemei
answers = solve(N, v, Q, queries)

# Scrierea raspunsurilor in fisierul nrapp.out
with open('nrapp.out', 'w') as file:
    for answer in answers:
        file.write(str(answer) + '\n')

</syntaxhighlight>