Question

100 БАЛЛОВ Утраченный символ Имя входного файла: input.txt Имя выходного файла: output.txt Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Стёпа очень любит многоуровневые компьютерные игры. Особенно ему нравятся те игры, в которых в любой момент можно узнать, на каком по счету уровне он сейчас находится и сколько всего уровней имеется в этой игре. Обычно где-нибудь в углу экрана находится надпись, например «10/100», которая означает, что сейчас Стёпа находится на 10 уровне, а всего в игре 100 уровней. На днях Стёпа установил на свой компьютер новую игру, но оказалось, что разработчик для вывода на экран надписи с номерами уровней использовал шрифт, которого нет на Стёпином компьютере. Шрифт автоматически заменился на какой-то другой, в котором не поддерживается символ «/». Теперь два числа, которые должны были быть разделены, слились в одно, и Стёпу это невероятно расстраивает. Он подумал о том, что можно попробовать самому угадывать место, в котором должен стоять символ «/», но потом понял, что в некоторых случаях подходящих вариантов может быть несколько. Например, если на экране написано «1234», это может означать как то, что он находится на 1 уровне из 234, так и то, что он находится на 12 уровне из 34. Ему стало интересно, а сколько всего существует способов подставить символ «/» в надпись на экране так, чтобы надпись была корректной, то есть чтобы слева и справа от символа были корректные числа без лидирующих нулей и при этом левое число не превосходило правое. Помогите Стёпе ответить на этот вопрос. Формат входных данных На вход подается одно целое число N — надпись на экране Стёпы (11 ⩽ N < 10100000). Формат выходных данных В выходной файл необходимо вывести одно целое число — количество способов подставить символ «/» в надпись на экране так, чтобы она была корректной. Гарантируется, что хотя бы один такой способ существует

Answer 1

Ответ:

n = int(input())

k = len(str(n)) - 1

l = 0

while k >= len(str(n))//2 :

   if (n // 10k <= n % 10k) and (n // 10**(k-1) % 10 != 0):

           l += 1

   k -= 1

print(l)

Объяснение:

Answer 2

Для решения этой задачи можно воспользоваться динамическим программированием. Давайте создадим массив dp, где dp[i] будет обозначать количество способов подставить символ '/' для первых i цифр так, чтобы получившаяся надпись была корректной.

Пусть строка s представляет собой числовую надпись. Тогда для каждой позиции i (0 <= i < len(s)), мы можем рассмотреть два варианта:

1. Одно число: Мы можем просто добавить текущую цифру к предыдущему числу.
2. Два числа: Мы можем добавить '/' перед текущей цифрой и создать новое число, начиная с текущей цифры.

Для каждой позиции i, мы будем проверять оба варианта и обновлять dp[i] соответствующим образом.

После прохода по всей строке s, результат будет храниться в dp[len(s)].

Пример на Python:

pythonCopy code
def count_ways(s):
    n = len(s)
    MOD = 1000000007
    dp = [0] * (n + 1)
    dp[0] = 1  # Базовый случай: один способ для пустой строки
    
    for i in range(1, n + 1):
        dp[i] = dp[i - 1]  # Одно число
        
        if s[i - 2] != '0':  # Проверяем два числа
            num = int(s[i - 2:i])
            if 1 <= num <= 99:  # Условие на корректность
                dp[i] = (dp[i] + dp[i - 2]) % MOD
    
    return dp[n]

# Чтение входных данных
n = input()
result = count_ways(n)
print(result)

Этот код считывает число n из входа, вызывает функцию count_ways для подсчета количества способов и выводит результат.

Обратите внимание, что в данной реализации используется модуль 1000000007 для вычисления остатка при делении на больших числах, чтобы избежать переполнения.