fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. long long t, n, m, ans, dp[17][2][2];
  5. bool ye;
  6. string s, l, r;
  7. char a[18];
  8.  
  9. //slv(0, 0, 0) -> banyak bilangan di antara R yang consist matching string
  10. long long slv(long long id, bool kurangR, bool lebihL)
  11. {
  12. 	//kurangR = 1 boleh milih digit yang lebih gede dari digit R sekarang
  13. 	//lebihL = 1 boleh milih digit yang lebih kecil dari digit L sekarang
  14. 	//kalo di interval matching string harus pilih digit yang sesuai
  15. 	if (dp[id][kurangR][lebihL] != -1) return dp[id][kurangR][lebihL];
  16. 	if (id == m) return 1;
  17. 	long long d;
  18. 	dp[id][kurangR][lebihL] = 0;
  19. 	for (d=0; d<=9; d++)
  20. 	{
  21. 		if ((!lebihL && d<l[id]-'0') || (!kurangR && d>r[id]-'0') || (a[id] != '#' && a[id]-'0' != d)) continue; // ga boleh
  22. 		// printf("id = %lld d = %lld\n", id, d);
  23. 		dp[id][kurangR][lebihL] += slv(id+1, kurangR|(d<r[id]-'0'), lebihL|(d>l[id]-'0'));
  24. 	}
  25. 	return dp[id][kurangR][lebihL];
  26. }
  27.  
  28. int main()
  29. {
  30. 	long long i, j, ii;
  31. 	scanf("%lld", &t);
  32. 	while (t--)
  33. 	{
  34. 		cin >> s >> l >> r;
  35. 		n = s.length();
  36. 		m = r.length();
  37. 		reverse(l.begin(), l.end());
  38. 		while (l.size()<m) l.push_back('0');
  39. 		reverse(l.begin(), l.end());
  40. 		ans = 0;
  41. 		for (i=0; i<m-n+1; i++)
  42. 		{
  43. 			//cek di subtring i sampai i+n-1
  44. 			if (i == 0 && s[0] == '0') continue; // ga boleh ada leazing zero ngabs
  45. 			for (j=0; j<m; j++)
  46. 			{
  47. 				if (j>=i && j<=i+n-1)
  48. 				{
  49. 					//sekarang posisi ke j-i di string s
  50. 					a[j] = s[j-i];
  51. 				} else 
  52. 				{
  53. 					a[j] = '#';
  54. 				}
  55. 			}
  56. 			// printf("i = %lld a = \n", i);
  57. 			// for (j=0; j<m; j++) printf("%c", a[j]);
  58. 			// printf("\n\n");
  59. 			memset(dp, -1, sizeof(dp));
  60. 			ans += slv(0, 0, 0); //kontribusi string s di antara L dan R di substring [i, i+n-1]
  61. 		}
  62. 		if (s[0] == '0' && n>1) ans = 0; // harusnya gini
  63. 		printf("%lld\n", ans);
  64. 	}
  65. }
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin 
6
22 23 234
0295 295 295
0 1 9999999999999999
2718 998244353 9982443530000000
869120 1234567890123456 2345678901234567
2023032520230325 1 9999999999999999
stdout 
12
0
14999999999999985
12982260572545
10987664021
1
https://ideone.com/tJkfVn
language:
C++ (gcc 8.3)
created:
11 days 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!