Lista de probleme 21

Filtrare

TSM

#2012

TH, Seba, Șcuțu și Năstuț se joacă noul joc numit TSM. TSM are un sistem de tip multiplayer foarte interesant: se formează două echipe care se vor confrunta, una ce conține 4 jucători ce vor avea rol de apărători și alta ce conține un singur jucător cu rol de atacator (foarte necinstit). Mygo a auzit că cei 4 prieteni și-au făcut echipă, iar pe el nu l-au invitat, așa că decide să îi provoace la joc. Într-o rundă de joc acțiunile se petrec pe un câmp de luptă, inițial gol, iar apărătorii disting următoarele evenimente:

1 x : TH observă că Mygo a trimis pe câmpul de luptă un tanc de coeficient x și își anunță aliații.
2 K : Seba consideră că cel mai periculos tip de tanc aflat pe câmpul de luptă este cel cu al K – lea cel mai mic coeficient și îl afișează în consolă, pe un nou rând.
3 : Năstuț scrie în consolă, pe un nou rând, coeficientul cel mai mic al unui tanc aflat în momentul respectiv pe câmpul de luptă.
4 : Șcuțu trage cu tunul într-un tanc de coeficient egal cu ultimul scris de Seba în consolă și îl elimină.

Fișiere Bogdan Ioan Popa dificilă Clasa 11 Structuri de date arborescente Structuri de date Heapuri Arbori indexați binar

Rezolvă

cntSQ

#2779

Se dă o matrice binară (valori 0 și 1). Să se determine câte pătrate exista cu proprietatea că acestea au pe marginea lor doar valori 1.

Fișiere Bogdan Ioan Popa dificilă Clasa 11 Structuri de date arborescente Structuri de date Arbori indexați binar

Rezolvă

NrSubCresc

#3209

Aflați numărul subsirurilor strict crescătoare de lungime k.

Consola Andrei Moca dificilă Clasa 11 Programare dinamică Probleme diverse de programare dinamică Arbori indexați binar

Rezolvă

company_tree

#3713

Undeva, într-un ținut îndepărtat, își desfășoară activitatea o vestită companie, mai exact Mondial Computers SRL. Aceștia lucrează cu mulți clienți de renume, deci au nevoie de multă forță de muncă. Astfel, ei au o bază de date în care mențin informații despre angajații lor, dar, recent, echipa care se ocupa de această bază de date a dat dovadă de un randament scăzut, iar ca urmare a acestui fapt, manager-ul general a decis, fără a ține cont de consecințe, să îi concedieze, iar aceștia, de supărare, au șters înainte de a pleca din companie toate datele angajaților. Acum manager-ul are nevoie de ajutorul vostru(voluntar, desigur) pentru reorganizarea acestei baze de date până reușește să angajeze noi oameni.

Consola Alexandru Lorintz dificilă Clasa 11 Teoria Grafurilor Arbori cu rădăcină Arbori indexați binar Arbori de intervale Range Minimum Query Cautare binara

Rezolvă

SecventaK

#1447

Se consideră un şir format din n numere naturale şi un număr dat k. Să se determine numărul secvenţelor din şir care au proprietatea că suma elementelor secvenţei este de cel puţin de k ori mai mare sau egală decât numărul elementelor secvenţei.

Fișiere Mihai Bunget dificilă Clasa 11 Programare dinamică Probleme diverse de programare dinamică Arbori indexați binar Sume parțiale Sortare

Rezolvă

Calafat

#1692

Se dă un șir format din N numere naturale. Pentru fiecare valoare distinctă dintr-o subsecvență cuprinsă între doi indici st si dr considerăm distanța dintre indicii primei și ultimei apariții ale acesteia în cadrul subsecvenței. Dându-se M subsecvențe de forma [st,dr], se cere să se calculeze suma distanțelor corespunzătoare tuturor valorilor distincte din subsecvență.

ONI 2016, clasele XI-XII

Fișiere Denis-Gabriel Mită concurs Clasa 11 Probleme diverse Probleme diverse Arbori de intervale Arbori indexați binar Șmenul lui Batog (Square Root Decomposition)

Rezolvă

permsort

#4228

Grădinarul Marian are la dispoziţie o permutare cu n elemente şi un număr natural S care iniţial are valoarea 0. Marian execută n operaţii de forma:

alege elementul poziția x a minimului din permutare
elimină acest element din permutare, iar toate elementele de la stânga sa le mută la sfârşitul permutării (păstrând ordinea elementelor din stânga)
adună la S pe x.

Determinaţi valoarea lui S după ce grădinarul Marian termină de executat toate cele n operaţii.

Lot Botosani 2012

Fișiere Vlad Ionescu concurs Clasa 11 Structuri de date arborescente Structuri de date Arbori indexați binar

Rezolvă

Inversiuni

#1715

Ludwig are o permutare p=(p[1],p[2],...,p[N]) a mulțimii {1,2,..,N} și o masă pe care putea așeza numerele din permutare. Ludwig ia primul număr din permutare, adică p[1], și îl așează pe masă. Al doilea număr, p[2], îl pune fie în stânga lui p[1], fie în dreapta lui p[1]. La fiecare pas, dacă s-au așezat pe masă deja numerele p[1], p[2], …, p[i], atunci numărul p[i+1] este pus fie în stânga numerelor deja așezate, fie în dreapta lor.

Ajutați-l pe Ludwig să determine o modalitate de așezare a întregii permutări pe masă astfel încât în final să se obțină o nouă permutare care are un număr minim de inversiuni.

Lot Juniori Focsani, 2016

Fișiere Dan Pracsiu concurs Clasa 11 Probleme diverse Probleme diverse Șmenul lui Batog (Square Root Decomposition) Arbori indexați binar

Rezolvă

Bisortare

#3756

Pentru o permutare p₁, p₂, …, p_N a numerelor de la 1 la N și o poziție K, (1 ≤ K ≤ N), notăm cu Best_K numărul minim de interschimbări (a valori situate pe poziții consecutive) necesare pentru a se obține o permutare descrescătoare de la poziția 1 la poziția K și crescătoare de la poziția K la poziția N. Se dă o permutare. Se cere să se rezolve una dintre următoarele două cerințe:
1. Pentru o poziție K dată să se calculeze Best_K.
2. Pentru toate pozițiile K de la 1 la N să se calculeze Best_K.

ONSEPI, 2021, clasele XI-XII

Consola Adrian Panaete concurs Clasa 11 Structuri de date arborescente Structuri de date Arbori indexați binar

Rezolvă

addk

#3861

Se consideră un şir A cu N elemente numere naturale A[1], ..., A[N] si un număr natural K. Se cere să se proceseze Q cerinţe de următoarele două tipuri:

1 i₁ i₂ ... i_K: se permută circular la stânga elementele şirului A[i₁], …, A[i_K]. Astfel noile valori ale elementelor A[i₁], A[i₂], …, A[i_K-1], A[i_K] vor fi A[i₂], A[i₃], …, A[i_K], A[i₁]. Remarcaţi că i₁, …, i_K sunt distincte şi nu neapărat in ordine crescătoare.
2 l r m: se cere calculul sumei elementelor tuturor subsecvenţelor continue de lungime m din secvenţa A[i_l], A[i_l+1], …, A[i_r-1], A[i_r]. Remarcaţi că elementele care apar în mai multe secvenţe vor fi adunate de mai multe ori.

EJOI 2021, ziua 1

Consola Mihai Bunget concurs Clasa 11 Structuri de date arborescente Structuri de date Arbori indexați binar

Rezolvă

Du-te sus!