Задание 22. Графы. Подсчёт количества программ. ЕГЭ 2023 по информатике

Проанализируем работу алгоритма (на примере программы на языке Паскаль). Условный оператор if L mod 2 <> 0 then M := 42; изменяет только начальное значение переменной M. К роли этого оператора мы вернёмся позже.

Цикл while выполняется до тех пор, пока значения переменных L и M не станут равными. На каждой итерации цикла изменяется значение той из переменных (L или M), которая больше. При этом из большей переменной вычитается меньшая. В результате выполнения цикла получим:

$\{\table\ L↖{~} = L - k · M↖{~}; \ M↖{~} = M - t · L↖{~};$

где $L↖{~}$, $M↖{~}$ - значения переменных L и M, полученные после выполнения алгоритма; L,M - исходные значения этих переменных; k, t - натуральные числа.

По условию в результате выполнения программы будет напечатано число 21. Так как выход из цикла происходит, когда $L↖{~} = M↖{~}$, то $L↖{~} = M↖{~} = 21$.

Получаем:

$\{\table\ 21 = L - 21 · k; \ 21 = M - 21 · t;$ $\{\table\ L = 21 · k + 21; \ M = 21 · t + 21;$

Следовательно, исходное значениеM должно делиться на 21. Из двух возможных значений M (71 и 42) этому условию удовлетворяет число 42. Так как это значение переменная M принимает, если l нечётное, при этом L = x, то x - нечётно и x = 21 · k + 21.

Требуется найти наименьшее x > 80. То есть должно выполняться неравенство 21 · k + 21 > 80. Получаем k > 2;8. Переменная x принимает наименьшее значение при k = 3. В этом случае x = 21 · 3 + 21 = 84.

Это значение чётно, и следовательно, оно не удовлетворяет условию задачи. При k = 4, x = 21 · 4 + 21 = 105 - удовлетворяет условию задачи.

Ответ: 105.

Код программы для нахождения ответа на С++:

bool f(int x){
    int d = 0;
    while (x > 0){
        d = d * 10 + x % 3;
        x /= 3;
    }
    if (d / 100 != 0 && d / 1000 == 0 && d % 10 == 2)
        return true;
    else
        return false;
}

int main() {
    for (int i = 1000; i >= 100; --i)
        if (f(i)) {
            cout << i << " ";
            break;
        }
    return 0;
}

Программа выдаст результат: 702

Решение на С++

for (int i = 1; i < 10000; ++i) {
    int x = i, a = 0, b = 0;
    while (x > 0){
        a++;
        if (x % 2 != 0) b++;
        x /= 2;
    }
    if (b == 3 && a == 7)
        cout << i << " "; // выводим то, что "вводили"
}