Lista de probleme 6

Filtrare

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

Fișiere Andrei Onuț concurs Clasa 9 Tablouri unidimensionale (vectori) Vectori caracteristici / de frecventa Șmenul lui Batog (Square Root Decomposition) multiset

Rezolvă

MaxSecvK

#3959

Se consideră un șir A de n numere întregi.
Pentru fiecare subsecvență de lungimea k să se afișeze valoarea maximă.

Folclorul informatic

Fișiere Eugen Nodea dificilă Clasa 10 Structuri de date liniare Coada Deque multiset

Rezolvă

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

Consola 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

Rezolvă

mset

#2224

Se consideră un șir A, inițial vid. Se definesc următoarele operații:

1 x – introduce valoarea x în șirul A
2 x – șterge toate aparițiile lui x din A (dacă x nu apare deloc în A, operația nu se execută)
3 – interogare: care este cea mai mică valoare din A și de câte ori apare (dacă A este șir vid, se va afișa doar valoarea -1)

Dându-se N operații, trebuie să afișați răspunsul la fiecare operație de tip 3.

Fișiere Dan Pracsiu medie Clasa 11 Structuri de date arborescente Structuri de date multiset

Rezolvă

third

#3699

Aveți la dispoziție un șir a₁, a₂, …, a_n de numere naturale și k un număr natural. Pentru fiecare secvență de lungime k din vector trebuie să determinăm pe third, cea de-a treia cea mai mică valoare. De exemplu, secvența 3,6,1,3,7,4 are ca third pe 3, iar secvența 7,7,7,2,2,2,6 are ca third pe 2. Calculați suma valorilor third pentru toate secvențele de lungime k din șir.

Folclorul informatic

Fișiere Dan Pracsiu medie Clasa 11 Structuri de date arborescente Structuri de date multiset Map Heapuri

Rezolvă

LHC

#4364

Cercetătorii din cadrul proiectului LHC (Large Hadron Collider) de la Geneva au anunțat descoperirea unei noi forme a materiei: flatquarkon. Putem reprezenta masa întregului sistem printr-o matrice cu N linii și M coloane unde m_ij reprezintă masa quarcului aflat pe linia i și coloana j.
Aplicând un câmp magnetic perpendicular pe planul unui flatquarkon, putem activa energetic unul sau mai mulți quarci, aceștia devenind capabili să participe în reacții nucleare. Dacă doi quarci activi sunt adiacenți (se învecinează pe linie sau pe coloană), atunci vor participa împreună în orice reacție nucleară. Considerăm un flatquarkon aflat într-un mediul lipsit de câmpuri magnetice. Se dă o listă de Q instrucțiuni de două tipuri:
1. Se aplică un câmp magnetic asupra quarkului de pe linia i și coloana j. Dacă quarkul este inactiv, acesta va fi activat de câmpul magnetic. Dacă este deja activ, nu se va întâmpla nimic.
2. Să se afle energia maximă degajată într-o reacție nucleară între două zone active ale flatquarkon-ului. O zonă activă este o porțiune conexă a matricii (toți quarcii incluși sunt adiacenți) ce conține doar quarci activi și are dimensiune maximă (nu se mai poate adăuga niciun alt quark activ fără a încălca proprietatea de conexitate).

Info-Oltenia 2023, individual 11-12

Consola Vlad-Ioan Țîr concurs Clasa 11 Teoria Grafurilor Arbori cu rădăcină Păduri de mulțimi disjuncte multiset

Rezolvă

Du-te sus!