Без двух нулей подряд, как решить??

Question

[DigiDiz]

Требуется посчитать количество последовательностей длины n, состоящих из цифр от 0 до k−1 таких, что никакие два соседних элемента последовательности не равны нулю одновременно.

Входные данные

Заданы два натуральных числа N и K (2≤K≤10; 2≤N; 4≤N+K≤18).

Выходные данные

Необходимо вывести целое число — ответ на задачу.

Попробовал решить, но кажется фигню полную сделал:

n = int(input())
k = int(input())
d[1] = k[-1]
d[0][1] = 0
for i in range(2):
d[i] = (d[i-1]+d0[i-1]) * (k-1)
d[0][i] = d[i-1]
print(d[n]+d0[n])

Comments

[Drill]

И где свой вариант решения?

[DigiDiz]

Drill, в голову ничего не идёт

[DigiDiz]

n = int(input())
k = int(input())
d[1] = k[-1]
d[0][1] = 0
for i in range(2):
d[i] = (d[i-1]+d0[i-1]) * (k-1)
d[0][i] = d[i-1]
print(d[n]+d0[n])

Сделал что-то вроде этого, но кажется фигня полная.

[Alexa2007]

DigiDiz, Точняк! Фигня полная.

[Zanak]

если я правильно понял задачу, то вам стоит проанализировать условия на n и k.
у меня получилось, что k=2, а n принадлежит [2..16].
в таком случае условие зазвучит как: посчитайте количество возможных последовательностей из 0 и 1, при условии, что ни где не встречается 2 нуля подряд и имеющие длинны из диапазона [2..16]

последний шаг оставляю вам на самостоятельную реализацию :)

[maksim-mshp]

Если ты решаешь курс Сириус. Информатика. Регионы. Ноябрь 2021. 7–8 класс, то присоединяйся к беседе по ссылке: https://t.me/joinchat/r1UNFzO4JcZhYTky

Answer 1

[Михаил]

я не уверен правильно ли понял тебя, но вот самый наглядный пример:

n = int(input('Input n: '))
k = int(input('Input k: '))

# 2≤K≤10; 2≤N; 4≤N+K≤18

while True:
	if 2 <= k:
		if k <= 10:
			if 2 <= n:
				a = n+k
				if 4 <= a:
					if a <= 18:
						print('Hello world!')
						print('Numbers: \nk='+str(k)+'\nn='+str(n)+'\nn+a='+str(a))
						break;
					else:
						a = a-1
				else:
					a = a+1
			else:
				n = n+1
		else:
			k = k-1
	else:
		k = k+1

exit = input()