Chef and Digits of Large Numbers Solution

#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <iterator>
#include <numeric>
#include <bitset>
#include <complex>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

#define X first
#define Y second
#define bit(x) ((ll)1 << (x))
#define sqr(x) ((x)*(x))
#define EPS (1e-8)
#define INF 0x3f3f3f3f
#define maxN 100010
#define maxK 60
#define mx 10000010
#define ml 19
#define mod 1000000007

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

char s[ml];
ll po[ml], fac[ml], tct[ml];
vector <string> pats[ml];
int b[11];

ll calc_pattern (string s)
{
	int i, j, k, len = s.size();
	j = 1; k = 0; char ch = s[0];
	ll tot = 1;
	for (i = 1; i < len; i++)
	{
		if (s[i] == ch)
		{
			j++;
		}
		else
		{
			tot *= fac[j];
			ch = s[i];
			j = 1;
		}
	}
	tot *= fac[j];
	return fac[len] / tot;
}

void pattern (int n, ll mul, string s)
{
	int i, j, lv = s.size();
	
	if (n == lv)
	{
		return;
	}
	
	if (mul >= fac[lv])
	{
		pats[lv].push_back(s);
		tct[lv] += calc_pattern(s);
	}
	
	for (i = s[lv - 1] - '0'; i <= 9; i++)
	{
		if (mul * i * po[n - lv - 1] >= fac[n])
		{
			pattern(n, mul * i, s + (char)('0' + i));
		}
	}

}

void init ()
{
	int i, j;
		
	po[0] = 1; 
	fac[0] = 1;
	for (i = 1; i < ml; i++)
	{
		po[i] = po[i - 1] * 9;
		fac[i] = fac[i - 1] * i;
	}
	
	memset(tct, 0, sizeof tct);
	string s; 
	s.clear();
	for (i = 1; i <= 9; i++) pattern(ml, i, s + (char)('0' + i));
	
	for (i = 1; i < ml; i++)
	{
		tct[i] += tct[i - 1];
	}
}

ll cal (string s)
{
	int i, j, k, len = s.size();
	ll cats, rlt = 0;
	for (auto pp : pats[len])
	{
		memset(b, 0, sizeof b);
		for (i = 0; i < len; i++) b[pp[i] - '0']++;
		cats = 1;
		for (i = 1; i <= 9; i++) cats *= fac[b[i]];

		for (i = 0; i < len; i++)
		{
			for (j = 0; j < s[i] - '0'; j++)
			{
				if (b[j] == 0)
				{
					continue;
				}
				rlt += fac[len - i - 1] * b[j] / cats;
			}
			
			if (b[j] == 0)
			{
				break;
			}
			cats /= b[j]--;
		}
		if (i == len) rlt++;
	}
	return rlt;
}

ll answer (string s)
{
	int i, j, len = s.size();
	if (len >= 19) return 0;
	return tct[len - 1] + cal(s);
}

int main ()
{
	int tc, i, j;
	ll n;
	init();
	scanf("%d", &tc);
	while (tc--)
	{
		string s;
		cin >> s;
		cout << answer(s) << endl;
	}
}

Program Python:

import sys
import bisect

NN=27

pw=[[1]*NN for i in range(NN)]
fac, cnt, adj, sz=[1]*NN, [0]*NN, [[] for i in range(NN)], [0]*NN

def dfs(val,num,ed):
    if val==0 and num>0:return 0
    if val==0:
        if ed!=1:return 0
        N,M,v=0,1,1
        for i in range(10):
            N+=cnt[i]
            M*=fac[cnt[i]]
            v*=pw[i][cnt[i]]
        NUM=fac[N]//M
        adj[N].append([v,NUM])
        return 0
    
    if pw[val][num]<ed:return 0
    for i in range(num+1):
        v=pw[val][i]
        cnt[val]=i
        dfs(val-1,num-i,(ed+v-1)//v)

def CLC(u):
    adj[u]=sorted(adj[u])
    ed=0
    for i in range(1,len(adj[u])):
        if adj[u][i][0]==adj[u][ed][0]:adj[u][ed][1]+=adj[u][i][1]
        else :
            adj[u][ed+1]=adj[u][i]
            ed+=1
    sz[u]=ed+1
    for i in range(ed-1,-1,-1):adj[u][i][1]+=adj[u][i+1][1]

a=[0]*NN

def seg(u,V):
    if u==0:
        if V<2: return 1
        else :return 0
    it=bisect.bisect_left(adj[u],[V,0],lo=0,hi=sz[u])
    if it==sz[u]:return 0
    return adj[u][it][1]

def calc(n):
    L=0
    while n>0:
        a[L]=n%10
        L+=1
        n//=10

    ans=0
    for i in range(1,L):ans+=seg(i,fac[i])
    V=fac[L]
    for i in range(L-1,-1,-1):
        for j in range(1,a[i]):ans+=seg(i,(V+j-1)//j)
        if a[i]==0:break
        V=(V+a[i]-1)//a[i]
        if i==0:
            if V==1:ans+=1
    return ans

if __name__=='__main__':
    for i in range(NN):
        for j in range(1,NN):pw[i][j]=pw[i][j-1]*i
    
    for i in range(1,NN):fac[i]=fac[i-1]*i

    for i in range(1,NN):
        CNT=0
        if i > 10: dfs(9,i,fac[i])
        else : dfs(9, i, 1)
        CLC(i)

    t=int(input())
    for i in range(t):
        n=int(input())
        n=min(n,10**22-1)
        print(min(n,calc(n)))

Codechef Long Challenges

August Long Challenge 2021 Solutions

• Olympics Ranking
• Problem Difficulties
• Chef and Bulb Invention
• Array Filling
• Special Triplets
• Geometry 1
• Charge Scheduling
• Chef and Digits of Large Numbers
• Fat Hut
• Alternating LG Queries

July Long Challenge 2021 Solutions

• Maximum Production
• Relativity
• XxOoRr
• Optimal Denomination
• K Path Query
• Chef vs Bharat
• Chef and Pairs
• Even Odd Partition
• Dakimakura Distribition
• Madoka and Ladder Decomposition