#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
int dp[200][20][2],x,l;
string s;
int len(int x){
int res = 0;
while(x > 0) x /= 10,res++;
return res;
}
int sum(int x){
int res = 0;
while(x > 0) res += x % 10,x /= 10;
return res;
}
int get(int x){
while(x >= 10) x = sum(x);
return x;
}
int f(int val,int pos,int ok){
if(pos == l + 1) return get(val);
int &cur = dp[val][pos][ok];
if(cur != -1) return cur;
int lim = (ok ? 9 : s[pos-1]-'0');
for(int i = 0; i <= lim; i++){
cur += f(val + i,pos + 1,(ok || i < s[pos-1]-'0'));
}
return cur += 1;
}
void solve(){
int q; cin >> q;
for(int i = 0; i < q; i++){
memset(dp,-1,sizeof(dp));
cin >> x; x--; l = len(x);
s = to_string(x); int cur = f(0,1,0);
memset(dp,-1,sizeof(dp)); cin >> x;
s = to_string(x); l = len(x);
cout << f(0,1,0) - cur << endl;
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
while(t--)
solve();
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
3 ms |
340 KB |
Output is correct |
| 3 |
Correct |
20 ms |
340 KB |
Output is correct |
| 4 |
Correct |
5 ms |
340 KB |
Output is correct |
| 5 |
Correct |
21 ms |
388 KB |
Output is correct |
