[Codeforces][Round #667][Div.3] D : Decrease the Sum of Digits (C++)

https://codeforces.com/contest/1409/problem/D

Problem - D - Codeforces

 

 

[난이도] Div.3
[유형] Greedy

[풀이]
N 제한이 10^18이기때문에 1씩 증가시켜서는 시간내에 통과가 불가능하다.
각 자릿수들의 합이 점점 작아지도록 할려면 0을 점점 늘려줘야 한다.
0을 늘리려면 10의 자리부터 자릿수 올림이 발생하도록 차례대로 숫자를 더해주면 된다.

 

#include <cstdio>
using namespace std;
using ll = long long;
int tc,s;
ll n,tn;
int sum(){
    int ret=0;
    ll tt=tn;
    while(tt>0){
        ret+=(tt%10);
        tt/=10;
    }
    return ret;
}
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%lld%d",&n,&s);
        ll k = 10;
        tn=n;
        while(sum()>s){
            ll r = tn%k;
            if(r!=0) tn+=k-r;
            k*=10;
        }
        printf("%lld\n",tn-n);
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round667-Div.3/D.cpp