Vizualizare sursă pentru „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>