fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long int
  5. #define pb push_back
  6. #define mp make_pair
  7.  
  8. bool check(ll n, ll k)
  9. {
  10.      if(k==0)
  11.           return false;
  12.      ll x = n, sum = 0;
  13.      while(n>0)
  14.      {
  15.           if(n>=k)
  16.                sum = sum + k;
  17.           else
  18.                sum = sum + n;
  19.           n = n-k;
  20.           n = n - n/10;
  21.      }
  22.      if(x%2==0)
  23.      {
  24.      if(sum>=x/2)
  25.           return true;
  26.      else
  27.           return false;  
  28.      }
  29.      else
  30.      {
  31.           if(sum>x/2)
  32.                return true;
  33.           else
  34.                return false;
  35.      }
  36. }
  37.  
  38. ll bs(ll n, ll s, ll e)
  39. {
  40.      ll mid = s + (e-s)/2;
  41.      bool a = check(n,mid-1);
  42.      bool b = check(n,mid+1);
  43.      if(a==true and b==true)
  44.           return bs(n,s,mid-1);
  45.      if(a==false and b==false)
  46.           return bs(n,s,mid+1);
  47.      if(a==false and b==true)
  48.      {
  49.           bool c = check(n,mid);
  50.           if(c==true)
  51.                return mid;
  52.           else
  53.                return mid+1;
  54.      }
  55. }
  56.  
  57. int main()
  58. {
  59.      std::ios::sync_with_stdio(false);
  60.      int t;
  61.      ll n;
  62.      cin>>n;
  63.      if(n<=10)
  64.      {
  65.           cout<<"1\n";
  66.           return 0;
  67.      }
  68.      ll k = bs(n,1,n);
  69.      if(check(n,k-1)==true)
  70.           cout<<k-1<<endl;
  71.      cout<<k<<endl;
  72.      return 0;
  73. }
Success #stdin #stdout 0s 4232KB
comments (?)
stdin
copy 
82
stdout
copy 
3
https://ideone.com/nEZXps
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!