Bonte Lucas Gabriel at 18:13, 29 November 2023

2023-11-29T18:13:13Z

Bonte Lucas Gabriel: Pagină nouă: ==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 po...

2023-10-31T16:23:53Z

Pagină nouă: ==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 po...

New page

==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>

2733 - nrapp - Revision history

Bonte Lucas Gabriel at 18:13, 29 November 2023