fork download
  1. #include "bits/stdc++.h"
  2.  
  3. using namespace std;
  4.  
  5. using ll = long long;
  6. using vi = vector<int>;
  7. using pii = pair<int, int>;
  8. #define F first
  9. #define S second
  10. #define all(v) (v).begin(), (v).end()
  11. #define SZ(v) int((v).size())
  12.  
  13. vi a;
  14. ll dp[11][11][2][2][11];
  15. int vis[11][11][2][2][11], vid;
  16. ll go(int i, int last, bool lo, bool nonzero, int need) {
  17. if (i == SZ(a))
  18. return need == 0;
  19.  
  20. ll &ret = dp[i][last + 1][lo][nonzero][need];
  21. if (vis[i][last + 1][lo][nonzero][need] == vid) return ret;
  22. vis[i][last + 1][lo][nonzero][need] = vid;
  23. ret = 0;
  24. int EN = lo ? 9 : a[i];
  25. for (int j = 0; j <= EN; ++j) {
  26. ret += go(i + 1, last, j != EN || lo, nonzero || j, need);
  27.  
  28. if (j > last && need && (nonzero || j))
  29. ret += go(i + 1, j, j != EN || lo, 1, need - 1);
  30. }
  31. return ret;
  32. }
  33. void build(int s) {
  34. ++vid;
  35. a.clear();
  36. while (s) {
  37. a.push_back(s % 10);
  38. s /= 10;
  39. }
  40. reverse(all(a));
  41. }
  42. pair<int, ll> solve(int s, int e) {
  43. vector<ll> lids(10);
  44. build(e);
  45. for (int i = 1; i < 10; ++i) {
  46. lids[i] += go(0, -1, 0, 0, i);
  47. }
  48. build(s - 1);
  49. for (int i = 1; i < 10; ++i) {
  50. lids[i] -= go(0, -1, 0, 0, i);
  51. }
  52. for (int i = 9; i >= 1; --i) {
  53. if (lids[i]) return {i, lids[i]};
  54. }
  55. return {0, 1};
  56. }
  57. void MAIN(int tc) {
  58. int s, e;
  59. scanf("%d%d", &s, &e);
  60. auto ret = solve(s, e);
  61. printf("Case %d: %d %lld\n", tc, ret.F, ret.S);
  62. }
  63.  
  64. int main() {
  65. ios_base::sync_with_stdio(0), cin.tie(0);
  66. #ifdef CLION
  67. freopen("in", "rt", stdin);
  68. #endif
  69. int nTests;
  70. scanf("%d", &nTests);
  71. for (int tc = 1; tc <= nTests; ++tc) {
  72. MAIN(tc);
  73. }
  74. }
Success #stdin #stdout 0s 5632KB
stdin
2
111 114
15432  15432
stdout
Case 1: 2 6
Case 2: 2 4