Lista de probleme 2042

Filtrare

Se dă o matrice cu N linii și N coloane. Trebuie să aflăm cea mai frumoasă submatrice pătratică din matrice. Dacă notăm cu A suma elementelor aflate pe diagonala principală din submatrice și cu B suma elementelor aflate pe diagonala secundară din submatrice, atunci frumusețea submatricei este dată de valoarea A - B. Să se determine frumusețea maximă a unei submatrice pătratice.

X3

#4759

Se dă un șir de n numere naturale. Definim prietenia dintre două elemente x și y din șir ca fiind x^y, unde ^ este operatorul pe biți xor - sau exclusiv. Se consideră toate perechile de numere din șir, se calculează pentru fiecare prietenia, apoi se determină suma tuturor prieteniilor. Să se determine această sumă totală.

bambusi

#4761

Eroul nostru, Mao, a ajuns în Crângul de Bambuși din Universul Paralel unde înălțimile tulpinilor de bambus sunt amețitoare. În crângul din acest univers se află n tulpini de înălțimi h[1], h[2], …, h[n]. Mao are nevoie să taie cel puțin M metri de bambus, așa că el procedează astfel: își alege o înălțime H și trece pe la fiecare tulpină în parte. Dacă bambusul i are înălțimea h[i] mai mare decât H, atunci taie din el partea de sus astfel încât să rămână exact H metri, iar dacă bambusul are cel mult H metri, atunci nu taie deloc. Să se determine înălțimea maximă H pe care o poate fixa Mao astfel încât după tăiere să poată pleca acasă cu cel puțin M metri de bambus.

Fie un șir de n valori 0 și 1 și un număr k. Afișați lungimea maximă a unei secvențe din șir care conține doar valori de 1 după ce s-au modificat cel mult k valori de 0 în valori de 1.

La o expoziție auto se află, în șir, mașini de epocă, fiecare având câte un cod, format prin alipirea, în această ordine, a două numere naturale nenule: identificatorul colecționarului care deține mașina, respectiv anul fabricației acesteia.

Scrieţi un program C/C++ care citeşte de la tastatură un număr x (x∈[1880,1950]), reprezentând un an calendaristic și un șir de cel mult 10 5 numere din intervalul [ 10 4 , 10 9 ], reprezentând codurile mașinilor, în ordinea din șirul în care sunt expuse.

Se cere să se afișeze pe ecran identificatorii colecționarilor care dețin ultimele două mașini, din șirul celor expuse, ambele fiind fabricate în anul x și aflate în șir pe poziții consecutive. Numerele, nu neapărat distincte, sunt afișate în ordinea în care mașinile corespunzătoare apar în șir, separate printr-un spațiu, iar dacă nu există două astfel de mașini, se afișează pe ecran mesajul nu exista.

Proiectați un algoritm eficient din punctul de vedere al memoriei utilizate și al timpului de executare.

Bacalaureat 2025 - model

Fiind date două numere naturale a și b, numim valoare generată de a și b un număr obținut din a prin alipirea la stânga sau la dreapta sa a cifrelor lui b, în ordinea în care apar în acesta. Exemplu: dacă a = 123 și b = 45, se pot obține două numere generate de acestea: 12345 și 45123.

Fiind date două numere naturale a și b, numim valoare generată de a și b un număr obținut din a prin alipirea la stânga sau la dreapta sa a cifrelor lui b, în ordinea în care apar în acesta. Scrieți un program C/C++ care citește de la tastatură două numere naturale din intervalul [2,50], m și n, și construiește în memorie un tablou bidimensional cu m linii, numerotate de la 1 la m, și n coloane, numerotate de la 1 la n, în care fiecare element este egal cu cea mai mică valoare generată de numerele de ordine ale liniei, respectiv coloanei pe care se află. Programul afișează pe ecran tabloul obținut, fiecare linie a tabloului pe câte o linie a ecranului, elementele fiecărei linii fiind separate prin câte un spațiu.

Fie o secvenţă de N valori binare reprezentând un număr natural scris în baza 2. De exemplu secvenţa de 4 biţi 1101 este reprezentarea binară a numărului natural 13. Cei N biţi sunt numerotaţi de la dreapta la stânga cu numere de la 0 la N-1. În continuare asupra secvenţei se vor efectua exact P operaţii. Fiecare operaţie este dată printr-un număr natural reprezentând indicele unui bit care se elimină din secvenţă. După fiecare din cele P operaţii de eliminare, trebuie să stabiliţi dacă secvenţa rămasă este sau nu reprezentarea binară a unui număr natural divizibil cu 3.

Considerăm şirul numerelor naturale nenule: 1, 2, 3, 4, ... Din acest şir se elimină N numere naturale distincte. Trebuie să răspundeţi la Q întrebări de forma: Pe ce poziţie se află numărul x în şir după eliminarea celor N numere?

aperm

#4712

Se consideră o matrice cu n linii și p coloane. Fiecare linie a matricei este o permutare a mulțimii {1, 2, ..., p}. Să se ordoneze lexicografic liniile matricei.

sir2dif

#4713

Se consideră un sir de numere naturale a1, a2, …, an. Să se determine suma maximă a unei expresii ai - aj + ak - ap, unde 1 ≤ i < j < k < p ≤ n.

Du-te sus!