fork download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. class Codechef
  6. {
  7.     static int [][][] dp;
  8.     static void preDP(){
  9.         dp=new int[16][145][10];  // ---> 10^15 so 16
  10.         for(int k=0;k<=9;k++){
  11. 	        dp[1][k][k]=1;
  12. 	    }
  13. 	    for(int i=2;i<=15;i++){
  14. 	        for(int j=0;j<=144;j++){
  15. 	            for(int k=0;k<=9;k++){
  16. 	                int rem=j-k;
  17. 	                if(rem>=0){
  18. 	                    for (int m=0;m<=9;m++) {
  19. 	                        dp[i][j][k]+=dp[i-1][rem][m];
  20. 	                    }
  21. 	                }
  22. 	            }
  23. 	        }
  24. 	    }
  25.     }
  26. 	public static void main (String[] args) throws java.lang.Exception
  27. 	{
  28. 		// your code goes here
  29. 		Scanner sc=new Scanner(System.in);
  30. 		int t=sc.nextInt();
  31. 		while(t-->0){
  32. 		    int sum=sc.nextInt();
  33. 		    String num=sc.next();
  34. 		    preDP();
  35. 		    System.out.println(solve(num,sum));
  36. 		}
  37. 	}
  38. 	static int digitSum(int n){
  39. 	    if(n==0)return 0;
  40. 	    return (n%10)+digitSum(n/10);
  41. 	}
  42. 	public static int solve(String num,int sum){
  43. 	    int n=num.length();
  44. 	    int cnt=0;
  45. 	    for(int i=1;i<n;i++){
  46. 	        for(int j=1;j<=9;j++){
  47. 	            cnt+=dp[i][sum][j];
  48. 	        }
  49. 	    }
  50. 	   int [] d=new int[num.length()];
  51. 	   for(int i=0;i<num.length();i++){
  52. 	       d[i]=num.charAt(i)-'0';
  53. 	   }
  54. 	   int psum=0; 
  55.         for(int i=0;i<n;i++){ 
  56.             int curr=d[i];
  57.             int f=0;
  58.             if(i==0){
  59.                 f=1;
  60.             }
  61.             for(int j=f;j<curr;j++){
  62.                 int b=sum-psum-j;
  63.                 int rem=n-1-i;
  64.                 if(b>=0){
  65.                     if(rem>0){
  66.                         for(int k=0;k<=9;k++){
  67.                             cnt+=dp[rem][b][k];
  68.                         }
  69.                     }
  70.                     else{
  71.                         if(b==0)cnt++;
  72.                     }
  73.                 }
  74.             }
  75.             psum+=curr;
  76.             if(psum>sum) break;
  77.         }
  78.         if(psum==sum)cnt+=1;
  79.         return cnt;
  80. 	}
  81. }
  82.  
Success #stdin #stdout 0.17s 57756KB
comments (?)
stdin
copy 
3
2 100
24 83542
24 99999
stdout
copy 
3
4911
5875
https://ideone.com/M7wLoM
language:
Java (HotSpot 12)
created:
5 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!