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

Страница задачи 6545

(М. Гутров) Многие целые числа можно превратить в палиндром после неоднократного сложения самого числа и его инвертированной копии. Например, для числа 254 нужно 3 итерации чтобы оно стало палиндромом: 254 + 452 = 706, 706 + 607 = 1313, 1313 + 3131 = 4444. В диапазоне чисел от 100 до 200 найдите количество чисел, которые могут быть превращены в палиндром не более чем за 5 итераций.

Решение

Создадим рекурсивную функцию, которая возвращает истину, если число можно преобразовать таким образом и ложь в противном случае. Вторым параметром в функцию передается количество оставшихся итераций. Как и во многих других задачах, преобразования и анализ можно осуществлять через целочисленные операции и через строки. Обратите внимание, что в целях минимизации кода, решение с использованием целочисленных операций использует небольшой алгоритмический трюк. Чтобы исходное число не сравнивалось со своей инвертированной копией, добавлено дополнительное условие. Сумма числа и инвертированной копии анализируется при значении k от 4 до 0.

Python через строки

def f(n, k=5):
    if k == 0:
        return False
    n += int(str(n)[::-1])
    if str(n) == str(n)[::-1]:
        return True
    return f(n, k - 1)


k = 0
for n in range(100, 201):
    if f(n):
        k += 1
print(k)

Python через целочисленные операции

def f(n, k=5):
    nn = 0
    z = n
    while z > 0:
        nn = nn *10 + z % 10
        z //= 10
    if n == nn and k < 5:
        return True
    if k == 0:
        return False
    return f(n + nn, k - 1)


k = 0
for n in range(100, 201):
    if f(n):
        k += 1
print(k)

PascalABC через строки

function F(n: Integer; k: Integer := 5): Boolean;
begin
    if k = 0 then
        result := False
    else
    begin
        n := n + StrToInt(IntToStr(n).Inverse());
        if IntToStr(n) = IntToStr(n).Inverse() then
            result := True
        else
            result := F(n, k -1);
    end;
end;

var
    n, k: Integer;
begin
    k := 0;
    for n := 100 to 200 do
        if f(n) then
            k := k + 1;
    Writeln(k);
end.

PascalABC через целочисленные операции

function F(n: Integer; k: Integer := 5): Boolean;
var
    nn, z: Integer;
begin
    nn := 0;
    z := n;
    while z > 0 do
    begin
        nn := nn * 10 + z mod 10;
        z := z div 10;
    end;
    if (n = nn) and (k < 5) then
        result := True
    else if k = 0 then
        result := False
    else
        result := F(n + nn, k - 1);
end;

var
    n, k: Integer;
begin
    k := 0;
    for n := 100 to 200 do
        if f(n) then
            k := k + 1;
    Writeln(k);
end.

C++ через строки

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

string inverse(string s)
{
    string r = "";
    for (int i = s.length() - 1; i >= 0; i--)
        r += s[i];
    return r;
}

bool f(int n, int k = 5)
{
    if (k == 0)
        return false;
    n += stoi(inverse(to_string(n)));
    if (to_string(n) == inverse(to_string(n)))
        return true;
    return f(n, k - 1);
}

int main()
{
    int k = 0;
    for (int n = 100; n < 201; n++)
        if (f(n))
            k++;
    cout << k << endl;
}

C++ через целочисленные операции

#include <iostream>
using namespace std;

bool f(int n, int k = 5)
{
    int nn = 0;
    int z = n;
    while (z > 0)
    {
        nn = nn * 10 + z % 10;
        z /= 10;
    }
    if (n == nn && k < 5)
        return true;
    if (k == 0)
        return false;
    return f(n + nn, k - 1);
}

int main()
{
    int k = 0;
    for (int n = 100; n < 201; n++)
        if (f(n))
            k++;
    cout << k << endl;
}