Seven Segment Display

Time Limit:  Seconds      Memory Limit:  KB

A seven segment display, or seven segment indicator, is a form of electronic display device for displaying decimal numerals that is an alternative to the more complex dot matrix displays. Seven segment displays are widely used in digital clocks, electronic meters, basic calculators, and other electronic devices that display numerical information.

Edward, a student in Marjar University, is studying the course "Logic and Computer Design Fundamentals" this semester. He bought an eight-digit seven segment display component to make a hexadecimal counter for his course project.

In order to display a hexadecimal number, the seven segment display component needs to consume some electrical energy. The total energy cost for display a hexadecimal number on the component is the sum of the energy cost for displaying each digit of the number. Edward found the following table on the Internet, which describes the energy cost for display each kind of digit.

Digit    Energy Cost

(units/s)

Digit    Energy Cost

(units/s)

A

B

C

D

E

F    

For example, in order to display the hexadecimal number "5A8BEF67" on the component for one second,  +  +  +  +  +  +  +  =  units of energy will be consumed.

Edward's hexadecimal counter works as follows:

    The counter will only work for n seconds. After n seconds the counter will stop displaying.

    At the beginning of the 1st second, the counter will begin to display a previously configured eight-digit hexadecimal number m.

    At the end of the i-th second ( ≤ i < n), the number displayed will be increased by . If the number displayed will be larger than the hexadecimal number "FFFFFFFF" after increasing, the counter will set the number to  and continue displaying.

Given n and m, Edward is interested in the total units of energy consumed by the seven segment display component. Can you help him by working out this problem?

Input

There are multiple test cases. The first line of input contains an integer T ( ≤ T ≤ ), indicating the number of test cases. For each test case:

The first and only line contains an integer n ( ≤ n ≤ ) and a capitalized eight-digit hexadecimal number m ( ≤ m ≤ FFFFFFFF), their meanings are described above.

We kindly remind you that this problem contains large I/O file, so it's recommended to use a faster I/O method. For example, you can use scanf/printf instead of cin/cout in C++.

Output

For each test case output one line, indicating the total units of energy consumed by the eight-digit seven segment display component.

Sample Input

 89ABCDEF

 FFFFFFFF

Sample Output

Hint

For the first test case, the counter will display  hexadecimal numbers (89ABCDEF, 89ABCDF0, 89ABCDF1, 89ABCDF2, 89ABCDF3) in  seconds. The total units of energy cost is ( +  +  +  +  +  +  + ) + ( +  +  +  +  +  +  + ) + ( +  +  +  +  +  +  + ) + ( +  +  +  +  +  +  + ) + ( +  +  +  +  +  +  + ) = .

For the second test case, the counter will display  hexadecimal numbers (FFFFFFFF, , ) in  seconds. The total units of energy cost is ( +  +  +  +  +  +  + ) + ( +  +  +  +  +  +  + ) + ( +  +  +  +  +  +  + ) = .

Author: ZHOU, Jiayu

Source: The 14th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple

Submit    Status

/**

题目：ZOJ 3962 Seven Segment Display

链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5594

题意：16进制的八位数加n。求加的过程中所有的花费。显示[0,F]有相应花费。

思路：数位dp

首先获得当前值m，将要加的为n；计算cal(n+m-1)-cal(m-1)即为结果。

cal(x)表示从00000000加x次的花费和，用数位dp计算每个[0,F]在x范围内的出现次数。

00000000表示第一个数。即：加一次;

*/

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cstdio>

#include<vector>

#include<set>

#include<cmath>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int inf = 0x3f3f3f3f;

const int maxn = 1e5+;

ll value[]={,,,,,,,,,,,,,,,};

char s[];

ll dp[][][];///dp[i][j][k]表示长度为i，前面出现j,k次，j出现的次数。

int digit[];

ll n;

ll dfs(int len,int value,int bounded,int cnt)

{

    if(len==){

        return cnt;

    }

    if(!bounded&&dp[len][value][cnt]!=-) return dp[len][value][cnt];

    int d = bounded?digit[len]:;

    ll ans = ;

    for(int i = ; i <= d; i++){

        ans += dfs(len-,value,bounded&&(i==d),cnt+(i==value));

    }

    if(!bounded){

        dp[len][value][cnt] = ans;

    }

    return ans;

}

ll cal(ll n)

{

    if(n<) return ;

    int len = ;

    while(n){

        digit[++len] = n%;

        n /= ;

    }

    while(len<){

        digit[++len] = ;

    }

    ll res = ;

    for(int j = ; j < ; j++){

        res += dfs(len,j,true,)*value[j];

    }

    return res;

}

ll getValue()

{

    ll cnt = ;

    ll p = , x;

    for(int i = ; i >= ; i--){

        if(s[i]>=''&&s[i]<=''){

            x = s[i]-'';

        }else

        {

            x = (s[i]-'A')+;

        }

        cnt += p*x;

        p *= ;

    }

    return cnt;

}

int main()

{

    int T;

    ll mas = (1LL<<);

    memset(dp, -, sizeof dp);

    //cout<<cal(0)<<endl;  //ans = 48;

    ll F8 = cal(mas-);

    //cout<<"cal(0) = "<<cal(0)<<endl;

    //cout<<"cal(1) = "<<cal(1)<<endl;

    //cout<<"F8 = "<<F8<<endl;

    cin>>T;

    while(T--)

    {

        scanf("%lld",&n);

        scanf("%s",s);

        ll m = getValue();

        if(n+m->mas){///当超出FFFFFFFF会重新变成00000000

            printf("%lld\n",cal(n-+m-mas)+F8-cal(m-));

        }else{

            printf("%lld\n",cal(n-+m)-cal(m-));

        }

    }

    return ;

}