Timus 1233
Difference between ru1 and ru2, changed 80 character(s)
~~~~~↵
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+R)/2  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;↵
}↵
~~~~~↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru2 Russian Felix_Mate 2019-07-21 18:37:24 80
ru1 Russian Felix_Mate 2019-07-21 18:36:17 2678 Первая редакция (опубликовано)