If we define , do you know what function means?
Actually, calculates the total number of enclosed areas produced by each digit in . The following table shows the number of enclosed areas produced by each digit:
Digit | Enclosed Area | Digit | Enclosed Area |
---|---|---|---|
0 | 1 | 5 | 0 |
1 | 0 | 6 | 1 |
2 | 0 | 7 | 0 |
3 | 0 | 8 | 2 |
4 | 1 | 9 | 1 |
For example, , and .
We now define a recursive function by the following equations:
For example, , and .
Given two integers and , please calculate the value of .
Input
There are multiple test cases. The first line of the input contains an integer (about ), indicating the number of test cases. For each test case:
The first and only line contains two integers and (). Positive integers are given without leading zeros, and zero is given with exactly one '0'.
<h4< dd="">Output
For each test case output one line containing one integer, indicating the value of .
<h4< dd="">Sample Input
6 123456789 1 888888888 1 888888888 2 888888888 999999999 98640 12345 1000000000 0
<h4< dd="">Sample Output
5 18 2 0 0 1000000000
这道题看第一眼,很容易想到暴力,然后就零分了。
不过仔细观察
观察一下0-9对应的值,很容易发现他们最后都指向了0,1
其余的数同理,最后都会指向1.0;
而0,1的值又是相互对应的。
我们就可以优化了--------------------
链接:不知道
---------------------------
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 int n; 5 const long long maxn=1e6; 6 int head; 7 int x; 8 int k; 9 int deal1(int x); 10 long long f[maxn]={1,0,0,0,1,0,1,0,2,1}; 11 void deal(int k,int x){ 12 while(x>=2&&k){ 13 // cout<<"d"<<x<<endl; 14 x=deal1(x); 15 k--; 16 } 17 // cout<<x<<endl 18 if(!k) 19 { 20 cout<<x<<endl; 21 return ; 22 } 23 if(k%2) 24 printf("%d\n",(!x)); 25 else 26 printf("%d\n",x); 27 return ; 28 } 29 30 int deal1(int x){ 31 int ans=0; 32 long long now; 33 while(x){ 34 now=x%10; 35 x/=10; 36 ans+=f[now]; 37 //cout<<now<<"dfsd"<<endl; 38 } 39 return ans; 40 } 41 int main(){ 42 scanf("%d",&n); 43 for(int i=1;i<=n;++i){ 44 scanf("%d%d",&x,&k); 45 if(k==0){ 46 printf("%d\n",x); 47 } 48 else 49 deal(k,x); 50 } 51 return 0; 52 }Ac