Felix_Mate's blog

By Felix_Mate, history, 5 years ago, In Russian
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;
}
  • Vote: I like it
  • 0
  • Vote: I do not like it