Почему в случае 1 10 ответ 9 если 0 тоже число в котором не идут два подряд ноля?

Просто 2 раза получил ВА, поменял на 9 и АС.

a valid n digit number can be found from valid n-1 and n-2 digit numbers

Edited by author 16.02.2021 13:56

Edited by author 16.02.2021 13:56

and also
N=6,K=10
N=7,K=10
N=6,K=2

Can anyone please tell me in tabular form what is are the values of answers for the above values. My algorithm is almost right and it is calculating accurately as far as I know but it is always responding No on test # 2. Please help!!! I am stuck and dissappointed.... :(

Edited by author 19.02.2016 19:17

why is  k =10 and n =2 output =90

I got AC with 0.015s,216Kb
I had read the problem several time until understand.
N is the length of the digit number.
It will be something like that
a1 a2 a3 ...an
for each ai in a1 a2 a3..an, 0 <= ai < K.
The output number i used was interger (compiler C++ 2010). (no big number).

hope it can help you.
And sorry for my poor English.

Edited by author 25.04.2014 23:05

This is my code:

import time
import sys
sys.setrecursionlimit(100000)

n = int(input("Enter N (for digits): "))
k = int(input("Enter K: "))

rangeVar = pow(k, n) - pow(k, n-1)
starter = pow(k, n) - rangeVar
counter = 0

start = time.clock()
def calc(i):
    global starter, rangeVar, counter, n, k

    temp = str(i)

    if i == pow(k, n):
        return counter
    else:
        for j in range(len(temp) - 1):
            if temp[j] == '0' and temp[j+1] == '0':
                counter += 1
        calc(i+1)

calc(starter)
end = time.clock()
print(rangeVar - counter)
print(end - start)

My English is poor, but I read it by a large time and I understood.
N=2,K=10  ==>it's a "2 digits 10-base"  10,11,...98,99... in Chinese "2位的十进制数字"

I got 89 for the example: 2 10, not 90, why? Any one know this?

i solved this by using Optimized backtracking and i don't understand why it needs DP?

Edited by author 21.01.2016 20:56

Edited by author 21.01.2016 20:56

First digit of the numbers will start from 1 and end with non-zero digit.and there will not present any successive zero.

Edited by author 27.10.2014 14:27

For example, I have n = 3 and k = 2, which means 0 and 1
Then there is 3 possible ways to made a number: 101, 111, 110
How to calculate this moment, when n is more than k?????

I think l have solved this problem,but i got WA on test #2.

help plz,thx!