Grade 12 · liceuRead in English
Algoritmi pentru clasa a xii-aGrade 12
Algoritmii de clasa a xii-a, capitol cu capitol. Citești ideea, rulezi codul pe exemple și vezi ce ai învățat.
- 50algoritmi
- 6capitole
- 1clasă
50 de algoritmi
Clasa a XII-aGrade 12
0%0%
Numere mari
Big numbers · 9 algoritmi
- Adunarea a două numere mariAdding two big numbersAdunăm ca pe hârtie, de la unități spre stânga. La rangul i calculăm s = a[i] + b[i] +…
- Citirea și afișarea unui număr mareReading and printing a big numberUn număr cu zeci sau sute de cifre nu încape în long long, așa că îl citim ca șir de…
- Compararea a două numere mariComparing two big numbersFără zerouri nesemnificative, numărul cu mai multe cifre este mai mare. Dacă au același…
- Factorialul unui număr mareFactorial as a big numberDeja 21! depășește long long, dar n! = 1 * 2 * ... * n se poate construi înmulțind…
- Termenul n din șirul lui Fibonacci (număr mare)The n-th Fibonacci term (big number)Șirul este F(1) = F(2) = 1 și F(i) = F(i - 1) + F(i - 2). Termenii cresc exponențial…
- Împărțirea unui număr mare la un număr micDividing a big number by a small numberSpre deosebire de adunare, împărțirea începe de la cifra cea mai semnificativă, exact ca…
- Înmulțirea a două numere mariMultiplying two big numbersCifra a[i] (rangul 10^i) înmulțită cu cifra b[j] (rangul 10^j) contribuie la rangul…
- Înmulțirea unui număr mare cu un număr micMultiplying a big number by a small numberNumărul mic k (cel mult 10^9) încape într-un int, deci nu trebuie despărțit în cifre.…
- Scăderea a două numere mariSubtracting two big numbersCalculăm A - B. Dacă A < B, calculăm B - A și punem semnul minus în față. Scădem de la…
0%
Algoritmi pe grile: Lee și fill
Grid algorithms: Lee and flood fill · 6 algoritmi
- Fill — cea mai mare zonăFlood fill: the largest regionAceeași matrice de 0 și 1, dar acum vrem numărul de celule al celei mai mari zone de 1…
- Fill — numărul de zoneFlood fill: the number of regionsMatricea are n linii și m coloane, cu 1 pentru teren și 0 pentru apă. O zonă este un…
- Insule în 8 direcțiiIslands in 8 directionsCa la numărarea zonelor, dar două celule de uscat (1) aparțin aceleiași insule dacă se…
- Lee cu mai multe surseLee with multiple sourcesGrila conține 0 (liber), 1 (zid) și 2 (sursă, de exemplu o fântână). Pentru fiecare…
- Lee — drumul minim într-o grilăLee: the shortest path in a gridGrila are n linii și m coloane: 0 = liber, 1 = obstacol. Ne putem deplasa sus, jos,…
- Lee cu reconstituirea drumuluiLee with path reconstructionDupă ce Lee a completat matricea de distanțe, drumul se reface de la final spre start:…
0%
Matematică pentru programare
Math for programming · 9 algoritmi
- Ciur cu cel mai mic divizor prim și factorizare rapidăSmallest-prime-factor sieve and fast factorizationO variantă a ciurului lui Eratostene: în loc să marcăm doar „compus”, reținem în dp[x]…
- Combinări modulo un număr primCombinations modulo a primeCalculăm C(n, k) mod P, cu P = 1 000 000 007 (prim) și n ≤ 10^6. Avem C(n, k) = n! / (k!…
- Algoritmul lui Euclid extinsExtended Euclidean algorithmPe lângă d = cmmdc(a, b), găsim numere întregi x și y cu a * x + b * y = d. Dacă b = 0,…
- Exponențierea modularăModular exponentiationCalculăm a^n mod m pentru n de până la 10^18. Folosim aceeași idee ca la exponențierea…
- Exponențierea rapidăFast exponentiationCalculăm a^n cu aproximativ log2(n) înmulțiri în loc de n. Ideea: a^n = (a^2)^(n/2) dacă…
- Numărul și suma divizorilor din descompunerea în factori primiNumber and sum of divisors from the prime factorizationDacă n = p1^e1 * p2^e2 * ... * pk^ek, un divizor alege pentru fiecare prim un exponent…
- Numărul multiplilor lui k dintr-un intervalNumber of multiples of k in a rangeCâte numere din [a, b] se divid cu k? Numerele din [1, x] divizibile cu k sunt k, 2k,…
- Suma unei progresii aritmetice: formulă vs. buclăSum of an arithmetic progression: formula vs. loopProgresia are primul termen a, rația r și n termeni: a, a + r, ..., a + (n-1) * r. Bucla…
- Triunghiul lui Pascal (combinări)Pascal's triangle (combinations)Combinările C(i, j) — numărul de submulțimi cu j elemente ale unei mulțimi cu i elemente…
0%
Tehnici avansate: doi pointeri, căutare binară pe răspuns, stive monotone
Advanced techniques: two pointers, binary search on the answer, monotonic stacks · 7 algoritmi
- Căutare binară pe răspunsBinary search on the answerAvem n capitole cu a[i] pagini, în ordine, și k corectori. Fiecare corector primește o…
- Doi pointeri — perechi cu suma x într-un vector sortatTwo pointers: pairs with sum x in a sorted arrayVectorul are n valori distincte, în ordine strict crescătoare. Vrem perechile de poziții…
- Element majoritar (Boyer-Moore)Majority element (Boyer-Moore)Elementul majoritar apare de mai mult de n / 2 ori. Algoritmul de vot ține un candidat…
- Fereastra glisantă — cea mai lungă secvență cu suma ≤ SSliding window: the longest subarray with sum ≤ SToate numerele sunt strict pozitive. Ținem o fereastră [st, dr] și suma ei. Extindem…
- Stiva monotonă — următorul element mai mareMonotonic stack: the next greater elementPentru fiecare a[i] căutăm prima valoare strict mai mare aflată în dreapta lui (sau -1).…
- Generarea submulțimilor cu măști de bițiGenerating subsets with bitmasksO submulțime a lui {a[0], ..., a[n-1]} se poate codifica printr-un număr masca între 0…
- Sume parțiale pe matrice2D prefix sumss[i][j] = suma elementelor din dreptunghiul cu colțurile (1, 1) și (i, j). Se calculează…
0%
Structuri de date și STL
Data structures and the STL · 9 algoritmi
- deque — minimul pe ferestre de lungime kdeque: sliding window minimum of length kPentru fiecare secvență de k elemente consecutive vrem minimul. Ținem într-un deque…
- queue — eliminarea din cercqueue: elimination in a circle (Josephus)n copii, numerotați de la 1 la n, stau în cerc. Se numără din k în k, iar copilul la…
- pair — reuniunea intervalelorpair: union of intervalspair<int, int> grupează două valori (first, second) și se compară lexicografic: întâi…
- stack — verificarea parantezelorstack: checking bracketsUn șir cu paranteze (), [] și {} este corect dacă fiecare paranteză închisă se…
- priority_queue — cele mai mari k valoripriority_queue: the k largest valuespriority_queue este un heap: top() dă elementul „cel mai important”, iar push și pop…
- set și map — frecvența cuvintelorset and map: word frequencyCitim cuvinte (litere mici) până la sfârșitul datelor. Un set<string> păstrează fiecare…
- Sortare cu comparatorSorting with a comparatorsort(început, sfârșit, cmp) ordonează după regula noastră: cmp(x, y) întoarce true dacă…
- Păduri de mulțimi disjuncte (union-find)Disjoint-set forests (union-find)Avem n elemente, fiecare inițial în propria mulțime. Operația 1 x y unește mulțimile lui…
- Containerul vector din STLThe STL vector containervector<int> este un tablou care își gestionează singur memoria: push_back adaugă la…
0%
Recapitulare pentru bacalaureat
Baccalaureate exam review · 10 algoritmi
- Fișier — cel mai mare și cel mai mic număr format din cifre dateFile: the largest and smallest number formed from given digitsCerința (tip subiectul III.3): fișierul date.in conține cel mult 10^6 cifre separate…
- Fișier — perechi de numere cu aceeași sumă a cifrelorFile: pairs of numbers with the same digit sumCerința (tip subiectul III.3): fișierul date.in conține pe prima linie n (2 ≤ n ≤ 10^6),…
- Fișier — cea mai lungă secvență de termeni cu aceeași paritateFile: the longest run of terms with the same parityCerința (tip subiectul III.3): fișierul date.in conține un șir de cel mult 10^6 numere…
- Fișier — valorile comune a două șiruri ordonateFile: the common values of two sorted sequencesCerința (tip subiectul III.3): fișierul date.in conține pe prima linie n și m (1 ≤ n, m…
- Fișier — valorile care apar o singură datăFile: the values that appear exactly onceCerința (tip subiectul III.3): fișierul date.in conține cel mult 10^6 numere naturale de…
- Matrice — contururi concentriceMatrix: concentric bordersCerința (tip subiectul III.2): se citește n (2 ≤ n ≤ 20). Construiți în memorie o…
- Subprogram — numărul format din cifrele pareSubprogram: the number formed from the even digitsCerința (tip subiectul III.1): subprogramul pare are un parametru n (0 ≤ n ≤ 10^9) și…
- Subprogram — câte numere dintr-un interval au un număr impar de divizoriSubprogram: how many numbers in a range have an odd number of divisorsCerința (tip subiectul III.1): subprogramul impare are parametrii a și b (1 ≤ a ≤ b ≤…
- Subprogram — eliminarea elementelor cu k cifre dintr-un tablouSubprogram: removing the elements with k digits from an arrayCerința (tip subiectul III.1): subprogramul elimina are parametrii v (un tablou cu n…
- Text — inversarea cuvintelor de lungime parăText: reversing the words of even lengthCerința (tip subiectul III.2): se citește un text de cel mult 100 de caractere, format…