I've tried to use Lalescu Liviu's method described on the webboard, but my implementation has some minor bug I can't find. Can someone please help me by sending me ac program in pascal? In return, I can send some of my ac-ed programs...

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

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

96 96 2 2

ans: 1

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

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?

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

My program gives right answer all tests in the forum but T've got WA#2.Please give me some test
Thanks

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?

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

Test:
B = 3
K = 2
X = 90
Y = 100
Result:
2
Is it right?
If not what is the right result of this test and why?

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

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