Viewing Text Document

Title:

Owner: Andrian Kurniady

Last updated on: Tuesday, 15 July 2008

Description:

Content:

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <deque>
#include <map>
#include <set>
#include <string>
#include <math.h>
using namespace std;

long long dpmat[20][20];

void precalc(){
    memset(dpmat,0,sizeof(dpmat));
    for (int i=0;i<=9;i++){
        if (i!=4) dpmat[1][i]=1;
    }
    for (int le=2;le<=15;le++){
        for (int i=0;i<=9;i++){
            if (i!=4)
            for (int j=0;j<=9;j++){
                if (j!=4){
                    if (i!=1 || j!=3){
                        dpmat[le][i]+=dpmat[le-1][j];
                    }
                }
            }
        }
    }
}
long long getnum(long long num, long long lastDigit, long long sisalen){
    if (!sisalen) return 1;
    else {
        long long firstDigit = num;
        int len = 1;
        while (len<sisalen)
            { firstDigit/=10; len++; }
        long long multiplier=1;
        for (int i=1;i<len;i++){
            multiplier*=10;
        }
        
        long long res = 0;
        
        for (long long i=0;i<firstDigit;i++){
            if (lastDigit!=1 || i!=3)
                res += dpmat[len][i];
        }
        if (lastDigit!=1 || firstDigit!=3)
            if (firstDigit!=4)
                res += getnum(num-firstDigit*multiplier, firstDigit, sisalen-1);
        return res;
    }
}
long long getnum2(long long num){
    int len = 1;
    long long xnum = num;
    while (xnum>9){
        xnum/=10;
        len++;
    }
    return getnum(num, 0, len);
}
int main(){
    precalc();

    int ntc;
    scanf("%d", &ntc);
    while (ntc--){
        long long a,b;
        scanf("%I64d%I64d", &a,&b);
        
        long long res = getnum2(a)-1;
        res *= b;
        printf("%I64d\n", res);
    }
    
    return 0;
}