2020.1.30--vj补题

C - C

题目内容：

After passing a test, Vasya got himself a box of n candies. He decided to eat an equal amount of candies each morning until there are no more candies. However, Petya also noticed the box and decided to get some candies for himself.

This means the process of eating candies is the following: in the beginning Vasya chooses a single integer k, same for all days. After that, in the morning he eats k candies from the box (if there are less than k candies in the box, he eats them all), then in the evening Petya eats 10% of the candies remaining in the box. If there are still candies left in the box, the process repeats — next day Vasya eats k candies again, and Petya — 10% of the candies left in a box, and so on.

If the amount of candies in the box is not divisible by 10, Petya rounds the amount he takes from the box down. For example, if there were 97 candies in the box, Petya would eat only 9 of them. In particular, if there are less than 10 candies in a box, Petya won't eat any at all.

Your task is to find out the minimal amount of k that can be chosen by Vasya so that he would eat at least half of the n candies he initially got. Note that the number k must be integer.

Input

The first line contains a single integer n (1≤n≤1018) — the initial amount of candies in the box.

Output

Output a single integer — the minimal amount of k that would allow Vasya to eat at least half of candies he got.

Example

Input

Output

Note

In the sample, the amount of candies, with k=3, would change in the following way (Vasya eats first):

68→65→59→56→51→48→44→41→37→34→31→28→26→23→21→18→17→14→13→10→9→6→6→3→3→0.

In total, Vasya would eat 39 candies, while Petya — 29.

题意：有n颗糖果，V和P来吃这些糖果，一开始，V选择一个整数k，以后每天都相同数量k个。之后，早上他从盒子里吃k个糖果（如果盒子里少于k个糖果，他就全部吃掉），然后晚上P吃掉盒子里剩余的10％的糖果。如果盒子里还剩下糖果，则重复此过程-第二天，V再吃k糖果，P-盒子里剩下的糖果的10％，依此类推。如果包装盒中的糖果数量不能被10整除，则P将其从包装盒中取出的糖果数量向下取整。例如，如果盒子里有97个糖果，那么P只吃其中的9个。特别是，如果一个盒子里的糖果少于10，那么P根本不会吃任何糖果。任务是找出V可以选择的最小数量的k，以便他可以吃掉最初获得的n糖果的至少一半。注意数字k为整数。

思路：运用二分法

#include <bits/stdc++.h>

using  namespace std;

typedef long long ll;

int main()

{

    ll n,l,r,mid,x,tmp,cnt,sum,ans=1e18;

    cin>>n;

    l=0,r=n;

    while(l<=r){

        sum=0;

        mid=(l+r)/2;

        if(mid==0) {l+=1;continue;}//如果枚举出0，那么肯定是不可以的，所以l+1

        tmp=n;

        while(1){

            if(tmp>=mid) tmp-=mid,sum+=mid;//如果剩余的大于mid，那么减去mid，否则，直接取完

            else sum+=tmp,tmp=0;

            tmp-=tmp/10;

            x=n%2?(n/2)+1:n/2;//n/2不是整数，那么加一（相当与向上取整）

            if(sum>=x) break;//如果a取的蛋糕比n的一半还要多，那么这个mid是可以的

            if(tmp==0) {sum=-1;break;}

        }

        if(sum!=-1) r=mid-1,ans=min(ans,mid);//如果mid满足条件，更新ans

        else l=mid+1;

    }

    cout<<ans<<endl;

    return 0;

}

巴特西

2020.1.30--vj补题

C - C

最新文章

热门文章