printРабочее место участника

printЗадачи

1688. Номер страницы

Ограничения: время – 2s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (1) idea

Однажды робот-библиотекарь решил устроить ревизию. На одной из полок, среди экземпляров тридцать третьего издания Кормена, он нашел листок из условий одного древнего контеста. Роботу известен формат оформления условий, однако этот листок привел его в замешательство.
Обычно внизу каждой страницы условий есть надпись вида "Страница `i` из `n`", где `i` — номер страницы условий, а `n` — количество страниц в условиях. Однако на этом листе была всего одна длинная последовательность цифр. Видимо, принтер почему-то не напечатал ни одного символа кроме цифр. Таким образом, номера `i` и `n` слились в единую последовательность цифр.
Теперь понять, какой же был номер у найденной страницы, стало большой проблемой, и решений у этой задачи может быть много. Роботу стало интересно, сколько существует решений, но так как робот не предназначен для решения таких задач, он нуждается в вашей помощи. Страницы в условиях нумеруются от 1 до `n`, числа `i` и `n` записываются без ведущих нулей.
Выясните, сколько есть корректных надписей вида "Страница `i` из `n`", при удалении из которых всех символов кроме цифр получается заданная во входном файле строка.
Формат ввод
Входной файл содержит строку, состоящую только из цифр. Длина строки лежит в пределах от 1 до `200\ 000`, включительно.
Формат вывод
Выведите количество корректных надписей вида "Страница `i` из `n`", при удалении из которых всех символов кроме цифр получается заданная во входном файле строка.

Пример ввода

23507645

Пример вывода

3
В приведенном примере можно проинтерпретировать строку тремя способами:
"Страница 2 из 3507645"
"Страница 23 из 507645"
"Страница 2350 из 7645"
Источник: XIX Командный чемпионат школьников Санкт-Петербурга по программированию, 2011
loading