Investigation V Judge, Digit DP

Revision en4, by SLIMSHADYNICK, 2020-07-27 09:01:20

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

Tags #dp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English SLIMSHADYNICK 2020-07-27 09:01:20 8092
en3 English SLIMSHADYNICK 2020-07-27 06:32:11 24 Tiny change: 'n\n~~~~~\n//package DigitDp;\n\n\nimport j' -> 'n\n~~~~~\nimport j' (published)
en2 English SLIMSHADYNICK 2020-07-27 06:28:23 9 (saved to drafts)
en1 English SLIMSHADYNICK 2020-07-27 06:26:32 3306 Initial revision (published)