Задача 5833. Источник: Поляков. Задание КИМ 5

(Е. Усов) Исполнитель Сыщик получает на вход натуральное число N и строит новое число R следующим образом.

Строится шестнадцатеричная запись числа N.
Далее эта запись обрабатывается по следующему правилу:
1. Если число чётное, справа приписывается максимально возможная цифра, в противном случае справа приписывается 0.
2. Справа приписывается шестнадцатеричная цифра – остаток от деления суммы цифр шестнадцатеричной записи на 16.
3. Пункт б выполняется ещё один раз.

Полученная таким образом запись является шестнадцатеричной записью искомого числа R.

Укажите минимальное число N, для которого максимальная цифра в полученной шестнадцатеричной записи встречается в пять раз реже, чем минимальная. В ответе это число запишите в десятичной системе счисления.

Решение

Последовательно перебирая числа N в цикле, получаем результат в соответствии с алгоритмом (операции в алгоритме выполняются через эквивалентные целочисленные операции десятичной системы счисления) и анализируем результат, пока не найдем требуемое значение. Решение через операции со строками так же возможно, но оно уже не будет таким простым и компактным, как в большинстве других задач. Исключение составляет только конечный анализ на Python, который можно выполнить гораздо проще. Результат алгоритма должен содержать не менее 6 разрядов, из которых три разряда добавляет алгоритм. Поэтому, начинаем с минимального трехразрядного шестнадцатеричного числа.

Python

for n in range(256, 1000000):
    r = n * 16
    if n % 2 == 0:
        r += 15
    for i in range(2):
        z = r
        s = 0
        while z > 0:
            s += z % 16
            z //= 16
        r = r * 16 + s % 16
    mx = -1
    mn = 16
    mxk = 0
    mnk = 0
    while r > 0:
        d = r % 16
        if d > mx:
            mx = d
            mxk = 1
        elif d == mx:
            mxk += 1
        if d < mn:
            mn = d
            mnk = 1
        elif d == mn:
            mnk += 1
        r //= 16
    if mxk * 5 == mnk:
        print(n)
        break

Python с конечным анализом через строки

for n in range(256, 1000000):
    r = n * 16
    if n % 2 == 0:
        r += 15
    for i in range(2):
        z = r
        s = 0
        while z > 0:
            s += z % 16
            z //= 16
        r = r * 16 + s % 16
    s = hex(r)[2:]
    if s.count(max(s)) * 5 == s.count(min(s)):
        print(n)
        break

PascalABC

var
    n, i, r, z, s, d, min, max, mink, maxk: Integer;
begin
    for n := 256 to 1000000 do
    begin
        r := n * 16;
        if n mod 2 = 0 then
            r := r + 15;
        for i := 1 to 2 do
        begin
            z := r;
            s := 0;
            while z > 0 do
            begin
                s := s + z mod 16;
                z := z div 16;
            end;
            r := r * 16 + s mod 16;
        end;
        max := -1;
        min := 16;
        maxk := 0;
        mink := 0;
        while r > 0 do
        begin
            d := r mod 16;
            if d > max then
            begin
                max := d;
                maxk := 1;
            end
            else if d = max then
                maxk := maxk + 1;
            if d < min then
            begin
                min := d;
                mink := 1;
            end
            else if d = min then
                mink := mink + 1;
            r := r div 16;
        end;
        if maxk * 5 = mink then
        begin
            Writeln(n);
            break;
        end;
    end;
end.

C++

#include <iostream>
using namespace std;
int main()
{
    for (int n = 265; n < 1000000; n++)
    {
        int r = n * 16;
        if (n % 2 == 0)
            r += 15;
        for (int i = 0; i < 2; i++)
        {
            int z = r;
            int s = 0;
            while (z > 0)
            {
                s += z % 16;
                z /= 16;
            }
            r = r * 16 + s % 16;
        }
        int max = -1;
        int min = 16;
        int maxk = 0;
        int mink = 0;
        while (r > 0)
        {
            int d = r % 16;
            if (d > max)
            {
                max = d;
                maxk = 1;
            }
            else if (d == max)
                maxk++;
            if (d < min)
            {
                min = d;
                mink = 1;
            }
            else if (d == min)
                mink++;
            r /= 16;
        }
        if (maxk * 5 == mink)
        {
            cout << n << endl;
            break;
        }
    }
}

Ответ

4096