Алгоритмы и Структуры Данных

#include <iostream>
#include <vector>
using namespace std;

void bubbleSort(vector& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; i++) {
bool swapped = false;        // оптимизация: флаг обмена
for (int j = 0; j < n - 1 - i; j++) {  // -i: последние i уже на месте
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
swapped = true;
}
}
if (!swapped) break;         // если не было обменов — уже отсортировано
}
}

int main() {
vector arr = {5, 3, 8, 1, 2};
bubbleSort(arr);
for (int x : arr) cout << x << " ";  // 1 2 3 5 8
return 0;
}

#include <iostream>
#include <vector>
using namespace std;

void selectionSort(vector& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) {
minIdx = j;         // запоминаем индекс минимума
}
}
if (minIdx != i) {
swap(arr[i], arr[minIdx]);  // ставим минимум на позицию i
}
}
}

int main() {
vector arr = {29, 10, 14, 37, 13};
selectionSort(arr);
for (int x : arr) cout << x << " ";  // 10 13 14 29 37
return 0;
}

#include <iostream>
#include <vector>
using namespace std;

void insertionSort(vector& arr) {
int n = arr.size();
for (int i = 1; i < n; i++) {
int key = arr[i];   // элемент для вставки
int j = i - 1;
// сдвигаем все элементы > key вправо
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;   // вставляем на своё место
}
}

int main() {
vector arr = {7, 3, 5, 1, 9};
insertionSort(arr);
for (int x : arr) cout << x << " ";  // 1 3 5 7 9
return 0;
}

#include <iostream>
#include <vector>
using namespace std;

// Слияние двух отсортированных частей arr[l..m] и arr[m+1..r]
void merge(vector& arr, int l, int m, int r) {
vector left(arr.begin() + l, arr.begin() + m + 1);
vector right(arr.begin() + m + 1, arr.begin() + r + 1);

int i = 0, j = 0, k = l;
while (i < (int)left.size() && j < (int)right.size()) {
    if (left[i] <= right[j])     // <= для стабильности!
        arr[k++] = left[i++];
    else
        arr[k++] = right[j++];
}
while (i < (int)left.size()) arr[k++] = left[i++];
while (j < (int)right.size()) arr[k++] = right[j++];
}

void mergeSort(vector& arr, int l, int r) {
if (l >= r) return;            // базовый случай
int m = l + (r - l) / 2;        // середина (без переполнения)
mergeSort(arr, l, m);            // сортируем левую
mergeSort(arr, m + 1, r);        // сортируем правую
merge(arr, l, m, r);             // сливаем
}

int main() {
vector arr = {38, 27, 43, 3, 9, 82, 10};
mergeSort(arr, 0, arr.size() - 1);
for (int x : arr) cout << x << " ";  // 3 9 10 27 38 43 82
return 0;
}

#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;

// Схема разделения Ломуто
int partition(vector& arr, int l, int r) {
// Рандомизация: выбираем случайный pivot, чтобы избежать O(n²)
int rndIdx = l + rand() % (r - l + 1);
swap(arr[rndIdx], arr[r]);

int pivot = arr[r];
int i = l;  // граница элементов ≤ pivot
for (int j = l; j < r; j++) {
    if (arr[j] <= pivot) {
        swap(arr[i], arr[j]);
        i++;
    }
}
swap(arr[i], arr[r]);  // pivot на своё место
return i;
}

void quickSort(vector& arr, int l, int r) {
if (l >= r) return;
int p = partition(arr, l, r);
quickSort(arr, l, p - 1);
quickSort(arr, p + 1, r);
}

int main() {
vector arr = {10, 80, 30, 90, 40, 50, 70};
quickSort(arr, 0, arr.size() - 1);
for (int x : arr) cout << x << " ";  // 10 30 40 50 70 80 90
return 0;
}

#include <iostream>
#include <vector>
using namespace std;

// Просеивание вниз: поддерживаем свойство max-heap
void heapify(vector& arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;

if (left < n && arr[left] > arr[largest])
    largest = left;
if (right < n && arr[right] > arr[largest])
    largest = right;

if (largest != i) {
    swap(arr[i], arr[largest]);
    heapify(arr, n, largest);   // рекурсивно просеиваем дальше
}
}

void heapSort(vector& arr) {
int n = arr.size();

// 1. Строим max-heap (от последнего нелистового узла до корня)
for (int i = n / 2 - 1; i >= 0; i--)
    heapify(arr, n, i);

// 2. Извлекаем максимумы один за другим
for (int i = n - 1; i > 0; i--) {
    swap(arr[0], arr[i]);     // максимум → конец
    heapify(arr, i, 0);       // восстанавливаем heap (размер = i)
}
}

int main() {
vector arr = {4, 10, 3, 5, 1};
heapSort(arr);
for (int x : arr) cout << x << " ";  // 1 3 4 5 10
return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void countingSort(vector& arr) {
if (arr.empty()) return;

int maxVal = *max_element(arr.begin(), arr.end());
int minVal = *min_element(arr.begin(), arr.end());
int range = maxVal - minVal + 1;

vector<int> count(range, 0);
vector<int> output(arr.size());

// 1. Подсчитываем вхождения
for (int x : arr)
    count[x - minVal]++;

// 2. Префиксные суммы (позиции)
for (int i = 1; i < range; i++)
    count[i] += count[i - 1];

// 3. Расставляем (справа налево для стабильности)
for (int i = arr.size() - 1; i >= 0; i--) {
    output[count[arr[i] - minVal] - 1] = arr[i];
    count[arr[i] - minVal]--;
}

arr = output;
}

int main() {
vector arr = {4, 2, 2, 8, 3, 3, 1};
countingSort(arr);
for (int x : arr) cout << x << " ";  // 1 2 2 3 3 4 8
return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Counting sort по разряду exp
void countingSortByDigit(vector& arr, int exp) {
int n = arr.size();
vector output(n);
int count[10] = {0};

for (int i = 0; i < n; i++)
    count[(arr[i] / exp) % 10]++;

for (int i = 1; i < 10; i++)
    count[i] += count[i - 1];

for (int i = n - 1; i >= 0; i--) {  // справа налево = стабильность
    output[count[(arr[i] / exp) % 10] - 1] = arr[i];
    count[(arr[i] / exp) % 10]--;
}

arr = output;
}

void radixSort(vector& arr) {
int maxVal = *max_element(arr.begin(), arr.end());
// Сортируем по каждому разряду
for (int exp = 1; maxVal / exp > 0; exp *= 10)
countingSortByDigit(arr, exp);
}

int main() {
vector arr = {170, 45, 75, 90, 802, 24, 2, 66};
radixSort(arr);
for (int x : arr) cout << x << " ";  // 2 24 45 66 75 90 170 802
return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Для вещественных чисел в диапазоне [0, 1)
void bucketSort(vector& arr) {
int n = arr.size();
if (n <= 0) return;

vector<vector<float>> buckets(n);

// Распределяем по корзинам
for (float x : arr) {
    int idx = (int)(x * n);  // индекс корзины
    buckets[idx].push_back(x);
}

// Сортируем каждую корзину
for (auto& bucket : buckets)
    sort(bucket.begin(), bucket.end());

// Собираем обратно
int k = 0;
for (auto& bucket : buckets)
    for (float x : bucket)
        arr[k++] = x;
}

int main() {
vector arr = {0.42f, 0.32f, 0.23f, 0.52f, 0.25f, 0.47f, 0.51f};
bucketSort(arr);
for (float x : arr) cout << x << " ";
// 0.23 0.25 0.32 0.42 0.47 0.51 0.52
return 0;
}

#include <iostream>
#include <vector>
using namespace std;

void shellSort(vector& arr) {
int n = arr.size();
// Последовательность Шелла: n/2, n/4, ..., 1
for (int gap = n / 2; gap > 0; gap /= 2) {
// Insertion sort с шагом gap
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j = i;
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
}

int main() {
vector arr = {35, 33, 42, 10, 14, 19, 27, 44};
shellSort(arr);
for (int x : arr) cout << x << " ";  // 10 14 19 27 33 35 42 44
return 0;
}

#include <iostream>
#include <vector>
using namespace std;

// Возвращает индекс первого вхождения или -1
int linearSearch(const vector<int>& arr, int target) {
    for (int i = 0; i < (int)arr.size(); i++) {
        if (arr[i] == target)
            return i;
    }
    return -1;  // не найден
}

// Вариант: поиск всех вхождений
vector<int> linearSearchAll(const vector<int>& arr, int target) {
    vector<int> result;
    for (int i = 0; i < (int)arr.size(); i++) {
        if (arr[i] == target)
            result.push_back(i);
    }
    return result;
}

// Вариант с «барьером» (sentinel) — убирает проверку границы
int sentinelSearch(vector<int>& arr, int target) {
    int n = arr.size();
    int last = arr[n - 1];
    arr[n - 1] = target;  // ставим «барьер»

    int i = 0;
    while (arr[i] != target) i++;  // без проверки i < n!

    arr[n - 1] = last;    // восстанавливаем

    if (i < n - 1 || last == target) return i;
    return -1;
}

int main() {
    vector<int> arr = {5, 3, 8, 1, 2, 8, 7};

    cout << linearSearch(arr, 8) << endl;     // 2

    auto all = linearSearchAll(arr, 8);
    for (int idx : all) cout << idx << " ";   // 2 5
    cout << endl;

    cout << linearSearch(arr, 99) << endl;    // -1
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

// ─── Итеративный бинарный поиск ───
int binarySearch(const vector<int>& arr, int target) {
    int lo = 0, hi = (int)arr.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;   // безопасно от переполнения
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target)  lo = mid + 1;
        else                          hi = mid - 1;
    }
    return -1;
}

// ─── Рекурсивный бинарный поиск ───
int binarySearchRec(const vector<int>& arr, int target, int lo, int hi) {
    if (lo > hi) return -1;
    int mid = lo + (hi - lo) / 2;
    if (arr[mid] == target) return mid;
    if (arr[mid] < target) return binarySearchRec(arr, target, mid + 1, hi);
    return binarySearchRec(arr, target, lo, mid - 1);
}

// ─── Lower Bound: первый элемент ≥ target ───
int lowerBound(const vector<int>& arr, int target) {
    int lo = 0, hi = arr.size();  // hi = n (за пределами!)
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] < target)   lo = mid + 1;
        else                      hi = mid;
    }
    return lo;  // позиция вставки или первое вхождение
}

// ─── Upper Bound: первый элемент > target ───
int upperBound(const vector<int>& arr, int target) {
    int lo = 0, hi = arr.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] <= target)  lo = mid + 1;
        else                      hi = mid;
    }
    return lo;
}

// ─── Бинарный поиск по ответу (пример: квадратный корень) ───
double sqrtBinarySearch(double x, double eps = 1e-9) {
    double lo = 0, hi = max(1.0, x);
    while (hi - lo > eps) {
        double mid = (lo + hi) / 2;
        if (mid * mid < x) lo = mid;
        else                hi = mid;
    }
    return (lo + hi) / 2;
}

int main() {
    vector<int> arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};

    cout << "Search 23: " << binarySearch(arr, 23) << endl;      // 5
    cout << "Search 99: " << binarySearch(arr, 99) << endl;      // -1

    cout << "LowerBound 8: " << lowerBound(arr, 8) << endl;     // 2
    cout << "UpperBound 8: " << upperBound(arr, 8) << endl;     // 3

    // Подсчёт вхождений числа:
    vector<int> arr2 = {1,2,2,2,3,4,5};
    int count = upperBound(arr2, 2) - lowerBound(arr2, 2);
    cout << "Count of 2: " << count << endl;  // 3

    cout << "sqrt(2) = " << sqrtBinarySearch(2.0) << endl;  // 1.41421...

    return 0;
}

#include <iostream>
#include <cmath>
using namespace std;

// Пример: ищем максимум функции f(x) = -(x-3)^2 + 10
// Максимум при x = 3, f(3) = 10
double f(double x) {
    return -(x - 3) * (x - 3) + 10;
}

// Тернарный поиск максимума на [lo, hi]
double ternarySearchMax(double lo, double hi, double eps = 1e-9) {
    while (hi - lo > eps) {
        double m1 = lo + (hi - lo) / 3.0;
        double m2 = hi - (hi - lo) / 3.0;
        if (f(m1) < f(m2))
            lo = m1;   // максимум в [m1, hi]
        else
            hi = m2;   // максимум в [lo, m2]
    }
    return (lo + hi) / 2.0;
}

// Тернарный поиск минимума (для выпуклой функции)
// Аналогично, но меняем знак сравнения
double ternarySearchMin(double lo, double hi, double eps = 1e-9) {
    while (hi - lo > eps) {
        double m1 = lo + (hi - lo) / 3.0;
        double m2 = hi - (hi - lo) / 3.0;
        if (f(m1) > f(m2))   // наоборот!
            lo = m1;
        else
            hi = m2;
    }
    return (lo + hi) / 2.0;
}

// Дискретный тернарный поиск (для массива)
int ternarySearchDiscrete(int arr[], int lo, int hi) {
    while (hi - lo > 2) {
        int m1 = lo + (hi - lo) / 3;
        int m2 = hi - (hi - lo) / 3;
        if (arr[m1] < arr[m2])
            lo = m1 + 1;
        else
            hi = m2 - 1;
    }
    // Проверяем 1-3 оставшихся элемента
    int best = lo;
    for (int i = lo; i <= hi; i++)
        if (arr[i] > arr[best]) best = i;
    return best;
}

int main() {
    double x = ternarySearchMax(0, 10);
    cout << "Max at x = " << x << ", f(x) = " << f(x) << endl;
    // Max at x = 3, f(x) = 10
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

int interpolationSearch(const vector<int>& arr, int target) {
    int lo = 0, hi = (int)arr.size() - 1;

    while (lo <= hi && target >= arr[lo] && target <= arr[hi]) {
        if (lo == hi) {
            return (arr[lo] == target) ? lo : -1;
        }

        // Интерполяция позиции
        int pos = lo + (long long)(target - arr[lo]) * (hi - lo)
                      / (arr[hi] - arr[lo]);

        if (arr[pos] == target)
            return pos;
        else if (arr[pos] < target)
            lo = pos + 1;
        else
            hi = pos - 1;
    }
    return -1;
}

int main() {
    vector<int> arr = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};

    cout << interpolationSearch(arr, 70) << endl;   // 6
    cout << interpolationSearch(arr, 25) << endl;   // -1
    cout << interpolationSearch(arr, 10) << endl;   // 0
    cout << interpolationSearch(arr, 100) << endl;  // 9

    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// ─── Задача 1: Two Sum (отсортированный массив) ───
pair<int,int> twoSum(const vector<int>& arr, int target) {
    int lo = 0, hi = (int)arr.size() - 1;
    while (lo < hi) {
        int sum = arr[lo] + arr[hi];
        if (sum == target)      return {lo, hi};
        else if (sum < target)  lo++;
        else                    hi--;
    }
    return {-1, -1};  // не найдено
}

// ─── Задача 2: Удаление дубликатов in-place ───
int removeDuplicates(vector<int>& arr) {
    if (arr.empty()) return 0;
    int slow = 0;  // указатель на последний уникальный
    for (int fast = 1; fast < (int)arr.size(); fast++) {
        if (arr[fast] != arr[slow]) {
            slow++;
            arr[slow] = arr[fast];
        }
    }
    return slow + 1;  // количество уникальных
}

// ─── Задача 3: Контейнер с наибольшим количеством воды ───
int maxWater(const vector<int>& height) {
    int lo = 0, hi = (int)height.size() - 1;
    int maxArea = 0;
    while (lo < hi) {
        int area = min(height[lo], height[hi]) * (hi - lo);
        maxArea = max(maxArea, area);
        if (height[lo] < height[hi]) lo++;
        else hi--;
    }
    return maxArea;
}

// ─── Задача 4: Проверка палиндрома ───
bool isPalindrome(const string& s) {
    int lo = 0, hi = (int)s.size() - 1;
    while (lo < hi) {
        if (s[lo] != s[hi]) return false;
        lo++;
        hi--;
    }
    return true;
}

// ─── Задача 5: Слияние двух отсортированных массивов ───
vector<int> mergeSorted(const vector<int>& a, const vector<int>& b) {
    vector<int> result;
    int i = 0, j = 0;
    while (i < (int)a.size() && j < (int)b.size()) {
        if (a[i] <= b[j]) result.push_back(a[i++]);
        else                result.push_back(b[j++]);
    }
    while (i < (int)a.size()) result.push_back(a[i++]);
    while (j < (int)b.size()) result.push_back(b[j++]);
    return result;
}

int main() {
    // Two Sum
    vector<int> arr = {2, 7, 11, 15};
    auto [a, b] = twoSum(arr, 9);
    cout << "Two Sum: [" << a << ", " << b << "]" << endl;  // [0, 1]

    // Remove Duplicates
    vector<int> arr2 = {1, 1, 2, 2, 3, 4, 4, 5};
    int len = removeDuplicates(arr2);
    cout << "Unique count: " << len << endl;  // 5

    // Palindrome
    cout << "abcba is palindrome: " << isPalindrome("abcba") << endl;  // 1

    // Max Water
    vector<int> h = {1,8,6,2,5,4,8,3,7};
    cout << "Max water: " << maxWater(h) << endl;  // 49

    return 0;
}

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

// ─── Задача 1: Макс. сумма подмассива длины k (фиксированное окно) ───
int maxSumSubarray(const vector<int>& arr, int k) {
    int n = arr.size();
    if (n < k) return -1;

    // Считаем сумму первого окна
    int windowSum = 0;
    for (int i = 0; i < k; i++)
        windowSum += arr[i];

    int maxSum = windowSum;

    // Сдвигаем окно: добавляем правый, убираем левый
    for (int i = k; i < n; i++) {
        windowSum += arr[i] - arr[i - k];
        maxSum = max(maxSum, windowSum);
    }
    return maxSum;
}

// ─── Задача 2: Минимальный подмассив с суммой ≥ target (переменное окно) ───
int minSubarrayLen(const vector<int>& arr, int target) {
    int n = arr.size();
    int left = 0, sum = 0;
    int minLen = n + 1;

    for (int right = 0; right < n; right++) {
        sum += arr[right];                // расширяем окно
        while (sum >= target) {           // пока условие выполняется
            minLen = min(minLen, right - left + 1);
            sum -= arr[left];             // сужаем окно
            left++;
        }
    }
    return (minLen > n) ? 0 : minLen;
}

// ─── Задача 3: Самая длинная подстрока без повторов ───
int longestUniqueSubstring(const string& s) {
    unordered_map<char, int> lastSeen;  // символ → последняя позиция
    int maxLen = 0, left = 0;

    for (int right = 0; right < (int)s.size(); right++) {
        if (lastSeen.count(s[right]) && lastSeen[s[right]] >= left) {
            left = lastSeen[s[right]] + 1;  // сдвигаем левую границу
        }
        lastSeen[s[right]] = right;
        maxLen = max(maxLen, right - left + 1);
    }
    return maxLen;
}

// ─── Задача 4: Подсчёт анаграмм подстроки ───
int countAnagrams(const string& text, const string& pattern) {
    int n = text.size(), m = pattern.size();
    if (n < m) return 0;

    vector<int> pCount(26, 0), wCount(26, 0);
    for (char c : pattern) pCount[c - 'a']++;

    int count = 0;
    for (int i = 0; i < n; i++) {
        wCount[text[i] - 'a']++;
        if (i >= m) wCount[text[i - m] - 'a']--;
        if (wCount == pCount) count++;
    }
    return count;
}

int main() {
    // Задача 1
    vector<int> arr1 = {2, 1, 5, 1, 3, 2};
    cout << "Max sum k=3: " << maxSumSubarray(arr1, 3) << endl;  // 9

    // Задача 2
    vector<int> arr2 = {2, 3, 1, 2, 4, 3};
    cout << "Min subarray sum>=7: " << minSubarrayLen(arr2, 7) << endl;  // 2

    // Задача 3
    cout << "Longest unique: " << longestUniqueSubstring("abcabcbb") << endl;  // 3

    // Задача 4
    cout << "Anagram count: " << countAnagrams("cbaebabacd", "abc") << endl;  // 2

    return 0;
}

#include <iostream>
#include <vector>
#include <stack>
#include <string>
using namespace std;

// ═══ Реализация стека на массиве ═══
template <typename T>
class MyStack {
    vector<T> data;
public:
    void push(T val) { data.push_back(val); }

    void pop() {
        if (data.empty()) throw runtime_error("Stack underflow");
        data.pop_back();
    }

    T top() const {
        if (data.empty()) throw runtime_error("Stack is empty");
        return data.back();
    }

    bool empty() const { return data.empty(); }
    int size() const { return data.size(); }
};

// ═══ Задача 1: Проверка сбалансированности скобок ═══
bool isBalanced(const string& s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if (st.empty()) return false;
            char top = st.top(); st.pop();
            if (c == ')' && top != '(') return false;
            if (c == ']' && top != '[') return false;
            if (c == '}' && top != '{') return false;
        }
    }
    return st.empty();
}

// ═══ Задача 2: Обратная польская запись (RPN) ═══
int evalRPN(const vector<string>& tokens) {
    stack<int> st;
    for (const string& t : tokens) {
        if (t == "+" || t == "-" || t == "*" || t == "/") {
            int b = st.top(); st.pop();
            int a = st.top(); st.pop();
            if (t == "+") st.push(a + b);
            else if (t == "-") st.push(a - b);
            else if (t == "*") st.push(a * b);
            else st.push(a / b);
        } else {
            st.push(stoi(t));
        }
    }
    return st.top();
}

// ═══ Задача 3: Следующий больший элемент (Next Greater Element) ═══
vector<int> nextGreater(const vector<int>& arr) {
    int n = arr.size();
    vector<int> result(n, -1);
    stack<int> st;  // стек индексов

    for (int i = 0; i < n; i++) {
        // пока текущий элемент больше того, что на вершине стека
        while (!st.empty() && arr[st.top()] < arr[i]) {
            result[st.top()] = arr[i];
            st.pop();
        }
        st.push(i);
    }
    return result;
}

// ═══ Задача 4: Инфикс → Постфикс (алгоритм Shunting Yard) ═══
int precedence(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

string infixToPostfix(const string& infix) {
    string result;
    stack<char> ops;

    for (char c : infix) {
        if (isalnum(c)) {
            result += c;
        } else if (c == '(') {
            ops.push(c);
        } else if (c == ')') {
            while (!ops.empty() && ops.top() != '(') {
                result += ops.top(); ops.pop();
            }
            ops.pop(); // убираем '('
        } else { // оператор
            while (!ops.empty() && precedence(ops.top()) >= precedence(c)) {
                result += ops.top(); ops.pop();
            }
            ops.push(c);
        }
    }
    while (!ops.empty()) { result += ops.top(); ops.pop(); }
    return result;
}

int main() {
    // Стек
    MyStack<int> s;
    s.push(10); s.push(20); s.push(30);
    cout << "Top: " << s.top() << endl;  // 30
    s.pop();
    cout << "Top after pop: " << s.top() << endl;  // 20

    // Скобки
    cout << "({[]}) balanced: " << isBalanced("({[]})") << endl;  // 1
    cout << "([)] balanced: " << isBalanced("([)]") << endl;      // 0

    // RPN: (3 + 4) * 2 = 14
    cout << "RPN: " << evalRPN({"3","4","+","2","*"}) << endl;  // 14

    // Next Greater
    vector<int> arr = {4, 5, 2, 10, 8};
    auto ng = nextGreater(arr);
    for (int x : ng) cout << x << " ";  // 5 10 10 -1 -1
    cout << endl;

    // Инфикс → Постфикс
    cout << "a+b*c = " << infixToPostfix("a+b*c") << endl;  // abc*+

    return 0;
}

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
using namespace std;

// ═══ Кольцевая очередь (Circular Queue) на массиве ═══
template <typename T>
class CircularQueue {
    vector<T> data;
    int head, tail, cnt, cap;
public:
    CircularQueue(int capacity)
        : data(capacity), head(0), tail(0), cnt(0), cap(capacity) {}

    void enqueue(T val) {
        if (cnt == cap) throw runtime_error("Queue overflow");
        data[tail] = val;
        tail = (tail + 1) % cap;  // кольцо!
        cnt++;
    }

    T dequeue() {
        if (cnt == 0) throw runtime_error("Queue underflow");
        T val = data[head];
        head = (head + 1) % cap;
        cnt--;
        return val;
    }

    T front() const {
        if (cnt == 0) throw runtime_error("Queue is empty");
        return data[head];
    }

    bool empty() const { return cnt == 0; }
    bool full() const { return cnt == cap; }
    int size() const { return cnt; }
};

// ═══ Очередь на двух стеках (собеседование!) ═══
class QueueViaStacks {
    stack<int> inbox, outbox;

    void transfer() {
        if (outbox.empty()) {
            while (!inbox.empty()) {
                outbox.push(inbox.top());
                inbox.pop();
            }
        }
    }
public:
    void enqueue(int val) { inbox.push(val); }

    int dequeue() {
        transfer();
        int val = outbox.top();
        outbox.pop();
        return val;
    }

    int front() {
        transfer();
        return outbox.top();
    }

    bool empty() { return inbox.empty() && outbox.empty(); }
};

// ═══ Задача: Генерация двоичных чисел от 1 до n ═══
vector<string> generateBinary(int n) {
    vector<string> result;
    queue<string> q;
    q.push("1");

    for (int i = 0; i < n; i++) {
        string curr = q.front(); q.pop();
        result.push_back(curr);
        q.push(curr + "0");  // порождаем следующие
        q.push(curr + "1");
    }
    return result;
}

int main() {
    // Кольцевая очередь
    CircularQueue<int> cq(5);
    cq.enqueue(10); cq.enqueue(20); cq.enqueue(30);
    cout << "Front: " << cq.front() << endl;    // 10
    cout << "Dequeue: " << cq.dequeue() << endl;  // 10
    cout << "Front: " << cq.front() << endl;      // 20

    // Очередь на стеках
    QueueViaStacks qs;
    qs.enqueue(1); qs.enqueue(2); qs.enqueue(3);
    cout << "Queue via stacks: ";
    cout << qs.dequeue() << " ";  // 1
    cout << qs.dequeue() << " ";  // 2
    qs.enqueue(4);
    cout << qs.dequeue() << " ";  // 3
    cout << qs.dequeue() << endl; // 4

    // Генерация двоичных чисел
    auto bins = generateBinary(5);
    for (auto& b : bins) cout << b << " ";  // 1 10 11 100 101
    cout << endl;

    return 0;
}

#include <iostream>
#include <deque>
#include <vector>
using namespace std;

// ═══ Задача: Максимум в скользящем окне размера k ═══
// Используем монотонный дек (убывающий)
vector<int> maxSlidingWindow(const vector<int>& arr, int k) {
    vector<int> result;
    deque<int> dq;  // хранит ИНДЕКСЫ в убывающем порядке значений

    for (int i = 0; i < (int)arr.size(); i++) {
        // Удаляем элементы вне окна
        while (!dq.empty() && dq.front() <= i - k)
            dq.pop_front();

        // Удаляем все элементы меньше текущего (поддерживаем убывание)
        while (!dq.empty() && arr[dq.back()] <= arr[i])
            dq.pop_back();

        dq.push_back(i);

        // Первое полное окно
        if (i >= k - 1)
            result.push_back(arr[dq.front()]);  // front = максимум
    }
    return result;
}

int main() {
    // STL deque
    deque<int> dq;
    dq.push_back(10);   // [10]
    dq.push_front(5);   // [5, 10]
    dq.push_back(20);   // [5, 10, 20]
    dq.push_front(1);   // [1, 5, 10, 20]

    cout << "Front: " << dq.front() << endl;  // 1
    cout << "Back: " << dq.back() << endl;    // 20
    dq.pop_front();  // [5, 10, 20]
    dq.pop_back();   // [5, 10]

    // Доступ по индексу тоже O(1)!
    cout << "dq[1] = " << dq[1] << endl;  // 10

    // Максимум в скользящем окне
    vector<int> arr = {1, 3, -1, -3, 5, 3, 6, 7};
    auto res = maxSlidingWindow(arr, 3);
    cout << "Max sliding window k=3: ";
    for (int x : res) cout << x << " ";  // 3 3 5 5 6 7
    cout << endl;

    return 0;
}

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int v) : val(v), next(nullptr) {}
};

class LinkedList {
    ListNode* head;
public:
    LinkedList() : head(nullptr) {}

    // Вставка в начало: O(1)
    void pushFront(int val) {
        ListNode* node = new ListNode(val);
        node->next = head;
        head = node;
    }

    // Вставка в конец: O(n)
    void pushBack(int val) {
        ListNode* node = new ListNode(val);
        if (!head) { head = node; return; }
        ListNode* cur = head;
        while (cur->next) cur = cur->next;
        cur->next = node;
    }

    // Удаление по значению: O(n)
    void remove(int val) {
        if (!head) return;
        if (head->val == val) {
            ListNode* tmp = head;
            head = head->next;
            delete tmp;
            return;
        }
        ListNode* cur = head;
        while (cur->next && cur->next->val != val)
            cur = cur->next;
        if (cur->next) {
            ListNode* tmp = cur->next;
            cur->next = tmp->next;
            delete tmp;
        }
    }

    // Поиск: O(n)
    bool contains(int val) const {
        ListNode* cur = head;
        while (cur) {
            if (cur->val == val) return true;
            cur = cur->next;
        }
        return false;
    }

    void print() const {
        ListNode* cur = head;
        while (cur) {
            cout << cur->val;
            if (cur->next) cout << " → ";
            cur = cur->next;
        }
        cout << " → NULL" << endl;
    }

    ListNode* getHead() { return head; }

    ~LinkedList() {
        while (head) { ListNode* t = head; head = head->next; delete t; }
    }
};

// ═══ Задача 1: Развернуть список (итеративно) ═══
ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr) {
        ListNode* next = curr->next;
        curr->next = prev;    // разворачиваем стрелку
        prev = curr;
        curr = next;
    }
    return prev;  // новый head
}

// ═══ Задача 2: Найти середину списка ═══
ListNode* findMiddle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;        // шаг 1
        fast = fast->next->next;  // шаг 2
    }
    return slow;  // slow теперь в середине
}

// ═══ Задача 3: Обнаружить цикл (Floyd's Algorithm) ═══
bool hasCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;  // встретились → цикл!
    }
    return false;
}

int main() {
    LinkedList list;
    list.pushBack(1);
    list.pushBack(2);
    list.pushBack(3);
    list.pushBack(4);
    list.pushBack(5);
    list.print();  // 1 → 2 → 3 → 4 → 5 → NULL

    // Середина
    ListNode* mid = findMiddle(list.getHead());
    cout << "Middle: " << mid->val << endl;  // 3

    return 0;
}

#include <iostream>
#include <unordered_map>
using namespace std;

struct DNode {
    int key, val;
    DNode* prev;
    DNode* next;
    DNode(int k, int v) : key(k), val(v), prev(nullptr), next(nullptr) {}
};

// ═══ LRU Cache (Least Recently Used) — собеседование! ═══
class LRUCache {
    int capacity;
    unordered_map<int, DNode*> map;  // key → node pointer
    DNode *head, *tail;  // фиктивные (sentinel) узлы для удобства

    // Добавление сразу после head (самый "свежий")
    void addToFront(DNode* node) {
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }

    // Удаление из списка
    void removeNode(DNode* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    // Перемещение обновленного элемента в начало
    void moveToFront(DNode* node) {
        removeNode(node);
        addToFront(node);
    }

public:
    LRUCache(int cap) : capacity(cap) {
        head = new DNode(0, 0);  // sentinel
        tail = new DNode(0, 0);  // sentinel
        head->next = tail;
        tail->prev = head;
    }

    int get(int key) {
        if (map.find(key) == map.end()) return -1;
        DNode* node = map[key];
        moveToFront(node);  // мы его использовали, он теперь самый свежий
        return node->val;
    }

    void put(int key, int value) {
        if (map.find(key) != map.end()) {
            DNode* node = map[key];
            node->val = value;
            moveToFront(node);
        } else {
            if ((int)map.size() == capacity) {
                // Выкидываем LRU (тот, что перед tail)
                DNode* lru = tail->prev;
                removeNode(lru);
                map.erase(lru->key);
                delete lru;
            }
            DNode* node = new DNode(key, value);
            addToFront(node);
            map[key] = node;
        }
    }

    ~LRUCache() {
        DNode* cur = head;
        while (cur) { DNode* t = cur; cur = cur->next; delete t; }
    }
};

int main() {
    LRUCache cache(3);  // ёмкость 3

    cache.put(1, 100);
    cache.put(2, 200);
    cache.put(3, 300);
    cout << cache.get(2) << endl;  // 200 (2 становится самым свежим)

    cache.put(4, 400);  // вытесняет ключ 1 (самый старый)
    cout << cache.get(1) << endl;  // -1 (вытеснен!)
    cout << cache.get(3) << endl;  // 300
    cout << cache.get(4) << endl;  // 400

    return 0;
}

#include <iostream>
#include <list>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
using namespace std;

// ═══ Реализация хеш-таблицы (метод цепочек) ═══
class HashTable {
    int size;
    vector<list<pair<int,string>>> table;

    int hash(int key) const { return key % size; }

public:
    HashTable(int sz = 13) : size(sz), table(sz) {}

    void insert(int key, const string& value) {
        int idx = hash(key);
        // Обновляем если ключ есть
        for (auto& [k, v] : table[idx]) {
            if (k == key) { v = value; return; }
        }
        table[idx].push_back({key, value});
    }

    string search(int key) const {
        int idx = hash(key);
        for (auto& [k, v] : table[idx]) {
            if (k == key) return v;
        }
        return "NOT FOUND";
    }

    void remove(int key) {
        int idx = hash(key);
        table[idx].remove_if([key](auto& p){ return p.first == key; });
    }
};

// ═══ Задача 1: Two Sum (самая популярная на LeetCode!) ═══
vector<int> twoSum(const vector<int>& nums, int target) {
    unordered_map<int, int> seen;  // value → index
    for (int i = 0; i < (int)nums.size(); i++) {
        int complement = target - nums[i];
        if (seen.count(complement))
            return {seen[complement], i};
        seen[nums[i]] = i;
    }
    return {};
}

// ═══ Задача 2: Группировка анаграмм ═══
vector<vector<string>> groupAnagrams(const vector<string>& strs) {
    unordered_map<string, vector<string>> groups;
    for (const string& s : strs) {
        string key = s;
        sort(key.begin(), key.end());  // ключ = отсортированная строка
        groups[key].push_back(s);
    }
    vector<vector<string>> result;
    for (auto& [k, v] : groups)
        result.push_back(v);
    return result;
}

int main() {
    // Two Sum
    auto res = twoSum({2, 7, 11, 15}, 9);
    cout << "Two Sum: [" << res[0] << ", " << res[1] << "]" << endl;  // [0, 1]

    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
#include <functional>
using namespace std;

// ═══ Min-Heap с нуля ═══
class MinHeap {
    vector<int> heap;

    void siftUp(int i) {
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (heap[parent] > heap[i]) {
                swap(heap[parent], heap[i]);
                i = parent;
            } else break;
        }
    }

    void siftDown(int i) {
        int n = heap.size();
        while (2 * i + 1 < n) {
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            int smallest = i;
            if (left < n && heap[left] < heap[smallest]) smallest = left;
            if (right < n && heap[right] < heap[smallest]) smallest = right;
            if (smallest == i) break;
            swap(heap[i], heap[smallest]);
            i = smallest;
        }
    }

public:
    void insert(int val) {
        heap.push_back(val);
        siftUp(heap.size() - 1);
    }

    int extractMin() {
        int minVal = heap[0];
        heap[0] = heap.back();
        heap.pop_back();
        if (!heap.empty()) siftDown(0);
        return minVal;
    }

    int peekMin() const { return heap[0]; }
    bool empty() const { return heap.empty(); }
    int size() const { return heap.size(); }
};

// ═══ Задача 1: K-й наибольший элемент ═══
int kthLargest(vector<int>& arr, int k) {
    // Min-heap размера k
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int x : arr) {
        pq.push(x);
        if ((int)pq.size() > k) pq.pop();  // удаляем наименьший
    }
    return pq.top();  // k-й наибольший
}

// ═══ Задача 3: Медиана потока данных ═══
class MedianFinder {
    priority_queue<int> maxHeap;                          // левая половина
    priority_queue<int, vector<int>, greater<int>> minHeap;  // правая половина
public:
    void addNum(int num) {
        maxHeap.push(num);
        minHeap.push(maxHeap.top());
        maxHeap.pop();
        // Балансировка: maxHeap может быть на 1 больше
        if (maxHeap.size() < minHeap.size()) {
            maxHeap.push(minHeap.top());
            minHeap.pop();
        }
    }

    double findMedian() {
        if (maxHeap.size() > minHeap.size())
            return maxHeap.top();
        return (maxHeap.top() + minHeap.top()) / 2.0;
    }
};

int main() {
    // Своя куча
    MinHeap mh;
    mh.insert(15); mh.insert(10); mh.insert(20); mh.insert(5);
    cout << "Min: " << mh.extractMin() << endl;  // 5

    // K-й наибольший
    vector<int> arr = {3, 2, 1, 5, 6, 4};
    cout << "2nd largest: " << kthLargest(arr, 2) << endl;  // 5

    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

class DSU {
    vector<int> parent, rank_;
    int components;

public:
    DSU(int n) : parent(n), rank_(n, 0), components(n) {
        for (int i = 0; i < n; i++) parent[i] = i;  // каждый — свой корень
    }

    // Найти корень с СЖАТИЕМ ПУТИ
    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);  // рекурсивно сжимаем путь
        return parent[x];
    }

    // Объединить по РАНГУ
    bool unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;  // уже в одном множестве

        // Подвешиваем меньшее дерево к большему
        if (rank_[rx] < rank_[ry]) swap(rx, ry);
        parent[ry] = rx;
        if (rank_[rx] == rank_[ry]) rank_[rx]++;
        components--;
        return true;
    }

    bool connected(int x, int y) { return find(x) == find(y); }
    int getComponents() const { return components; }
};

// ═══ Задача: Обнаружение цикла в неориентированном графе ═══
bool hasCycle(int n, vector<pair<int,int>>& edges) {
    DSU dsu(n);
    for (auto& [u, v] : edges) {
        if (!dsu.unite(u, v))
            return true;  // u и v уже в одном множестве → добавление ребра создает цикл!
    }
    return false;
}

int main() {
    DSU dsu(5);
    dsu.unite(0, 1);
    dsu.unite(2, 3);
    dsu.unite(1, 3);

    cout << "0 и 3 связаны: " << dsu.connected(0, 3) << endl;  // 1
    cout << "0 и 4 связаны: " << dsu.connected(0, 4) << endl;  // 0
    cout << "Компонент: " << dsu.getComponents() << endl;       // 2

    // Цикл
    vector<pair<int,int>> edges = {{0,1},{1,2},{2,0}};
    cout << "Has cycle: " << hasCycle(3, edges) << endl;  // 1

    return 0;
}

#include <iostream>
#include <vector>
#include <string>
using namespace std;

struct TrieNode {
    TrieNode* children[26];
    bool isEnd;
    int prefixCount;  // сколько слов проходят через этот узел

    TrieNode() : isEnd(false), prefixCount(0) {
        for (int i = 0; i < 26; i++) children[i] = nullptr;
    }
};

class Trie {
    TrieNode* root;

    void collectWords(TrieNode* node, string& current, vector<string>& result) {
        if (node->isEnd) result.push_back(current);
        for (int i = 0; i < 26; i++) {
            if (node->children[i]) {
                current += ('a' + i);
                collectWords(node->children[i], current, result);
                current.pop_back();
            }
        }
    }

public:
    Trie() { root = new TrieNode(); }

    // Вставка слова: O(L)
    void insert(const string& word) {
        TrieNode* cur = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!cur->children[idx])
                cur->children[idx] = new TrieNode();
            cur = cur->children[idx];
            cur->prefixCount++;
        }
        cur->isEnd = true;
    }

    // Поиск слова: O(L)
    bool search(const string& word) const {
        TrieNode* cur = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!cur->children[idx]) return false;
            cur = cur->children[idx];
        }
        return cur->isEnd;
    }

    // Есть ли слово с таким префиксом: O(L)
    bool startsWith(const string& prefix) const {
        TrieNode* cur = root;
        for (char c : prefix) {
            int idx = c - 'a';
            if (!cur->children[idx]) return false;
            cur = cur->children[idx];
        }
        return true;
    }

    // Автодополнение: все слова с данным префиксом
    vector<string> autocomplete(const string& prefix) {
        vector<string> result;
        TrieNode* cur = root;
        for (char c : prefix) {
            int idx = c - 'a';
            if (!cur->children[idx]) return result;
            cur = cur->children[idx];
        }
        string current = prefix;
        collectWords(cur, current, result);
        return result;
    }
};

int main() {
    Trie trie;
    trie.insert("apple");
    trie.insert("app");
    trie.insert("application");
    trie.insert("banana");

    cout << "search 'app': " << trie.search("app") << endl;          // 1
    cout << "search 'ap': " << trie.search("ap") << endl;            // 0
    cout << "startsWith 'ap': " << trie.startsWith("ap") << endl;    // 1

    cout << "Autocomplete 'app': ";
    auto suggestions = trie.autocomplete("app");
    for (auto& s : suggestions) cout << s << " ";
    // app apple application
    cout << endl;

    return 0;
}

#include <iostream>
#include <queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

class BST {
public:
    TreeNode* root = nullptr;

    // ═══ Вставка ═══
    TreeNode* insert(TreeNode* node, int val) {
        if (!node) return new TreeNode(val);
        if (val < node->val)      node->left = insert(node->left, val);
        else if (val > node->val) node->right = insert(node->right, val);
        return node;  // дубликаты игнорируем
    }

    void insert(int val) { root = insert(root, val); }

    // ═══ Поиск ═══
    bool search(TreeNode* node, int val) {
        if (!node) return false;
        if (val == node->val) return true;
        if (val < node->val) return search(node->left, val);
        return search(node->right, val);
    }

    bool search(int val) { return search(root, val); }

    // ═══ Минимум и максимум ═══
    TreeNode* findMin(TreeNode* node) {
        while (node->left) node = node->left;
        return node;
    }

    TreeNode* findMax(TreeNode* node) {
        while (node->right) node = node->right;
        return node;
    }

    // ═══ Удаление (3 случая) ═══
    TreeNode* remove(TreeNode* node, int val) {
        if (!node) return nullptr;

        if (val < node->val)
            node->left = remove(node->left, val);
        else if (val > node->val)
            node->right = remove(node->right, val);
        else {
            // Случай 1: лист
            if (!node->left && !node->right) {
                delete node;
                return nullptr;
            }
            // Случай 2: один ребёнок
            if (!node->left) {
                TreeNode* tmp = node->right;
                delete node;
                return tmp;
            }
            if (!node->right) {
                TreeNode* tmp = node->left;
                delete node;
                return tmp;
            }
            // Случай 3: два ребёнка → заменяем на inorder successor
            TreeNode* successor = findMin(node->right);
            node->val = successor->val;
            node->right = remove(node->right, successor->val);
        }
        return node;
    }

    void remove(int val) { root = remove(root, val); }

    // ═══ Обходы ═══
    void inorder(TreeNode* node) {
        if (!node) return;
        inorder(node->left);
        cout << node->val << " ";
        inorder(node->right);
    }

    // ═══ Высота дерева ═══
    int height(TreeNode* node) {
        if (!node) return -1;  // или 0, зависит от определения
        return 1 + max(height(node->left), height(node->right));
    }

    // ═══ Проверка: является ли BST (Собеседование!) ═══
    bool isValidBST(TreeNode* node, long long minVal, long long maxVal) {
        if (!node) return true;
        if (node->val <= minVal || node->val >= maxVal) return false;
        return isValidBST(node->left, minVal, node->val) &&
               isValidBST(node->right, node->val, maxVal);
    }
};

int main() {
    BST tree;
    tree.insert(8); tree.insert(3); tree.insert(10);
    tree.insert(1); tree.insert(6); tree.insert(14);

    cout << "Inorder: ";
    tree.inorder(tree.root);  // 1 3 6 8 10 14
    cout << endl;

    cout << "Search 6: " << tree.search(6) << endl;   // 1
    tree.remove(3);  // удаляем узел с двумя детьми
    cout << "After remove 3: ";
    tree.inorder(tree.root);  // 1 6 8 10 14
    cout << endl;

    return 0;
}

#include <iostream>
using namespace std;

struct AVLNode {
    int val, height;
    AVLNode *left, *right;
    AVLNode(int v) : val(v), height(1), left(nullptr), right(nullptr) {}
};

class AVLTree {
    int height(AVLNode* n) { return n ? n->height : 0; }
    int balanceFactor(AVLNode* n) { return n ? height(n->left) - height(n->right) : 0; }

    void updateHeight(AVLNode* n) {
        n->height = 1 + max(height(n->left), height(n->right));
    }

    // Правый поворот (LL case)
    //     y            x
    //    / \          / \
    //   x   C  →    A   y
    //  / \              / \
    // A   B            B   C
    AVLNode* rotateRight(AVLNode* y) {
        AVLNode* x = y->left;
        AVLNode* B = x->right;
        x->right = y;
        y->left = B;
        updateHeight(y);
        updateHeight(x);
        return x;  // новый корень
    }

    // Левый поворот (RR case)
    AVLNode* rotateLeft(AVLNode* x) {
        AVLNode* y = x->right;
        AVLNode* B = y->left;
        y->left = x;
        x->right = B;
        updateHeight(x);
        updateHeight(y);
        return y;
    }

    // Балансировка узла
    AVLNode* balance(AVLNode* node) {
        updateHeight(node);
        int bf = balanceFactor(node);

        // LL: левое поддерево тяжелее, вставка в его левое
        if (bf > 1 && balanceFactor(node->left) >= 0)
            return rotateRight(node);

        // RR: правое поддерево тяжелее, вставка в его правое
        if (bf < -1 && balanceFactor(node->right) <= 0)
            return rotateLeft(node);

        // LR: левое тяжелее, но вставка в его правое
        if (bf > 1 && balanceFactor(node->left) < 0) {
            node->left = rotateLeft(node->left);
            return rotateRight(node);
        }

        // RL: правое тяжелее, но вставка в его левое
        if (bf < -1 && balanceFactor(node->right) > 0) {
            node->right = rotateRight(node->right);
            return rotateLeft(node);
        }

        return node;  // уже сбалансировано
    }

    AVLNode* findMin(AVLNode* node) {
        while (node->left) node = node->left;
        return node;
    }

public:
    AVLNode* root = nullptr;

    AVLNode* insert(AVLNode* node, int val) {
        if (!node) return new AVLNode(val);
        if (val < node->val)      node->left = insert(node->left, val);
        else if (val > node->val) node->right = insert(node->right, val);
        else return node;  // дубликат

        return balance(node);  // балансируем при возврате по стеку вызовов!
    }

    AVLNode* remove(AVLNode* node, int val) {
        if (!node) return nullptr;
        if (val < node->val)      node->left = remove(node->left, val);
        else if (val > node->val) node->right = remove(node->right, val);
        else {
            if (!node->left || !node->right) {
                AVLNode* tmp = node->left ? node->left : node->right;
                delete node;
                return tmp;
            }
            AVLNode* succ = findMin(node->right);
            node->val = succ->val;
            node->right = remove(node->right, succ->val);
        }
        return balance(node);
    }

    void insert(int val) { root = insert(root, val); }
    void remove(int val) { root = remove(root, val); }

    void preorder(AVLNode* node) {
        if (!node) return;
        cout << node->val << " ";
        preorder(node->left);
        preorder(node->right);
    }
};

int main() {
    AVLTree avl;
    // Вставляем в порядке, который бы создал вырожденное BST
    for (int x : {10, 20, 30, 40, 50, 25}) {
        avl.insert(x);
    }

    cout << "Preorder (показывает структуру): ";
    avl.preorder(avl.root);  // 30 20 10 25 40 50
    cout << endl;
    // Дерево само сбалансировалось! Корень стал 30.

    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

// ═══ Рекурсивные обходы ═══
void preorder(TreeNode* node) {
    if (!node) return;
    cout << node->val << " ";  // 1) корень
    preorder(node->left);       // 2) лево
    preorder(node->right);      // 3) право
}

void inorder(TreeNode* node) {
    if (!node) return;
    inorder(node->left);        // 1) лево
    cout << node->val << " ";  // 2) корень
    inorder(node->right);       // 3) право
}

void postorder(TreeNode* node) {
    if (!node) return;
    postorder(node->left);      // 1) лево
    postorder(node->right);     // 2) право
    cout << node->val << " ";  // 3) корень
}

// ═══ Level-order (BFS) ═══
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> result;
    if (!root) return result;

    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        int size = q.size();  // узлы на текущем уровне
        vector<int> level;
        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front(); q.pop();
            level.push_back(node->val);
            if (node->left)  q.push(node->left);
            if (node->right) q.push(node->right);
        }
        result.push_back(level);
    }
    return result;
}

// ═══ Итеративный inorder (без рекурсии, на стеке) ═══
vector<int> inorderIterative(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> st;
    TreeNode* curr = root;

    while (curr || !st.empty()) {
        while (curr) {           // идём максимально влево
            st.push(curr);
            curr = curr->left;
        }
        curr = st.top(); st.pop();
        result.push_back(curr->val);
        curr = curr->right;
    }
    return result;
}

int main() {
    //       1
    //      / \
    //     2   3
    //    / \   \
    //   4   5   6
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(6);

    cout << "Preorder:  "; preorder(root);  cout << endl;  // 1 2 4 5 3 6
    cout << "Inorder:   "; inorder(root);   cout << endl;  // 4 2 5 1 3 6
    cout << "Postorder: "; postorder(root); cout << endl;  // 4 5 2 6 3 1

    cout << "Level-order: ";
    auto levels = levelOrder(root);
    for (auto& lvl : levels) {
        cout << "[";
        for (int x : lvl) cout << x << " ";
        cout << "] ";
    }
    cout << endl;  // [1] [2 3] [4 5 6]

    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

class SegTree {
    int n;
    vector<long long> tree, lazy;

    // Вспомогательная: 1-based индексация (дети 2v и 2v+1)
    void build(const vector<int>& arr, int v, int tl, int tr) {
        if (tl == tr) {
            tree[v] = arr[tl];
            return;
        }
        int tm = (tl + tr) / 2;
        build(arr, 2*v, tl, tm);
        build(arr, 2*v+1, tm+1, tr);
        tree[v] = tree[2*v] + tree[2*v+1];
    }

    // Проталкивание отложенных операций детям
    void push(int v, int tl, int tr) {
        if (lazy[v] != 0) {
            int tm = (tl + tr) / 2;
            apply(2*v, tl, tm, lazy[v]);
            apply(2*v+1, tm+1, tr, lazy[v]);
            lazy[v] = 0;
        }
    }

    void apply(int v, int tl, int tr, long long val) {
        tree[v] += val * (tr - tl + 1);
        lazy[v] += val;
    }

    // Запрос суммы на [l, r]
    long long query(int v, int tl, int tr, int l, int r) {
        if (l > tr || r < tl) return 0;          // вне отрезка
        if (l <= tl && tr <= r) return tree[v];   // полностью внутри
        
        push(v, tl, tr); // Обязательно проталкиваем lazy перед спуском
        
        int tm = (tl + tr) / 2;
        return query(2*v, tl, tm, l, r) + query(2*v+1, tm+1, tr, l, r);
    }

    // Обновление: прибавить val ко всем элементам на [l, r]
    void update(int v, int tl, int tr, int l, int r, long long val) {
        if (l > tr || r < tl) return;
        if (l <= tl && tr <= r) {
            apply(v, tl, tr, val);
            return;
        }
        push(v, tl, tr);
        int tm = (tl + tr) / 2;
        update(2*v, tl, tm, l, r, val);
        update(2*v+1, tm+1, tr, l, r, val);
        tree[v] = tree[2*v] + tree[2*v+1];
    }

    // Точечное обновление: arr[pos] = val (если без lazy)
    void pointUpdate(int v, int tl, int tr, int pos, int val) {
        if (tl == tr) { tree[v] = val; return; }
        int tm = (tl + tr) / 2;
        if (pos <= tm) pointUpdate(2*v, tl, tm, pos, val);
        else            pointUpdate(2*v+1, tm+1, tr, pos, val);
        tree[v] = tree[2*v] + tree[2*v+1];
    }

public:
    SegTree(const vector<int>& arr) {
        n = arr.size();
        tree.assign(4 * n, 0);
        lazy.assign(4 * n, 0);
        build(arr, 1, 0, n - 1);
    }

    long long query(int l, int r) { return query(1, 0, n-1, l, r); }
    void update(int l, int r, long long val) { update(1, 0, n-1, l, r, val); }
    void pointUpdate(int pos, int val) { pointUpdate(1, 0, n-1, pos, val); }
};

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11};
    SegTree st(arr);

    cout << "Sum [1,4]: " << st.query(1, 4) << endl;  // 3+5+7+9 = 24
    
    st.pointUpdate(2, 10);  // arr[2] = 10 (было 5)
    cout << "After point update, Sum [1,4]: " << st.query(1, 4) << endl;  // 3+10+7+9 = 29

    st.update(0, 3, 2);  // прибавить 2 ко всем на [0,3] (Lazy Propagation)
    cout << "After range update +2 on [0,3], Sum [0,5]: "
         << st.query(0, 5) << endl;  // (1+2)+(3+2)+(10+2)+(7+2)+9+11 = 49

    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class BIT {
    vector<long long> tree;
    int n;

public:
    BIT(int n) : n(n), tree(n + 1, 0) {}

    BIT(const vector<int>& arr) : n(arr.size()), tree(arr.size() + 1, 0) {
        for (int i = 0; i < n; i++)
            update(i, arr[i]);
    }

    // Прибавить delta к arr[idx]
    void update(int idx, long long delta) {
        idx++;  // BIT работает в 1-индексации
        while (idx <= n) {
            tree[idx] += delta;
            idx += idx & (-idx);  // переход к родителю (добавляем младший бит)
        }
    }

    // Сумма arr[0..idx]
    long long prefixSum(int idx) {
        idx++;
        long long sum = 0;
        while (idx > 0) {
            sum += tree[idx];
            idx -= idx & (-idx);  // переход к предыдущему блоку (убираем младший бит)
        }
        return sum;
    }

    // Сумма arr[l..r]
    long long rangeSum(int l, int r) {
        return prefixSum(r) - (l > 0 ? prefixSum(l - 1) : 0);
    }
};

// ═══ Задача: Подсчёт инверсий за O(n log n) ═══
long long countInversions(vector<int>& arr) {
    int n = arr.size();
    // Координатная компрессия (чтобы индексы BIT не были гигантскими)
    vector<int> sorted_arr = arr;
    sort(sorted_arr.begin(), sorted_arr.end());
    sorted_arr.erase(unique(sorted_arr.begin(), sorted_arr.end()), sorted_arr.end());

    BIT bit(sorted_arr.size());
    long long inv = 0;

    // Идем справа налево
    for (int i = n - 1; i >= 0; i--) {
        int compressed = lower_bound(sorted_arr.begin(), sorted_arr.end(), arr[i])
                         - sorted_arr.begin();
        inv += bit.prefixSum(compressed - 1);  // сколько меньших элементов уже встретили справа
        bit.update(compressed, 1);             // добавляем текущий элемент в BIT
    }
    return inv;
}

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11};
    BIT bit(arr);

    cout << "Sum [1,4]: " << bit.rangeSum(1, 4) << endl;  // 3+5+7+9 = 24
    
    bit.update(2, 5);  // arr[2] += 5 → arr[2] = 10
    cout << "After +5 at idx 2, Sum [1,4]: " << bit.rangeSum(1, 4) << endl;  // 29

    // Инверсии
    vector<int> arr2 = {5, 3, 2, 4, 1};
    cout << "Inversions: " << countInversions(arr2) << endl;  // 8

    return 0;
}

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

class LCA {
    int n, LOG;
    vector<vector<int>> adj;  // граф (дерево)
    vector<vector<int>> up;   // up[v][k] = предок v на расстоянии 2^k
    vector<int> depth;

    void dfs(int v, int parent, int d) {
        depth[v] = d;
        up[v][0] = parent; // 2^0 = 1 шаг (непосредственный родитель)
        
        for (int k = 1; k < LOG; k++)
            up[v][k] = up[up[v][k-1]][k-1];  // 2^k = 2^(k-1) + 2^(k-1)

        for (int u : adj[v])
            if (u != parent)
                dfs(u, v, d + 1);
    }

public:
    LCA(int n, const vector<vector<int>>& adj, int root = 0)
        : n(n), adj(adj), LOG(log2(n) + 2), depth(n) {
        up.assign(n, vector<int>(LOG, 0));
        dfs(root, root, 0);
    }

    int query(int u, int v) {
        if (depth[u] < depth[v]) swap(u, v); // Пусть u всегда глубже

        // 1. Поднимаем u до уровня v
        int diff = depth[u] - depth[v];
        for (int k = 0; k < LOG; k++)
            if ((diff >> k) & 1)
                u = up[u][k];

        if (u == v) return u; // Если v оказался предком u

        // 2. Поднимаем обоих, пока предки не совпадут
        for (int k = LOG - 1; k >= 0; k--) {
            // Прыгаем, только если предки РАЗНЫЕ (ищем уровень прямо под LCA)
            if (up[u][k] != up[v][k]) {
                u = up[u][k];
                v = up[v][k];
            }
        }
        return up[u][0]; // Возвращаем родителя
    }

    // Расстояние между вершинами
    int dist(int u, int v) {
        return depth[u] + depth[v] - 2 * depth[query(u, v)];
    }
};

int main() {
    //       0
    //      / \
    //     1   2
    //    / \   \
    //   3   4   5
    //  /
    // 6
    int n = 7;
    vector<vector<int>> adj(n);
    auto addEdge = [&](int u, int v) { adj[u].push_back(v); adj[v].push_back(u); };
    addEdge(0, 1); addEdge(0, 2);
    addEdge(1, 3); addEdge(1, 4);
    addEdge(2, 5); addEdge(3, 6);

    LCA lca(n, adj);

    cout << "LCA(3, 4) = " << lca.query(3, 4) << endl;  // 1
    cout << "LCA(6, 5) = " << lca.query(6, 5) << endl;  // 0
    cout << "LCA(6, 4) = " << lca.query(6, 4) << endl;  // 1
    cout << "LCA(3, 3) = " << lca.query(3, 3) << endl;  // 3

    // Расстояние в дереве!
    cout << "Dist(6, 5) = " << lca.dist(6, 5) << endl;  // 4
    cout << "Dist(3, 4) = " << lca.dist(3, 4) << endl;  // 2

    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int V = 5, E = 6;
    // Граф:  0—1, 0—4, 1—2, 1—3, 1—4, 2—3

    // ═══ 1. Список смежности (самый частый) ═══
    vector<vector<int>> adj(V);
    auto addEdge = [&](int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);  // для неориентированного
    };
    addEdge(0,1); addEdge(0,4); addEdge(1,2);
    addEdge(1,3); addEdge(1,4); addEdge(2,3);

    cout << "Adjacency List:" << endl;
    for (int i = 0; i < V; i++) {
        cout << i << ": ";
        for (int v : adj[i]) cout << v << " ";
        cout << endl;
    }

    // ═══ 2. Список смежности (взвешенный) ═══
    vector<vector<pair<int,int>>> wadj(V);  // {сосед, вес}
    wadj[0].push_back({1, 10});
    wadj[0].push_back({4, 5});
    wadj[1].push_back({2, 3});

    // ═══ 3. Матрица смежности ═══
    vector<vector<int>> matrix(V, vector<int>(V, 0));
    matrix[0][1] = matrix[1][0] = 1;
    matrix[0][4] = matrix[4][0] = 1;
    matrix[1][2] = matrix[2][1] = 1;
    // Для взвешенного: matrix[u][v] = weight

    // ═══ 4. Список рёбер ═══
    struct Edge { int u, v, w; };
    vector<Edge> edges = {{0,1,10},{0,4,5},{1,2,3},{1,3,7},{1,4,2},{2,3,1}};

    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// ═══ Базовый BFS ═══
void bfs(const vector<vector<int>>& adj, int start) {
    int n = adj.size();
    vector<bool> visited(n, false);
    queue<int> q;

    visited[start] = true;
    q.push(start);

    while (!q.empty()) {
        int v = q.front(); q.pop();
        cout << v << " ";

        for (int u : adj[v]) {
            if (!visited[u]) {
                visited[u] = true;
                q.push(u);
            }
        }
    }
}

// ═══ BFS с кратчайшим путём ═══
vector<int> bfsShortestPath(const vector<vector<int>>& adj, int start) {
    int n = adj.size();
    vector<int> dist(n, -1);
    vector<int> parent(n, -1);
    queue<int> q;

    dist[start] = 0;
    q.push(start);

    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (int u : adj[v]) {
            if (dist[u] == -1) {
                dist[u] = dist[v] + 1;
                parent[u] = v;
                q.push(u);
            }
        }
    }
    return dist;
}

// Восстановление пути
vector<int> restorePath(const vector<int>& parent, int target) {
    vector<int> path;
    for (int v = target; v != -1; v = parent[v])
        path.push_back(v);
    reverse(path.begin(), path.end());
    return path;
}

// ═══ Задача: BFS на сетке (лабиринт) ═══
int bfsGrid(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    if (grid[0][0] == 1 || grid[m-1][n-1] == 1) return -1;

    int dx[] = {0,0,1,-1};
    int dy[] = {1,-1,0,0};

    queue<pair<int,int>> q;
    q.push({0, 0});
    grid[0][0] = 1;  // помечаем как посещённый
    int steps = 0;

    while (!q.empty()) {
        int sz = q.size();
        for (int i = 0; i < sz; i++) {
            auto [x, y] = q.front(); q.pop();
            if (x == m-1 && y == n-1) return steps;

            for (int d = 0; d < 4; d++) {
                int nx = x + dx[d], ny = y + dy[d];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 0) {
                    grid[nx][ny] = 1;
                    q.push({nx, ny});
                }
            }
        }
        steps++;
    }
    return -1;  // недостижимо
}

// ═══ Задача: Проверка двудольности (bipartite) ═══
bool isBipartite(const vector<vector<int>>& adj) {
    int n = adj.size();
    vector<int> color(n, -1);  // -1 = не раскрашен

    for (int start = 0; start < n; start++) {
        if (color[start] != -1) continue;
        queue<int> q;
        q.push(start);
        color[start] = 0;

        while (!q.empty()) {
            int v = q.front(); q.pop();
            for (int u : adj[v]) {
                if (color[u] == -1) {
                    color[u] = 1 - color[v];  // другой цвет
                    q.push(u);
                } else if (color[u] == color[v]) {
                    return false;  // конфликт — не двудольный
                }
            }
        }
    }
    return true;
}

int main() {
    // Граф: 0—1, 0—2, 1—3, 2—4, 3—4, 3—5
    int n = 6;
    vector<vector<int>> adj(n);
    adj[0] = {1,2}; adj[1] = {0,3}; adj[2] = {0,4};
    adj[3] = {1,4,5}; adj[4] = {2,3}; adj[5] = {3};

    cout << "BFS: ";
    bfs(adj, 0);  // 0 1 2 3 4 5
    cout << endl;

    auto dist = bfsShortestPath(adj, 0);
    cout << "Distance 0→5: " << dist[5] << endl;  // 3

    // Лабиринт
    vector<vector<int>> grid = {
        {0,0,0},
        {1,1,0},
        {0,0,0}
    };
    cout << "Grid shortest path: " << bfsGrid(grid) << endl;  // 4

    return 0;
}

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

// ═══ Рекурсивный DFS ═══
void dfsRecursive(const vector<vector<int>>& adj, int v, vector<bool>& visited) {
    visited[v] = true;
    cout << v << " ";
    for (int u : adj[v]) {
        if (!visited[u])
            dfsRecursive(adj, u, visited);
    }
}

// ═══ Итеративный DFS ═══
void dfsIterative(const vector<vector<int>>& adj, int start) {
    int n = adj.size();
    vector<bool> visited(n, false);
    stack<int> st;
    st.push(start);

    while (!st.empty()) {
        int v = st.top(); st.pop();
        if (visited[v]) continue;
        visited[v] = true;
        cout << v << " ";

        // В обратном порядке чтобы обрабатывать в прямом
        for (int i = adj[v].size() - 1; i >= 0; i--)
            if (!visited[adj[v][i]])
                st.push(adj[v][i]);
    }
}

// ═══ Подсчёт компонент связности ═══
int countComponents(const vector<vector<int>>& adj) {
    int n = adj.size(), count = 0;
    vector<bool> visited(n, false);
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfsRecursive(adj, i, visited);
            count++;
        }
    }
    return count;
}

// ═══ Обнаружение цикла в ориентированном графе ═══
// Состояния: 0=белый, 1=серый (в обработке), 2=чёрный (завершён)
bool hasCycleDFS(const vector<vector<int>>& adj, int v, vector<int>& state) {
    state[v] = 1;  // серый — начали обрабатывать
    for (int u : adj[v]) {
        if (state[u] == 1) return true;   // встретили серого → цикл!
        if (state[u] == 0 && hasCycleDFS(adj, u, state))
            return true;
    }
    state[v] = 2;  // чёрный — полностью обработан
    return false;
}

bool hasCycleDirected(const vector<vector<int>>& adj) {
    int n = adj.size();
    vector<int> state(n, 0);
    for (int i = 0; i < n; i++)
        if (state[i] == 0 && hasCycleDFS(adj, i, state))
            return true;
    return false;
}

// ═══ Обнаружение цикла в неориентированном графе ═══
bool hasCycleUndirected(const vector<vector<int>>& adj, int v, int parent,
                         vector<bool>& visited) {
    visited[v] = true;
    for (int u : adj[v]) {
        if (!visited[u]) {
            if (hasCycleUndirected(adj, u, v, visited)) return true;
        } else if (u != parent) {
            return true;  // посещённый сосед ≠ родитель → цикл
        }
    }
    return false;
}

// ═══ DFS с временами входа/выхода ═══
int timer_val = 0;
void dfsTimestamps(const vector<vector<int>>& adj, int v,
                   vector<bool>& visited, vector<int>& tin, vector<int>& tout) {
    visited[v] = true;
    tin[v] = timer_val++;
    for (int u : adj[v])
        if (!visited[u])
            dfsTimestamps(adj, u, visited, tin, tout);
    tout[v] = timer_val++;
}

int main() {
    // Неориентированный граф
    int n = 6;
    vector<vector<int>> adj(n);
    adj[0] = {1,2}; adj[1] = {0,3}; adj[2] = {0,4};
    adj[3] = {1,5}; adj[4] = {2}; adj[5] = {3};

    cout << "DFS recursive: ";
    vector<bool> vis(n, false);
    dfsRecursive(adj, 0, vis);  // 0 1 3 5 2 4
    cout << endl;

    cout << "DFS iterative: ";
    dfsIterative(adj, 0);
    cout << endl;

    // Ориентированный граф с циклом: 0→1→2→0
    vector<vector<int>> dag = {{1},{2},{0}};
    cout << "Has cycle (directed): " << hasCycleDirected(dag) << endl;  // 1

    // DAG (без цикла): 0→1→2, 0→2
    vector<vector<int>> dag2 = {{1,2},{2},{}};
    cout << "Has cycle (DAG): " << hasCycleDirected(dag2) << endl;  // 0

    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

typedef pair<int,int> pii;  // {вес, вершина}

struct DijkstraResult {
    vector<long long> dist;
    vector<int> parent;
};

DijkstraResult dijkstra(const vector<vector<pii>>& adj, int start) {
    int n = adj.size();
    vector<long long> dist(n, LLONG_MAX);
    vector<int> parent(n, -1);
    // min-heap: {расстояние, вершина}
    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;

    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [d, v] = pq.top(); pq.pop();

        if (d > dist[v]) continue;  // устаревшая запись — пропускаем

        for (auto [u, w] : adj[v]) {
            if (dist[v] + w < dist[u]) {          // релаксация
                dist[u] = dist[v] + w;
                parent[u] = v;
                pq.push({dist[u], u});
            }
        }
    }
    return {dist, parent};
}

// Восстановление пути
vector<int> restorePath(const vector<int>& parent, int target) {
    vector<int> path;
    for (int v = target; v != -1; v = parent[v])
        path.push_back(v);
    reverse(path.begin(), path.end());
    return path;
}

int main() {
    // Граф: 0→1(4), 0→2(2), 1→3(5), 1→4(7), 2→1(1), 2→3(7), 3→4(1)
    int n = 5;
    vector<vector<pii>> adj(n);
    adj[0] = {{1,4},{2,2}};
    adj[1] = {{3,5},{4,7}};
    adj[2] = {{1,1},{3,7}};
    adj[3] = {{4,1}};

    auto [dist, parent] = dijkstra(adj, 0);

    cout << "Distances from 0:" << endl;
    for (int i = 0; i < n; i++)
        cout << "  0 → " << i << " = " << dist[i] << endl;
    // 0→0=0, 0→1=3, 0→2=2, 0→3=8, 0→4=9

    auto path = restorePath(parent, 4);
    cout << "Path 0→4: ";
    for (int v : path) cout << v << " ";  // 0 2 1 3 4
    cout << endl;

    return 0;
}

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

struct Edge { int u, v, w; };

// Возвращает dist[] или пустой вектор если есть отрицательный цикл
vector<long long> bellmanFord(int n, const vector<Edge>& edges, int start) {
    vector<long long> dist(n, LLONG_MAX);
    dist[start] = 0;

    // V-1 итераций
    for (int i = 0; i < n - 1; i++) {
        bool updated = false;
        for (auto& [u, v, w] : edges) {
            if (dist[u] != LLONG_MAX && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                updated = true;
            }
        }
        if (!updated) break;  // раннее завершение (оптимизация)
    }

    // Проверка отрицательного цикла (V-я итерация)
    for (auto& [u, v, w] : edges) {
        if (dist[u] != LLONG_MAX && dist[u] + w < dist[v]) {
            cout << "NEGATIVE CYCLE DETECTED!" << endl;
            return {};  // есть отрицательный цикл
        }
    }

    return dist;
}

int main() {
    int n = 5;
    vector<Edge> edges = {
        {0,1,6}, {0,2,7}, {1,2,8}, {1,3,5},
        {1,4,-4}, {2,3,-3}, {2,4,9}, {3,1,-2}, {4,0,2}, {4,3,7}
    };

    auto dist = bellmanFord(n, edges, 0);
    if (!dist.empty()) {
        for (int i = 0; i < n; i++)
            cout << "0 → " << i << " = " << dist[i] << endl;
        // 0→0=0, 0→1=2, 0→2=7, 0→3=4, 0→4=-2
    }

    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

const long long INF = 1e18;

void floydWarshall(vector<vector<long long>>& dist) {
    int n = dist.size();

    // Ключевая тройка циклов — k ПЕРВЫЙ (промежуточные вершины)
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (dist[i][k] < INF && dist[k][j] < INF)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}

// Проверка отрицательного цикла: dist[i][i] < 0
bool hasNegativeCycle(const vector<vector<long long>>& dist) {
    for (int i = 0; i < (int)dist.size(); i++)
        if (dist[i][i] < 0) return true;
    return false;
}

int main() {
    int n = 4;
    vector<vector<long long>> dist(n, vector<long long>(n, INF));
    for (int i = 0; i < n; i++) dist[i][i] = 0;

    // Рёбра: 0→1(3), 0→3(7), 1→0(8), 1→2(2), 2→0(5), 2→3(1), 3→0(2)
    dist[0][1]=3; dist[0][3]=7; dist[1][0]=8; dist[1][2]=2;
    dist[2][0]=5; dist[2][3]=1; dist[3][0]=2;

    floydWarshall(dist);

    cout << "All-pairs shortest paths:" << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dist[i][j] >= INF) cout << "INF ";
            else cout << dist[i][j] << "   ";
        }
        cout << endl;
    }

    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class DSU {
    vector<int> p, rank_;
public:
    DSU(int n) : p(n), rank_(n, 0) { 
        for(int i=0; i<n; i++) p[i] = i; 
    }
    int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (rank_[a] < rank_[b]) swap(a, b);
        p[b] = a;
        if (rank_[a] == rank_[b]) rank_[a]++;
        return true;
    }
};

struct Edge {
    int u, v, w;
    bool operator<(const Edge& o) const { return w < o.w; }
};

pair<long long, vector<Edge>> kruskal(int n, vector<Edge>& edges) {
    sort(edges.begin(), edges.end());  // сортируем по весу
    DSU dsu(n);

    long long totalWeight = 0;
    vector<Edge> mstEdges;

    for (auto& e : edges) {
        if (dsu.unite(e.u, e.v)) {      // разные компоненты?
            totalWeight += e.w;
            mstEdges.push_back(e);
            if ((int)mstEdges.size() == n - 1) break;  // MST готово
        }
    }
    return {totalWeight, mstEdges};
}

int main() {
    int n = 4;
    vector<Edge> edges = {{0,1,4},{0,3,3},{1,2,1},{1,3,5},{2,3,2}};

    auto [weight, mst] = kruskal(n, edges);
    cout << "MST weight: " << weight << endl;  // 6
    cout << "MST edges:" << endl;
    for (auto& e : mst)
        cout << "  " << e.u << " — " << e.v << " (" << e.w << ")" << endl;

    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

typedef pair<int,int> pii;

long long prim(const vector<vector<pii>>& adj) {
    int n = adj.size();
    vector<bool> inMST(n, false);
    // min-heap: {вес_ребра, вершина}
    priority_queue<pii, vector<pii>, greater<pii>> pq;

    pq.push({0, 0});  // начинаем с вершины 0
    long long totalWeight = 0;
    int edgesAdded = 0;

    while (!pq.empty() && edgesAdded < n) {
        auto [w, v] = pq.top(); pq.pop();

        if (inMST[v]) continue;  // уже в MST
        inMST[v] = true;
        totalWeight += w;
        edgesAdded++;

        for (auto [u, weight] : adj[v]) {
            if (!inMST[u])
                pq.push({weight, u});
        }
    }
    return totalWeight;
}

int main() {
    int n = 4;
    vector<vector<pii>> adj(n);
    auto add = [&](int u, int v, int w) {
        adj[u].push_back({v,w}); adj[v].push_back({u,w});
    };
    add(0,1,4); add(0,3,3); add(1,2,1); add(1,3,5); add(2,3,2);

    cout << "MST weight (Prim): " << prim(adj) << endl;  // 6

    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

// ═══ Метод 1: Kahn (BFS по входящим степеням) ═══
vector<int> topologicalSortKahn(int n, const vector<vector<int>>& adj) {
    vector<int> inDegree(n, 0);
    for (int v = 0; v < n; v++)
        for (int u : adj[v])
            inDegree[u]++;

    queue<int> q;
    for (int i = 0; i < n; i++)
        if (inDegree[i] == 0)
            q.push(i);  // вершины без зависимостей

    vector<int> order;
    while (!q.empty()) {
        int v = q.front(); q.pop();
        order.push_back(v);
        for (int u : adj[v]) {
            inDegree[u]--;
            if (inDegree[u] == 0)
                q.push(u);
        }
    }

    // Если order.size() < n → есть цикл!
    if ((int)order.size() != n) return {};  // не DAG
    return order;
}

// ═══ Метод 2: DFS ═══
void topoSortDFS(int v, const vector<vector<int>>& adj,
                 vector<bool>& visited, vector<int>& order) {
    visited[v] = true;
    for (int u : adj[v])
        if (!visited[u])
            topoSortDFS(u, adj, visited, order);
    order.push_back(v);  // добавляем ПОСЛЕ обработки всех потомков (postorder)
}

vector<int> topologicalSortDFS(int n, const vector<vector<int>>& adj) {
    vector<bool> visited(n, false);
    vector<int> order;
    for (int i = 0; i < n; i++)
        if (!visited[i])
            topoSortDFS(i, adj, visited, order);
    reverse(order.begin(), order.end());  // переворачиваем результат
    return order;
}

int main() {
    // 5→0, 5→2, 4→0, 4→1, 2→3, 3→1
    int n = 6;
    vector<vector<int>> adj(n);
    adj[5] = {0, 2}; adj[4] = {0, 1}; adj[2] = {3}; adj[3] = {1};

    auto order1 = topologicalSortDFS(n, adj);
    cout << "Topo (DFS):  ";
    for (int v : order1) cout << v << " ";  // 5 4 2 3 1 0
    cout << endl;

    auto order2 = topologicalSortKahn(n, adj);
    cout << "Topo (Kahn): ";
    for (int v : order2) cout << v << " ";  // 4 5 0 2 3 1 (другой порядок, тоже валидный)
    cout << endl;

    return 0;
}

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

class Kosaraju {
    int n;
    vector<vector<int>> adj, radj;  // граф и транспонированный
    vector<bool> visited;
    stack<int> order;

    void dfs1(int v) {
        visited[v] = true;
        for (int u : adj[v])
            if (!visited[u]) dfs1(u);
        order.push(v);  // запоминаем порядок завершения
    }

    void dfs2(int v, vector<int>& component) {
        visited[v] = true;
        component.push_back(v);
        for (int u : radj[v])
            if (!visited[u]) dfs2(u, component);
    }

public:
    Kosaraju(int n) : n(n), adj(n), radj(n) {}

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        radj[v].push_back(u);  // транспонированный
    }

    vector<vector<int>> findSCCs() {
        // Шаг 1: DFS по прямому графу, запоминаем порядок
        visited.assign(n, false);
        for (int i = 0; i < n; i++)
            if (!visited[i]) dfs1(i);

        // Шаг 2: DFS по транспонированному в обратном порядке
        visited.assign(n, false);
        vector<vector<int>> sccs;

        while (!order.empty()) {
            int v = order.top(); order.pop();
            if (!visited[v]) {
                vector<int> component;
                dfs2(v, component);
                sccs.push_back(component);
            }
        }
        return sccs;
    }
};

int main() {
    Kosaraju k(8);
    k.addEdge(0,1); k.addEdge(1,2); k.addEdge(2,0);  // SCC: {0,1,2}
    k.addEdge(2,3); k.addEdge(3,4); k.addEdge(4,3);  // SCC: {3,4}
    k.addEdge(4,5); k.addEdge(5,6); k.addEdge(6,5);  // SCC: {5,6}
    k.addEdge(6,7);                                     // SCC: {7}

    auto sccs = k.findSCCs();
    cout << "SCCs (" << sccs.size() << " components):" << endl;
    for (auto& scc : sccs) {
        cout << "  {";
        for (int v : scc) cout << v << " ";
        cout << "}" << endl;
    }

    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

class BridgesAndAP {
    int n, timer = 0;
    vector<vector<int>> adj;
    vector<int> tin, low;
    vector<bool> visited;
    vector<pair<int,int>> bridges;
    vector<bool> isAP;

    void dfs(int v, int parent) {
        visited[v] = true;
        tin[v] = low[v] = timer++;
        int children = 0;

        for (int u : adj[v]) {
            if (u == parent) continue;

            if (visited[u]) {
                low[v] = min(low[v], tin[u]);  // обратное ребро
            } else {
                dfs(u, v);
                low[v] = min(low[v], low[u]);
                children++;

                // Мост: нет обратного ребра из поддерева u выше v
                if (low[u] > tin[v])
                    bridges.push_back({v, u});

                // Точка сочленения (не корень)
                if (parent != -1 && low[u] >= tin[v])
                    isAP[v] = true;
            }
        }
        // Точка сочленения (корень дерева DFS с ≥2 независимыми поддеревьями)
        if (parent == -1 && children > 1)
            isAP[v] = true;
    }

public:
    BridgesAndAP(int n) : n(n), adj(n), tin(n), low(n), visited(n, false), isAP(n, false) {}

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    void find() {
        for (int i = 0; i < n; i++)
            if (!visited[i])
                dfs(i, -1);
    }

    void printBridges() {
        cout << "Bridges: ";
        for (auto [u, v] : bridges)
            cout << u << "-" << v << " ";
        cout << endl;
    }

    void printAPs() {
        cout << "Articulation Points: ";
        for (int i = 0; i < n; i++)
            if (isAP[i]) cout << i << " ";
        cout << endl;
    }
};

int main() {
    //   0 — 1 — 2
    //   |       |
    //   3       4
    //   |
    //   5 — 6
    BridgesAndAP g(7);
    g.addEdge(0,1); g.addEdge(1,2); g.addEdge(0,3);
    g.addEdge(2,4); g.addEdge(3,5); g.addEdge(5,6);

    g.find();
    g.printBridges();  // 0-1 1-2 0-3 2-4 3-5 5-6 (все рёбра — мосты в дереве)
    g.printAPs();       // 0 1 2 3 5

    return 0;
}

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

// Эйлеров цикл/путь для ориентированного графа (алгоритм Хирхольцера)
vector<int> eulerPath(int n, vector<vector<int>>& adj) {
    // Определяем стартовую вершину
    vector<int> inDeg(n, 0), outDeg(n, 0);
    for (int v = 0; v < n; v++) {
        outDeg[v] = adj[v].size();
        for (int u : adj[v]) inDeg[u]++;
    }

    int start = 0;
    for (int i = 0; i < n; i++)
        if (outDeg[i] - inDeg[i] == 1) { start = i; break; }

    // Алгоритм Хирхольцера
    stack<int> st;
    vector<int> path;
    vector<int> ptr(n, 0);  // указатель на следующее ребро (оптимизация удаления)

    st.push(start);
    while (!st.empty()) {
        int v = st.top();
        if (ptr[v] < (int)adj[v].size()) {
            st.push(adj[v][ptr[v]++]);  // идём и "сжигаем" ребро
        } else {
            path.push_back(v);  // тупик — пишем в ответ
            st.pop();
        }
    }
    reverse(path.begin(), path.end());
    return path;
}

int main() {
    // Граф: 0→1→2→0, 0→3→4→0
    int n = 5;
    vector<vector<int>> adj(n);
    adj[0] = {1, 3}; adj[1] = {2}; adj[2] = {0};
    adj[3] = {4}; adj[4] = {0};

    auto path = eulerPath(n, adj);
    cout << "Euler circuit: ";
    for (int v : path) cout << v << " ";
    // 0 1 2 0 3 4 0
    cout << endl;

    return 0;
}

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

// 1. Наивная рекурсия — O(2^n) ❌ (Будет TLE для n > 40)
long long fibNaive(int n) {
    if (n <= 1) return n;
    return fibNaive(n - 1) + fibNaive(n - 2);
}

// 2. Top-down (мемоизация) — O(n), O(n) память
unordered_map<int, long long> memo;
long long fibMemo(int n) {
    if (n <= 1) return n;
    if (memo.count(n)) return memo[n];
    return memo[n] = fibMemo(n - 1) + fibMemo(n - 2);
}

// 3. Bottom-up (таблица) — O(n), O(n) память
long long fibDP(int n) {
    if (n <= 1) return n;
    vector<long long> dp(n + 1);
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

// 4. Оптимальный — O(n), O(1) память ✅
long long fibOptimal(int n) {
    if (n <= 1) return n;
    long long a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        long long c = a + b;
        a = b;
        b = c;
    }
    return b;
}

int main() {
    for (int n : {0, 1, 5, 10, 45}) {
        cout << "F(" << n << ") = " << fibOptimal(n) << endl;
    }
    // F(0)=0, F(1)=1, F(5)=5, F(10)=55, F(45)=1134903170
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

// ═══ 2D версия ═══
int knapsack2D(int W, vector<int>& wt, vector<int>& val) {
    int n = wt.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            dp[i][w] = dp[i-1][w];  // не берём предмет i
            if (wt[i-1] <= w)
                dp[i][w] = max(dp[i][w], dp[i-1][w - wt[i-1]] + val[i-1]);  // берём
        }
    }
    return dp[n][W];
}

// ═══ 1D оптимизация (O(W) памяти) ═══
int knapsack1D(int W, vector<int>& wt, vector<int>& val) {
    int n = wt.size();
    vector<int> dp(W + 1, 0);

    for (int i = 0; i < n; i++) {
        // Идём СПРАВА НАЛЕВО! (чтобы не использовать предмет дважды)
        for (int w = W; w >= wt[i]; w--) {
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
        }
    }
    return dp[W];
}

// ═══ Восстановление набора предметов ═══
vector<int> knapsackItems(int W, vector<int>& wt, vector<int>& val) {
    int n = wt.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    for (int i = 1; i <= n; i++)
        for (int w = 0; w <= W; w++) {
            dp[i][w] = dp[i-1][w];
            if (wt[i-1] <= w)
                dp[i][w] = max(dp[i][w], dp[i-1][w - wt[i-1]] + val[i-1]);
        }

    // Обратный ход
    vector<int> items;
    int w = W;
    for (int i = n; i > 0; i--) {
        if (dp[i][w] != dp[i-1][w]) {  // предмет i был взят
            items.push_back(i - 1);
            w -= wt[i-1];
        }
    }
    return items;
}

int main() {
    vector<int> wt = {1, 3, 4, 5};
    vector<int> val = {1, 4, 5, 7};
    int W = 7;

    cout << "Max value (2D): " << knapsack2D(W, wt, val) << endl;  // 9
    cout << "Max value (1D): " << knapsack1D(W, wt, val) << endl;  // 9

    auto items = knapsackItems(W, wt, val);
    cout << "Items taken: ";
    for (int i : items) cout << i << "(w=" << wt[i] << ",v=" << val[i] << ") ";
    // Items: 2(w=4,v=5) 1(w=3,v=4)  → total weight=7, value=9
    cout << endl;

    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

int unboundedKnapsack(int W, vector<int>& wt, vector<int>& val) {
    vector<int> dp(W + 1, 0);
    for (int i = 0; i < (int)wt.size(); i++) {
        for (int w = wt[i]; w <= W; w++) {  // СЛЕВА НАПРАВО!
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
        }
    }
    return dp[W];
}

int main() {
    vector<int> wt = {2, 3, 5};
    vector<int> val = {3, 4, 7};
    int W = 10;
    cout << "Max value: " << unboundedKnapsack(W, wt, val) << endl;
    // Можно взять: 5×(w=2,v=3)=15 или 2×(w=5,v=7)=14 → 15
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// ═══ O(n²) DP (Проще понять, но медленно) ═══
int lisQuadratic(const vector<int>& arr) {
    int n = arr.size();
    vector<int> dp(n, 1);  // dp[i] = длина LIS, заканчивающейся в i
    int maxLen = 1;

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[j] < arr[i])
                dp[i] = max(dp[i], dp[j] + 1);
        }
        maxLen = max(maxLen, dp[i]);
    }
    return maxLen;
}

// ═══ O(n log n) с бинарным поиском ═══
int lisBinarySearch(const vector<int>& arr) {
    vector<int> tails;  // tails[i] = наименьший хвост LIS длины i+1

    for (int x : arr) {
        auto it = lower_bound(tails.begin(), tails.end(), x);
        if (it == tails.end())
            tails.push_back(x);   // удлиняем LIS
        else
            *it = x;              // заменяем на меньший хвост
    }
    return tails.size();
}

// ═══ O(n log n) с восстановлением самой LIS ═══
vector<int> lisWithRecovery(const vector<int>& arr) {
    int n = arr.size();
    vector<int> tails, tailIdx, parent(n, -1);

    for (int i = 0; i < n; i++) {
        auto it = lower_bound(tails.begin(), tails.end(), arr[i]);
        int pos = it - tails.begin();

        if (it == tails.end()) {
            tails.push_back(arr[i]);
            tailIdx.push_back(i);
        } else {
            *it = arr[i];
            tailIdx[pos] = i;
        }
        parent[i] = (pos > 0) ? tailIdx[pos - 1] : -1;
    }

    // Восстанавливаем
    vector<int> lis;
    for (int i = tailIdx.back(); i != -1; i = parent[i])
        lis.push_back(arr[i]);
    reverse(lis.begin(), lis.end());
    return lis;
}

int main() {
    vector<int> arr = {10, 9, 2, 5, 3, 7, 101, 18};

    cout << "LIS length (O(n^2)): " << lisQuadratic(arr) << endl;       // 4
    cout << "LIS length (O(n log n)): " << lisBinarySearch(arr) << endl; // 4

    auto lis = lisWithRecovery(arr);
    cout << "LIS itself: ";
    for (int x : lis) cout << x << " ";  // 2 3 7 18
    cout << endl;

    return 0;
}

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int lcsLength(const string& s1, const string& s2) {
    int n = s1.size(), m = s2.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s1[i-1] == s2[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;   // совпадение
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);  // пропуск
        }
    }
    return dp[n][m];
}

string lcsString(const string& s1, const string& s2) {
    int n = s1.size(), m = s2.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            dp[i][j] = (s1[i-1] == s2[j-1])
                ? dp[i-1][j-1] + 1
                : max(dp[i-1][j], dp[i][j-1]);

    // Восстановление
    string result;
    int i = n, j = m;
    while (i > 0 && j > 0) {
        if (s1[i-1] == s2[j-1]) {
            result += s1[i-1];  // собираем с конца
            i--; j--;
        } else if (dp[i-1][j] > dp[i][j-1]) {
            i--;  // идём туда, откуда пришло большее значение
        } else {
            j--;
        }
    }
    reverse(result.begin(), result.end()); // переворачиваем!
    return result;
}

int main() {
    cout << "LCS length: " << lcsLength("ABCBDAB", "BDCAB") << endl;   // 4
    cout << "LCS string: " << lcsString("ABCBDAB", "BDCAB") << endl;   // BCAB
    return 0;
}

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int editDistance(const string& s1, const string& s2) {
    int n = s1.size(), m = s2.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1));

    // База: превратить пустую строку
    for (int i = 0; i <= n; i++) dp[i][0] = i;  // удаления
    for (int j = 0; j <= m; j++) dp[0][j] = j;  // вставки

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s1[i-1] == s2[j-1]) {
                dp[i][j] = dp[i-1][j-1];         // символы совпадают
            } else {
                dp[i][j] = 1 + min({
                    dp[i-1][j],     // удаление
                    dp[i][j-1],     // вставка
                    dp[i-1][j-1]    // замена
                });
            }
        }
    }
    return dp[n][m];
}

int main() {
    cout << editDistance("kitten", "sitting") << endl;     // 3 (k->s, e->i, +g)
    cout << editDistance("sunday", "saturday") << endl;    // 3
    cout << editDistance("", "abc") << endl;               // 3
    cout << editDistance("abc", "abc") << endl;            // 0
    return 0;
}

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

// Задача 1: Минимальное количество монет для суммы amount
int coinChangeMin(const vector<int>& coins, int amount) {
    // Инициализируем (amount + 1) как безопасный аналог бесконечности,
    // чтобы избежать переполнения INT_MAX + 1
    vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;

    for (int a = 1; a <= amount; a++) {
        for (int coin : coins) {
            if (coin <= a)
                dp[a] = min(dp[a], dp[a - coin] + 1);
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

// Задача 2: Количество комбинаций способов набрать сумму
long long coinChangeWays(const vector<int>& coins, int amount) {
    vector<long long> dp(amount + 1, 0);
    dp[0] = 1;

    // Перебираем МОНЕТЫ во внешнем цикле (чтобы не считать перестановки)
    for (int coin : coins) {
        for (int a = coin; a <= amount; a++) {
            dp[a] += dp[a - coin];
        }
    }
    return dp[amount];
}

int main() {
    vector<int> coins = {1, 5, 10, 25};

    cout << "Min coins for 30: " << coinChangeMin(coins, 30) << endl;  // 2 (25+5)
    cout << "Min coins for 11: " << coinChangeMin(coins, 11) << endl;  // 2 (10+1)
    cout << "Ways to make 10: " << coinChangeWays(coins, 10) << endl;  // 4 (10; 5+5; 5+1x5; 1x10)

    return 0;
}

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int matrixChain(const vector<int>& dims) {
    int n = dims.size() - 1;  // количество матриц
    // dp[i][j] = мин. число умножений для матриц от i до j
    vector<vector<int>> dp(n, vector<int>(n, 0));

    // len — длина цепочки
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            dp[i][j] = INT_MAX;
            // Пробуем все точки разделения k
            for (int k = i; k < j; k++) {
                int cost = dp[i][k] + dp[k+1][j]
                         + dims[i] * dims[k+1] * dims[j+1];
                dp[i][j] = min(dp[i][j], cost);
            }
        }
    }
    return dp[0][n-1];
}

int main() {
    // 3 матрицы: 10×30, 30×5, 5×60
    vector<int> dims = {10, 30, 5, 60};
    cout << "Min multiplications: " << matrixChain(dims) << endl;
    // (10×30)×(30×5) + (10×5)×(5×60) = 1500+3000 = 4500
    // vs 10×(30×5×60) + ... = 27000
    return 0;
}

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

// ═══ Можно ли набрать сумму target? ═══
bool subsetSum(const vector<int>& arr, int target) {
    vector<bool> dp(target + 1, false);
    dp[0] = true;

    for (int x : arr) {
        for (int s = target; s >= x; s--) {  // СПРАВА НАЛЕВО!
            if (dp[s - x]) dp[s] = true;
        }
    }
    return dp[target];
}

// ═══ Задача: Разбить массив на две части с равной суммой ═══
bool canPartition(const vector<int>& arr) {
    int total = accumulate(arr.begin(), arr.end(), 0);
    // Если сумма нечетная, разбить на две целые равные части невозможно
    if (total % 2 != 0) return false;
    return subsetSum(arr, total / 2);
}

// ═══ Подсчёт количества подмножеств с данной суммой ═══
int countSubsetSum(const vector<int>& arr, int target) {
    vector<int> dp(target + 1, 0);
    dp[0] = 1;
    for (int x : arr) {
        for (int s = target; s >= x; s--) {
            dp[s] += dp[s - x];
        }
    }
    return dp[target];
}

int main() {
    vector<int> arr = {3, 34, 4, 12, 5, 2};
    cout << "Subset sum 9: " << subsetSum(arr, 9) << endl;     // 1 (4+5)
    cout << "Subset sum 30: " << subsetSum(arr, 30) << endl;   // 0

    // Equal Partition
    vector<int> arr2 = {1, 5, 11, 5};
    cout << "Can partition: " << canPartition(arr2) << endl;    // 1 ({1,5,5} и {11})

    // Count
    vector<int> arr3 = {1, 2, 3, 3};
    cout << "Count subsets sum=6: " << countSubsetSum(arr3, 6) << endl;  // 3

    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Activity {
    int start, end, index;
};

// ═══ Максимальное количество непересекающихся интервалов ═══
vector<Activity> activitySelection(vector<Activity>& acts) {
    // Сортируем по времени ОКОНЧАНИЯ
    sort(acts.begin(), acts.end(), [](const Activity& a, const Activity& b) {
        return a.end < b.end;
    });

    vector<Activity> selected;
    int lastEnd = -1;

    for (auto& act : acts) {
        if (act.start >= lastEnd) {
            selected.push_back(act);
            lastEnd = act.end;
        }
    }
    return selected;
}

// ═══ Вариация: минимальное количество комнат для всех встреч ═══
// (Meeting Rooms II — популярная задача на собеседованиях)
int minMeetingRooms(vector<pair<int,int>>& intervals) {
    vector<int> starts, ends;
    for (auto& [s, e] : intervals) {
        starts.push_back(s);
        ends.push_back(e);
    }
    sort(starts.begin(), starts.end());
    sort(ends.begin(), ends.end());

    int rooms = 0, maxRooms = 0;
    int i = 0, j = 0;
    while (i < (int)starts.size()) {
        if (starts[i] < ends[j]) {
            rooms++;
            i++;
        } else {
            rooms--;
            j++;
        }
        maxRooms = max(maxRooms, rooms);
    }
    return maxRooms;
}

// ═══ Вариация: слияние пересекающихся интервалов ═══
vector<pair<int,int>> mergeIntervals(vector<pair<int,int>>& intervals) {
    sort(intervals.begin(), intervals.end());
    vector<pair<int,int>> merged;

    for (auto& [s, e] : intervals) {
        if (!merged.empty() && s <= merged.back().second) {
            merged.back().second = max(merged.back().second, e);
        } else {
            merged.push_back({s, e});
        }
    }
    return merged;
}

int main() {
    vector<Activity> acts = {
        {1,4,0}, {3,5,1}, {0,6,2}, {5,7,3}, {3,9,4},
        {5,9,5}, {6,10,6}, {8,11,7}, {8,12,8}, {2,14,9}, {12,16,10}
    };

    auto selected = activitySelection(acts);
    cout << "Selected " << selected.size() << " activities:" << endl;
    for (auto& a : selected)
        cout << "  [" << a.start << ", " << a.end << ")" << endl;
    // [1,4), [5,7), [8,11), [12,16)

    // Meeting Rooms
    vector<pair<int,int>> meetings = {{0,30},{5,10},{15,20}};
    cout << "Min rooms: " << minMeetingRooms(meetings) << endl;  // 2

    // Merge intervals
    vector<pair<int,int>> intervals = {{1,3},{2,6},{8,10},{15,18}};
    auto merged = mergeIntervals(intervals);
    cout << "Merged: ";
    for (auto& [s,e] : merged) cout << "[" << s << "," << e << "] ";
    // [1,6] [8,10] [15,18]
    cout << endl;

    return 0;
}

// ═══ Доказательство корректности жадного выбора ═══
// Пусть OPT — оптимальное решение. Пусть жадный выбрал активность A
// с наименьшим end. Если OPT не содержит A, заменим первую активность
// OPT на A — это не ухудшит решение (A заканчивается не позже).
// Значит, жадный выбор безопасен. По индукции — всё решение оптимально.

#include <iostream>
#include <queue>
#include <unordered_map>
#include <string>
using namespace std;

struct HuffNode {
    char ch;
    int freq;
    HuffNode *left, *right;
    HuffNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};

// Компаратор для min-heap
struct Compare {
    bool operator()(HuffNode* a, HuffNode* b) {
        return a->freq > b->freq;
    }
};

// Рекурсивно собираем коды
void buildCodes(HuffNode* root, string code, unordered_map<char, string>& codes) {
    if (!root) return;
    if (!root->left && !root->right) {  // лист
        codes[root->ch] = code.empty() ? "0" : code;
        return;
    }
    buildCodes(root->left, code + "0", codes);
    buildCodes(root->right, code + "1", codes);
}

unordered_map<char, string> huffmanCoding(const unordered_map<char, int>& freq) {
    priority_queue<HuffNode*, vector<HuffNode*>, Compare> pq;

    // Создаём листья
    for (auto& [ch, f] : freq)
        pq.push(new HuffNode(ch, f));

    // Строим дерево
    while (pq.size() > 1) {
        HuffNode* left = pq.top(); pq.pop();
        HuffNode* right = pq.top(); pq.pop();

        HuffNode* parent = new HuffNode('\0', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }

    unordered_map<char, string> codes;
    buildCodes(pq.top(), "", codes);
    return codes;
}

// Кодирование строки
string encode(const string& text, const unordered_map<char, string>& codes) {
    string result;
    for (char c : text)
        result += codes.at(c);
    return result;
}

// Декодирование
string decode(const string& encoded, HuffNode* root) {
    string result;
    HuffNode* cur = root;
    for (char bit : encoded) {
        cur = (bit == '0') ? cur->left : cur->right;
        if (!cur->left && !cur->right) {
            result += cur->ch;
            cur = root;
        }
    }
    return result;
}

int main() {
    unordered_map<char, int> freq = {
        {'a',5}, {'b',9}, {'c',12}, {'d',13}, {'e',16}, {'f',45}
    };

    auto codes = huffmanCoding(freq);

    cout << "Huffman Codes:" << endl;
    int totalBits = 0;
    for (auto& [ch, code] : codes) {
        cout << "  '" << ch << "': " << code
             << " (len=" << code.size() << ", freq=" << freq[ch] << ")" << endl;
        totalBits += code.size() * freq[ch];
    }
    cout << "Total bits: " << totalBits << endl;
    cout << "Fixed 3-bit: " << 3 * 100 << " bits" << endl;
    cout << "Savings: " << (300 - totalBits) * 100 / 300 << "%" << endl;

    // Кодирование/декодирование
    string text = "abcdef";
    string encoded = encode(text, codes);
    cout << "Encoded: " << encoded << endl;

    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Item {
    double value, weight;
    double ratio() const { return value / weight; }
};

double fractionalKnapsack(double W, vector<Item>& items) {
    // Сортируем по удельной ценности (убывание)
    sort(items.begin(), items.end(), [](const Item& a, const Item& b) {
        return a.ratio() > b.ratio();
    });

    double totalValue = 0;
    double remainW = W;

    for (auto& item : items) {
        if (remainW <= 0) break;

        if (item.weight <= remainW) {
            // Берём полностью
            totalValue += item.value;
            remainW -= item.weight;
            cout << "  Take full: v=" << item.value << ", w=" << item.weight << endl;
        } else {
            // Берём дробную часть
            double fraction = remainW / item.weight;
            totalValue += item.value * fraction;
            cout << "  Take " << (fraction*100) << "%: v="
                 << item.value * fraction << endl;
            remainW = 0;
        }
    }
    return totalValue;
}

int main() {
    vector<Item> items = {{60,10}, {100,20}, {120,30}};
    double W = 50;

    double result = fractionalKnapsack(W, items);
    cout << "Max value: " << result << endl;  // 240

    return 0;
}

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// ═══ Построение prefix-функции ═══
vector<int> buildPrefixFunction(const string& pattern) {
    int m = pattern.size();
    vector<int> pi(m, 0);

    int len = 0;  // длина текущего совпавшего префикса-суффикса
    int i = 1;

    while (i < m) {
        if (pattern[i] == pattern[len]) {
            len++;
            pi[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = pi[len - 1];  // откатываемся, НЕ увеличивая i
            } else {
                pi[i] = 0;
                i++;
            }
        }
    }
    return pi;
}

// ═══ Поиск всех вхождений pattern в text ═══
vector<int> kmpSearch(const string& text, const string& pattern) {
    int n = text.size(), m = pattern.size();
    vector<int> result;

    if (m == 0) return result;

    vector<int> pi = buildPrefixFunction(pattern);

    int j = 0;  // указатель в pattern
    for (int i = 0; i < n; i++) {
        // При несовпадении откатываемся по prefix-функции
        while (j > 0 && text[i] != pattern[j])
            j = pi[j - 1];

        if (text[i] == pattern[j])
            j++;

        if (j == m) {
            result.push_back(i - m + 1);  // найдено на позиции i-m+1
            j = pi[j - 1];                // продолжаем искать
        }
    }
    return result;
}

// ═══ Применение: проверка, является ли строка периодической ═══
// Строка s периодична с периодом p, если p | n и s = s[0..p-1] повторённая
int findPeriod(const string& s) {
    auto pi = buildPrefixFunction(s);
    int n = s.size();
    int period = n - pi[n - 1];
    if (n % period == 0) return period;
    return n;  // непериодическая
}

int main() {
    // Поиск подстроки
    string text = "ABABABABAC";
    string pattern = "ABABAC";

    auto positions = kmpSearch(text, pattern);
    cout << "Pattern found at: ";
    for (int p : positions) cout << p << " ";  // 4
    cout << endl;

    // Prefix-функция
    auto pi = buildPrefixFunction(pattern);
    cout << "Prefix function: ";
    for (int x : pi) cout << x << " ";  // 0 0 1 2 3 0
    cout << endl;

    // Множественные вхождения
    auto pos2 = kmpSearch("AABAACAADAABAABA", "AABA");
    cout << "AABA in AABAACAADAABAABA: ";
    for (int p : pos2) cout << p << " ";  // 0 9 12
    cout << endl;

    // Период строки
    cout << "Period of 'abcabcabc': " << findPeriod("abcabcabc") << endl;  // 3
    cout << "Period of 'abcabd': " << findPeriod("abcabd") << endl;        // 6

    return 0;
}

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// ═══ Базовый Rabin-Karp ═══
vector<int> rabinKarp(const string& text, const string& pattern) {
    int n = text.size(), m = pattern.size();
    vector<int> result;
    if (m > n) return result;

    const long long d = 256;      // размер алфавита
    const long long q = 1e9 + 7;  // большое простое число

    // Вычисляем d^(m-1) mod q
    long long h = 1;
    for (int i = 0; i < m - 1; i++)
        h = (h * d) % q;

    // Хеш паттерна и первого окна
    long long pHash = 0, tHash = 0;
    for (int i = 0; i < m; i++) {
        pHash = (d * pHash + pattern[i]) % q;
        tHash = (d * tHash + text[i]) % q;
    }

    for (int i = 0; i <= n - m; i++) {
        if (pHash == tHash) {
            // Хеши совпали — проверяем посимвольно (защита от коллизий)
            if (text.substr(i, m) == pattern)
                result.push_back(i);
        }

        // Rolling hash: убираем text[i], добавляем text[i+m]
        if (i < n - m) {
            tHash = (d * (tHash - text[i] * h) + text[i + m]) % q;
            if (tHash < 0) tHash += q;  // отрицательный остаток
        }
    }
    return result;
}

// ═══ Полиномиальное хеширование строки (для задач) ═══
struct StringHash {
    vector<long long> h, pw;
    long long mod = 1e9 + 7, base = 31;

    StringHash(const string& s) {
        int n = s.size();
        h.resize(n + 1, 0);
        pw.resize(n + 1, 1);

        for (int i = 0; i < n; i++) {
            h[i + 1] = (h[i] * base + s[i] - 'a' + 1) % mod;
            pw[i + 1] = pw[i] * base % mod;
        }
    }

    // Хеш подстроки s[l..r] (0-indexed)
    long long getHash(int l, int r) {
        long long result = (h[r + 1] - h[l] * pw[r - l + 1] % mod + mod * mod) % mod;
        return result;
    }

    // Сравнение подстрок за O(1)
    bool equal(int l1, int r1, int l2, int r2) {
        return getHash(l1, r1) == getHash(l2, r2);
    }
};

int main() {
    // Rabin-Karp
    auto pos = rabinKarp("AABAACAADAABAABA", "AABA");
    cout << "Found at: ";
    for (int p : pos) cout << p << " ";  // 0 9 12
    cout << endl;

    // String Hashing
    StringHash sh("abcabc");
    cout << "hash(abc) == hash(abc): "
         << sh.equal(0, 2, 3, 5) << endl;  // 1
    cout << "hash(abc) == hash(bca): "
         << sh.equal(0, 2, 1, 3) << endl;  // 0

    return 0;
}

#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<int> zFunction(const string& s) {
    int n = s.size();
    vector<int> z(n, 0);
    int l = 0, r = 0;  // [l, r) — самый правый Z-блок

    for (int i = 1; i < n; i++) {
        if (i < r)
            z[i] = min(r - i, z[i - l]);  // используем уже вычисленное

        // Наивно расширяем
        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
            z[i]++;

        // Обновляем Z-блок
        if (i + z[i] > r) {
            l = i;
            r = i + z[i];
        }
    }
    return z;
}

// ═══ Поиск pattern в text через Z-функцию ═══
vector<int> zSearch(const string& text, const string& pattern) {
    string concat = pattern + "$" + text;
    auto z = zFunction(concat);

    vector<int> result;
    int m = pattern.size();
    for (int i = m + 1; i < (int)concat.size(); i++)
        if (z[i] == m)
            result.push_back(i - m - 1);
    return result;
}

// ═══ Задача: сжатие строки ═══
// Найти кратчайшую строку t, чтобы s = t + t + ... + t
string compress(const string& s) {
    auto z = zFunction(s);
    int n = s.size();
    for (int i = 1; i < n; i++) {
        // Если s можно разбить на блоки длины i
        if (n % i == 0 && z[i] == n - i)
            return s.substr(0, i);
    }
    return s;
}

int main() {
    // Z-функция
    auto z = zFunction("aabxaab");
    cout << "Z-function: ";
    for (int x : z) cout << x << " ";  // 0 1 0 0 3 1 0
    cout << endl;

    // Поиск
    auto pos = zSearch("AABAACAADAABAABA", "AABA");
    cout << "Found at: ";
    for (int p : pos) cout << p << " ";  // 0 9 12
    cout << endl;

    // Сжатие
    cout << "Compress 'abcabcabc': " << compress("abcabcabc") << endl;  // "abc"
    cout << "Compress 'abcd': " << compress("abcd") << endl;            // "abcd"

    return 0;
}

#include <iostream>
#include <vector>
#include <string>
using namespace std;

string longestPalindrome(const string& s) {
    // Трансформация: "abc" → "^#a#b#c#$"
    string t = "^#";
    for (char c : s) { t += c; t += '#'; }
    t += '$';

    int n = t.size();
    vector<int> p(n, 0);  // p[i] = радиус палиндрома с центром i
    int center = 0, right = 0;

    for (int i = 1; i < n - 1; i++) {
        int mirror = 2 * center - i;

        if (i < right)
            p[i] = min(right - i, p[mirror]);

        // Расширяем палиндром
        while (t[i + p[i] + 1] == t[i - p[i] - 1])
            p[i]++;

        // Обновляем центр и правую границу
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
    }

    // Находим максимум
    int maxLen = 0, maxCenter = 0;
    for (int i = 1; i < n - 1; i++) {
        if (p[i] > maxLen) {
            maxLen = p[i];
            maxCenter = i;
        }
    }

    // Конвертируем обратно
    int start = (maxCenter - maxLen) / 2;
    return s.substr(start, maxLen);
}

// ═══ Подсчёт всех палиндромных подстрок ═══
int countPalindromicSubstrings(const string& s) {
    string t = "^#";
    for (char c : s) { t += c; t += '#'; }
    t += '$';

    int n = t.size();
    vector<int> p(n, 0);
    int center = 0, right = 0;

    for (int i = 1; i < n - 1; i++) {
        if (i < right)
            p[i] = min(right - i, p[2 * center - i]);
        while (t[i + p[i] + 1] == t[i - p[i] - 1])
            p[i]++;
        if (i + p[i] > right) {
            center = i;
            right = i + p[i];
        }
    }

    // Каждый p[i] для '#' — палиндромы чётной длины
    // Каждый p[i] для буквы — палиндромы нечётной длины
    int count = 0;
    for (int i = 1; i < n - 1; i++)
        count += (p[i] + 1) / 2;  // каждый радиус r даёт ⌈r/2⌉ палиндромов

    return count;
}

int main() {
    cout << longestPalindrome("babad") << endl;      // "bab" или "aba"
    cout << longestPalindrome("cbbd") << endl;       // "bb"
    cout << longestPalindrome("abacaba") << endl;    // "abacaba"
    cout << longestPalindrome("a") << endl;          // "a"
    cout << longestPalindrome("racecar") << endl;    // "racecar"

    cout << "Palindromic substrings in 'abc': "
         << countPalindromicSubstrings("abc") << endl;   // 3 (a,b,c)
    cout << "Palindromic substrings in 'aaa': "
         << countPalindromicSubstrings("aaa") << endl;   // 6 (a,a,a,aa,aa,aaa)

    return 0;
}

#include <iostream>
#include <numeric>  // C++17: std::gcd, std::lcm
using namespace std;

// Рекурсивный
long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

// Итеративный (чуть быстрее из-за отсутствия вызовов стека)
long long gcdIter(long long a, long long b) {
    while (b) { 
        a %= b; 
        swap(a, b); 
    }
    return a;
}

long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;  // делим первым для защиты от переполнения!
}

// GCD массива
long long gcdArray(long long arr[], int n) {
    long long result = arr[0];
    for (int i = 1; i < n; i++)
        result = gcd(result, arr[i]);
    return result;
}

int main() {
    cout << "gcd(252, 105) = " << gcd(252, 105) << endl;  // 21
    cout << "lcm(252, 105) = " << lcm(252, 105) << endl;  // 1260
    cout << "gcd(0, 5) = " << gcd(0, 5) << endl;          // 5
    cout << "gcd(17, 13) = " << gcd(17, 13) << endl;      // 1 (взаимно простые)

    // C++17
    cout << "std::gcd(12,8) = " << std::gcd(12, 8) << endl;  // 4

    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

// ═══ Классическое решето ═══
vector<bool> sieve(int n) {
    vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;

    for (int i = 2; i * i <= n; i++) {
        if (is_prime[i]) {
            // Оптимизация: начинаем с i², так как меньшие кратные 
            // (i*2, i*3) уже были вычеркнуты ранее
            for (int j = i * i; j <= n; j += i)
                is_prime[j] = false;
        }
    }
    return is_prime;
}

// ═══ Линейное решето (O(n), хранит минимальный делитель SPF) ═══
vector<int> linearSieve(int n) {
    vector<int> spf(n + 1, 0);  // smallest prime factor
    vector<int> primes;

    for (int i = 2; i <= n; i++) {
        if (spf[i] == 0) {  // i — простое
            spf[i] = i;
            primes.push_back(i);
        }
        for (int p : primes) {
            // Каждое составное число вычёркивается ровно 1 раз
            // своим наименьшим простым делителем
            if (p > spf[i] || (long long)i * p > n) break;
            spf[i * p] = p;
        }
    }
    return spf;
}

// ═══ Быстрая факторизация за O(log n) через SPF ═══
vector<int> factorize(int n, const vector<int>& spf) {
    vector<int> factors;
    while (n > 1) {
        factors.push_back(spf[n]);
        n /= spf[n];
    }
    return factors;
}

int main() {
    auto is_prime = sieve(30);
    cout << "Primes up to 30: ";
    for (int i = 2; i <= 30; i++)
        if (is_prime[i]) cout << i << " ";
    cout << endl;  // 2 3 5 7 11 13 17 19 23 29

    auto spf = linearSieve(100);
    auto factors = factorize(84, spf);
    cout << "84 = ";
    for (int f : factors) cout << f << " × ";  // 2 × 2 × 3 × 7
    cout << endl;

    return 0;
}

#include <iostream>
using namespace std;

// ═══ Итеративный (рекомендуется, не тратит память стека) ═══
long long fastPow(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1)                     // бит 1 (степень нечётная)
            result = (result * base) % mod;
        base = (base * base) % mod;      // возводим основание в квадрат
        exp >>= 1;                       // целочисленное деление на 2
    }
    return result;
}

// ═══ Рекурсивный (проще для понимания) ═══
long long fastPowRec(long long base, long long exp, long long mod) {
    if (exp == 0) return 1;
    if (exp % 2 == 1)
        return (base % mod * fastPowRec(base, exp - 1, mod)) % mod;
    long long half = fastPowRec(base, exp / 2, mod);
    return (half * half) % mod;
}

int main() {
    const long long MOD = 1e9 + 7;

    cout << "3^13 mod MOD = " << fastPow(3, 13, MOD) << endl;         // 1594323
    cout << "2^10 mod 1000 = " << fastPow(2, 10, 1000) << endl;       // 24 (1024 % 1000)
    
    // По Малой теореме Ферма: a^(-1) ≡ a^(p-2) (mod p)
    long long inv7 = fastPow(7, MOD - 2, MOD);
    cout << "7^(-1) mod (10^9+7) = " << inv7 << endl;
    cout << "Check: (7 * inv7) % MOD = " << (7LL * inv7 % MOD) << endl; // 1

    return 0;
}

#include <iostream>
using namespace std;

const long long MOD = 1e9 + 7;

long long mod(long long a) { return ((a % MOD) + MOD) % MOD; }
long long add(long long a, long long b) { return mod(mod(a) + mod(b)); }
long long sub(long long a, long long b) { return mod(mod(a) - mod(b) + MOD); }
long long mul(long long a, long long b) { return mod(mod(a) * mod(b)); }

// Быстрая степень для обратного
long long power(long long base, long long exp) {
    long long result = 1; base %= MOD;
    while (exp > 0) {
        if (exp & 1) result = (result * base) % MOD;
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return result;
}

// Обратный элемент
long long modInverse(long long a) { 
    return power(a, MOD - 2); 
}

// Деление по модулю
long long divide(long long a, long long b) { 
    return mul(a, modInverse(b)); 
}

int main() {
    // (10^18 + 10^18) mod (10^9+7)
    long long hugeA = 1000000000000000000LL;
    long long hugeB = 1000000000000000000LL;
    cout << "Add: " << add(hugeA, hugeB) << endl; // Без переполнений

    // Вычитание, уходящее в минус
    cout << "Sub: " << sub(2, 5) << endl; // -3 mod (1e9+7) = 1000000004

    // Деление (5! / 3!)
    cout << "Div (5!/3!): " << divide(120, 6) << endl; // 20

    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 200001;
const long long MOD = 1e9 + 7;

long long fact[MAXN], inv_fact[MAXN];

long long power(long long base, long long exp) {
    long long result = 1; base %= MOD;
    while (exp > 0) {
        if (exp & 1) result = result * base % MOD;
        base = base * base % MOD;
        exp >>= 1;
    }
    return result;
}

void precompute() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++)
        fact[i] = (fact[i - 1] * i) % MOD;

    // Вычисляем обратный факториал только для самого большого числа O(log MOD)
    inv_fact[MAXN - 1] = power(fact[MAXN - 1], MOD - 2);
    
    // Остальные получаем за O(1) итеративно! (1/3! = 1/4! * 4)
    for (int i = MAXN - 2; i >= 0; i--)
        inv_fact[i] = (inv_fact[i + 1] * (i + 1)) % MOD;
}

// ═══ Сочетания C(n, k) за O(1) ═══
long long C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD;
}

// ═══ Перестановки P(n, k) за O(1) ═══
long long P(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * inv_fact[n - k] % MOD;
}

// ═══ Числа Каталана: C_n = C(2n, n) / (n+1) ═══
long long catalan(int n) {
    return C(2 * n, n) * power(n + 1, MOD - 2) % MOD;
}

// ═══ Треугольник Паскаля (без предрасчетов, O(N^2)) ═══
vector<vector<long long>> pascalTriangle(int n) {
    vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, 0));
    for (int i = 0; i <= n; i++) {
        dp[i][0] = dp[i][i] = 1;
        for (int j = 1; j < i; j++)
            dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % MOD;
    }
    return dp;
}

int main() {
    precompute();  // НЕ ЗАБУДЬТЕ ВЫЗВАТЬ В MAIN!

    cout << "C(5,2) = " << C(5, 2) << endl;      // 10
    cout << "C(10,3) = " << C(10, 3) << endl;    // 120
    cout << "C(52,5) = " << C(52, 5) << endl;    // 2598960
    cout << "P(5,3) = " << P(5, 3) << endl;      // 60

    // Числа Каталана
    for (int i = 0; i <= 6; i++)
        cout << "Cat(" << i << ")=" << catalan(i) << " ";
    // 1 1 2 5 14 42 132
    cout << endl;

    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

// ═══ Для одного числа: O(√n) ═══
long long eulerTotient(long long n) {
    long long result = n;
    for (long long p = 2; p * p <= n; p++) {
        if (n % p == 0) {
            // Вычитаем долю чисел, кратных p
            result -= result / p;
            
            // Удаляем все множители p
            while (n % p == 0) 
                n /= p;
        }
    }
    // Если остался простой делитель > √n
    if (n > 1) 
        result -= result / n;
        
    return result;
}

// ═══ Решето для вычисления φ от 1 до n: O(n log log n) ═══
vector<int> eulerSieve(int n) {
    vector<int> phi(n + 1);
    for (int i = 0; i <= n; i++) phi[i] = i;  // Изначально phi[i] = i

    for (int i = 2; i <= n; i++) {
        // Если phi[i] не изменилось, то i — простое число
        if (phi[i] == i) {
            for (int j = i; j <= n; j += i) {
                // Все кратные числу i содержат делитель i
                phi[j] -= phi[j] / i;
            }
        }
    }
    return phi;
}

int main() {
    cout << "φ(12) = " << eulerTotient(12) << endl;  // 4
    cout << "φ(36) = " << eulerTotient(36) << endl;  // 12
    cout << "φ(97) = " << eulerTotient(97) << endl;  // 96 (простое)

    auto phi = eulerSieve(20);
    for (int i = 1; i <= 20; i++)
        cout << "φ(" << i << ")=" << phi[i] << " ";
    cout << endl;

    return 0;
}

#include <iostream>
using namespace std;

// Возвращает gcd, записывает x, y: a*x + b*y = gcd(a,b)
long long extgcd(long long a, long long b, long long &x, long long &y) {
    if (b == 0) { 
        x = 1; 
        y = 0; 
        return a; 
    }
    long long x1, y1;
    long long g = extgcd(b, a % b, x1, y1);
    
    x = y1;
    y = x1 - (a / b) * y1;
    
    return g;
}

// ═══ Использование 1: Модульное обратное по ЛЮБОМУ модулю ═══
// Работает, только если a и m взаимно просты (НОД=1)
long long modInverse(long long a, long long m) {
    long long x, y;
    long long g = extgcd(a, m, x, y);
    if (g != 1) return -1;  // обратного не существует
    return (x % m + m) % m; // x может быть отрицательным!
}

// ═══ Использование 2: Линейное диофантово уравнение ax + by = c ═══
// Решение существует тогда и только тогда, когда c кратно НОД(a, b)
bool solveDiophantine(long long a, long long b, long long c,
                       long long &x, long long &y) {
    long long g = extgcd(abs(a), abs(b), x, y);
    if (c % g != 0) return false;
    
    x *= c / g;
    y *= c / g;
    
    if (a < 0) x = -x;
    if (b < 0) y = -y;
    
    return true;
}

int main() {
    long long x, y;
    long long g = extgcd(30, 21, x, y);
    cout << "30 * (" << x << ") + 21 * (" << y << ") = " << g << endl;
    // 30*(-2) + 21*(3) = 3

    cout << "3^(-1) mod 11 = " << modInverse(3, 11) << endl;  // 4 (3*4=12≡1)
    
    // Модуль 26 не простое! Ферма здесь не работает, а Евклид работает:
    cout << "7^(-1) mod 26 = " << modInverse(7, 26) << endl;  // 15 (7*15=105≡1)

    return 0;
}