# ЕГЭ

## 24

==ПРОВЕРЯЙ ЧЕРЕЗ CTRL+F, ЕСЛИ ЕСТЬ ВОЗМОЖНОТЬ==

### 24 с количеством одинаковых символов

/**
 * Одинаковые символы идущие подряд (вероятно, найти самую длинную цепочку, в ответ символ и длину)
*/
#include <fstream>
#include <iostream>
#include <string>
using namespace std;
int main() {
    fstream file;
    file.open("24test.txt", ios::in);
    string line;
    getline(file, line);
    int max_len = 0;
    int curr_len = 0;
    char max_char = ' ';
    for (int i = 1; i < line.size(); i++) {
        curr_len = 1;
        while (line[i] == line[i - 1] && i < line.size()) {
            i++;
            curr_len++;
        }
        if (curr_len > max_len) {
            max_len = curr_len;
            max_char = line[i - 1];
        }
    }
    cout << curr_len << " " << max_char << endl;
}

### 24 с подстрокой без AD

/**
 * Максимальная длина подстроки в которой нет AD
*/
#include <fstream>
#include <iostream>
#include <string>
using namespace std;
int main() {
    fstream file;
    file.open("24test.txt", ios::in);
    string line;
    getline(file, line);
    int max_counter = 0;
    int curr_len = 1;

    for (int i = 1; i < line.size(); i++) {
        // aaaaddadadaaa
        if (line[i - 1] == 'A' && line[i] == 'D') {
            if (curr_len > max_counter) {
                max_counter = curr_len;
            }
            curr_len = 1;
        } else {
            curr_len++;
        }
    }
    cout << max_counter << endl;
}

## 25

### Количество простых

/**
 * Количество простых на отрезке
*/
#include <iostream>
#include <math.h>
using namespace std;

bool is_prime(int n) {
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    int start = 100000;
    int end = 400000;
    int counter = 0;
    for (int i = start; i <= end; i++) {
        if (is_prime(i)) {
            counter++;
        }
    }
    cout << counter << endl;
}

### У большого числа ровно 5 нечётных делителей

/**
 * Найдите все натуральные числа, принадлежащие отрезку [35 000 000; 40 000 000], у которых ровно пять различных нечётных делителей (количество чётных делителей может быть любым). В ответе перечислите найденные числа в порядке возрастания.
*/
#include <iostream>
#include <math.h>
using namespace std;

int is_prime(int n) {
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

bool five_divs(int n) {
    // пусть a, b, c - простые числа > 2
    // n = a*b*c: 1, a, b, c, ab, bc, ac, abc   | 8 divs
    // n = a*b*b: 1, a, b, ab, bb, abb          | 6 divs
    // n = a*a*a: 1, a, aa, aaa                 | 4 divs
    // n = a*a*a*a:                             | 5 divs
    // n = a*a*a*a*a:                           | 6 divs
    while (n % 2 == 0) {
        n /= 2;
    }
    int s1 = sqrt(n);
    int s2 = sqrt(s1);
    if (s2 * s2 * s2 * s2 != n) {
        return false;
    }
    return is_prime(s2);
}

int main() {
    for (int i = 35000000; i <= 40000000; i++) {
        if (five_divs(i)) {
            cout << i << endl;
        }
    }
}

## 26 чемоданы

==ВНИМАТЕЛЬНО ЧИТАЙ УСЛОВИЕ, ОНО МОЖЕТ ОТЛИЧАТЬСЯ==
Первая строка: количество чемоданов и максимальный вес, который можно загрузить

Дальше - вес каждого чемодана

В ответе недо указать, сколько чемоданов можно загрузить и вес минимального, незагруженного

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

int main() {
    fstream file;
    file.open("26.txt", ios::in);
    string line;
    getline(file, line, ' ');
    int N = stoi(line);
    getline(file, line);
    int K = stoi(line);
    vector<int> arr;
    for (int i = 0; i < N; i++) {
        getline(file, line);
        arr.push_back(stoi(line));
    }
    file.close();
    sort(arr.begin(), arr.end());
    int i = 0;
    int counter = 0;
    while (K >= 0) {
        K -= arr[i];
        counter++;
        i++;
    }
    counter--;
    i--;
    K += arr[i];
    cout << counter << " " << arr[i] << endl;
}

## 27

### Условие:

На вход программы поступает последовательность N целых положительных чисел. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше 5 (разница в индексах элементов должна быть 5 или более). Необходимо определить количество пар, произведение чисел в которых кратно простому числу (было дано КОНКРЕТНОЕ простое число)
Пример этого числа 13.

### Пример (генерирую на основе Полякова)

11 - N (кол-во чисел)
4
14
27
39
7
2
13
6
7
26
1

### Идея решения

Задача очень похожа на ту, где мы находили минимальную сумму квадратов пар. Идея решения заключается в том, чтобы хранить для кажого шага количество элементов, кратное 13:

| Входные данные | Количество чисел, кратных 13 на данный момент (`vector<int> arr` ) |
| -------------- |:--------------------------------------------- |
| 4 | 0 |
| 14 | 0 |
| 27 | 0 |
| 39 | 1 |
| 7 | 1 |
| 2 | 1 |
| 13 | 2 |
| 6 | 2 |
| 7 | 2 |
| 26 | 3 |
| 1 | 3 |

Обновление счётчика:

1. Если новое значение некратно 13, то `counter += arr[i-5]` (образуется столько новых пар, сколько чисел, кратных 13 было в доступном промежудке)
2. Если новое значение кратно 13, то `counter+= i-5+1` (+1 из-за того, что индексация с 0) - мы можем образовать i-5 новых пар (т.е. по паре со всеми числами из доступного промежудка)

#include <fstream>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
    int K = 13;
    fstream file;
    file.open("27.txt", ios::in);
    string line;
    getline(file, line);
    int N = stoi(line);
    vector<int> arr;
    int counter = 0;
    for (int line_index = 0; line_index < N; line_index++) {
        getline(file, line);
        int v = stoi(line);
        int increment = int(v % K == 0);

        if (line_index == 0) {
            arr.push_back(increment);
        } else {
            arr.push_back(arr[arr.size() - 1] + increment);
        }
        if (line_index >= 5) {
            if (increment) {
                counter += line_index - 5 + 1;
            } else {
                counter += arr[line_index - 5];
            }
        }
    }
    file.close();
    cout << counter << endl;
}