Submission #660682

#	Time	Username	Problem	Language	Result	Execution time	Memory
660682		Koful123	Trol (COCI19_trol)	C++17	50 / 50	21 ms	388 KiB

trol

#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 / 50