111 211
3
10

the answer is 0 or 1... why?

thanks you..

who know this problem!Time limit exceeded 7 help me please

Edited by author 13.06.2013 22:47

Edited by author 13.06.2013 22:48

96 96 2 2

ans: 1

Well, after all, I solved this problem, but it took a long time for me to find all mistakes in my calculations.

My idea was to generate F[N,K] in a O(log(N)*log(N)) time, which means an amount of numbers with N or less digits (in a certain base) with K one-digits. Then I wrote a function C(N, K), which finds an amount of numbers with K one-digits in [1, N] using F and deleting its first digit every time. Actually it's all about dynamic programming.

But I think there must be more clear and efficient solutions, than mine (O(log(N)*log(N)) for time and memory). If it does, please, would you be so kind to share it?

Why does my program always get WA#1?
I have tried all the tests in the forum, and all of them are correct.
I think there is a very strange mistake in my program.

#include <stdio.h>
#define re(i, n) for (int i=0; i<n; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
const int MAXN = 32;
int b, k;
long long c[MAXN][MAXN], res = 0;
void prp(void)
{
     re(i, MAXN) re(j, MAXN) if (i < j) c[i][j] = 0; else if (!j) c[i][j] = 1; else c[i][j] = c[i - 1][j - 1] * i / j;
}
long long xxx(long long v)
{
     int a[MAXN], len = 0;
     long long r0 = 0;
     while (v) {a[len++] = v % b; v /= b;}
     int k0 = k;
     rre(i, len) {
        int x = a[i];
        if (x >= 2) {r0 += c[i + 1][k0]; break;}
        if (x) {r0 += c[i][k0]; k0--;}
     }
     return r0;
}
int main(void)
{
    long long s, t;
    scanf("%lld%lld%d%d", &s, &t, &k, &b);
    prp();
    res = xxx(t + 1) - xxx(s);
    printf("%lld\n", res);
    return 0;
}


Edited by author 04.09.2010 20:07

It says:
17=2^4+2^0
18=2^4+2^1
20=2^4+2^2

But, since the limit is [15;20], 16 must also be included:
16=2^3+2^3

This is my program:
program Ural1057;

var
  a,l,r,n,k,ans:longint;
  p:array[0..200]of longint;
  d:array[0..200]of qword;
  num:qword;

procedure dfs(o:longint);

var
  i:longint;

begin
  for i:=p[o-1]+1 to 30 do
    begin
      p[o]:=i;
      num:=num+d[p[o]];
      if num>r then
      begin
        num:=num-d[p[o]];
        exit;
      end;
      if o=n then begin
        if l<=num then inc(ans);
      end else
      dfs(o+1);
      num:=num-d[p[o]];
    end;
end;

begin
  readln(l,r,n,k);
  fillchar(p,sizeof(p),0);
  d[0]:=1;
  a:=1;
  while (d[a-1]<r)and(a<40) do
    begin
      d[a]:=d[a-1]*k;
      inc(a);
    end;
  ans:=0;
  num:=0;
  p[0]:=-1;
  dfs(1);
  writeln(ans);
end.

I don't know why Wa6, who can help me?

All of test you gave in discuss , my program took the right answer , but it wa in test 2 . Can you help me ?

Edited by author 25.11.2008 22:17

Edited by author 25.11.2008 22:17

Edited by author 25.11.2008 22:19

My program gives right answer all tests in the forum but T've got WA#1

my program output result:

1 1000000000 3 13   -> 84

1 1 2 2 ---> 0

1 100 2 4 ->6

1 300 4 8 ->0

1 400 4 2 ->111

1 2147483647 13 3 --> 77520

1 2147483647 20 2  --> 84672315

1 3 1 2 --> 2

is right?

if full right , but i alway  wa #7,   who can give much testdata to me ?


Edited by author 03.09.2008 10:39

Edited by author 05.09.2008 02:08

I input test data: 100 200 3 3
Is the example  right?

100 = 3^ 4 + 2 * (3^2) + 1

109 = 3^4 + 3^3 + 3^0

117 = 3^4 + 3^2 + 3^1

141 = 3 ^4 + 2* (3^3) + 2 * 3



which model is  right ? or all right ?

Edited by author 07.08.2008 08:27

what's the text8?

what's the test 1?
i had compared with a ACed code many times.
there's nothing wrong. but i always wa on test 1?

who can help me?

I've investigated my old solution...

It doesn't pass tests like

1 8 2 3
1 900 2 10
1 123456789 4 10
1 999999999 8 10

but gets AC.

I used only 0.001 sec... it`s just O((log_B^N)^2).

u can check it here.
http://acm.timus.ru/status.aspx?space=1&pos=841174

This program compiles on my PC but I got compile error...
Please help me..
#include <iostream.h>
#include <math.h>
unsigned long fackt(int t)
{
    unsigned long tot=1;
    int h;
    for (h=1;h<=t;h++)
    tot*=h;
    return tot;
}
unsigned long f(int t, int t2)
{
if ((t<t2)||(t<=0)) return 0;
double o=1;
int p;
for(p=t-t2+1;p<=t;p++)
o*=p;
o/=fackt(t2);
return (unsigned long)o;
}
unsigned long getres(unsigned long val,int k2,bool bb,int b)
{
if (k2==0) return 0;
unsigned long res=0;
int kk=(int)(log(val)/log(b)+1);
bool b2=false;
if (val-pow(b,kk-1)<pow(b,kk-2)) b2=true;
res+=f(kk-1,k2);
if (k2>1)res+=getres(unsigned long(val-pow(b,kk-1)),k2-1,b2,b);
if (bb)
{
int i=0;
    unsigned long buf=0;
    for (i=0;i<k2;i++)
    buf+=unsigned long(pow(b,kk-i-1));
    if ((val>=buf)&&(buf>0)) res++;
}
return res;
}
int main()
{

    unsigned long x,y;
    int k,b;
    cin>>x>>y>>k>>b;

    unsigned long l,u,total=0;

    l=getres(y,k,true,b);
    u=getres(x-1,k,true,b);

    cout<<l-u;

    return 0;
}