oj.uz

Submission #660682

# Submission time Handle Problem Language Result Execution time Memory
660682 2022-11-22T19:03:33 Z Koful123 Trol (COCI19_trol) C++17
50 / 50
 21 ms 388 KB 
#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;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory 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