Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- ///http://www.spoj.com/problems/CPCRC1C/
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long int
- #define db(x) cout<<#x<<" -> "<<x<<endl
- vector<int>digit;
- const int mx = 83;
- int sz = -1;
- ll dp[10][2][2][83];
- void init(ll n){
- digit.clear();
- while(n){
- digit.push_back(n%10);
- n/=10;
- }
- reverse(digit.begin(),digit.end());
- sz = digit.size();
- return ;
- }
- ll recur(int pos,bool small,bool start,int sum){
- if(pos==sz){
- return sum;
- }
- if(dp[pos][small][start][sum]!=-1){
- return dp[pos][small][start][sum];
- }
- int lim = (small)?9:digit[pos];
- ll ret = 0;
- if(! start){ ///
- for(int i=0; i<=lim; i++){
- ret+= recur(pos+1, small | i<digit[pos] , 0, sum+i);
- }
- }
- else{
- for(int i=1; i<=lim; i++){
- ret+= recur(pos+1, small | i<digit[pos], 0, sum+i);
- }
- ret+= recur(pos+1,1,1,0);
- }
- return dp[pos][small][start][sum]=ret;
- }
- ll fuck(ll n){
- if(n==0){
- return 0LL;
- }
- if(n<=9){
- ll temp = n*(n+1)/2;
- return temp;
- }
- init(n);
- memset(dp,-1,sizeof(dp));
- return recur(0,0,1,0);
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- ll n,m;
- while(cin>>n>>m){
- if(n==-1 && m==-1){
- return 0;
- }
- ll f = fuck(n-1);
- ll s = fuck(m);
- ll samia = s-f;
- cout<<samia<<endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement