LightOJ – How Many Zeroes?

L
Problem NameHow Many Zeroes?
JudgeLightOJ
Problem Linkhttps://lightoj.com/problem/how-many-zeroes
Algorithms & DSDigit DP
#include<bits/stdc++.h> using namespace std; typedef long long ll; vector<ll>num; ll dp[30][30][2][2]; ll dgtDP(ll pos, ll cnt, ll topDgt, ll notLead) { if(pos==num.size()){ return cnt; } if(dp[pos][cnt][topDgt][notLead]!=-1)return dp[pos][cnt][topDgt][notLead]; ll ans=0; ll lmt=(topDgt)?num[pos]:9; for(ll dgt=0;dgt<=lmt;dgt++){ ll ncnt=(notLead)?(cnt+(dgt==0)) : 0; ll ntopDgt=(topDgt&&(dgt == num[pos])); ll nnotLead=((dgt!=0)||notLead); ans+=dgtDP(pos+1,ncnt,ntopDgt,nnotLead); } return dp[pos][cnt][topDgt][notLead]=ans; } ll solve(ll n) { num.clear(); if(n==-1)return -1; while(n>0){ num.push_back(n%10); n/=10; } reverse(num.begin(),num.end()); memset(dp,-1,sizeof(dp)); ll ans=dgtDP(0,0,1,0); return ans; } int main() { ll t; cin>>t; ll a, b; for(ll T=1;T<=t;T++){ cin>>a>>b; ll ans; ans=solve(b)-solve(a-1); cout<<"Case "<<T<<": "; cout<<ans<<"\n"; } return 0; }
Code language: PHP (php)

About the author

আবু রিফাত মুহাম্মদ

সখের বশে প্রোগ্রামিং করি। নতুন নতুন জিনিস শিখতে এবং শেখাতে ভালবাসি।

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments

আবু রিফাত মুহাম্মদ

সখের বশে প্রোগ্রামিং করি। নতুন নতুন জিনিস শিখতে এবং শেখাতে ভালবাসি।

যোগাযোগ করুন

error: Alert: Content is protected !!