Join Us
why we need to use dp. is it not a simple question which can directly be solved by using base = 5 ?? Or there are some hidden testcases where it might fail ?
Entering edit mode
#include<bits/stdc++.h>
using namespace std;
int mod = 1e9+7;
int dp[11][2][11][11][11];
int f(string &s, int n, int tight, int count_2, int count_4, int count_8){
if(n==0){
if(count_2!=0 && count_2==count_4 && count_8==count_4){
return 1;
}
return 0;
}
if(dp[n][tight][count_2][count_4][count_8]!=-1) return dp[n][tight][count_2][count_4][count_8];
int total =0;
int ub = (tight?(s[s.size()-n]-'0'):9);
for(int i=0; i<=ub; i++){
if(i==2){
total +=f(s, n-1, tight&(i==ub),count_2+1, count_4, count_8)%mod;
}
else if(i==4){
total +=f(s, n-1, tight&(i==ub),count_2, count_4+1, count_8)%mod;
}
else if(i==8){
total +=f(s, n-1, tight&(i==ub),count_2, count_4, count_8+1)%mod;
}
else{
total +=f(s, n-1, tight&(i==ub),count_2, count_4, count_8)%mod;
}
}
return dp[n][tight][count_2][count_4][count_8]=total;
}
int main(){
long long n ;
cin>>n;
string s =to_string(n);
int count_2=0;
int count_4=0;
int count_8=0;
memset(dp, -1,sizeof(dp));
cout<<f(s,s.size(), 1, count_2, count_4, count_8)<<endl;// (string s, digit, tight);
}
Entering edit mode
Question 1 Solution
int dp[12][3][2][4][4][4];
int sol(int i,string &s,int tight,bool flag,int two_cnt,int fr_cnt,int eig_cnt)
{
if(i>=s.length())
{
if(flag && two_cnt>=1 && (two_cnt==fr_cnt && fr_cnt==eig_cnt))
return 1;
else
return 0;
}
if(dp[i][tight][flag][two_cnt][fr_cnt][eig_cnt]!=-1)
return dp[i][tight][flag][two_cnt][fr_cnt][eig_cnt];
int res=0;
int lim=tight?(s[i]-'0'):9;
if(flag==0)
res=sol(i+1,s,0,0,0,0,0);
for(int j=0;j<=lim;j++)
{
int newtight=0;
if(j==lim && tight==1)
newtight=1;
int nt=!(j==2)?two_cnt:two_cnt+1;
int nf=!(j==4)?fr_cnt:fr_cnt+1;
int ne=!(j==8)?eig_cnt:eig_cnt+1;
res+=sol(i+1,s,newtight,1,nt,nf,ne);
}
return dp[i][tight][flag][two_cnt][fr_cnt][eig_cnt]=res;
}
void solve()
{
int n;
cin>>n;
string res=to_string(n);
memset(dp,-1,sizeof(dp));
//cout<<res<<endl;
cout<<sol(0,res,1,0,0,0,0)<<endl;
}
Entering edit mode
Find Number
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector <ll>
#define for0(i,l,r) for(ll i = l;i<r;i++)
int main()
{
string str;
cin>>str;
ll n = str.size();
ll num=1;
if(n==1){
num = 1;
}else{
num+= ((5*(pow(5,n-1)-1))/4);
}
for(ll i=0;i<n;i++){
ll temp = str[i]-'A';
ll d = pow(5,n-i-1);
num+=(temp*d);
}
cout<<num;
}
Entering edit mode
Question 2 Solution
int dp[21][3][2];
int sol(int i,string &s,int tight,bool flag)
{
if(i>=s.length())
return flag;
if(dp[i][tight][flag]!=-1)
return dp[i][tight][flag];
int res=0;
int lim=tight?(s[i]-'0'):5;
if(flag==0)
res=sol(i+1,s,0,0);
for(int j=1;j<=lim;j++)
{
int newtight=0;
if(j==lim && tight==1)
newtight=1;
res+=sol(i+1,s,newtight,1);
}
return dp[i][tight][flag]=res;
}
void solve()
{
string s;
cin>>s;
string res;
memset(dp,-1,sizeof(dp));
for(auto i:s)
{
if(i=='A')
res+="1";
else if(i=='B')
res+="2";
else if(i=='C')
res+="3";
else if(i=='D')
res+="4";
else
res+="5";
}
//cout<<res<<endl;
cout<<sol(0,res,1,0)<<endl;
}
Entering edit mode
Question 1: Without using a flag state, we traverse from left to right hence 0000.....248 will be counted just once
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define endl "\n"
const ll mod = 1e9+7;
const ld eps = 1e-9 ;
const ll maxn = 1e5+1;
const ll inf = 1e15 ;
const ll minf = -inf ;
// dp[n][a][b][c][t]
int dp[11][11][11][11][2];
int f(int n, int a, int b, int c, int t, string& s){
if(n == 0){
if(a>0 && a==b && b==c) return 1;
else return 0;
}
if(dp[n][a][b][c][t] != -1) return dp[n][a][b][c][t];
int ans = 0;
int ub = t?(int)(s[s.size()-n]-'0'):9;
for(int i = 0; i<ub; i++){
ans = (ans+f(n-1, a+(i == 2), b+(i == 4), c+(i == 8), t&(i == ub), s))%mod;
}
return dp[n][a][b][c][t] = ans;
}
void test(){
int n; cin>>n;
string s = to_string(n);
memset(dp, -1, sizeof(dp));
cout<<f(s.size(), 0, 0, 0, 1, s)<<endl;
return;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
// int t; cin>>t;
while(t--){
test();
}
return 0;
}
Loading Similar Posts
what the purpose of using flag
to check whether we have encountered any non-zero digit or not otherwise 06 && 006 will be counted two time but they are the same
ohh leading zeros this was in my mind just sked for confirmation