Untitled

mail@pastecode.io avatar
unknown
c_cpp
25 days ago
1.3 kB
0
Indexable
Never
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int maxn = 2e5 + 7;
const ll inf  = 1e15;

#define ios ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
#define pb(x) push_back(x)
#define all(x) sort(x.begin() , x.end())

void dbg(){
     cerr << endl;
}

template<typename H, typename... T> void dbg(H h, T... t){
     cerr << h << ", ";
     dbg(t...);
}

#define er(...) cerr << __LINE__ << " <" << #__VA_ARGS__ << ">: ", dbg(__VA_ARGS__)
ll dp[maxn] , res[maxn];
int v[maxn];

int main(){
     for(int i = 1 ; i <= 9 ; i++){ //first fix the bases!
	 	dp[i] = dp[i-1] + 1;
	 	v[i] = i;
		res[v[i]] = 1;
	 }
	 for(int i = 10 ; i <= maxn ; i++){
		string s = to_string(i);
		int x = int(s[0]) - '0';
		int y = int(s[s.length() - 1] - '0');
		if(y == 0){
			dp[i] = dp[i-1];
			continue;
		}
		if(x == y){
			res[i] = res[v[x]] + 1;
			dp[i] += (res[i] + dp[i-1] + 1);
			v[x] = i;
		}
		else{
			string s , s2;
			s += to_string(x); s += to_string(y);
			s2 += to_string(y); s2 += to_string(x);
			int d = stoi(s);
			int f = stoi(s2);
			res[i] = res[v[f]];
			dp[i] += (res[v[f]] + dp[i-1] + (v[f] == 0 ? 0 : 2));
			v[d] = i; 
		}
	 }	
	 cout << dp[200000];
     return 0;
}