Codeforces Round #643 (Div. 2) Sequence with Digits【思维】题解

系统管理员 2021-07-24 15:06 323阅读 0赞

### 目录 ###

*   *   *  1.题目
         *  2.题意
         *  3.思路
         *  4.代码

### 1.题目 ###

Let’s define the following recurrence:  
an+1=an+minDigit(an)⋅maxDigit(an).  
Here minDigit(x) and maxDigit(x) are the minimal and maximal digits in the decimal representation of x without leading zeroes. For examples refer to notes.

Your task is calculate aK for given a1 and K.

Input  
The first line contains one integer t (1≤t≤1000) — the number of independent test cases.

Each test case consists of a single line containing two integers a1 and K (1≤a1≤1018, 1≤K≤1016) separated by a space.

Output  
For each test case print one integer aK on a separate line.

Example  
Input  
8  
1 4  
487 1  
487 2  
487 3  
487 4  
487 5  
487 6  
487 7  
Output  
42  
487  
519  
528  
544  
564  
588  
628  
Note  
a1=487

a2=a1+minDigit(a1)⋅maxDigit(a1)=487+min(4,8,7)⋅max(4,8,7)=487+4⋅8=519

a3=a2+minDigit(a2)⋅maxDigit(a2)=519+min(5,1,9)⋅max(5,1,9)=519+1⋅9=528

a4=a3+minDigit(a3)⋅maxDigit(a3)=528+min(5,2,8)⋅max(5,2,8)=528+2⋅8=544

a5=a4+minDigit(a4)⋅maxDigit(a4)=544+min(5,4,4)⋅max(5,4,4)=544+4⋅5=564

a6=a5+minDigit(a5)⋅maxDigit(a5)=564+min(5,6,4)⋅max(5,6,4)=564+4⋅6=588

a7=a6+minDigit(a6)⋅maxDigit(a6)=588+min(5,8,8)⋅max(5,8,8)=588+5⋅8=628

### 2.题意 ###

给出a\[1\]和k，其中a\[n\]=a\[n-1\]+a\[n-1\]各位数中最小值 \* a\[n-1\]各位数中最大值，求a\[k\]。

### 3.思路 ###

模拟，需要注意的是一旦乘积出现0，往后的数都为一个值，可以直接退出，很大程度上节约了时间。

### 4.代码 ###

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    int a[30];
    long long  calculate(long long  n)  //计算n各位数中最小值 * n各位数中最大值
    { 
    	memset(a, 0, sizeof(a));
    	int t = 0;
    	while (n != 0)
    	{ 
    		a[t++] = n % 10;
    		n /= 10;
    	}
    	sort(a, a + t);
    	return a[0] * a[t - 1];
    }
    int main()
    { 
    	int T;
    	cin >> T;
    	while(T--)
    	{ 
    		long long n, k; //long long 要注意
    		cin >> n >> k;
    		for(int i=1;i<k;i++)
    		{ 
    			if (calculate(n) == 0) break; /// 一旦出现0，往后的数都不用算了
    			n += calculate(n);
    		}
    		cout << n << endl;
    		
    	}
    	return 0;
    }