Algorithms platformCitește în română
266 C++ algorithms, explained and runnable
The complete high school computer science collection (grades 9–12), from the digits of a number to graphs and dynamic programming. Read the idea, edit the code, run it on a real compiler and track your progress with a free account.
- 266algorithms
- 27chapters
- 4grades
266 algorithms
Grade 9Clasa a IX-a
0%0%
Digits of a number
Cifrele unui număr · 15 algorithms
- Number of occurrences of digit kNumărul de apariții ale cifrei kWe go through the digits of n and count how many are equal to k. With do-while, for n = 0 and k = 0 the answer is correctly 1.
- Largest number formed from the digits of nCel mai mare număr format cu cifrele lui nWe count how many times each digit appears, in a frequency array with 10 positions (frecv[c] = how many times digit c appears). The largest number…
- Check digit (digital root)Cifra de controlThe check digit is obtained by repeatedly replacing the number with the sum of its digits until a single digit remains (for example 99999 -> 45 ->…
- Largest and smallest digitCifra maximă și cifra minimăWe start with the maximum at 0 (the smallest possible digit) and the minimum at 9 (the largest possible digit), then compare every digit with them.…
- Checking for distinct digitsVerificarea cifrelor distincteChecks whether all digits of n are different. We remember which digits we have already seen (vazut[c] becomes true on the first occurrence of c); if…
- Printing the digits in their order in the numberAfișarea cifrelor în ordinea din numărWith n % 10 the digits come out from right to left. To print them from left to right, we first compute p = the largest power of 10 not greater than…
- Doubling the odd digitsDublarea cifrelor impareEvery odd digit of n appears twice in the result. We build the result from right to left with rez = rez + digit * p; an odd digit is added twice, so…
- Removing the even digitsEliminarea cifrelor pareWe build a new number from the odd digits of n, keeping their order. The digits come from right to left, so every kept digit is placed in front of…
- Replacing one digit with anotherÎnlocuirea unei cifre cu altaReplaces every occurrence of digit x in n with digit y. We rebuild the number from right to left with rez = rez + digit * p, putting y in place of…
- Palindrome numberNumăr palindromA number is a palindrome if it reads the same from left to right and from right to left, i.e. it is equal to its reverse. We work on a copy, because…
- Number of digits of a numberNumărul de cifre ale unui numărCounts the digits of n by cutting off the last digit at every step (n / 10) until the number becomes 0. We use do-while so that the number 0 is…
- Reverse of a numberOglinditul unui numărBuilds the number made of the digits of n written in reverse order. At every step we take the last digit (n % 10), append it to the right of the…
- First digit of a numberPrima cifră a unui numărThe first (leftmost) digit is what remains after we cut off all the other digits: we divide by 10 while the number has at least two digits (n >= 10).
- Product of the digits of a numberProdusul cifrelor unui numărMultiplies the digits of n. The product starts from 1 (the identity element of multiplication), not from 0. With do-while, for n = 0 we correctly…
- Sum of the digits of a numberSuma cifrelor unui numărAdds up the digits of n. The last digit is obtained with n % 10, then removed with n / 10. We repeat until n becomes 0.
0%
Divisibility and prime numbers
Divizibilitate și numere prime · 17 algorithms
- GCD by repeated division (Euclid's algorithm)Cmmdc prin împărțiri repetate (algoritmul lui Euclid)The greatest common divisor does not change if we replace the pair (a, b) with (b, a % b). We repeat until b becomes 0; then the GCD is a. It also…
- GCD by repeated subtractionCmmdc prin scăderi repetateWe subtract the smaller number from the larger one until they become equal; the common value is the GCD. It only works for a, b > 0 (with a 0 the…
- Least common multipleCel mai mic multiplu comunWe use the relation gcd(a, b) * lcm(a, b) = a * b. We compute the GCD with Euclid's algorithm on copies of a and b, then lcm = a / gcd * b (we…
- Prime factorizationDescompunerea în factori primiWe try the factors d = 2, 3, 4, ... and divide n by d as many times as possible, counting how many times (the exponent). A composite d no longer…
- Prime divisors of a numberDivizorii primi ai unui numărThis is the prime factorization, printing only the factors, without exponents. Every factor found is removed completely from n.
- Proper divisors of a numberDivizorii proprii ai unui numărProper divisors are the divisors other than 1 and n. We use the same two passes as when printing all divisors, but start from d = 2, so 1 and its…
- Divisors of a numberDivizorii unui numărDivisors come in pairs: if d divides n, then n / d divides n too, and one of them is at most the square root of n. So it is enough to try d from 1…
- Euler's totient functionIndicatorul lui Eulerφ(n) is the number of values in 1..n that are coprime with n. If p1, p2, ... are the prime divisors of n, then φ(n) = n · (1 - 1/p1) · (1 - 1/p2) ·…
- Perfect numberNumăr perfectA number is perfect if it equals the sum of its divisors smaller than itself (6 = 1 + 2 + 3). We compute the sum of all divisors in O(√n) and…
- Number of divisorsNumărul divizorilorFor every d with d * d <= n that divides n we count two divisors, d and n / d, except when d * d == n, when the two coincide.
- Pairs of twin primesPerechi de numere prime gemeneTwo prime numbers are twins if their difference is 2 (for example 11 and 13). We print all pairs (p, p + 2) with p + 2 <= n, testing both numbers…
- Coprime numbersNumere prime între eleTwo numbers are coprime if their only common divisor is 1, i.e. gcd(a, b) = 1. The numbers themselves do not have to be prime: 15 and 28 are coprime.
- The first n prime numbersPrimele n numere primeWe take the candidates 2, 3, 4, ... one by one and test them with the primality test up to √x. We stop after printing n prime numbers.
- Simplifying a fractionSimplificarea unei fracțiiA fraction a / b becomes irreducible if we divide the numerator and the denominator by gcd(a, b). We compute the GCD on copies, to keep the original…
- Sum of divisorsSuma divizorilorWe add the divisors in pairs (d and n / d) for d * d <= n; when n is a perfect square, the root is added only once.
- Primality testTest de primalitateA number is prime if it has exactly two divisors: 1 and itself (so 0 and 1 are not prime). If n has a divisor d between 2 and n - 1, it also has one…
- Last digit of x to the power yUltima cifră a lui x la puterea yThe last digit of a product depends only on the last digits of the factors. The last digits of powers repeat with period 4 (for example for 3: 3, 9,…
0%
Number sequences read one at a time
Șiruri de numere citite pe rând · 13 algorithms
- Longest run of equal elementsCea mai lungă secvență de elemente egaleA run means elements on consecutive positions. lung is the length of the current run: it grows when the new number equals the previous one and goes…
- Largest Fibonacci term not greater than nCel mai mare termen Fibonacci cel mult egal cu nWe generate the terms of the Fibonacci sequence (1, 1, 2, 3, 5, ...) while the next term does not exceed n. The last term kept is the answer. We…
- The two largest valuesCele mai mari două valoriWe keep the largest value (max1) and the second one (max2). If the new number exceeds max1, the old max1 moves down to second place; otherwise, if…
- Reading a sequence terminated by 0Citirea unui șir terminat cu 0We do not know in advance how many numbers follow: we read up to the first 0, which only marks the end and is not part of the sequence. The program…
- GCD of several numbersCmmdc-ul mai multor numeregcd(a, b, c) = gcd(gcd(a, b), c). We keep in rez the GCD of the numbers read so far and combine it, with Euclid's algorithm, with every new number.…
- The n-th term of the Fibonacci sequenceAl n-lea termen al șirului lui FibonacciThe Fibonacci sequence starts with 1, 1 and every term is the sum of the two before it: 1, 1, 2, 3, 5, 8, ... We do not need an array: we keep only…
- Maximum and minimum of a sequenceMaximul și minimul unui șirn is read, then n integers. The maximum and the minimum start from the first number read (not from 0, because all numbers may be negative), then…
- Counting elements with a propertyNumărarea elementelor cu o proprietaten and n natural numbers are read. We count how many of them are even and how many have the last digit equal to the first. Each property has its own…
- Number of sign changesNumărul de schimbări de semnn non-zero numbers are read. A sign change happens between two consecutive terms with opposite signs, i.e. when their product is negative. We…
- Pairs of consecutive terms with a propertyPerechi de termeni consecutivi cu o proprietateWe count the pairs of adjacent terms that have the same parity. A sequence of n terms has n - 1 consecutive pairs; for every new term x, the pair is…
- Checking an arithmetic progressionVerificarea unei progresii aritmeticeA sequence is an arithmetic progression if the difference between two consecutive terms is always the same (the common difference). The difference…
- Checking a non-decreasing sequenceVerificarea unui șir crescătorThe sequence is non-decreasing if every number is at least equal to the one before it. We keep the previous number in the variable ant and compare…
- Sum and arithmetic meanSuma și media aritmeticăn and n integers are read; their sum and arithmetic mean are printed, with two decimals. For the mean we divide a real number by n (1.0 * suma / n);…
0%
Number bases
Baze de numerație · 6 algorithms
- Converting from base 10 to base bConversia din baza 10 în baza bWe repeatedly divide n by b; the remainders are the digits in base b, but they come from the last to the first. That is why every new digit is…
- Converting to base 10 using powers of the baseConversia în baza 10 cu puterile bazeiThe version for b <= 10, when the number can be read as an integer: its digits are extracted from the right with n % 10, and every digit is…
- Converting from base b to base 10Conversia din baza b în baza 10The number in base b is read as text (it may contain A..F), then Horner's scheme is applied: we go through the digits from left to right and do rez…
- Converting between any two basesConversia între două baze oarecareWe go through base 10: first we convert the number from base b1 to base 10 (Horner's scheme), then from base 10 to base b2 (repeated division). The…
- Number of 1 bits in binaryNumărul de biți 1 din scrierea în baza 2The base-2 digits are obtained just like the base-10 digits, except that we divide by 2: the last binary digit is n % 2. We count how many of them…
- Checking for a power of 2Verificarea unei puteri a lui 2A power of 2 has a single 1 bit in base 2 (for example 64 = 1000000). Subtracting 1 turns that bit into 0 and all the bits to its right into 1 (63 =…
0%
One-dimensional arrays (vectors)
Tablouri unidimensionale (vectori) · 11 algorithms
- Reading and printing an arrayCitirea și afișarea unui vectorAn array stores several values of the same type, accessed by index. We declare the array with a fixed maximum size and use positions 1..n. n and the…
- Removing the even elementsEliminarea elementelor pareInstead of deleting the even elements one by one (every deletion shifts the whole rest of the array), we make a single pass: k counts the elements…
- Inserting a value after every even elementInserarea unei valori după fiecare element parWe go through the array from the end to the beginning. When v[i] is even, we shift the elements after it one position to the right and put x at…
- Inserting an element at a positionInserarea unui element pe o pozițieTo put val at position poz, we make room: we shift the elements v[poz..n] one position to the right. Shifting starts from the end (from n down to…
- Reversing an arrayInversarea unui vectorWe swap the first element with the last, the second with the second to last, and so on: v[i] with v[n - i + 1]. We stop halfway (i <= n / 2); if we…
- The maximum and the positions where it appearsMaximul și pozițiile pe care apareUnlike a sequence read one value at a time, an array can be traversed several times: in the first pass we find the maximum, in the second we print…
- Circular shift to the rightPermutarea circulară la dreaptaEvery element moves one position to the right, and the last one goes to the first position. We save v[n], shift the rest from the end towards the…
- Circular shift to the leftPermutarea circulară la stângaEvery element moves one position to the left, and the first one goes to the last position. We save v[1] in a variable, shift the rest (v[i] = v[i +…
- Deleting the element at a positionȘtergerea elementului de pe o pozițieTo delete the element at position poz, we shift the elements after it one position to the left, from left to right (v[i] = v[i + 1]), then n…
- Sum of the elements on even and odd positionsSuma elementelor de pe pozițiile pare și impareMind the difference between the position (the index i) and the value (v[i]). Parity is checked here for the index: v[2], v[4], ... are on even…
- Checking a symmetric arrayVerificarea unui vector simetricAn array is symmetric (a palindrome) if v[i] = v[n - i + 1] for every i. We compare the pairs from both ends towards the middle and stop at the…
0%
Sorting and searching
Sortare și căutare · 10 algorithms
- Binary searchCăutarea binarăIt only works on an array sorted in increasing order. We compare x with the middle element of the range [st, dr]: if they are equal, we are done; if…
- Linear searchCăutarea secvențialăWe check the elements one by one, starting from the first, until we find the value x or reach the end of the array. It works on any array, sorted or…
- Merging two sorted arraysInterclasarea a doi vectori sortațiFrom two arrays sorted in increasing order we build a third, also sorted. We compare the current elements a[i] and b[j], copy the smaller one and…
- First position with a value greater than or equal to xPrima poziție cu valoare mai mare sau egală cu xThe binary search variant that does not stop at the first match: in an array sorted in increasing order, we look for the smallest position p with…
- Sorting with std::sortSortarea cu std::sortThe <algorithm> library has the sort function, which orders in O(n log n). It takes the start and the end of the range: for positions 1..n we write…
- Sorting by two criteriaSortarea după două criteriiWe order the numbers increasingly by their last digit, and numbers with the same last digit decreasingly by value. The sorting algorithm stays the…
- Insertion sortSortarea prin inserțieLike arranging playing cards in your hand: the first i - 1 elements are already sorted, and v[i] is inserted in its place among them. We save v[i]…
- Bubble sortSortarea prin metoda bulelorWe go through the array and swap any two neighbouring elements that are in the wrong order (v[i] > v[i + 1]). After every pass, the largest…
- Counting sortSortarea prin numărareWhen the values are small natural numbers (here 0..10000), we do not compare elements: we count how many times each value appears in a frequency…
- Selection sortSortarea prin selecțieFor every position i, from 1 to n - 1, we look for the minimum of v[i..n] and bring it to position i with a single swap. After step i, the first i…
0%
Frequency arrays, prefix sums and the Sieve of Eratosthenes
Frecvență, sume parțiale și ciurul lui Eratostene · 10 algorithms
- Common digits of two numbersCifrele comune a două numereIn two arrays of 10 positions we mark which digits appear in each number (aparA[c], aparB[c]). The common digits are the ones marked in both arrays;…
- Sieve of EratosthenesCiurul lui EratosteneFinds all prime numbers up to n. We start with all numbers unmarked; for every unmarked i (hence prime) we mark its multiples as not prime, starting…
- Majority elementElementul majoritarThe majority element appears more than n / 2 times. The voting algorithm (Boyer-Moore) keeps a candidate and a counter: an element equal to the…
- The missing number in a permutationNumărul lipsă dintr-o permutaren and n - 1 distinct numbers from the set {1, 2, ..., n} are given; exactly one is missing. The sum of all numbers from 1 to n is n · (n + 1) / 2…
- Subarray of length k with the maximum sumSecvența de lungime k cu suma maximăSliding window: we compute the sum of the first k elements, then slide the window one position to the right: we add the element that enters (v[i])…
- Maximum subarray sum (Kadane's algorithm)Secvența de sumă maximă (algoritmul lui Kadane)We go through the array and keep the sum of the current subarray, which ends at position i. If the sum so far has become negative, it no longer…
- Prefix sumsSume parțiales[i] = v[1] + v[2] + ... + v[i], with s[0] = 0, is computed in a single pass: s[i] = s[i - 1] + v[i]. Then the sum over any range [st, dr] is s[dr]…
- Distinct values and their frequenciesValorile distincte și frecvențele lorOnce the frequency array is built, the distinct values are the indices val with frecv[val] > 0. Going through them in increasing order, we print…
- Marking ranges with a difference arrayMarcarea intervalelor cu vectorul de diferențeWe have n positions, initially 0, and m operations 'add 1 to positions a..b'. Instead of walking every range, we only note its ends: d[a]++ (it…
- Frequency arrayVectorul de frecvențăFor small natural values (here 0..1000), frecv[x] stores how many times the value x has appeared. The value becomes an index, so every number read…
0%
Text files
Fișiere text · 5 algorithms
- Reading until the end of the fileCitirea până la sfârșitul fișieruluiThe file date.in contains integers, but we do not know how many. The expression fin >> x returns 'true' as long as reading succeeds and 'false' at…
- Counting the values in a fileNumărarea valorilor dintr-un fișierThe file date.in contains a natural number k on the first line, and on the following lines a sequence of natural numbers of unknown length. We read…
- Processing a file line by linePrelucrarea unui fișier pe liniigetline(fin, linie) reads a whole line, spaces included, up to '\n'. The loop while (getline(fin, linie)) stops at the end of the file. We count the…
- Formatted writing to a fileScrierea formatată într-un fișiern is read from date.in and the numbers from 1 to n are written to date.out, five per line. ofstream is used exactly like cout; a new line is written…
- Sum of the numbers on each lineSuma numerelor de pe fiecare linieEvery line of date.in contains a few integers, an unknown number of them. We read the line with getline, then 're-read' it as a stream of numbers…
Grade 10Clasa a X-a
0%0%
Subprograms (functions)
Subprograme (funcții) · 11 algorithms
- GCD and LCM functionsFuncție cmmdc și cmmmcThe function cmmdc(a, b) applies Euclid's algorithm by division: while b is not 0, the pair (a, b) becomes (b, a % b). The function cmmmc(a, b)…
- Primality functionFuncție de primalitateWe write the function estePrim(x) once, returning true if x is prime, and call it for every number read. The function looks for a divisor d between…
- Function with an array parameter (the maximum)Funcție cu vector ca parametru (maximul)An array is passed to a function together with the number of elements: int maxim(int v[], int n). The function actually receives the address of the…
- Function returning the reverse of a numberFuncție care întoarce oglinditulThe function oglindit(x) builds the number with the digits of x in reverse order and returns it. With its help, the function palindrom(x) fits on…
- Function for the sum of digitsFuncție pentru suma cifrelorThe function sumaCifre(x) receives the number by value (it works on a copy, so the x in main is not destroyed) and returns the sum of its digits. In…
- Swapping by referenceInterschimbare prin referințăWe compare two functions that try to swap the values of two variables. schimbaValoare(int x, int y) receives copies, so the changes are lost when…
- Minimum and maximum returned by referenceMinim și maxim întoarse prin referințăA function can return a single value with return. When we need several results, we make them reference parameters: void minMax(int v[], int n, int…
- Amicable numbersNumere prieteneTwo numbers a and b are amicable if the sum of the proper divisors of a (the divisors smaller than a) is b and the sum of the proper divisors of b…
- Super-prime numbersNumere superprimeA number is super-prime if all its prefixes are prime. For example 239 is super-prime: 2, 23 and 239 are prime. The function estePrim(x) is reused…
- Palindromes in a rangePalindroame dintr-un intervalA problem solved by splitting it into small functions: oglindit(x) returns the reverse of x, palindrom(x) uses the first one, and main only walks…
- Global and local variablesVariabile globale și variabile localeA global variable (declared outside the functions) is visible from the whole program, starts automatically at 0 and keeps its value between calls. A…
0%
Two-dimensional arrays (matrices)
Tablouri bidimensionale (matrice) · 15 algorithms
- Bordering a matrixBordarea matriceiBordering a matrix means adding a new row and/or column on its edge. Here we add column m + 1, holding the sum of each row, and row n + 1, holding…
- Reading and printing a matrixCitirea și afișarea unei matriceA matrix with n rows and m columns is declared as int a[101][101] and traversed with two nested for loops: the first picks the row i, the second the…
- Main diagonal and secondary diagonalDiagonala principală și diagonala secundarăIn an n x n square matrix indexed from 1, the elements on the main diagonal have i == j, and those on the secondary diagonal have i + j == n + 1. We…
- Row with the maximum sumLinia cu suma maximăWe compute the sum of every row and compare it with the largest sum found so far. The maximum starts from the sum of the first row (not from 0,…
- Generating a serpentine (zigzag) matrixGenerarea matricei în serpentinăWe fill the matrix with the numbers 1, 2, ..., n * m in a zigzag: odd rows from left to right, even rows from right to left. A counter val grows…
- Checking a symmetric matrixVerificarea matricei simetriceA square matrix is symmetric about the main diagonal if a[i][j] == a[j][i] for every i and j (it equals its transpose). It is enough to check the…
- Spiral traversalParcurgerea în spiralăWe keep four borders: top, bottom, left, right. On every lap we walk the top row (to the right), the right column (down), the bottom row (to the…
- Product of two matricesProdusul a două matriceThe product exists only if the number of columns of A equals the number of rows of B. For A (n x m) and B (m x p) the result C has n x p elements,…
- Saddle pointPunct șaA saddle point is an element that is the minimum of its row and the maximum of its column. For every element a[i][j] we check the two conditions…
- Rotating a matrix by 90 degreesRotirea unei matrice cu 90 de gradeWhen rotating clockwise, the first column read from bottom to top becomes the first row. The result matrix b has m rows and n columns, and the…
- Deleting a row and a columnȘtergerea unei linii și a unei coloaneAs with arrays, deleting means moving elements over the deleted one. For row k, every row i from k to n - 1 receives row i + 1, then n decreases by…
- Row sums and column sumsSuma pe linii și pe coloaneFor the sum of row i we keep i fixed and move j from 1 to m. For the sum of column j we do the opposite: j fixed in the outer loop, i varying in the…
- Generating a chessboardGenerarea tablei de șahOn a chessboard, the colour of a square depends only on the parity of i + j: squares with an even i + j have one colour (1), those with an odd i + j…
- Transpose of a matrixTranspusa unei matriceThe transpose of the matrix a (n rows, m columns) has m rows and n columns: row i of the transpose is column i of a, i.e. t[j][i] = a[i][j]. No…
- The four zones of a square matrixCele patru zone ale matricei pătraticeThe two diagonals split a square matrix into four zones (without the elements on the diagonals). With indices from 1: North: i < j and i + j < n + 1…
0%
Character strings
Șiruri de caractere · 16 algorithms
- The longest wordCel mai lung cuvântWe split the sentence into words with strtok and keep the longest word in a separate string, copying it with strcpy (we cannot write celMaiLung = p,…
- Caesar cipherCifrul lui CezarEvery letter is replaced by the letter k positions further in the alphabet, circularly (after 'z' comes 'a'). We turn the letter into its position…
- Palindrome words in a sentenceCuvintele palindrom dintr-o frazăWe combine two things learned before: strtok splits the sentence into words, and the function estePalindrom(p) checks a word with two indices moving…
- Removing the vowelsEliminarea vocalelorWe delete the vowels in the original string itself, with two indices: i reads every character, k shows where the next kept character is written.…
- Extracting the numbers from a textExtragerea numerelor dintr-un textWe walk the text; when we meet a digit, we build the number as in grade 9 (nr = nr * 10 + (s[i] - '0')) while digits follow. The expression s[i] -…
- Letter frequencyFrecvența literelorWe count how many times each letter appears, without distinguishing uppercase from lowercase: tolower(c) - 'a' gives the letter's position in the…
- Splitting into words with strtokÎmpărțirea în cuvinte cu strtokstrtok(s, separators) returns the first word of s; the following calls are made with NULL instead of s and return the other words one by one, until…
- Replacing one word with anotherÎnlocuirea unui cuvânt cu altulA text and two words, old and new, are read (each on its own line). We build the result in a new string: spaces are copied as they are, and every…
- Converting to uppercase and lowercaseTransformarea în majuscule și minusculeIn the ASCII table the uppercase letters 'A'..'Z' and the lowercase 'a'..'z' are a constant distance apart: 'a' - 'A' = 32. A lowercase letter…
- Counting the wordsNumărarea cuvintelorWithout strtok: a word starts where a non-space character follows a space (or sits at the very beginning of the string). We count these…
- Counting the vowelsNumărarea vocalelorFor every character we check whether it appears in the string "aeiouAEIOU" with the function strchr: strchr(vowels, c) returns the address of the…
- Operations with std::stringOperații cu std::stringThe string class from <string> manages its own memory: it is assigned with =, concatenated with +, compared with == and <. getline(cin, s) reads the…
- Walking a string and its lengthParcurgerea unui șir și lungimea luiA C-style string is a char array terminated by the null character '\0'. cin.getline(s, 256) reads the whole line, spaces included (cin >> s would…
- Sorting words alphabeticallySortarea alfabetică a cuvintelorWe split the sentence into words with strtok and copy them into a character matrix cuv[100][31] (every row is a string). We sort with bubble sort;…
- Checking a palindrome stringVerificarea unui șir palindromFirst we keep only the letters, turned into lowercase (so 'Ele fac cafele' becomes 'elefaccafele'). Then we use two indices: st starts at the…
- Checking anagramsVerificarea anagramelorTwo words are anagrams if they have the same letters, the same number of times, in a different order (for example 'roma' and 'amor'). We use a…
0%
The struct type
Tipul struct · 5 algorithms
- Comparing calendar datesCompararea datelor calendaristiceA calendar date has three fields: day, month, year. Two dates are compared first by year, with equal years by month, and with equal months by day;…
- Adding durations (hours, minutes, seconds)Adunarea duratelor (ore, minute, secunde)A duration is kept in a structure with three fields. To add easily, we turn the duration into seconds (h * 3600 + m * 60 + s), add the numbers and…
- Students sorted by average and nameElevi sortați după medie și numeThe struct type groups data of different types under a single name: struct Elev { char nume[31]; double medie; }. A field is accessed with a dot…
- Operations with fractionsOperații cu fracțiiA fraction has two fields, the numerator a and the denominator b, so we represent it with struct Fractie { long long a, b; }. A function can return…
- Points in the planePuncte în planA point has the coordinates x and y: struct Punct { int x, y; }. The distance between two points is sqrt((x1 - x2)^2 + (y1 - y2)^2). For comparisons…
0%
Recursion
Recursivitate · 12 algorithms
- Printing the digits in order, recursivelyAfișarea cifrelor în ordine, recursivWhere we print relative to the recursive call matters. In inOrdine we print AFTER the recursive call: first the call for n / 10 finishes (printing…
- Recursive GCDCmmdc recursivEuclid's algorithm written recursively: gcd(a, 0) = a, and gcd(a, b) = gcd(b, a % b). The recursive call is the last operation in the function (tail…
- Converting to base 2, recursivelyConversia în baza 2, recursivWhen converting by repeated division by 2, the remainders come out in the reverse of the order they must be written in. Recursion solves this by…
- Recursive factorialFactorial recursivThe mathematical definition is already recursive: 0! = 1 and n! = n * (n - 1)!. The function has a stopping condition (n == 0) and a recursive call…
- Recursive FibonacciFibonacci recursivThe Fibonacci sequence: F(0) = 0, F(1) = 1, F(n) = F(n - 1) + F(n - 2). The direct translation has two recursive calls, so the call tree almost…
- The Ackermann functionFuncția AckermannThe Ackermann function has two arguments: A(0, n) = n + 1; A(m, 0) = A(m - 1, 1); A(m, n) = A(m - 1, A(m, n - 1)). Its values grow extremely fast…
- The Manna-Pnueli functionFuncția Manna-PnueliThe function is defined as: f(x) = x - 1 if x >= 12, otherwise f(x) = f(f(x + 2)). The inner call f(x + 2) is computed first, and its result becomes…
- Reversing a string, recursivelyInversarea unui șir de caractere, recursivThe function inverseaza(s, i) handles the characters from position i to the end. If s[i] is not '\0', it first calls itself for the rest of the…
- Number of occurrences in an array, recursivelyNumărul de apariții într-un vector, recursivThe number of occurrences of x among the first n elements is the number of occurrences among the first n - 1 elements, plus 1 if the last element…
- Recursive palindrome checkPalindrom recursivA word is a palindrome if its first and last characters are equal and what remains between them is also a palindrome. The function palindrom(s, st,…
- Power of a number, recursivelyPuterea unui număr, recursivThe direct version uses a^n = a * a^(n - 1) and makes n calls. The fast version halves the exponent: if n is even, a^n = (a^(n/2))^2, otherwise a^n…
- Sum of digits, recursivelySuma cifrelor, recursivThe digit sum of n is its last digit (n % 10) plus the digit sum of the number left after cutting it off (n / 10). Stop: a one-digit number (n < 10)…
0%
Divide and conquer
Divide et impera · 8 algorithms
- Recursive binary searchCăutare binară recursivăThe array is sorted in increasing order. We compare x with the middle element: if they are equal we are done; if x is smaller, we search only the…
- GCD of an array's elements with divide and conquerCmmdc-ul elementelor unui vector prin divide et imperaThe GCD of a portion is the GCD of the left half's GCD and the right half's GCD, because gcd(a, b, c, d) = gcd(gcd(a, b), gcd(c, d)). The base case:…
- Maximum of an array with divide and conquerMaximul unui vector prin divide et imperaThe three stages of the method: we split the portion [st, dr] into two halves at the middle m = (st + dr) / 2 (divide); we find the maximum of each…
- Counting the even elements with divide and conquerNumărul elementelor pare prin divide et imperaThe same pattern as for the sum: the result for the portion [st, dr] is the sum of the results of the two halves. Only the base case differs: a…
- Merge sortSortarea prin interclasare (Merge Sort)We split the array into two halves, sort each half recursively, then merge them: we always compare the first remaining elements of the two halves…
- Quick sortSortarea rapidă (Quick Sort)We pick a pivot (here the middle element) and rearrange the portion so that values <= pivot end up on the left and values >= pivot on the right:…
- Sum of the elements with divide and conquerSuma elementelor prin divide et imperaThe sum of the portion [st, dr] is the sum of the left half [st, m] plus the sum of the right half [m + 1, dr]. A portion with a single element has…
- Towers of HanoiTurnurile din HanoiThere are n disks on rod A, in decreasing order of size, and we want to move them to rod C, using rod B, without ever placing a large disk on a…
Grade 11Clasa a XI-a
0%0%
Backtracking
Metoda backtracking · 12 algorithms
- Generating arrangements (k-permutations)Generarea aranjamentelorPrints, in lexicographic order, all arrangements of n elements taken k at a time: sequences of k distinct values from {1, ..., n} where order…
- Map coloringColorarea hărțilorA map has n countries numbered from 1, and m pairs (a, b) say that countries a and b are neighbours. We color every country with one of the colors…
- Generating combinationsGenerarea combinărilorPrints all k-element subsets of the set {1, ..., n} (combinations of n taken k at a time). To avoid getting the same subset several times, the…
- Paths in a mazeDrumuri într-un labirintThe maze is an n × m matrix of 0 (free) and 1 (wall). We start in the top-left corner (1, 1) and want to reach the bottom-right corner (n, m),…
- The n-queens problemProblema celor n dameWe place n queens on an n × n board so that none attacks another (no pair on the same row, column or diagonal). We put one queen on every row, and…
- Generating balanced parenthesesGenerarea parantezărilor corectePrints, in lexicographic order ('(' before ')'), all balanced strings made of n pairs of round brackets. We keep the number of brackets opened and…
- Partitions of a natural numberPartițiile unui număr naturalPrints all ways of writing n as a sum of non-zero natural numbers, where the order of the terms does not matter. To avoid repeating the same…
- Permutations with neighbours of alternating parityPermutări cu vecini de parități diferitePrints the permutations of the set {1, ..., n} in which any two neighbouring elements have different parities (one even, the other odd). Compared…
- Generating permutationsGenerarea permutărilorPrints, in lexicographic order, all permutations of the set {1, 2, ..., n}. The solution is built in the array x, position by position. At position…
- Paying a sum with given coinsPlata unei sume cu monede dateThere are n coin types with values v[1..n], as many of each as we want. We print all ways of paying exactly the sum S. x[k] is the number of coins…
- Cartesian productProdusul carteziann sets are given; set i is {1, 2, ..., a[i]}. All elements of the Cartesian product are printed, i.e. all sequences (x1, ..., xn) with 1 ≤ xi ≤…
- Generating subsetsGenerarea submulțimilorPrints all non-empty subsets of the set {1, ..., n}, in lexicographic order. The elements of a subset are placed in strictly increasing order (as…
0%
The greedy method
Metoda greedy · 6 algorithms
- Covering a segment with the minimum number of intervalsAcoperirea unui segment cu număr minim de intervaleWe want to cover the segment [A, B] using as few as possible of the n given intervals [s[i], f[i]]. We sort the intervals by their left end. We keep…
- Scheduling shows (activity selection)Planificarea spectacolelorn shows can be held in a hall; show i starts at time s[i] and ends at time f[i]. We want to schedule as many non-overlapping shows as possible (one…
- Paying a sum with the minimum number of banknotesPlata unei sume cu număr minim de bancnoten banknote values are given (we have any number of each) and a sum S. The greedy strategy: pay as much as possible with the largest banknote, then…
- The knapsack problem (fractional version)Problema rucsacului (varianta fracționară)A knapsack holds at most G kilograms. There are n objects; object i has weight g[i] and value v[i], and we may take just a piece (a fraction) of any…
- Maximum sum with k elementsSuma maximă cu k elementeFrom a sequence of n integers we choose exactly k elements (on different positions) with the largest possible sum. The greedy choice is obvious:…
- Minimizing the average waiting timeMinimizarea timpului mediu de așteptaren customers wait at a counter; serving customer i takes t[i] minutes. A customer's waiting time is the sum of the service times of the customers…
0%
Dynamic programming
Programare dinamică · 10 algorithms
- Longest common subsequenceCel mai lung subșir comunTwo words a and b are given. We look for the longest sequence of letters that appears as a subsequence (letters in order, not necessarily adjacent)…
- Edit distanceDistanța de editareWhat is the minimum number of operations needed to turn the word a into the word b? An operation means inserting, deleting or replacing a letter.…
- Maximum-sum path in a matrixDrum de sumă maximă în matriceIn an n × m matrix we start from the corner (1, 1) and reach (n, m) moving only right or down. We want the maximum sum of the elements on the path.…
- Number of paths in a grid with obstaclesNumărul de drumuri într-o grilă cu obstacoleAn n × m grid has free cells (0) and obstacles (1). How many paths lead from (1, 1) to (n, m) if we move only right or down and never enter…
- Minimum number of coinsNumărul minim de monedeThere are n coin types (any number of each) and we want to pay exactly the sum S with as few coins as possible. Greedy can be wrong (for the coins…
- Number of partitions of a numberNumărul partițiilor unui numărIn how many ways can n be written as a sum of non-zero natural numbers, where the order of the terms does not matter? (4 = 4 = 3+1 = 2+2 = 2+1+1 =…
- The knapsack problem (0/1 version)Problema rucsacului (varianta discretă)A knapsack holds at most G kilograms; there are n objects with weights g[i] and values v[i], and an object is taken whole or not at all. Here greedy…
- Longest strictly increasing subsequenceSubșirul strict crescător de lungime maximăFrom a sequence of n numbers we choose a strictly increasing subsequence (elements in their order in the sequence, not necessarily adjacent) that is…
- Maximum sum in a number triangleSuma maximă în triunghiul de numereA triangle has n rows; row i holds i numbers. We start from the top and at every step go either straight down (a[i+1][j]) or down and to the right…
- Number of ways to climb a staircaseNumărul de moduri de a urca o scarăA staircase has n steps; at every move we climb either one step or two. In how many ways can we reach the top? Step i is reached either from step i…
0%
Dynamic allocation: lists, stacks, queues
Alocare dinamică: liste, stive, cozi · 10 algorithms
- Queue implemented with a linked listCoada implementată cu o listă înlănțuităThe queue is kept as a singly linked list with two pointers: prim (where we remove) and ultim (where we add). push links a new node after ultim; pop…
- Queue implemented with an arrayCoada implementată cu un vectorThe queue is a FIFO structure (first in, first out): elements are added at the end and removed from the front, as at a ticket counter. With an array…
- Evaluating an expression in postfix (reverse Polish) notationEvaluarea unei expresii în formă poloneză postfixatăIn postfix notation the operator is written after its operands: (3 + 4) * 2 becomes 3 4 + 2 *, and parentheses are no longer needed. We read the…
- Inserting into a sorted listInserarea într-o listă ordonatăWe read n numbers and insert them one by one into a singly linked list that is always kept in increasing order. If the new value is smaller than the…
- Doubly linked listLista dublu înlănțuităIn a doubly linked list every node stores both the address of the next node (urm) and that of the previous one (ant), so the list can be traversed…
- Singly linked list: create, print, addLista simplu înlănțuită: creare, afișare, adăugareEvery element of the list is a dynamically allocated node (with new) that stores a value (info) and the address of the next node (urm). We keep the…
- Deleting nodes from a singly linked listȘtergerea nodurilor dintr-o listă simplu înlănțuităA list is built from n values, then all nodes containing the value x are deleted. Deleting the first node moves the pointer prim to the next node.…
- Stack implemented with a linked listStiva implementată cu o listă înlănțuităThe top of the stack is the first node of a singly linked list. push creates a new node and links it in front of the top; pop moves the top to the…
- Stack implemented with an arrayStiva implementată cu un vectorThe stack is a LIFO structure (last in, first out): elements are added and removed only at the top. With an array st and an index vf (the number of…
- Checking brackets with a stackVerificarea parantezelor cu o stivăA string made of the brackets ( ) [ ] { } is correct if every opening bracket is closed by one of the same type, in the right order. We walk the…
0%
Undirected graphs
Grafuri neorientate · 10 algorithms
- Connected componentsComponentele conexeA graph is connected if there is a path between any two nodes. A connected component is a maximal connected 'piece' of the graph. We take the nodes…
- Detecting a cycleDetectarea unui cicluA cycle is a simple path whose first node is also its last. We run a DFS traversal and keep for every node its parent (the node we came from). If…
- Shortest path between two nodes (BFS)Lanțul de lungime minimă între două noduri (BFS)The length of a path is its number of edges. Breadth-first search started from x discovers the nodes in order of their distance from x, so the first…
- Checking a bipartite graphVerificarea unui graf bipartitA graph is bipartite if its nodes can be split into two sets A and B so that every edge has one end in A and the other in B. We color the nodes with…
- Adjacency listsListele de adiacențăFor every node we store only the list of its neighbours. The edge [x, y] is added twice: y to the list of x and x to the list of y. The memory used…
- Adjacency matrix and node degreesMatricea de adiacență și gradele nodurilorAn undirected graph with n nodes and m edges can be stored in a matrix a with n rows and n columns: a[i][j] = 1 if the edge [i, j] exists, otherwise…
- Isolated nodes and the complete graphNoduri izolate și graful completAn isolated node has degree 0. A graph is complete if any two distinct nodes are joined by an edge; the complete graph with n nodes has n · (n - 1)…
- Depth-first search (DFS)Parcurgerea în adâncime (DFS)Depth-first search goes as far as it can: from the current node it moves to the first unvisited neighbour, from there to that node's first unvisited…
- Breadth-first search (BFS)Parcurgerea în lățime (BFS)Breadth-first search visits the nodes 'in layers': first the start node, then all its neighbours, then the neighbours' neighbours, and so on. We use…
- Checking a path (chain)Verificarea unui lanțA sequence of nodes x1, x2, ..., xk is a path if any two consecutive nodes are joined by an edge; the length of the path is k - 1 (the number of…
0%
Directed graphs and shortest paths
Grafuri orientate și drumuri minime · 6 algorithms
- Strongly connected componentsComponentele tare conexeA directed graph is strongly connected if for any two nodes x and y there is a path from x to y and a path from y to x. A strongly connected…
- Shortest paths from one node (Dijkstra's algorithm)Drumuri minime de la un nod (algoritmul lui Dijkstra)We want the minimum cost of the path from node s to every other node, when all arc costs are non-negative. d[s] = 0, the rest 'infinity'. At every…
- In-degrees and out-degreesGradele interne și externeIn a directed graph the edges have a direction and are called arcs: the arc (x, y) leaves x and enters y. The out-degree d+(x) is the number of arcs…
- Reachability matrix (Roy-Warshall algorithm)Matricea drumurilor (algoritmul Roy-Warshall)The reachability matrix has d[i][j] = 1 if there is a path (of length at least 1) from i to j and 0 otherwise. We start from the adjacency matrix.…
- Shortest paths between all pairs of nodes (Roy-Floyd)Drumuri minime între toate perechile de noduri (Roy-Floyd)Every arc (x, y) has a cost c ≥ 0. The cost matrix d starts with d[i][i] = 0, d[x][y] = the arc's cost and 'infinity' where there is no arc. For…
- Topological sortSortarea topologicăThe arc (x, y) means 'x must be done before y'. A topological sort is an order of all nodes in which every arc goes from left to right; it exists…
0%
Trees
Arbori · 8 algorithms
- Minimum spanning tree (Kruskal's algorithm)Arborele parțial de cost minim (algoritmul lui Kruskal)Kruskal builds the minimum spanning tree starting from n trees with a single node each. We sort the edges by cost in increasing order (on ties they…
- Minimum spanning tree (Prim's algorithm)Arborele parțial de cost minim (algoritmul lui Prim)In a connected undirected graph with edge costs we look for a spanning tree (n - 1 edges connecting all nodes) with the minimum total cost. Prim…
- Binary search tree: insert, search, sorted printArbore binar de căutare: inserare, căutare, afișare sortatăIn a binary search tree, for every node, all values in the left subtree are smaller than the node's value and those in the right subtree are larger.…
- Children, descendants and ancestors of a nodeFiii, descendenții și ascendenții unui nodThe tree is given by its parent array (t[root] = 0). The children of x are the nodes i with t[i] = x. A node y is a descendant of x if, climbing…
- Diameter of a treeDiametrul unui arboreThe diameter of a tree is the length (number of edges) of the longest path between two nodes. The two-traversal method: we run a BFS from node 1 and…
- Traversals of a binary treeParcurgerile unui arbore binarIn a binary tree every node has at most two children: a left one and a right one. We store it with the arrays st[i] and dr[i] (0 if the child is…
- Parent array: root, leaves, levels, heightVectorul de tați: rădăcină, frunze, niveluri, înălțimeA rooted tree can be stored as a parent array: t[i] is the parent of node i, and for the root t[i] = 0. The root is the node with t = 0. The leaves…
- Checking whether a graph is a treeVerificarea că un graf este arboreA tree is a connected undirected graph without cycles. For a graph with n nodes the following statements are equivalent: it is a tree; it is…
Grade 12Clasa a XII-a
0%0%
Big numbers
Numere mari · 9 algorithms
- Adding two big numbersAdunarea a două numere mariWe add as on paper, from the units to the left. At position i we compute s = a[i] + b[i] + carry; the result digit is s % 10, and the new carry is s…
- Reading and printing a big numberCitirea și afișarea unui număr mareA number with tens or hundreds of digits does not fit in long long, so we read it as a string and keep its digits in an array, starting with the…
- Comparing two big numbersCompararea a două numere mariWithout leading zeros, the number with more digits is larger. If they have the same number of digits, we compare them from the most significant…
- Factorial as a big numberFactorialul unui număr mareAlready 21! exceeds long long, but n! = 1 * 2 * ... * n can be built by repeatedly multiplying a big number by a small one. We start from the array…
- The n-th Fibonacci term (big number)Termenul n din șirul lui Fibonacci (număr mare)The sequence is F(1) = F(2) = 1 and F(i) = F(i - 1) + F(i - 2). The terms grow exponentially (F(93) no longer fits in long long), so we keep them as…
- Dividing a big number by a small numberÎmpărțirea unui număr mare la un număr micUnlike addition, division starts from the most significant digit, exactly like long division on paper. We keep the remainder r; for every digit we…
- Multiplying two big numbersÎnmulțirea a două numere mariThe digit a[i] (rank 10^i) multiplied by the digit b[j] (rank 10^j) contributes to rank 10^(i+j). We first add all the products into c[i + j],…
- Multiplying a big number by a small numberÎnmulțirea unui număr mare cu un număr micThe small number k (at most 10^9) fits in an int, so it does not need to be split into digits. For every digit a[i], from the units, we compute t =…
- Subtracting two big numbersScăderea a două numere mariWe compute A - B. If A < B, we compute B - A and put a minus sign in front. We subtract from the units: d = a[i] - b[i] - borrow; if d comes out…
0%
Grid algorithms: Lee and flood fill
Algoritmi pe grile: Lee și fill · 6 algorithms
- Flood fill: the largest regionFill — cea mai mare zonăThe same matrix of 0s and 1s, but now we want the number of cells of the largest region of 1s (adjacency through sides). This time the fill is done…
- Flood fill: the number of regionsFill — numărul de zoneThe matrix has n rows and m columns, with 1 for land and 0 for water. A region is a maximal group of 1 cells connected through their sides (up,…
- Islands in 8 directionsInsule în 8 direcțiiLike counting regions, but two land cells (1) belong to the same island if they touch even at a corner, i.e. the neighbourhood has 8 directions. The…
- Lee with multiple sourcesLee cu mai multe surseThe grid holds 0 (free), 1 (wall) and 2 (source, for example a well). For every free cell we want the minimum number of steps to the nearest source.…
- Lee: the shortest path in a gridLee — drumul minim într-o grilăThe grid has n rows and m columns: 0 = free, 1 = obstacle. We can move up, down, left, right. Lee's algorithm is a breadth-first search: d[xs][ys] =…
- Lee with path reconstructionLee cu reconstituirea drumuluiAfter Lee has filled the distance matrix, the path is rebuilt from the end towards the start: if we are in a cell with value k, one of its…
0%
Math for programming
Matematică pentru programare · 9 algorithms
- Smallest-prime-factor sieve and fast factorizationCiur cu cel mai mic divizor prim și factorizare rapidăA variant of the Sieve of Eratosthenes: instead of only marking 'composite', we store in dp[x] the smallest prime divisor of x. For every prime p…
- Combinations modulo a primeCombinări modulo un număr primWe compute C(n, k) mod P, with P = 1,000,000,007 (prime) and n ≤ 10^6. We have C(n, k) = n! / (k! * (n-k)!), but division cannot be done directly on…
- Extended Euclidean algorithmAlgoritmul lui Euclid extinsBesides d = gcd(a, b), we find integers x and y with a * x + b * y = d. If b = 0, then d = a, x = 1, y = 0. Otherwise we solve recursively for (b, a…
- Modular exponentiationExponențierea modularăWe compute a^n mod m for n up to 10^18. We use the same idea as fast exponentiation, but after every multiplication we take the remainder modulo m:…
- Fast exponentiationExponențierea rapidăWe compute a^n with about log2(n) multiplications instead of n. The idea: a^n = (a^2)^(n/2) if n is even and a^n = a * a^(n-1) if n is odd. The…
- Number and sum of divisors from the prime factorizationNumărul și suma divizorilor din descompunerea în factori primiIf n = p1^e1 * p2^e2 * ... * pk^ek, a divisor chooses for every prime an exponent between 0 and ei, so the number of divisors is (e1 + 1) * (e2 + 1)…
- Number of multiples of k in a rangeNumărul multiplilor lui k dintr-un intervalHow many numbers in [a, b] are divisible by k? The numbers in [1, x] divisible by k are k, 2k, ..., (x / k) * k, i.e. x / k of them (integer…
- Sum of an arithmetic progression: formula vs. loopSuma unei progresii aritmetice: formulă vs. buclăThe progression has first term a, common difference r and n terms: a, a + r, ..., a + (n-1) * r. The loop adds the terms one by one, so it takes n…
- Pascal's triangle (combinations)Triunghiul lui Pascal (combinări)The combinations C(i, j), the number of j-element subsets of an i-element set, satisfy C(i, j) = C(i-1, j-1) + C(i-1, j): either we choose element…
0%
Advanced techniques: two pointers, binary search on the answer, monotonic stacks
Tehnici avansate: doi pointeri, căutare binară pe răspuns, stive monotone · 7 algorithms
- Binary search on the answerCăutare binară pe răspunsWe have n chapters with a[i] pages, in order, and k proofreaders. Every proofreader gets a run of consecutive chapters. We want the busiest…
- Two pointers: pairs with sum x in a sorted arrayDoi pointeri — perechi cu suma x într-un vector sortatThe array has n distinct values in strictly increasing order. We want the position pairs i < j with a[i] + a[j] = x. Instead of trying all n * (n-1)…
- Majority element (Boyer-Moore)Element majoritar (Boyer-Moore)The majority element appears more than n / 2 times. The voting algorithm keeps a candidate and a counter: a value equal to the candidate increases…
- Sliding window: the longest subarray with sum ≤ SFereastra glisantă — cea mai lungă secvență cu suma ≤ SAll numbers are strictly positive. We keep a window [st, dr] and its sum. We always extend the right end by one element; while the sum exceeds S, we…
- Monotonic stack: the next greater elementStiva monotonă — următorul element mai mareFor every a[i] we look for the first strictly greater value to its right (or -1). We keep a stack with the positions still 'waiting' for a greater…
- Generating subsets with bitmasksGenerarea submulțimilor cu măști de bițiA subset of {a[0], ..., a[n-1]} can be encoded as a number masca between 0 and 2^n - 1: bit i of the mask is 1 if a[i] belongs to the subset. Bit i…
- 2D prefix sumsSume parțiale pe matrices[i][j] = the sum of the elements in the rectangle with corners (1, 1) and (i, j). It is computed once: s[i][j] = a[i][j] + s[i-1][j] + s[i][j-1] -…
0%
Data structures and the STL
Structuri de date și STL · 9 algorithms
- deque: sliding window minimum of length kdeque — minimul pe ferestre de lungime kFor every run of k consecutive elements we want the minimum. We keep the 'candidate' positions in a deque, with values increasing from front to…
- queue: elimination in a circle (Josephus)queue — eliminarea din cercn children, numbered from 1 to n, stand in a circle. We count k at a time, and the child where the count stops leaves the game; counting continues…
- pair: union of intervalspair — reuniunea intervalelorpair<int, int> groups two values (first, second) and compares lexicographically: first by first, then by second. So sort on an array of pairs orders…
- stack: checking bracketsstack — verificarea parantezelorA string with the brackets (), [] and {} is correct if every closing bracket matches the last opening bracket still left open. 'Last opened, first…
- priority_queue: the k largest valuespriority_queue — cele mai mari k valoripriority_queue is a heap: top() gives the 'most important' element, and push and pop cost O(log size). By default the top is the maximum; with…
- set and map: word frequencyset și map — frecvența cuvintelorWe read words (lowercase letters) until the end of the input. A set<string> keeps every word once, in alphabetical order, so size() gives the number…
- Sorting with a comparatorSortare cu comparatorsort(begin, end, cmp) orders by our own rule: cmp(x, y) returns true if x must come before y. Here we sort the contestants of a competition by score…
- Disjoint-set forests (union-find)Păduri de mulțimi disjuncte (union-find)We have n elements, each initially in its own set. Operation 1 x y joins the sets of x and y, and operation 2 x y asks whether x and y are in the…
- The STL vector containerContainerul vector din STLvector<int> is an array that manages its own memory: push_back adds at the end (O(1) on average), size() gives the number of elements, and v[i]…
0%
Baccalaureate exam review
Recapitulare pentru bacalaureat · 10 algorithms
- File: the largest and smallest number formed from given digitsFișier — cel mai mare și cel mai mic număr format din cifre dateThe task (exam part III.3 style): the file date.in holds at most 10^6 digits separated by spaces. Using all the digits, each exactly once, print on…
- File: pairs of numbers with the same digit sumFișier — perechi de numere cu aceeași sumă a cifrelorThe task (exam part III.3 style): the file date.in holds n (2 ≤ n ≤ 10^6) on the first line, then n natural numbers with at most 9 digits. Print how…
- File: the longest run of terms with the same parityFișier — cea mai lungă secvență de termeni cu aceeași paritateThe task (exam part III.3 style): the file date.in holds a sequence of at most 10^6 natural numbers with at most 9 digits. A parity run is a run of…
- File: the common values of two sorted sequencesFișier — valorile comune a două șiruri ordonateThe task (exam part III.3 style): the file date.in holds n and m (1 ≤ n, m ≤ 10^5) on the first line, n natural numbers in increasing order on the…
- File: the values that appear exactly onceFișier — valorile care apar o singură datăThe task (exam part III.3 style): the file date.in holds at most 10^6 natural numbers with at most three digits, separated by spaces. Print on the…
- Matrix: concentric bordersMatrice — contururi concentriceThe task (exam part III.2 style): n is read (2 ≤ n ≤ 20). Build in memory a matrix with n rows and n columns in which the elements on the outer…
- Subprogram: the number formed from the even digitsSubprogram — numărul format din cifrele pareThe task (exam part III.1 style): the subprogram pare has a parameter n (0 ≤ n ≤ 10^9) and returns the number formed from the even digits of n, in…
- Subprogram: how many numbers in a range have an odd number of divisorsSubprogram — câte numere dintr-un interval au un număr impar de divizoriThe task (exam part III.1 style): the subprogram impare has the parameters a and b (1 ≤ a ≤ b ≤ 10^12) and returns how many numbers in [a, b] have…
- Subprogram: removing the elements with k digits from an arraySubprogram — eliminarea elementelor cu k cifre dintr-un tablouThe task (exam part III.1 style): the subprogram elimina has the parameters v (an array of n natural numbers), n and k; it deletes from v all…
- Text: reversing the words of even lengthText — inversarea cuvintelor de lungime parăThe task (exam part III.2 style): a text of at most 100 characters is read, made of lowercase words separated by single spaces. Print the text in…