Lista de probleme 19
Filtrare
KSum2
#3846
După ce Ionuț a învățat despre algoritmul lui Kadane își pune următoarea întrebare: se dă N și K apoi un vector cu N elemente, din acest vector care este suma maximă a unei secvențe (elemente adiacente) de lungime cel puțin K. A zis să vă întrebe pe voi cum se face.
infoleague.net propunere runda 2 problema 2.
mexitate
#2451
Se dă o matrice A cu N linii și M coloane cu elemente numere naturale nu neapărat distincte. Pentru o submatrice definim mex-ul acesteia ca fiind cea mai mică valoare naturală nenulă care nu apare în aceasta.
Să se calculeze produsul mex-urilor tuturor submatricelor având K linii și L coloane ale matricei A.
ONI 2018 clasa a IX-a
Pracsiu Dan (dnprx)
Eugenie Daniel Posdarascu
concurs
Clasa 9
Tablouri bidimensionale (matrice)
Parcurgerea matricelor oarecare
Vector de frecvență
Șmenul lui Batog (Square Root Decomposition)
fsecv
#3085
Se consideră un șir A format din N numere întregi, numerotate de la 1 la N. Numim secvență a șirului A orice succesiune de elemente consecutive din șir de forma A[i], A[i+1], …, A[j], cu 0 < i < j ≤ N. Fiind dat șirul A cu N numere întregi se cere să se răspundă la Q întrebări de forma: i j k (0 < i < j ≤ N). Pentru fiecare întrebare se cere să se determine câte numere din secvența A[i], …, A[j] au frecvența de apariții egală cu k.
Lot Național Juniori 2019
weekend
#3468
În acest weekend tocmai s-au pus în vânzare bilete pentru concertul celui mai în vogă artist. Cum acesta este extrem de popular, un număr de n persoane s-au așezat la coadă la casa de bilete. Pentru simplitate, prima persoană așezată la coadă va avea indicele 1, a doua va avea indicele 2 și așa mai departe. Deoarece statul la coadă este extrem de plictisitor, fiecare om a început să numere câte persoane mai scunde decât el se află în fața sa. Fiind dat șirul inițial de observații ale oamenilor care stau la coadă, să se reconstruiască șirul minim lexicografic care poate reprezenta înălțimile acestora.
Info-Oltenia 2020, Clasele IX-X
Cartita
#3759
În grădina lui Macarie există un șir de N morcovi, numerotați de la 1 la N. Ca să știe unde sunt plantați, Macarie a făcut câte o grămăjoară de pământ în dreptul fiecărui morcov și a notat înălțimea fiecăreia exprimată în centimetri. Astfel morcovul i are în dreptul său o grămăjoară de pământ cu înălțimea de h[i] centimetri. Ajutați-l pe Macarie să identifice înălțimea grămăjoarei celui mai tentant morcov, pentru mai multe intervale date, după efectuarea tuturor modificărilor realizate de cârtiță.
ONSEPI, 2021, baraj juniori
Medians
#3831
Se dă un vector cu n elemente. Să se determine numărul de secvențe care au medianul valorilor egal cu k.
infoleague.net runda 2 problema 1.
Iacob Tudor (IacobTudor)
Cozma Tiberiu Ștefan
concurs
Clasa 9
Tablouri unidimensionale (vectori)
Probleme cu secvențe
Șmenul lui Batog (Square Root Decomposition)
kth1
#4433
Se dă un șir V ce conține N numere întregi numerotate începând de la 1: V[1], V[2], ..., V[N] și două numere naturale nenule K și L, cu proprietatea că: 1 ≤ K ≤ L ≤ N. Mihai studiază doar secvențele de lungime L, adică secvențele formate din exact L elemente situate pe poziții alăturate în acest șir V. El își poate pune următoarea întrebare: “Dacă aș rearanja, în ordine crescătoare, elementele secvenței de lungime L care începe la poziția poz în șirul V, ce valoare s-ar afla pe poziția a K-a în cadrul secvenței rezultate?”. Pentru secvența din șir care începe la poziția poz și are L elemente, adică V[poz], V[poz+1], ..., V[poz+L-1], valoarea elementului de pe poziția a K-a în cadrul secvenței este V[poz+K-1]. Ajutați-l pe Mihai să afle care este răspunsul corect pentru Q întrebări de tipul descris mai sus!
ONI 2023 clasa a VIII-a
nrinversiuni
#3206
Se dă șirul a1, a2, …, an care este o permutare a mulțimii {1, 2, ..., n}. O inversiune în permutare este o pereche (i, j) cu proprietatea că i < j și a[i] > a[j]. Să se determine numărul inversiunilor permutării.
E-BirocratieInterstelara
#3830
Anual, Imperiul Interstelar organizează o întâlnire administrativă în capitală. La întâlnire sunt invitați toți guvernatorii planetelor din imperiu. Planetele imperiului pot fi numerotate cu valori de la 0 la MOD-1(inclusiv) unde planeta 0 este chiar capitala. Distanțele mari dintre planete fac transportul obișnuit între planete aproape imposibil. Din fericire, găuri de vierme conectează tot imperiul. Vom nota planeta către care duce o gaură de vierme cu f(x) = (x * a + b) % MOD. Astfel, de la planeta x există un drum către planeta f(x) și un drum de la planeta f(x) la planeta x. Fiecare guvernator începe de pe o planetă cunoscută și trebuie să ajungă în capitală. Atenție, pozițiile inițiale nu trebuie să fie distincte! Fiecare salt printr-o gaură de vierme consumă o unitate de energie din rețeaua centrală. Se presupune că fiecare guvernator ia ruta cea mai scurtă către capitală. Din motive birocratice, sunteți rugați să calculați cantitatea de energie consumată de transportul guvernatorilor către captială.
infoleague.net runda de antrenament, problema E.
Iacob Tudor (IacobTudor)
Tudose Rareș Felix
concurs
Clasa 10
Probleme diverse
Diverse
Șmenul lui Batog (Square Root Decomposition)
number theory
Median_Heaps
#1901
Se dă un vector de N numere naturale nenule, indexat de la 1.
Se cere să se raspundă la Q interogări de tipul:
- pentru un interval
[l, r]din vector, aflați costul total mimin, al egalizării tuturor elementelor din interval.
ad-hoc
Dumitrescu Ovidiu Mihail (dovidiu)
Bucă Mihnea-Vicențiu, Ovidiu Mihail Dumitrescu
dificilă
Clasa 11
Structuri de date arborescente
Structuri de date
Șmenul lui Batog (Square Root Decomposition)
Arbori indexați binar
set
multiset