Untitled
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; }