fork(1) download 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int B;
  5. string Y;
  6. int memo[100001];
  7.  
  8. int DP(int index) {
  9. 	if(index >= Y.size()) return 1;
  10. 	if(memo[index] != -1) return memo[index];
  11. 	int digit = 0, ans = 0, next = index;
  12. 	while(next < Y.size() && digit < B) {
  13. 		digit = 10*digit + (Y[next++]-'0');
  14. 		ans += DP(next);
  15. 	}
  16. 	return memo[index] = ans;
  17. }
  18.  
  19. int main() {
  20. 	cin >> B >> Y;
  21. 	for(int i = 0; i < Y.size(); i++)
  22. 		memo[i] = -1;
  23. 	for(int i = 0; i < Y.size(); i++)
  24. 		cout << DP(i) << " ";
  25. 	cout << endl;
  26. 	return 0;
  27. }
  28. /*
  29. 01234567
  30. 71112016
  31.  
  32. DP(X) = berapa banyak kemungkinan input untuk
  33.         string mulai index ke-X
  34.         
  35. DP(0) = seluruh string
  36. DP(4) = untuk string "2016"
  37. DP(7) = untuk string "6"
  38. DP(8) = 1
  39.  
  40. 71(1)12016
  41. 71(11)2016
  42.  
  43. DP(2) = DP("112016")
  44. = DP(3)
  45. + DP(4)
  46.  
  47. */
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
16
114240
stdout 
18 10 5 3 2 1
https://ideone.com/NsIXxR
language:
C++ (gcc 8.3)
created:
2 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!