Дано натуральное число n. Требуется найти кол-во цифр '0', встретившихся в записи чисел от 1 до n, n <= 10^16. Очевидно, тривиальный алгоритм будет работать долго.
Ответ
Как и для большинства олимпиадных задач, для этой нашлось довольно короткое и быстрое решение. Решил ее так: рассматривал заданное число N по цифрам от младших разрядов к старшим. На каждом шаге имеются:
цифра в текущем разряде
число - младшие разряды (все что справа от текущей позиции)
число - старшие разряды (все что слева от текущей позиции)
1) Для первого разряда верно утверждение, что 0 там будет встречаться ровно такое число раз, которое осталось в старших разрядах. Т.е. для числа 234, 0 в разрядах единиц будет встречаться 23 раза, для 105 - 10 раз и т.д.
2) Для остальных разрядов (десятки, сотни, тысячи и т.д.) нужно рассмотреть два случая - когда цифра больше нуля и когда она равна нулю:
Когда цифра в разряде больше нуля, то логика практически такая же как и для первого разряда: На этой позиции 0 будет встречаться ровно такое число раз, которое осталось в старших разрядах, но умноженное на 10 в степени текущего разряда. Поясню на примере: число 123. На позиции двойки 0 будет встречаться 1 * 10 = 10 раз - для чисел 100 - 109. Или, число 2308: на позиции тройки 0 будет встречаться 2 * 100 = 200 раз. Это числа 1000-1099 и 2000-2099
Когда цифра в разряде равна нулю, то НЕВЕРНО утверждать, что 0 в ней встретиться столько раз, сколько было в предыдущем случае (когда цифра не равна нулю). Сейчас он там встретится меньшее число раз. Опять сразу перейду к примеру: число 201. сколько раз 0 будет стоять в разряде десятков? Ответ - 12. Это числа 100-109, 200 и 201. Так как же получить это число?.. Для этого нужно из числа в старших разрядах вычесть единицу, умножить его на 10 в степени текущего разряда и прибавить к этому произведению число в младших разрядах. И еще добавить единицу. Т.е. для приведенного выше числа 201 это будет 1 * 10 + 1 + 1 = 12. Дополнительная единица нужна, чтобы не потерять число, когда младшие разряды равно нулю, это 200 в данном случае. (Долго шел к этому пункту, и извиняюсь за невнятное объяснение. Кому будет проще, то это действие у меня вызывает аналогию с вычитанием в столбик, когда вычитаемое содержит нули)
Ну и собственно, реализация алгоритма:
int rank = 1; // Номер разряда (начинаем с младших)
long res = 0; // Результат
long high = N; // Число в старших разрядах (изначально равно N)
long low = 0; // Число в младших разрядах (изначально равно 0)
while (high > 0)
{
long digit = high % 10; // Текущая цифра
high = high / 10; // Уменьшаем число в старших разрядах
if (rank > 1 && digit == 0)
{
res += ((high - 1) * rank) + (low + 1); // Случай 2.2
}
else
{
res += high * rank; // Случаи 1 и 2.1
}
low += rank * digit; // Увеличиваем число в младших разрядах
rank *= 10; // Переходим к следующему разряду
}
// output res
Комментариев нет:
Отправить комментарий