oj.uz

Submission #199962

# Submission time Handle Problem Language Result Execution time Memory
199962 2020-02-04T14:09:41 Z dvdg6566 Palindrome-Free Numbers (BOI13_numbers) C++14
100 / 100
 11 ms 504 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef pair<int,pi> pii;
typedef vector<pi> vpi;
typedef double dl;
#define mp make_pair
#define pb push_back
#define f first
#define s second
int MOD = 1e9+7;
#define lb lower_bound
#define ub upper_bound
ll INF = 100000000000000000;
#define SZ(x) x.size()
#define Aint(x) x.begin(),x.end()
const int MAXN = 1001000;

ll DP[20][11][11][2];
string a,b,S;
ll t;

ll query(int a, int b, int c, int d){
  if (DP[a][b][c][d] != -1)return DP[a][b][c][d];
  if (a == 0)return DP[a][b][c][d] = 1;
  ll res = 0;
  if (d == 1){
    int x = S[SZ(S) - a] - '0';
    for (int i=0;i<x;++i){
      if (i == b || i == c)continue;
      res += query(a-1, c, i, 0);
    }
    if (b != x && c != x)res += query(a-1, c, x, 1);
    return res;
  }
  for (int i=1;i<=9;++i){
    if (i==b||i==c)continue;
    res += query(a-1, c, i, 0);
    // if (a == 3)cout<<query(a-1,c,i,0)<<'\n';
  }
  if ((b!=0) && (c!=0)){
    if (c == 10){
      // assert(b==10);
      res += query(a-1, 10, 10, 0);
    }
    else res += query(a-1, c, 0, 0);
  }
  // if (a == 3)cout<<query(a-1, c, 0, 0)<<'\n';

  return DP[a][b][c][d] = res;
}

ll out (string x){
  if (x == "-1")return 0;
  S = x;
  
  ll T = SZ(S);
  ll res = 0;
  for (int i=1;i<S[0]-'0'; ++i){
    res += query(T-1, 10, i, 0);
  }
  if (S[0] != '0')res += query(T-1, 10, 10, 0);
  // cout<<res<<'\n';
  res += query(T-1, 10, S[0] - '0', 1);
  return res;
}

int main(){
  // freopen("input.txt","r",stdin);
  memset(DP,-1,sizeof(DP));
  cin>>t>>b;
  ll x = out(to_string(t-1));
  memset(DP,-1,sizeof(DP));
  ll y = out(b);
  // cout<<y<<' '<<x<<'\n';
  cout<<y-x;
  // cin>>a>>b;
  // cout<< out(b) - out(a-1);
  
  // cout<<query(2,10,10)<<'\n';
  // for (int i=0;i<3;++i){
    // for (int j=0;j<=9;++j){
      // for (int k=0;k<=9;++k)cout<<DP[i][j][k][0]<<' ';
      // cout<<'\n';
    // }
    // cout<<"\n\n";
  // }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 380 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 380 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 280 KB Output is correct
17 Correct 6 ms 376 KB Output is correct
18 Correct 5 ms 376 KB Output is correct
19 Correct 6 ms 504 KB Output is correct
20 Correct 6 ms 376 KB Output is correct

Subtask #2
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 11 ms 376 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 424 KB Output is correct
14 Correct 5 ms 296 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 5 ms 248 KB Output is correct
19 Correct 6 ms 376 KB Output is correct
20 Correct 7 ms 376 KB Output is correct
21 Correct 5 ms 376 KB Output is correct
22 Correct 5 ms 400 KB Output is correct
23 Correct 5 ms 376 KB Output is correct
24 Correct 6 ms 376 KB Output is correct
25 Correct 5 ms 376 KB Output is correct
26 Correct 5 ms 296 KB Output is correct
27 Correct 5 ms 376 KB Output is correct
28 Correct 5 ms 376 KB Output is correct
29 Correct 6 ms 376 KB Output is correct
30 Correct 5 ms 376 KB Output is correct
31 Correct 6 ms 376 KB Output is correct
32 Correct 5 ms 376 KB Output is correct
33 Correct 5 ms 376 KB Output is correct
34 Correct 5 ms 376 KB Output is correct
35 Correct 5 ms 376 KB Output is correct
36 Correct 5 ms 376 KB Output is correct
37 Correct 5 ms 376 KB Output is correct
38 Correct 5 ms 376 KB Output is correct
39 Correct 5 ms 376 KB Output is correct
40 Correct 5 ms 376 KB Output is correct
41 Correct 5 ms 376 KB Output is correct
42 Correct 5 ms 376 KB Output is correct
43 Correct 5 ms 376 KB Output is correct
44 Correct 6 ms 376 KB Output is correct
45 Correct 5 ms 376 KB Output is correct