Задача: Бомбомбини Гузини
Бомбомбини Гузини решил сменить имя, чтобы Бомбардиро Крокодило было труднее его выследить. А именно, Бомбомбини решил заменить первую часть своего имени «Бомбом» на какое-нибудь натуральное число а. При этом Гузини хочет, чтобы его имя не сильно поменялось, поэтому он хочет, чтобы а удовлетворяло следующим условиям:
1. а состоит из чётного числа цифр.
2. Первая половина в записи а совпадает со второй половиной в записи а.
Например, числа 33 и 147147 Гузини подойдут, а 333 и 147741 — нет.
Также по правилам страны, в которой живёт Гузини, в имени любого гражданина могут встречаться не любые натуральные
числа, а только числа от 1 до N.
Ваша задача посчитать, сколько вариантов смены имени есть у Бомбомбини.
Формат входных данных:
На вход подаётся единственное целое число N (1 < N < 1012)
1 Ответ
Решение:
Для k=1: base=11, X от 1 до 9 (включительно). Например, 11*1=11, 11*2=22, …, 11*9=99.
Для k=2: base=101, X от 10 до 99. Например, 101*10=1010, 101*11=1111, …, 101*99=9999.
Для k=3: base=1001, X от 100 до 999.
И так далее.
Проверка на примерах:
N=33:
k=1: base=11, lower=1, upper=min(9, 33//11=3) = 3. count += 3.
k=2: base=101, lower=10, upper=min(99, 33//101=0) -> нет подходящих.
Ответ: 3.
N=1390:
k=1: base=11, upper=min(9, 1390//11=126) -> 9-1+1=9.
k=2: base=101, upper=min(99, 1390//101=13) -> 13-10+1=4.
k=3: base=1001 > 1390? Нет, 1001<=1390, но upper=min(999, 1390//1001=1) -> lower=100, upper=1 -> нет (100>1).
Итого: 9+4=13.
Ответ совпадает с примерами.
Итоговый код:
