Hi all!↵
I have a problem with the task.↵
Give me hint how to solve or tell me about my mistake↵
F(N, K) = amount of numbers x from 1 to N such that x<=K (lexicographically)↵
Q(N, p) = amount of numbers x from 1 to N such that x = p* where * is some sequence of numbers (may be empty)↵
My algo is binary search by N:↵
F(N, K) <= F(N+1, K) and find such N that F(N, K) = M↵
~~~~~↵
↵
↵
↵
~~~~~↵
#include <iostream>↵
#include <vector>↵
#include <string>↵
#include <algorithm>↵
using namespace std;↵
↵
↵
#define ll unsigned long long↵
const ll inf = 18446744073709551615;↵
↵
ll K, M;↵
↵
vector<int> to_vec(ll X);↵
ll F(ll N, ll K);↵
ll F(ll N, ll K);↵
ll Q(ll N, ll pref, int len);↵
ll deg[20];↵
↵
↵
int main()↵
{↵
deg[0] = (ll)1;↵
for(int i=1;i<20;i++)↵
deg[i] = deg[i-1] * (ll)10;↵
cin>>K>>M;↵
↵
↵
↵
ll L = K, R = inf;↵
while(R-L>1)↵
{↵
ll m = L/2 + R/2;↵
if(r1==1 && r2==1)↵
m+=(ll)1;↵
if(F(m, K)<=M) L=m;↵
else R=m;↵
}↵
↵
if(F(L,K)==M) cout<<L;↵
else↵
{↵
if(F(L+1,K)==M) cout<<L+1;↵
else cout<<"0";↵
}↵
↵
↵
return 0;↵
}↵
↵
↵
↵
vector<int> to_vec(ll X)↵
{↵
vector<int> res;↵
do↵
{↵
res.push_back(X % 10);↵
X/=10;↵
}↵
while(X > 0);↵
reverse(res.begin(),res.end()); ↵
return res;↵
}↵
↵
↵
ll Q(ll N, ll pref, int len)↵
{↵
ll res = (ll)0;↵
vector<int> n = to_vec(N); ↵
if (len > n.size() || len == n.size() && pref > N)↵
return (ll)0;↵
else↵
{↵
if(len == n.size()) ↵
return (ll)1;↵
else↵
{↵
ll nr = N / deg[n.size() - len];↵
if(pref > nr)↵
return res;↵
if(pref == nr)↵
{↵
res += (deg[n.size() - len] - (ll)1) / (ll)9;↵
return res + N % deg[n.size() - len] + 1;↵
}↵
return res += (deg[n.size() - len + 1] - (ll)1) / (ll)9;↵
}↵
}↵
}↵
↵
↵
ll F(ll N, ll K)↵
{↵
if(K == 0) return (ll)0;↵
ll res = (ll)1;↵
vector<int> k = to_vec(K);↵
vector<int> n = to_vec(N);↵
for(int q=1;q<k[0];q++) res+=Q(N, q, 1);↵
for(int r=0;r<k.size()-1;r++)↵
{↵
ll pref = (ll)0;↵
for(int j=0;j<=r;j++)↵
pref = ((ll)10 * pref) + (ll)k[j];↵
res += (ll)1;↵
for(int q=0;q<k[r+1];q++)↵
{↵
res+=Q(N, pref * (ll)10 + (ll)q, r + 2); ↵
}↵
}↵
return res;↵
}↵
~~~~~↵
↵
