fork download 
  1. #include <bits/stdc++.h> 
  2. using namespace std;  
  3.  
  4. typedef long long ll;  
  5. typedef pair<int, int> ii;  
  6.  
  7. const int INF = 1e9;  
  8. const ll LINF = 1e18;  
  9.  
  10. template<typename T>
  11. void maximize(T& a, const T& b) {
  12. 	if (a < b) a = b;  
  13. }
  14.  
  15. ll a, b; 
  16. vector<int> digit_a, digit_b;   
  17.  
  18. vector<int> getDigit(ll n) {
  19. 	vector<int> ans; 
  20. 	for (; n > 0; n /= 10) ans.push_back(n % 10);  
  21. 	return ans; 
  22. }
  23.  
  24. ll memo[19][2][2][2]; 
  25.  
  26. // Tích lớn nhất có thể có của phần còn lại khi phần
  27. // prefix ở trước vị trí idx mang theo điều kiện leading, larger, smaller
  28. ll dp(int idx, bool leading, bool larger, bool smaller) {
  29. 	if (idx == -1) return 1;  
  30.  
  31. 	ll& ans = memo[idx][leading][smaller][larger]; 
  32. 	if (ans != -1) return ans;  
  33.  
  34. 	ans = 0;   
  35. 	int min_digit = (larger) ? 0 : digit_a[idx]; 
  36. 	int max_digit = (smaller) ? 9 : digit_b[idx]; 
  37. 	for (ll i = min_digit; i <= max_digit; i++) {
  38. 		ll val = (i == 0 && leading) ? 1 : i; 
  39. 		maximize(ans, val * dp(idx - 1, leading & (i == 0), larger | (i > digit_a[idx]), smaller | (i < digit_b[idx]))); 
  40. 	}
  41.  
  42. 	return ans; 
  43. }
  44.  
  45. // Truy vết
  46. void trace(int idx, bool leading, bool larger, bool smaller) {
  47. 	if (idx == -1) return;  
  48.  
  49. 	ll max_prod = dp(idx, leading, larger, smaller); 
  50.  
  51. 	int min_digit = (larger) ? 0 : digit_a[idx]; 
  52. 	int max_digit = (smaller) ? 9 : digit_b[idx];
  53. 	ll best_digit = -1;  
  54. 	for (ll i = min_digit; i <= max_digit; i++) {
  55. 		ll val = (i == 0 && leading) ? 1 : i; 
  56. 		ll prod = val * dp(idx - 1, leading & (i == 0), larger | (i > digit_a[idx]), smaller | (i < digit_b[idx])); 
  57. 		if (prod == max_prod) {
  58. 			best_digit = i;
  59. 			break;   
  60. 		}
  61. 	}
  62.  
  63. 	if (!leading || best_digit > 0) cout << best_digit; 
  64. 	trace(idx - 1, leading & (best_digit == 0), larger | (best_digit > digit_a[idx]), smaller | (best_digit < digit_b[idx])); 
  65. }
  66.  
  67. void solve(ll a, ll b) {
  68. 	digit_a = getDigit(a), digit_b = getDigit(b);  
  69. 	while (digit_a.size() < digit_b.size()) digit_a.push_back(0);  
  70.  
  71. 	memset(memo, -1, sizeof memo);  
  72. 	trace(digit_b.size() - 1, 1, 0, 0);  
  73. }
  74.  
  75. int main() {
  76. 	ios::sync_with_stdio(0); cin.tie(0);  	
  77. 	cin >> a >> b; 
  78. 	solve(a, b); 
  79. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin 
51 62
stdout 
59
https://ideone.com/NA8oyp
language:
C++14 (gcc 8.3)
created:
1 year 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!