fork(2) download
copy 
  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
comments (?)
stdin
copy 
2
111 114
15432  15432
stdout
copy 
Case 1: 2 6
Case 2: 2 4
https://ideone.com/QGXuo9
language:
C++14 (gcc 8.3)
created:
3 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!