fork download
copy 
  1. #include <stdio.h> 
  2. #include <string.h>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. int main() {
  7. 	long long n;
  8. 	int m, d, cases = 0;
  9. 	while (scanf("%lld %d", &n, &m) == 2) {
  10. 		char buf[32];
  11. 		sprintf(buf, "%lld", n);
  12. 		d = strlen(buf);
  13. 		long long low = -(1LL<<59), upp = 1LL<<59;
  14. 		for (int i = (1<<10) - 1; i > 0; i--) {
  15. 			if (__builtin_popcount(i) <= m) {
  16. 				int t = 0, pos;
  17. 				long long A[10];
  18. 				long long dp[32][3] = {}, pre = 0; // < = >
  19.  
  20. 				for (int j = 0; j < 10; j++)
  21. 					if ((i>>j)&1)	A[t++] = j;
  22. 				for (int j = 0; j < d; j++)
  23. 					dp[j][0] = dp[j][1] = -(1LL<<59), dp[j][2] = 1LL<<59;
  24. 				for (int j = 0; j < d; j++) {
  25. 					pre = pre * 10 + buf[j] - '0';
  26. 					if (j == 0) {
  27. 						dp[0][0] = 0;
  28. 						for (int k = 0; k < t; k++) {
  29. 							if (A[k] < pre)			dp[j][0] = max(dp[j][0], A[k]);
  30. 							else if (A[k] == pre)	dp[j][1] = max(dp[j][1], A[k]);
  31. 							else if (A[k] > pre)	dp[j][2] = min(dp[j][2], A[k]);
  32. 						}
  33. 					} else {
  34. 						for (int k = 0; k < t; k++) {
  35. 							dp[j][0] = max(dp[j][0], dp[j-1][0] * 10 + A[k]);
  36. 							dp[j][2] = min(dp[j][2], dp[j-1][2] * 10 + A[k]);
  37. 							if (dp[j-1][1] * 10 + A[k] < pre)
  38. 								dp[j][0] = max(dp[j][0], dp[j-1][1] * 10 + A[k]);
  39. 							else if (dp[j-1][1] * 10 + A[k] == pre)
  40. 								dp[j][1] = max(dp[j][1], dp[j-1][1] * 10 + A[k]);
  41. 							else if (dp[j-1][1] * 10 + A[k] > pre)
  42. 								dp[j][2] = min(dp[j][2], dp[j-1][1] * 10 + A[k]);
  43. 						}
  44. 					}
  45. //					printf("%lld %lld %lld\n", dp[j][0], dp[j][1], dp[j][2]);
  46. 					low = max(low, max(dp[j][0], dp[j][1]));
  47. 					if (dp[j][2] > n)	upp = min(upp, dp[j][2]);
  48. 				}
  49. 			}
  50. 		}
  51. 		printf("Case %d: ", ++cases);
  52. 		if (llabs(low - n) == llabs(upp - n) && low != upp)
  53. 			printf("%lld %lld\n", low, upp);
  54. 		else
  55. 			printf("%lld\n", llabs(low - n) < llabs(upp - n) ? low : upp);
  56. 	}
  57. 	return 0;
  58. }
  59. /*
  60. 3355798521 10
  61. 262004 2
  62. 8000 1
  63. 1000 1
  64. 2243 2
  65. 88449 2
  66. 123456789 1
  67. 7099 2
  68. */
Success #stdin #stdout 0s 3300KB
comments (?)
stdin
copy 
3355798521 10
262004 2
8000 1
1000 1
2243 2
88449 2
123456789 1
7099 2
stdout
copy 
Case 1: 3355798521
Case 2: 262222
Case 3: 7777
Case 4: 999
Case 5: 2242 2244
Case 6: 88448
Case 7: 111111111
Case 8: 7111
https://ideone.com/UNzxSb
language:
C++14 (gcc 8.3)
created:
10 years 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!