fork download
copy 
  1. #include <iostream>
  2. #define long long long
  3. const int maxn = 16;
  4. const int maxk = 9;
  5. const int maxs = 135;
  6. using namespace std;
  7. long dp[maxn+1][maxk+1][maxs+1];
  8. void init()
  9. {
  10. 	for (int i=0; i<maxn; i++)
  11. 	{ 
  12. 		for (int j=0; j<maxk; j++)
  13. 	    { 
  14. 	    	for (int z=0; z<maxs; z++)
  15. 	        {
  16. 	        	dp[i][j][z] = -1;
  17. 	        }
  18. 	    }
  19. 	}
  20. }
  21. long cdp(int n,int d,int k)
  22. {
  23. 	if (dp[n][d][k]!=-1)
  24. 	{
  25. 		return dp[n][d][k];
  26. 	}
  27. 	else
  28. 	{
  29. 	    if (k<0)
  30. 		{
  31. 			return 0;
  32. 			exit(0);
  33. 		}
  34. 		else
  35. 		if (n==0)
  36. 		dp[n][d][k]=0;
  37. 		else
  38. 		if ((n==1) and (d==k) and (0<=k) and (9>=k))
  39. 		dp[n][d][k]=1;
  40. 	    else
  41. 		if ((n==1) and ((k!=d) or (k>9)))
  42. 		dp[n][d][k]=0;
  43.         else
  44.         {
  45.         	dp[n][d][k] = 0;
  46.         	for (int i=0; i<=9; i++)
  47.         	{
  48.         		dp[n][d][k]+=cdp(n-1,i,k-d);
  49.         	}
  50.         }
  51.         return dp[n][d][k];
  52. 	}
  53. }
  54. long aa,bb,res1,res2,a[maxn+1],b[maxn+1];
  55. int s,ss;
  56. void tach()
  57. {
  58. 	a[0] = 0;
  59.     b[0] = 0;
  60. 	do
  61. 	{
  62. 		a[0]++;
  63. 		a[a[0]] = aa%10;
  64. 		aa = aa/10;
  65. 	}
  66. 	while (aa!=0);
  67. 	do
  68. 	{
  69. 		b[0]++;
  70. 		b[b[0]] = bb%10;
  71. 		bb = bb/10;
  72. 	}
  73. 	while (bb!=0);
  74. }
  75. void solve()
  76. {
  77. 	cin >> aa >> bb >> ss;
  78. 	aa--;
  79. 	tach();
  80. 	res1 = 0;
  81. 	s = ss;
  82. 	for (int i=0; i<=a[a[0]]; i++)
  83. 	{
  84. 		res1 += cdp(a[0],i,s);
  85. 	} 
  86. 	s -= a[1];
  87. 	for (int i=a[0]-1; i>=1; i--)
  88. 	{
  89. 		for (int j=a[i]+1; j<=9; j++)
  90. 		{
  91. 			res1 -= cdp(i,j,s);
  92. 		}
  93. 		s = s-a[i];
  94. 	}
  95. 	res2 = 0;
  96. 	s = ss;
  97. 	for (int i=0; i<=b[b[0]]; i++)
  98. 	{
  99. 		res2 += cdp(b[0],i,s);
  100. 	} 
  101. 	s -= b[1];
  102. 	for (int i=b[0]-1; i>=1; i--)
  103. 	{
  104. 		for (int j=b[i]+1; j<=9; j++)
  105. 		{
  106. 			res2 -= cdp(i,j,s);
  107. 		}
  108. 		s = s-b[i];
  109. 	}	
  110. 	cout << res2-res1;
  111. }
  112. int main() {
  113. 	init();
  114. 	int t;
  115. 	cin >> t;
  116. 	for (int i = 1; i<=t; i++)
  117. 	{ solve(); }
  118. 	return 0;
  119. }
Success #stdin #stdout 0s 3644KB
comments (?)
stdin
copy 
1
1 20 10
stdout
copy 
1
https://ideone.com/Q2FNbS
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!