```
public class CombsMaxDiffConsec {
static int u=100,v=100,w=100;
static long c,memoG[][][]=new long[u][v][w];
public static void main(String[] args) {
int i,j,k;
long t=time();
System.out.println("Initialising.");
for(i=0;i<u;i++)
for(j=0;j<u;j++)
for(k=0;k<w;k++)
memoG[i][j][k]=-1;
System.out.println("Time: "+(time()-t)/1000.0+" seconds");
t=time();
System.out.println("\nDoing test cases.");
// begin test cases
a(naive(10,4,2)==7);
a(naive(5,2,3)==7);
a(naive(5,3,3)==8);
a(naive(16,4,100)==1820);
for(i=0;i<10;i++)
for(j=0;j<=i;j++)
for(k=2;k<=i-j;k++)
a(f(i,j,k)==naive(i,j,k));
// end test cases
System.out.println("Time: "+(time()-t)/1000.0+" seconds");
t=time();
System.out.println("\nUsing fast algorithm:");
System.out.println("f(80,13,6) = "+f(80,13,6));
System.out.println("Time: "+(time()-t)/1000.0+" seconds");
t=time();
System.out.println("\nUsing naive algorithm:");
System.out.println("f(80,13,6) = "+naive(80,13,6));
System.out.println("Time: "+(time()-t)/1000.0+" seconds");
}
static long f(int n,int k,int x) {
if(k>n||x<2) return 0;
if(k<1||k==n) return 1;
if(k==1) return n;
int i;
long r=0;
for(i=k;i<=n;i++)
r+=g(i,k,x);
return r;
}
static long g(int n,int k,int x) {
if(k<1||k>n) return 0;
if(k==1) return 1;
if(n<u&&k<v&&x<w&&memoG[n][k][x]!=-1) return memoG[n][k][x];
int i;
long r=0;
for(i=Math.max(1,n+1-x);i<=n-1;i++)
r+=g(i,k-1,x);
if(n<u&&k<v&&x<w) memoG[n][k][x]=r;
return r;
}
static long naive(int n,int k,int x) {
if(k>n||x<2) return 0;
if(k<1||k==n) return 1;
if(k==1) return n;
c=0;
naive2(k,0,n,x);
return c;
}
static void naive2(int r,int j,int n,int x) {
if(r==0) {
c++;
return;
}
int i,m=n-r+1;
if(j>0) m=Math.min(m,j+x-1);
for(i=j;i<m;i++)
naive2(r-1,i+1,n,x);
}
static void a(boolean b) {
if(!b) throw new AssertionError();
}
static long time() {
return System.currentTimeMillis();
}
}
```