Intended Problem : LightOj 1140
The problem Asks to output The number of 0’s to be write in range [A,B] inclusive,,,
Okay, The strategy to solve this kind of problem is Simple , Function…
Let F(N) -> be a function which returns the number of 0’s in range [1,N] .( we keep 0 as a special case.)
Then The number of 0’s in range [A,B] = F[B] – F[A-1]
Now only problem remains how to calculate values of F(N) efficiently…
Let string y = "decimal representation of N" y = "101" if N = 101
We iterate through the y..
The first digit -> 1
So we can place [0,1] , not more than that.
We declare a variable upto = Which far I can go in this given condition. The condition will be see soon,,
So , ->>> We put 0 in the first position. Go to the next digit..
Can you tell ,which digits I can place in 2nd position ???
0 ?
Not exactly … As We started from 0, and whatever I put in the 2nd position ,It will remain smaller Than N..
This is the condition…. So I need a comparator to tell me whether The I can [0,9] or to the certain limit..
This is done using a bool variable …
low = (low || d < y[i]-'0') if low == true: d in range [0,9] else d in range[0,y[i]-'0']
This value is proceded to the next stage..
Again ,One more information is needed to to be propagated. That is Is The number is valid..
Like Putting 0 in the first place doesn’t make any valid representation of the Number…
So we wipe out this chances…
Putting A variable…. prv0
This value is true if we placed valid digits [1,9] in some left digits.
and false otherwise.
Again , We need a counter function, That counts ,how many number can be created if we place d in the i’th place…
This is simple ….
N = 167 how many Number can be created which is <= N && starts with 1 .... this is 68 [100,167] how many Number can be created which is <= N && starts with 0 .... this is 68 [000,99]
Is it clear ???
Now The solution:::
#include <bits/stdc++.h>
using namespace std;
/*------- Constants---- */
#define LMT 100
#define ll long long
#define ull unsigned long long
#define MOD 1000000007
#define MEMSET_INF 63
#define MEM_VAL 1061109567
#define FOR(i,n) for( int i=0 ; i < n ; i++ )
#define mp(i,j) make_pair(i,j)
#define lop(i,a,b) for( int i = (a) ; i < (b) ; i++)
#define pb(a) push_back((a))
#define gc getchar_unlocked
#define PI acos(-1.0)
#define inf 1<<30
#define lc ((n)<<1)
#define rc ((n)<<1 |1)
#define msg(x) cout<<x<<endl;
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
/*------ template functions ------ */
inline void sc(ll &x)
{
register int c = gc();
x = 0;
int neg = 0;
for(;((c<48 | c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
if(neg) x=-x;
}
template <class T> inline T bigmod(T p,T e,T M){
ll ret = 1;
for(; e > 0; e >>= 1){
if(e & 1) ret = (ret * p) % M;
p = (p * p) % M;
} return (T)ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}
/*************************** END OF TEMPLATE ****************************/
string y;
ll dp[11][2][2];
ll cnt ( int inx, int low, int prv0)
{
if(prv0 == 0) return 0;
ll r = 0 ;
for (int i = inx ; i < y.length() ; i ++ ) {
r = 10 * r + (low ? 9 : y[i]-'0');
}
return r+1;
}
ll cal(int inx , int low , int prv0)
{
if(inx == y.length()) return 0;
if(dp[inx][low][prv0] !=-1 ) return dp[inx][low][prv0];
int up = (low ? 9 : y[inx]-'0');
ll r = 0;
for (int d = 0 ; d <= up ; d ++ ) {
r += cal(inx+1, (low || (d < y[inx]-'0')) , prv0 || d);
if(d == 0) r += cnt (inx+1, (low || (d < y[inx]-'0')) , prv0 || d);
}
return dp[inx][low][prv0] = r;
}
int main()
{
ll tc ,cs =0 ;
ll a , b ;
sc(tc);
while (tc -- ) {
sc(a);
sc(b);
ms(dp, -1);
ll k1 = 0;
if(a-1>=0 )
{
ll p = a-1;
y.clear();
while(p){
y.push_back(p%10+'0');
p/=10;
}
reverse(y.begin(), y.end());
k1 = cal(0,0,0);
}
ll p = b;
y.clear();
while (p) {
y.push_back(p%10+'0'); p/=10;
}
reverse(y.begin(), y.end());
ms(dp, -1);
ll k2 = cal(0, 0, 0);
if(a == 0) k2 ++;
printf("Case %lld: %lld\n" ,++cs, k2 - k1);
}
return 0;
}
In my code, call function is the main generator, helper cnt function ..
Using DP , avoids same calculation..
This occurs as overlapping sub-problems..
N = 489 cal(0,0,0) -> cal(1,1,0) , Put 0 in the 1st place -> cal(1,1,1) ,Put 1 in the first place -> cal(1,1,1),Put 2 in the first Place -> cal(1,1,1) ,Put 3 in the first place -> cal(1,0,1) ,Put 4 in the first Place
So we memoize the result and write a recursive dp solution.
We just needed to store The value for 0 , we place a condition on d , then add to it
Second Problem : SPOJ MDIGITS
The only change is that we will need to store all the digits, not for only 0’s
Here is The code:
#include <bits/stdc++.h>
using namespace std;
/*------- Constants---- */
#define LMT 15
#define ll long long
#define ull unsigned long long
#define mod 1000000007
#define MEMSET_INF 63
#define MEM_VAL 1061109567
#define FOR(i,n) for( int i=0 ; i < n ; i++ )
#define mp(i,j) make_pair(i,j)
#define lop(i,a,b) for( int i = (a) ; i < (b) ; i++)
#define pb(a) push_back((a))
#define gc getchar_unlocked
#define PI acos(-1.0)
#define inf 1<<30
#define lc ((n)<<1)
#define rc ((n)<<1 |1)
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
/*------ template functions ------ */
inline void sc(int &x)
{
register int c = gc();
x = 0;
int neg = 0;
for(;((c<48 | c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
if(neg) x=-x;
}
template <class T> inline T bigmod(T p,T e,T M){
ll ret = 1;
for(; e > 0; e >>= 1){
if(e & 1) ret = (ret * p) % M;
p = (p * p) % M;
} return (T)ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}
/*************************** END OF TEMPLATE ****************************/
string y;
struct W {
int A[10];
W(){ms(A, 0);}
void show(){
FOR(i, 10) printf("%5d" , A[i]);
printf("\n");
}
};
W dp[20][2][2];
W EMPTY;
bool vis[20][2][2];
int cnt( int index , int low , int ZERO)
{
if(ZERO == 0) return 0;
int sum = 0 ;
for (int i = index ; i < y.length() ; i ++ ) {
sum = 10 * sum + (low ? 9 : y[i] -'0');
}
return sum + 1;
}
W cal(int index , int low, int ZERO)
{
if(index == y.length() ) return EMPTY;
if(vis[index][low][ZERO] ) return dp[index][low][ZERO];
W r;
int upTo = (low ? 9: y[index] - '0');
for (int d = 0 ; d <= upTo ; d ++ ) {
W t = cal(index + 1 , low || d < y[index] -'0' , ZERO || d) ;
int h =cnt (index + 1, low || d < y[index] -'0' , ZERO || d );
for (int i = 0; i < 10 ; i ++ ) r.A[i] += t.A[i];
r.A[d] += h ;
}
vis[index][low][ZERO] = true;
return dp[index][low][ZERO] = r;
}
int main(void){
for(int a, b; scanf("%d %d", &a, &b) == 2 && (a || b); ){
if(a>b) swap(a, b);
ms(dp, 0);
ms(vis, false);
y = to_string(a-1);
W k = cal(0, 0, 0);
ms(dp, 0);
ms(vis , false);
y = to_string(b);
W k2 = cal(0 , 0, 0);
for (int i = 0; i < 10; i ++ ) {
if(i) printf(" ");
printf("%d",k2.A[i] - k.A[i]);
}
printf("\n");
}
return 0;
}
Another Example :
Given A range [A,B],
Digit Product of a number if the multiplication of all the digits of a number ,
DigitProduct(123) = 1 * 2 * 3 = 6
DigitProduct(1021) = 1 * 0 * 2 * 1 = 0
So you need to summation all the DigitProducts in the range [A,B]
Try To figure it out ??
Code for Fun 