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

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

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)

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
    class Program
    {
        static void Main(string[] args)
        {
            int k;
            int n;
            do
            {
            do{
             n = int.Parse(Console.ReadLine());
            } while (!(n >= 2));
            do
            {
               k = int.Parse(Console.ReadLine());
            } while (!(k >= 2 && k <= 10));
            } while (!(n + k <= 18));
            int start = (int)Math.Pow(10, n - 1);
            int end = 0;
            int check = start;
            int BigCount = 0;
                for (int i = n - 1; i >= 0; i--)
                    end += (k - 1) * (int)Math.Pow(10, i);
                int h = end - start + 1;
                int o = 0;
                for (int l = 0; l < n; l++)
                {
                    o += h % 10 * (int)Math.Pow(k, l);
                    h = h / 10;
                }
                for (int i = 0; i < o; i++)
                {
                    int count = 0;
                    double p = check;
                    for (int j = 0; j < n / 2; j++)
                    {
                        if ((p % 10 + p / 10 % 10) > 0) count++;
                        p = p / 100;
                    }
                    if (count != 0) BigCount++;
                    check++;
                    count = 0;
                    p = check;
                    int r = 0;
                    int m = 0;
                    for (int l = 0; l < n; l++)
                    {
                        if (p % 10 == k)
                        {
                            count++;
                            m += (10 - k) * (int)Math.Pow(10, l);
                            r = 10 - k;
                        }
                        p += r;
                        p = (int)p / 10;
                    }
                    check += m;
                }

                Console.Write(BigCount);
            }
        }
Норм решение?

Edited by author 16.01.2017 04:29

Edited by author 16.01.2017 04:30

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

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

Edited by author 19.02.2016 19:17

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 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

var n,k,tc:integer;
    a:array [1..20] of integer;
procedure gen(x:integer);
 var i:integer;
 begin
   if x = n+1 then
      inc(tc)
   else
    begin
    if x=1 then
           for i:=1 to k-1 do
       begin
       a[x]:=i;
       gen(x+1);
       end
    else
     for i:=0 to k-1 do
       begin
       a[x]:=i;
       if (a[x-1]=0) then
       begin
        if (i=0) then
           begin
              inc(x);
              dec(x);
           end;
        end
        else
            gen(x+1);
       end;
    end;
 end;
 begin
  readln(n);
  readln(k);
  gen(1);
  writeln(tc);
 end.
What is it!

Give me example plz

Brute force (полный перебор) method gives Time Limit Exceeded. In Java it takes 6 seconds to for parameters N=8, K=10. So the clever method (which uses recurrent calls) is the way to go.

i have tested it, and it look like working, can you say me is this look like correct, or can you advise me how to fix it?)

#include <iostream>

using namespace std;

int main()
{
    unsigned __int64 n, b, i, r, sum = 0;
    cin>>n>>b;
    for (i = 2; i <= n - 1; i++)
    {
        r = (n - 1) / i + (n - 1) % i;
        sum += r * pow(double(b - 1), double(n - i));
    }
    cout<<unsigned __int64(pow(double(b), double(n)) - pow(double(b), double(n - 1)) - sum)<<endl;
    //system("pause");
}

#include <iostream>
#include <string>
#include <stdio.h>
#include <cmath>

using namespace std;

int n,k,col=0;

int main() {

    cin>>n>>k;
    int bo=0;
    int z,z1;
    z=pow(10.0,(n-1));
    z1=pow(10.0,n);
    for(int i=z;i<z1;++i)
    {
        for (int v = i; v; v /= 10)
        {
            if (((v%10)>=k) || (((v%10)==0) && ((v%100)==0)))  {bo=1; v=0;};
        }
        if (!bo) ++col;
        bo=0;
    }
    cout<<col;
    return 0;
}