Bonte Lucas Gabriel at 20:21, 3 January 2024

2024-01-03T20:21:36Z

@@ Line 1: / Line 1: @@
-Se consideră un șir A, inițial vid. Asupra lui A se aplică n operații de două tipuri:
+Se consideră un șir '''A''', inițial vid. Asupra lui '''A''' se aplică '''n''' operații de două tipuri:
-x – adaugă numărul x în A
+'''1 x''' – adaugă numărul '''x''' în '''A'''
-k – dacă A ar fi ordonat crescător, care ar fi a k-a valoare?
+'''2 k''' – dacă '''A''' ar fi ordonat crescător, care ar fi a '''k'''-a valoare?
-Date de intrare
+==Cerința==
-Date de ieșire
+Să se răspundă la cele '''n''' întrebări.
-Restricții și precizări
+==Date de intrare==
+Fișierul de intrare '''bstqin.txt''' conține pe prima linie numărul '''n''', iar pe următoarele '''n''' linii se află câte o operație de tip '''1''' sau '''2'''.
+==Date de ieșire==
+Fișierul de ieșire '''bstqout.txt''' va conține atâtea linii câte operații de tip '''2''' sunt în fișierul de intrare.
+==Restricții și precizări==
 Explicație
-La prima întrebare, 2 3, deja în A sunt valorile 3,7,7,9, deci a treia valoare este 7.
+*'''1 ≤ n ≤ 200.000'''
-La a doua întrebare, 2 2, A = 3,7,7,9, deci a doua valoare este 7.
+*Numerele care se adaugă în '''A''' sunt numere întregi reprezentate pe '''32''' de biți cu semn.
-La a treia întrebare, 2 4, A = 2,3,7,7,9,10, deci a patra valoare este 7.
+*Este garantat că la orice operație '''2 k''' valoarea lui '''k''' este mai mică sau egală decât numărul de elemente din '''A'''.
-La a patra întrebare, 2 5, A = 2,3,7,7,9,10, deci a cincea valoare este 9.
+*Este garantat că numerele care se introduc în '''A''' prin operația de tip '''1''' sunt generate aleator.
 La a cincea întrebare, 2 3, A = 2,3,5,7,7,9,10, deci a treia valoare este 5.
 from bisect import insort_left
@@ Line 84: / Line 109: @@
      except IndexError:
          file_out.write("Datele de intrare nu corespund restrictiilor impuse")

Bonte Lucas Gabriel: Pagină nouă: Se consideră un șir A, inițial vid. Asupra lui A se aplică n operații de două tipuri: 1 x – adaugă numărul x în A 2 k – dacă A ar fi ordonat crescător, care ar fi a k-a valoare? Cerința Să se răspundă la cele n întrebări. Date de intrare Fișierul de intrare bstq.in conține pe prima linie numărul n, iar pe următoarele n linii se află câte o operație de tip 1 sau 2. Date de ieșire Fișierul de ieșire bstq.out va conține atâtea linii câte oper...

2024-01-03T16:10:10Z

Pagină nouă: Se consideră un șir A, inițial vid. Asupra lui A se aplică n operații de două tipuri: 1 x – adaugă numărul x în A 2 k – dacă A ar fi ordonat crescător, care ar fi a k-a valoare? Cerința Să se răspundă la cele n întrebări. Date de intrare Fișierul de intrare bstq.in conține pe prima linie numărul n, iar pe următoarele n linii se află câte o operație de tip 1 sau 2. Date de ieșire Fișierul de ieșire bstq.out va conține atâtea linii câte oper...

New page

Se consideră un șir A, inițial vid. Asupra lui A se aplică n operații de două tipuri:

1 x – adaugă numărul x în A
2 k – dacă A ar fi ordonat crescător, care ar fi a k-a valoare?
Cerința
Să se răspundă la cele n întrebări.

Date de intrare
Fișierul de intrare bstq.in conține pe prima linie numărul n, iar pe următoarele n linii se află câte o operație de tip 1 sau 2.

Date de ieșire
Fișierul de ieșire bstq.out va conține atâtea linii câte operații de tip 2 sunt în fișierul de intrare.

Restricții și precizări
1 ≤ n ≤ 200.000
Numerele care se adaugă în A sunt numere întregi reprezentate pe 32 de biți cu semn.
Este garantat că la orice operație 2 k valoarea lui k este mai mică sau egală decât numărul de elemente din A.
Este garantat că numerele care se introduc în A prin operația de tip 1 sunt generate aleator.
Exemplu:
bstq.in

16
1 7
1 9
1 3
1 7
2 3
2 2
1 10
1 2
2 4
2 5
1 5
2 3
1 8
1 10
1 4
1 3
bstq.out

7
7
7
9
5
Explicație
La prima întrebare, 2 3, deja în A sunt valorile 3,7,7,9, deci a treia valoare este 7.
La a doua întrebare, 2 2, A = 3,7,7,9, deci a doua valoare este 7.
La a treia întrebare, 2 4, A = 2,3,7,7,9,10, deci a patra valoare este 7.
La a patra întrebare, 2 5, A = 2,3,7,7,9,10, deci a cincea valoare este 9.
La a cincea întrebare, 2 3, A = 2,3,5,7,7,9,10, deci a treia valoare este 5.

from bisect import insort_left

def validare(nr_n, operatii):
if nr_n > 200000:
raise ValueError
for operation in operatii:
if operation[0] == 1 and (operation[1] < -2147483648 or operation[1] > 2147483647):
raise ValueError
file_out.write("Datele de intrare corespund restrictiilor impuse\n")

def process_operations(operatii, fisier_out):
a = []
for operation in operatii:
if operation[0] == 1:
insort_left(a, operation[1])
elif operation[0] == 2:
fisier_out.write(str(a[operation[1] - 1]) + '\n')

if __name__ == '__main__':
file_in = open("bstqin.txt", "r")
file_out = open("bstqout.txt", "w")
try:
n = int(file_in.readline())
operations = [list(map(int, file_in.readline().split())) for _ in range(n)]
validare(n, operations)
process_operations(operations, file_out)
except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")
except IndexError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")

4088 - BSTQ - Revision history

Bonte Lucas Gabriel at 20:21, 3 January 2024