Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Chef and Digits CodeChef Solution – Queslers
Problem: Chef and Digits CodeChef Solution
Chef loves integers, but of course not all of them. For some personal reason, he considers the integers a0, a1, …, and a9 unlucky. If for an integer x, suppose there exists some digit i (0 ≤ i ≤ 9) which appears exactly ai times in the decimal presentation of x (without leading zeros), then Chef dislikes x. Otherwise Chef loves it.
Chef wants to count the number of the integers between L and R, both inclusive, which he loves. Can you please help him in this?
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follow.
The first line of each test case contains two space separated integers L, R.
The second line will contain exactly 10 space separated integers, the i-th integer denotes ai-1.
Output
For each test case, output an integer corresponding to the answer, in a new line.
Constraints
- 1 ≤ T ≤ 20
- 1 ≤ L ≤ R ≤ 1018
- 0 ≤ ai ≤ 18
Subtasks
Subtask #1 (25 points)
- 1 ≤ L ≤ R ≤ 105
Subtask #2 (15 points)
- ai = 0, for all i
Subtask #3 (60 points)
- 1 ≤ L ≤ R ≤ 1018
Sample Input 1
2
21 28
5 4 3 2 1 1 2 3 4 5
233 23333
2 3 3 3 3 2 3 3 3 3
Sample Output 1
6
19627
Explanation
In example 1. Chef dislikes the integers 24 because the digit 4 appears exactly 1 time in 24, and a4 = 1. Similarly, he also dislikes the integer 25 because the digit 5 appears exactly 1 time in 25 and a5 = 1. These are the only two integers which Chef dislikes in the range [21,28]. Thus Chef loves the integers 21, 22, 23, 26, 27, and 28. Therefore the answer is 6.
Chef and Digits CodeChef Solution Using C++
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define triple pair<pair<int,int>,int>
#define vpii vector<pii >
#define Graph vector<vector<int> >
#define WGraph vector<vector<pii>>
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define xx first
#define yy second
#define sci1(a) scanf("%d",&a)
#define sci2(a,b) scanf("%d %d",&a,&b)
#define sci3(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define scs(s) scanf("%s",s)
#ifndef GET_MACRO
#define GET_MACRO(__1,__2,__3,NAME,...) NAME
#endif // GET_MACRO
#define sci(...) GET_MACRO(__VA_ARGS__,sci3,sci2,sci1)(__VA_ARGS__)
#define read freopen("input.txt","r",stdin)
#define write freopen("output.txt","w",stdout)
#define infl 0xfffffffffffffffll
#define infi 2000000000
#define LSB(i) ((i)&(-(i)))
#define mp(a,b) make_pair(a,b)
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define bound(i,j,n,m) ((i)<n&&(j)<m&&(i)>=0&&(j)>=0)
inline void debugMode()
{
#ifndef ONLINE_JUDGE
read;
//write;
#endif // ONLINE_JUDGE
}
int d[10];
int td[10];
ll fact[20];
ll solve3(int mask,int len)
{
int sum=0;
ll ans=fact[len];
int cnt=0;
for(int i=0;i<10;++i)
{
if((mask>>i)&1)
{
if(td[i]<0)
return 0;
ans/=fact[td[i]];
sum+=td[i];
++cnt;
}
}
if(sum>len)
return 0;
if(cnt==10&&sum!=len)
return 0;
ans/=fact[len-sum];
if(cnt%2)
ans*=-1;
while(sum<len)
{
ans*=(10-cnt);
++sum;
}
return ans;
}
ll solve2(int len)
{
ll ans=1;
for(int i=0;i<len;++i){
ans*=10;
}
for(int i=1;i<(1<<10);++i)
{
ans+=solve3(i,len);
}
return ans;
}
ll solve(ll a)
{
if(!a)
return 0;
vector<int> b;
ll ta=a;
while(ta>0)
{
b.push_back(ta%10);
ta/=10;
}
reverse(b.begin(),b.end());
ll ans=0;
for(int i=0;i<10;++i)
td[i]=d[i];
for(int i=0;i<(int)b.size()-1;++i)
{
for(int j=1;j<10;++j)
{
--td[j];
ans+=solve2(i);
++td[j];
}
}
for(int i=0;i<(int)b.size();++i)
{
int j=(i==0?1:0);
for(;j<b[i];++j)
{
--td[j];
ans+=solve2((int)b.size()-1-i);
++td[j];
}
--td[b[i]];
}
++ans;
for(int i=0;i<10;++i)
{
int cnt=0;
for(auto e:b)
cnt+=e==i;
if(cnt==d[i])
{
--ans;
break;
}
}
return ans;
}
ll brute(ll l,ll r)
{
int cnt[10];
memset(cnt,0,sizeof(cnt));
int ans=0;
for(int i=l;i<=r;++i)
{
int j=i;
while(j>0)
{
++cnt[j%10];
j/=10;
}
for(int j=0;j<10;++j)
{
if(cnt[j]==d[j])
{
--ans;
break;
}
}
memset(cnt,0,sizeof(cnt));
++ans;
if(solve(i)!=ans)
{
cout<<i<<' ';
}
}
return ans;
}
void solvecases(int cse)
{
ll l,r;
cin>>l>>r;
for(int i=0;i<10;++i)
cin>>d[i];
cout<<solve(r)-solve(l-1)<<'\n';
}
int main()
{
fastio;
fact[0]=1;
for(int i=1;i<20;++i)
{
fact[i]=fact[i-1]*i;
}
int t=1;
cin>>t;
for(int i=1;i<=t;i++)
{
solvecases(i);
}
}
Chef and Digits CodeChef Solution Using C++
#include<bits/stdc++.h>
using namespace std;
#define ll long long
map<vector<int>,ll> DP[20][2][2];
vector<int> v;
int idx[10];
ll digDP(vector<int> &nums,int pos,bool f,bool p,vector<int> &vect,vector<int> &dig){
if(pos == nums.size()){
for(int i=0;i<=9;i++){
if(idx[i] != -1 && v[idx[i]] != dig[i]){
// for(int i=0;i<vect.size();i++)cout<<vect[i]<<" ";
// cout<<endl;
return 0;
}
}
return 1;
}
int sum = 0,sz = nums.size();
for (int i = 0; i < 10; i++) {
if (idx[i] != -1) {
if (sz - pos < dig[i] - v[idx[i]]) return 0;
sum += dig[i] - v[idx[i]];
}
}
if (sz - pos < sum) return 0;
if(DP[pos][f][p].count(v))return DP[pos][f][p][v];
ll res = 0;
int lmt = 0;
if(f == 0)lmt = nums[pos];
else lmt = 9;
for(int dgt=0;dgt<=lmt;dgt++){
// cout<<pos<<" "<<dgt<<" "<<lmt<<endl;
int nf = f;
if(f == 0 && dgt < lmt)nf = 1;
int np = p;
if(p == 0 && dgt == 0)np = 0;
else np = 1;
if(np == 0){
vect.push_back(dgt);
res += digDP(nums,pos+1,nf,np,vect,dig);
vect.pop_back();
}
else{
if(idx[dgt] != -1){
if( v[idx[dgt]] < dig[dgt]){
vect.push_back(dgt);
v[idx[dgt]]++;
res += digDP(nums,pos+1,nf,np,vect,dig);
v[idx[dgt]]--;
vect.pop_back();
}
}
else {
vect.push_back(dgt);
res += digDP(nums,pos+1,nf,np,vect,dig);
vect.pop_back();
}
}
}
//return res;
return DP[pos][f][p][v] = res;
}
ll process(ll a,vector<int> &dig){
vector<int> nums;
int sz = 0;
while(a){
nums.push_back(a%10);
a /= 10;
sz++;
}
reverse(nums.begin(), nums.end());
vector<int> vect;
ll ret = 0;
for(int i=1;i<1024;i++){
v.clear();
int sum = 0,cnt = 0;
memset(idx, -1, sizeof idx);
for(int j=0;j<10;j++){
if((1 << j) & i){
cnt++;
sum += dig[j];
idx[j] = v.size();
v.push_back(0);
}
}
if(sum > sz)continue;
for(int j=0;j<20;j++){
DP[j][0][0].clear();
DP[j][0][1].clear();
DP[j][1][0].clear();
DP[j][1][1].clear();
}
ll x = digDP(nums,0,0,0,vect,dig);
if(cnt&1)ret += x;
else ret -= x;
}
return ret;
}
int main(){
int t;
cin>>t;
for(int i=0;i<t;i++){
ll a,b;
cin>>a>>b;
vector<int> dig(10);
for(int i=0;i<=9;i++)cin>>dig[i];
cout<<(b - a + 1) - process(b,dig) + process(a-1,dig)<<endl;
}
}
Chef and Digits CodeChef Solution Using C++
/**
* Problem: Codechef_DGTCNT (April Challenge 2017)
* Link: https://www.codechef.com/problems/DGTCNT
* Tags: DP Digit
*
* Solution: - Xét bài toán không chặn:
* + Đếm số lượng số có x chữ số có ít nhất 1 chữ số thỏa cnt[num] = a[num]
* + giải bằng kCn và bao hàm loại trừ (19! ~ 1.2e17)
**/
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int MASK = 1 << 10;
ll pw[10][20];
ll fact[20];
ll kCn(int k, int n) {
if (0 <= k && k <= n)
return fact[n] / fact[k] / fact[n - k];
return 0;
}
int dig[MASK];
ll count(int n, vector<int> cnt_need) {
ll ans(0);
for (int msk = 1, sz = cnt_need.size(), MASK = 1 << sz; msk < MASK; ++msk) {
int cnt(0);
ll tmp(1);
for (int j = 0; j < sz; ++j)
if (msk >> j & 1) {
tmp *= kCn(cnt_need[j], n - cnt);
cnt += cnt_need[j];
}
if (cnt <= n)
ans += (dig[msk] & 1 ? 1 : -1) * tmp * pw[10 - dig[msk]][n - cnt];
}
return ans;
}
void init() {
for (int i = 0; i < 10; ++i) {
pw[i][0] = 1;
for (int j = 1; j < 20; ++j)
pw[i][j] = pw[i][j - 1] * i;
}
fact[0] = 1;
for (int i = 1; i < 20; ++i)
fact[i] = fact[i - 1] * i;
for (int msk = 1; msk < MASK; ++msk)
dig[msk] = dig[msk >> 1] + (msk & 1);
}
vector<int> new_vec(vector<int> a) {
vector<int> b;
for (int x : a)
if (x >= 0) b.push_back(x);
return b;
}
int num[20];
ll query(ll x, vector<int> a) {
int n(0);
while (x) {
num[++n] = x % 10;
x /= 10;
}
ll ans(0);
for (int num = 1; num < 10; ++num) {
--a[num];
vector<int> b = new_vec(a);
++a[num];
for (int k = 1; k < n; ++k)
ans += count(k - 1, b);
}
for (int k = n; k > 0; --k) {
for (int j = (k == n ? 1 : 0); j < num[k]; ++j) {
--a[j];
ans += count(k - 1, new_vec(a));
++a[j];
}
--a[num[k]];
}
return ans;
}
// ---------------brute------------------
bool check(ll i, vector<int> a) {
fill(num, num + 10, 0);
while (i) ++num[i % 10], i /= 10;
for (int i = 0; i < 10; ++i)
if (num[i] == a[i]) return false;
return true;
}
ll brute(ll l, ll r, vector<int> a) {
ll cnt(0);
for (ll i = l; i <= r; ++i)
cnt += check(i, a);
return cnt;
}
// ---------------brute------------------
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
init();
int test; cin >> test; while (test--) {
ll l, r; cin >> l >> r;
vector<int> a(10);
for (int &x : a) cin >> x;
cout << (r - l + 1) - (query(r + 1, a) - query(l, a)) << '\n';
}
}
/*
2
999999999999999900 1000000000000000000
2 3 3 3 3 2 3 3 3 3
999999999999999900 1000000000000000000
2 3 3 3 3 2 3 3 3 3
*/
/** /\_/\
* (= ._.)
* / >0 \>1
**/
Chef and Digits CodeChef Solution Review:
In our experience, we suggest you solve this Chef and Digits CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
Chef and Digits Problem is available on Hacker Rank for Free, if you are stuck anywhere between a compilation, just visit Queslers to get Chef and Digits CodeChef Solution.
Conclusion:
I hope this Chef and Digits CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Hacker Rank, Leetcode, Codechef, Codeforce Solution.
This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.
Keep Learning!
More on Queslers >>
