РЕШУ ЕГЭ — информатика

Задания

Обозначим через a%b остаток от деления натурального числа a на натуральное число b, а через a//b  — целую часть от деления a на b.

Функция F(n), где n  — неотрицательное целое число, задана следующими соотношениями:

F(n)  =  0, если n  =  0;

F(n)  =  F(n//10) + n%10, если n > 0 и n чётно;

F(n)  =  F(n//10), если n нечётно.

Определите количество таких целых k, что 10⁹ ≤ k ≤ 2 · 10⁹ и F(k)  =  2.

Решение. Для примера найдем значение F(12345):

$F левая круглая скобка 12345 правая круглая скобка = F левая круглая скобка 1234 правая круглая скобка = F левая круглая скобка 123 правая круглая скобка плюс 4 = F левая круглая скобка 12 правая круглая скобка плюс 4 = F левая круглая скобка 1 правая круглая скобка плюс 2 плюс 4 = F левая круглая скобка 0 правая круглая скобка плюс 2 плюс 4 = 6.$ $F левая круглая скобка 12345 правая круглая скобка = F левая круглая скобка 1234 правая круглая скобка = F левая круглая скобка 123 правая круглая скобка плюс 4 =$
$= F левая круглая скобка 12 правая круглая скобка плюс 4 = F левая круглая скобка 1 правая круглая скобка плюс 2 плюс 4 = F левая круглая скобка 0 правая круглая скобка плюс 2 плюс 4 = 6.$

То есть алгоритм считает сумму всех четных цифр в числе. Поскольку по условию задачи требуется найти числа, сумма четных цифр которых равна 2, то число может состоять только из нечетных цифр, нуля и одной двойки. Достаточно посчитать все возможные варианты. На первом месте может стоять 1, далее одна двойка на любом месте и цифры из набора 0 (так как 0 в сумме не увеличивает число), 1, 3, 5, 7, 9 (всего 6). Посчитаем количество чисел из диапазона 10⁹ ≤ k ≤ 2 · 10⁹−1, удовлетворяющих условию:

$1 умножить на 9 умножить на 6 умножить на 6 умножить на 6 умножить на 6 умножить на 6 умножить на 6 умножить на 6 умножить на 6 = 15 116 544.$

Также подходит число 2 · 10⁹, так как содержит одну двойку. Всего подходящих чисел:

$15 116 544 плюс 1 = 15 116 545.$

Ответ: 15 116 545.

Приведём решение Артёма Гридина на языке C#.

using System;

namespace N63065

{

    internal class Program

    {

        static int F(int n)

        {

            if (n== 0)

                return 0;

            else if (n % 2 == 0)

                return F(n / 10) + n % 10;

            else

                return F(n / 10);

        }

        static void Main()

        {

            var p = Convert.ToInt32(Math.Pow(10, 9));

            var cnt = 0;

            for (int k = p; k<=2*p; k++)

            {

                if (F(k) == 2)

                    cnt++;

            }

            Console.WriteLine(cnt);

            Console.ReadKey();

        }

№ п/п	№ задания	Ответ
1	63065	15116545

Ключ