爱奇艺 最后一位 数学

题目描述

牛牛选择了一个正整数X,然后把它写在黑板上。然后每一天他会擦掉当前数字的最后一位,直到他擦掉所有数位。 在整个过程中,牛牛会把所有在黑板上出现过的数字记录下来,然后求出他们的总和sum.
例如X = 509, 在黑板上出现过的数字依次是509, 50, 5, 他们的和就是564.
牛牛现在给出一个sum,牛牛想让你求出一个正整数X经过上述过程的结果是sum.

输入描述:

输入包括正整数sum(1 ≤ sum ≤ 10^18)

输出描述:

输出一个正整数,即满足条件的X,如果没有这样的X,输出-1。

示例1

输入

564

输出

509

#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long int
ll maxn = 1e18+5;
ll bsearch(ll left,ll ri,ll num);
ll judge(ll i,ll num);
int main()
{
    ll num;
    while(cin>>num)
    {
        if(bsearch(0,maxn,num)==-2)
        {
            cout<<"-1"<<endl;
        }else cout<<bsearch(0,maxn,num)<<endl;        
    }
    return 0;
}
ll bsearch(ll left,ll ri,ll num)
{
    while (left <= ri)
    {
        ll mid = (left + ri)/2;
        //cout<<mid<<"mid值"<<endl;
        if(judge(mid,num)==-1) left = mid+1;
        else if(judge(mid,num)==1)
        {
            ri=mid-1;
        }else 
        {
            return mid;        
        }
    }
    return -2;
}
ll judge(ll i,ll num)        //i 为检验的值，num 为 
{
    ll a=i;
    ll b=a;
    //cout<<i<<"i值"<<endl;
    //cout<<a<<"a值"<<endl;
    while(a)
    {
        a/=10;
        b+=a;        
    }
    //cout<<b<<endl;
    if(b>num)
    {
        return 1;
    }else if(b==num)
    {
        return 0;
    }else {
        return -1;
    }
    return 0;
}