Advertisement
Guest User

c.cpp

a guest
Jun 23rd, 2018
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.06 KB | None | 0 0
  1. #include <iostream>
  2. #include <cassert>
  3. #include <algorithm>
  4. #include <numeric>
  5. #include <vector>
  6. #include <cstdlib>
  7.  
  8. typedef long long ll;
  9.  
  10. ll sum(ll n, ll k) {
  11.     ll r = 0;
  12.     while (n > 0) {
  13.         ll curr = std::min(n, k);
  14.         r += curr;
  15.         n -= curr;
  16.         n -= n / 10;
  17.     }
  18.     return r;
  19. }
  20.  
  21. ll solve(ll n) {
  22.     ll low = 0, high = n;
  23.     while (high - low > 1) {
  24.         ll mid = (low + high) / 2;
  25.         if (2 * sum(n, mid) >= n) {
  26.             high = mid;
  27.         } else {
  28.             low = mid;
  29.         }
  30.     }
  31.     return high;
  32. }
  33.  
  34. ll slow(ll n) {
  35.     for (ll k = 1; k <= n; ++k) {
  36.         if (2*sum(n,k) >= n) {
  37.             return k;
  38.         }
  39.     }
  40.     throw 1;
  41. }
  42.  
  43. void test() {
  44.     for (ll n = 1; n <= 100; ++n) {
  45.         assert(slow(n) == solve(n));
  46.     }
  47.     std::cout << "ok!";
  48.     std::exit(0);
  49. }
  50.  
  51. int main() {
  52.     //test();
  53.     std::ios_base::sync_with_stdio(false);
  54.     std::cin.tie(0); std::cout.tie(0); std::cerr.tie(0);
  55.    
  56.     ll n;
  57.     std::cin >> n;
  58.     std::cout << solve(n);
  59.     return 0;
  60. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement