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 r1 = L%2, r2 = R%2;
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;
}
