I need help in this problem. I have tried all the test cases on Udebug as well, they are passing. But Vjudge is not accepting my code.↵
↵
↵
~~~~~↵
import java.io.IOException;↵
import java.util.ArrayList;↵
import java.util.HashMap;↵
import java.util.Scanner;↵
↵
class Investigation {↵
public static void main(String[] args)throws IOException {↵
Scanner s=new Scanner(System.in);↵
int test=s.nextInt();↵
StringBuilder print=new StringBuilder();↵
int c=1;↵
while(test--!=0){↵
print.append("Case "+c+": ");↵
c++;↵
char a[]=Integer.toString(s.nextInt()-1).toCharArray();↵
char b[]=s.next().toCharArray();↵
int m=s.nextInt();↵
if(m>=100){↵
print.append("0\n");↵
continue;↵
}↵
int r=solve(b,m);↵
int l=solve(a,m);↵
int ans=r-l;↵
print.append(ans+"\n");↵
}↵
System.out.println(print.toString());↵
}↵
public static int solve(char a[],int m){↵
int n=a.length;↵
HashMap<ArrayList<Integer>,Integer> map=new HashMap<>();↵
ArrayList<Integer> temp=new ArrayList<>();↵
temp.add(0);temp.add(0);temp.add(1);↵
map.put(temp,1);↵
for(int i=1;i<=n;i++){↵
int cd=a[i-1]-48;↵
HashMap<ArrayList<Integer>,Integer> curr=new HashMap<>();↵
for(int p=0;p<=9;p++){↵
for(ArrayList<Integer> t:map.keySet()){↵
int x=t.get(0);↵
int y=t.get(1);↵
int z=t.get(2);↵
int nx=(x*10+p)%m;↵
int ny=(y+p)%m;↵
int val=map.get(t);↵
if(p<cd){↵
ArrayList<Integer> te=new ArrayList<>();↵
te.add(nx);te.add(ny);te.add(0);↵
curr.put(te,curr.getOrDefault(te,0)+val);↵
}↵
else if(p==cd){↵
if(z==0){↵
ArrayList<Integer> te=new ArrayList<>();↵
te.add(nx);te.add(ny);te.add(0);↵
curr.put(te,curr.getOrDefault(te,0)+val);↵
}↵
if(z==1){↵
ArrayList<Integer> te2=new ArrayList<>();↵
te2.add(nx);te2.add(ny);te2.add(1);↵
curr.put(te2,curr.getOrDefault(te2,0)+val);↵
}↵
}↵
else{↵
if(z==0){↵
ArrayList<Integer> te=new ArrayList<>();↵
te.add(nx);te.add(ny);te.add(0);↵
curr.put(te,curr.getOrDefault(te,0)+val);↵
}↵
}↵
}↵
}↵
map=curr;↵
}↵
int ans=0;↵
for(ArrayList<Integer> t:map.keySet()){↵
if(t.get(0)==0&&t.get(1)==0){↵
ans+=map.get(t);↵
}↵
}↵
return ans↵
↵
import java.io.DataInputStream;↵
import java.io.FileInputStream;↵
import java.io.IOException;↵
↵
class Investigation {↵
static class Reader↵
{↵
final private int BUFFER_SIZE = 1 << 16;↵
private DataInputStream din;↵
private byte[] buffer;↵
private int bufferPointer, bytesRead;↵
↵
public Reader()↵
{↵
din = new DataInputStream(System.in);↵
buffer = new byte[BUFFER_SIZE];↵
bufferPointer = bytesRead = 0;↵
}↵
↵
public Reader(String file_name) throws IOException↵
{↵
din = new DataInputStream(new FileInputStream(file_name));↵
buffer = new byte[BUFFER_SIZE];↵
bufferPointer = bytesRead = 0;↵
}↵
↵
public String readLine() throws IOException↵
{↵
byte[] buf = new byte[64]; // line length↵
int cnt = 0, c;↵
while ((c = read()) != -1)↵
{↵
if (c == '\n')↵
break;↵
buf[cnt++] = (byte) c;↵
}↵
return new String(buf, 0, cnt);↵
}↵
↵
public int nextInt() throws IOException↵
{↵
int ret = 0;↵
byte c = read();↵
while (c <= ' ')↵
c = read();↵
boolean neg = (c == '-');↵
if (neg)↵
c = read();↵
do↵
{↵
ret = ret * 10 + c - '0';↵
} while ((c = read()) >= '0' && c <= '9');↵
↵
if (neg)↵
return -ret;↵
return ret;↵
}↵
↵
public long nextLong() throws IOException↵
{↵
long ret = 0;↵
byte c = read();↵
while (c <= ' ')↵
c = read();↵
boolean neg = (c == '-');↵
if (neg)↵
c = read();↵
do {↵
ret = ret * 10 + c - '0';↵
}↵
while ((c = read()) >= '0' && c <= '9');↵
if (neg)↵
return -ret;↵
return ret;↵
}↵
↵
public double nextDouble() throws IOException↵
{↵
double ret = 0, div = 1;↵
byte c = read();↵
while (c <= ' ')↵
c = read();↵
boolean neg = (c == '-');↵
if (neg)↵
c = read();↵
↵
do {↵
ret = ret * 10 + c - '0';↵
}↵
while ((c = read()) >= '0' && c <= '9');↵
↵
if (c == '.')↵
{↵
while ((c = read()) >= '0' && c <= '9')↵
{↵
ret += (c - '0') / (div *= 10);↵
}↵
}↵
↵
if (neg)↵
return -ret;↵
return ret;↵
}↵
↵
private void fillBuffer() throws IOException↵
{↵
bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);↵
if (bytesRead == -1)↵
buffer[0] = -1;↵
}↵
↵
private byte read() throws IOException↵
{↵
if (bufferPointer == bytesRead)↵
fillBuffer();↵
return buffer[bufferPointer++];↵
}↵
↵
public void close() throws IOException↵
{↵
if (din == null)↵
return;↵
din.close();↵
}↵
}↵
public static void main(String[] args)throws IOException {↵
Reader s=new Reader();↵
int test=s.nextInt();↵
int c=1;↵
while(test--!=0){↵
char a[]=Long.toString(s.nextLong()-1).toCharArray();↵
char b[]=Long.toString(s.nextLong()).toCharArray();↵
int m=s.nextInt();↵
if(m>=100){↵
System.out.println("Case "+c+": 0");↵
c++;↵
continue;↵
}↵
long r=solve(b,m);↵
long l=solve(a,m);↵
// System.out.println(l+" "+r);↵
long ans=r-l;↵
System.out.println("Case "+c+": "+ans);↵
c++;↵
}↵
}↵
public static long solve(char a[],int m){↵
int n=a.length;↵
long dp[][][][]=new long[n+1][m][m][2];↵
dp[0][0][0][1]=1;↵
for(int i=1;i<=n;i++){↵
int cd=a[i-1]-48;↵
for(int p=0;p<=9;p++){↵
for(int j=0;j<m;j++){↵
int nj=(j*10+p)%m;↵
for(int k=0;k<m;k++){↵
int nk=(k+p)%m;↵
if(p<cd){↵
dp[i][nj][nk][0]+=dp[i-1][j][k][0]+dp[i-1][j][k][1];↵
}↵
else if(p==cd){↵
dp[i][nj][nk][0]+=dp[i-1][j][k][0];↵
dp[i][nj][nk][1]+=dp[i-1][j][k][1];↵
}↵
else{↵
dp[i][nj][nk][0]+=dp[i-1][j][k][0];↵
}↵
}↵
}↵
}↵
}↵
return dp[n][0][0][1]+dp[n][0][0][0];↵
}↵
}↵
↵
↵
~~~~~↵
↵
Here's the problem [Link](https://vjudge.net/problem/LightOJ-1068)↵
↵
↵
↵
~~~~~↵
import java.util.ArrayList;↵
import java.util.HashMap;↵
import java.util.Scanner;↵
↵
class Investigation {↵
public static void main(String[] args)throws IOException {↵
Scanner s=new Scanner(System.in);↵
int test=s.nextInt();↵
StringBuilder print=new StringBuilder();↵
int c=1;↵
while(test--!=0){↵
print.append("Case "+c+": ");↵
c++;↵
char a[]=Integer.toString(s.nextInt()-1).toCharArray();↵
char b[]=s.next().toCharArray();↵
int m=s.nextInt();↵
if(m>=100){↵
print.append("0\n");↵
continue;↵
}↵
int r=solve(b,m);↵
int l=solve(a,m);↵
int ans=r-l;↵
print.append(ans+"\n");↵
}↵
System.out.println(print.toString());↵
}↵
public static int solve(char a[],int m){↵
int n=a.length;↵
HashMap<ArrayList<Integer>,Integer> map=new HashMap<>();↵
ArrayList<Integer> temp=new ArrayList<>();↵
temp.add(0);temp.add(0);temp.add(1);↵
map.put(temp,1);↵
for(int i=1;i<=n;i++){↵
int cd=a[i-1]-48;↵
HashMap<ArrayList<Integer>,Integer> curr=new HashMap<>();↵
for(int p=0;p<=9;p++){↵
for(ArrayList<Integer> t:map.keySet()){↵
int x=t.get(0);↵
int y=t.get(1);↵
int z=t.get(2);↵
int nx=(x*10+p)%m;↵
int ny=(y+p)%m;↵
int val=map.get(t);↵
if(p<cd){↵
ArrayList<Integer> te=new ArrayList<>();↵
te.add(nx);te.add(ny);te.add(0);↵
curr.put(te,curr.getOrDefault(te,0)+val);↵
}↵
else if(p==cd){↵
if(z==0){↵
ArrayList<Integer> te=new ArrayList<>();↵
te.add(nx);te.add(ny);te.add(0);↵
curr.put(te,curr.getOrDefault(te,0)+val);↵
}↵
if(z==1){↵
ArrayList<Integer> te2=new ArrayList<>();↵
te2.add(nx);te2.add(ny);te2.add(1);↵
curr.put(te2,curr.getOrDefault(te2,0)+val);↵
}↵
}↵
else{↵
if(z==0){↵
ArrayList<Integer> te=new ArrayList<>();↵
te.add(nx);te.add(ny);te.add(0);↵
curr.put(te,curr.getOrDefault(te,0)+val);↵
}↵
}↵
}↵
}↵
map=curr;↵
}↵
int ans=0;↵
for(ArrayList<Integer> t:map.keySet()){↵
if(t.get(0)==0&&t.get(1)==0){↵
ans+=map.get(t);↵
}↵
}↵
return ans
↵
import java.io.DataInputStream;↵
import java.io.FileInputStream;↵
import java.io.IOException;↵
↵
class Investigation {↵
static class Reader↵
{↵
final private int BUFFER_SIZE = 1 << 16;↵
private DataInputStream din;↵
private byte[] buffer;↵
private int bufferPointer, bytesRead;↵
↵
public Reader()↵
{↵
din = new DataInputStream(System.in);↵
buffer = new byte[BUFFER_SIZE];↵
bufferPointer = bytesRead = 0;↵
}↵
↵
public Reader(String file_name) throws IOException↵
{↵
din = new DataInputStream(new FileInputStream(file_name));↵
buffer = new byte[BUFFER_SIZE];↵
bufferPointer = bytesRead = 0;↵
}↵
↵
public String readLine() throws IOException↵
{↵
byte[] buf = new byte[64]; // line length↵
int cnt = 0, c;↵
while ((c = read()) != -1)↵
{↵
if (c == '\n')↵
break;↵
buf[cnt++] = (byte) c;↵
}↵
return new String(buf, 0, cnt);↵
}↵
↵
public int nextInt() throws IOException↵
{↵
int ret = 0;↵
byte c = read();↵
while (c <= ' ')↵
c = read();↵
boolean neg = (c == '-');↵
if (neg)↵
c = read();↵
do↵
{↵
ret = ret * 10 + c - '0';↵
} while ((c = read()) >= '0' && c <= '9');↵
↵
if (neg)↵
return -ret;↵
return ret;↵
}↵
↵
public long nextLong() throws IOException↵
{↵
long ret = 0;↵
byte c = read();↵
while (c <= ' ')↵
c = read();↵
boolean neg = (c == '-');↵
if (neg)↵
c = read();↵
do {↵
ret = ret * 10 + c - '0';↵
}↵
while ((c = read()) >= '0' && c <= '9');↵
if (neg)↵
return -ret;↵
return ret;↵
}↵
↵
public double nextDouble() throws IOException↵
{↵
double ret = 0, div = 1;↵
byte c = read();↵
while (c <= ' ')↵
c = read();↵
boolean neg = (c == '-');↵
if (neg)↵
c = read();↵
↵
do {↵
ret = ret * 10 + c - '0';↵
}↵
while ((c = read()) >= '0' && c <= '9');↵
↵
if (c == '.')↵
{↵
while ((c = read()) >= '0' && c <= '9')↵
{↵
ret += (c - '0') / (div *= 10);↵
}↵
}↵
↵
if (neg)↵
return -ret;↵
return ret;↵
}↵
↵
private void fillBuffer() throws IOException↵
{↵
bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);↵
if (bytesRead == -1)↵
buffer[0] = -1;↵
}↵
↵
private byte read() throws IOException↵
{↵
if (bufferPointer == bytesRead)↵
fillBuffer();↵
return buffer[bufferPointer++];↵
}↵
↵
public void close() throws IOException↵
{↵
if (din == null)↵
return;↵
din.close();↵
}↵
}↵
public static void main(String[] args)throws IOException {↵
Reader s=new Reader();↵
int test=s.nextInt();↵
int c=1;↵
while(test--!=0){↵
char a[]=Long.toString(s.nextLong()-1).toCharArray();↵
char b[]=Long.toString(s.nextLong()).toCharArray();↵
int m=s.nextInt();↵
if(m>=100){↵
System.out.println("Case "+c+": 0");↵
c++;↵
continue;↵
}↵
long r=solve(b,m);↵
long l=solve(a,m);↵
// System.out.println(l+" "+r);↵
long ans=r-l;↵
System.out.println("Case "+c+": "+ans);↵
c++;↵
}↵
}↵
public static long solve(char a[],int m){↵
int n=a.length;↵
long dp[][][][]=new long[n+1][m][m][2];↵
dp[0][0][0][1]=1;↵
for(int i=1;i<=n;i++){↵
int cd=a[i-1]-48;↵
for(int p=0;p<=9;p++){↵
for(int j=0;j<m;j++){↵
int nj=(j*10+p)%m;↵
for(int k=0;k<m;k++){↵
int nk=(k+p)%m;↵
if(p<cd){↵
dp[i][nj][nk][0]+=dp[i-1][j][k][0]+dp[i-1][j][k][1];↵
}↵
else if(p==cd){↵
dp[i][nj][nk][0]+=dp[i-1][j][k][0];↵
dp[i][nj][nk][1]+=dp[i-1][j][k][1];↵
}↵
else{↵
dp[i][nj][nk][0]+=dp[i-1][j][k][0];↵
}↵
}↵
}↵
}↵
}↵
return dp[n][0][0][1]+dp[n][0][0][0];↵
}↵
}↵
↵
↵
~~~~~↵
↵
Here's the problem [Link](https://vjudge.net/problem/LightOJ-1068)↵
↵
