[codeforces 1373E] Sum of Digits 十位數百位數乃至更高位的進位不可能發生

Educational Codeforces Round 90 (Rated for Div. 2)   參與排名人數12840git

[codeforces 1373E]    Sum of Digits  十位數百位數乃至更高位的進位不可能發生學習

總目錄詳見https://blog.csdn.net/mrcrack/article/details/103564004spa

在線測評地址http://codeforces.com/contest/1373/problem/E.net

題目大意：尋找知足公式的最小x.若找不到，輸出-1.code

難點：思考了一下，主要涉及進位比較難處理。又想了想，知足條件的x應該有時會比較多，如何找最小？blog

基本思路：get

1.十位數百位數乃至更高位的進位不可能發生，舉例以下it

x=99,k=3
x+0=99
x+1=100
x+2=101
x+3=102

各位位上數字之和9+9+1+0+0+1+0+1+1+0+2=24，對應的n是24

n=24能夠找到比上述x更小的狀況
x=18,k=3
x+0=18
x+1=19
x+2=20
x+3=21
各位位上數字之和1+8+1+9+2+0+2+1=24

2.因要找最小的x,能夠大體斷定x+0,x+1,x+2,......,x+k,這k+1個數，在各個位置上的數字差別很小。io

3.因要找最小的x,低位儘量擺大的數，高位儘量的擺小的數，考慮到要湊成n,故個位上的數須要枚舉(從0枚舉到9)。table

樣例模擬過程以下，如下模擬過程，若閱讀有障礙，可結合AC代碼進行學習。

42 7

4

x的個位是0
0,0+1=1,0+2=2,0+3=3,0+4=4,0+5=5,0+6=6,0+7=7
個位上數字之和0+1+2+3+4+5+6+7=28
還剩42-28=14
14沒法均分爲7+1=8份，此種狀況排除

x的個位是1
1,1+1=2,1+2=3,1+3=4,1+4=5,1+5=6,1+6=7,1+7=8
個位上數字之和1+2+3+4+5+6+7+8=36
還剩42-36=6
6沒法均分爲7+1=8份，此種狀況排除


x的個位是2
2,2+1=3,2+2=4,2+3=5,2+4=6,2+5=7,2+6=8,2+7=9
個位上數字之和2+3+4+5+6+7+8+9=44
還剩42-44=-2
還剩下-2,此種狀況排除

x的個位是3
3,3+1=4,3+2=5,3+3=6,3+4=7,3+5=8,3+6=9,3+7=10(1+0=1)
個位上數字之和3+4+5+6+7+8+9+1=43
還剩42-43=-1
還剩下-1,此種狀況排除

x的個位是4
4,4+1=5,4+2=6,4+3=7,4+4=8,4+5=9,4+6=10(1+0=1),4+7=11(1+1=2)
個位上數字之和4+5+6+7+8+9+1+2=42
還剩42-42=0
還剩下0,此種狀況,十位上數字均分的是0/(1+7)=0
因涉及個位上的進位，x+k對應的十位數是0+1=1

接下來處理x+k
1*10+2=12,12-1=11(注，-1是扣除4+7=11(1+1=2)對應的1+1=2的十位上的1的影響)，此處若不明，可結合AC代碼進行研究。
11-7=4此時，算出的便是x=4.

AC代碼以下：

#include <cstdio>
#include <algorithm>
#define LL long long
#define INF (LL)1<<63-1
using namespace std;
int p[]={0,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9};//0,1,2,3,4,5,6,7,8,9,10(1+0=1),11(1+1=2),12(1+2=3),13(1+3=4),14(1+4=5),15(1+5=6),16(1+6=7),17(1+7=8),18(1+8=9)
LL ans;
LL solve(int st,int n,int k){
	int i,sum=0;
	LL ret=0,pow=10;//注意pow=10,從十位開始
	for(i=st;i<=st+k;i++)sum+=p[i];//個位之和,已包含進位，這個技巧妙啊
	n-=sum;//剩下的和值
	if(n<0||n%(k+1))return INF;//n<0表示湊不成n;n%(k+1)!=0表示剩下的數據，沒法均分
	n/=(k+1);//平均分爲k+1份，每份的數值
	if(st+k>=10)n++;//研究最大的數x+k.n++記錄的是十位的進位
	while(n>0){
		int tmp=9;//除個位，最高位外的數據
		if(n<9)tmp=n;//可能的最高位數據
		ret+=tmp*pow;
		pow*=10;
		n-=9;//低位，數據越大越好
	}
	ret+=p[st+k];//補回個位，對應x+k數據
	if(st+k>=10)ret--;//退位，尾巴多了１，故退去
	if(ret>=k)return ret-k;
	else return INF;
}
int main(){
	int t,i,n,k;
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&k);
		ans=INF;
		for(i=0;i<=9;i++)//個位上的數值
			ans=min(ans,solve(i,n,k));//,printf("i=%d ans=%lld\n",i,ans);
		if(ans==INF)printf("-1\n");
		else printf("%lld\n",ans);	
	}
	return 0;
}