Question

Сколькими способами из данного слова можно составить слово CAT? Если индекс буквы C равен i, индекс буквы A равен j, а индекс буквы T равен k, то должновыполняться условие iПоскольку эти число может быть достаточно большим, выведите в качестве ответа остаток отделения этого числа на 10000019107 + 19.Формат входных данных:В первой строке содержится непустая последовательность, состоящая из символов C, A, T (заглавных букв латинского алфавита), в том порядке, в котором они появляются на экране. Последовательность имеет длину не более 105 символов.Гарантируется, что последовательность содержит хотя бы один символ C, хотя бы один символA и хотя бы один символ T.Формат выходных данных:Выведите единственное целое число — остаток от деления на 10000019107 + 19 количестваспособов, которыми может сформировать слово CAязык питон

Answer 1

def count_ways(s):

c_indices = [i for i in range(len(s)) if s[i] == 'C']

a_indices = [i for i in range(len(s)) if s[i] == 'A']

t_indices = [i for i in range(len(s)) if s[i] == 'T']

ways = 0

for c in c_indices:

for a in a_indices:

if a > c:

for t in t_indices:

if t > a:

ways += 1

return ways

def main():

s = input().strip()

ways = count_ways(s)

print(ways % (107 + 19))

if __name__ == '__main__':

main()

Answer 2

Для решения этой задачи, вы можете использовать динамическое программирование. Создайте трехмерный массив (трехмерную таблицу) dp, где dp[i][j][k] будет представлять количество способов составить слово "CAT" из первых i букв входной последовательности, имея j букв 'A' и k букв 'T'. Затем обновите этот массив с учетом следующей буквы в последовательности.

Вот пример кода на Python для решения этой задачи:

pythonCopy code
MOD = 10000019107 + 19

def countCATWays(s):
    n = len(s)
    dp = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]

    for i in range(n + 1):
        for j in range(n + 1):
            for k in range(n + 1):
                if i + j + k == 0:
                    dp[i][j][k] = 1
                else:
                    dp[i][j][k] = 0

    for i in range(1, n + 1):
        for j in range(n + 1):
            for k in range(n + 1):
                dp[i][j][k] = dp[i - 1][j][k]
                if s[i - 1] == 'A':
                    if j > 0:
                        dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - 1][k]) % MOD
                elif s[i - 1] == 'T':
                    if k > 0:
                        dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k - 1]) % MOD

    return dp[n][n][n]

s = input()
result = countCATWays(s)
print(result)

Этот код сначала инициализирует трехмерный массив dp, а затем заполняет его, учитывая буквы во входной последовательности. В конце он выводит остаток от деления количества способов на 10000019107 + 19.