Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cassert>
- #include <algorithm>
- #include <numeric>
- #include <vector>
- #include <cstdlib>
- typedef long long ll;
- ll sum(ll n, ll k) {
- ll r = 0;
- while (n > 0) {
- ll curr = std::min(n, k);
- r += curr;
- n -= curr;
- n -= n / 10;
- }
- return r;
- }
- ll solve(ll n) {
- ll low = 0, high = n;
- while (high - low > 1) {
- ll mid = (low + high) / 2;
- if (2 * sum(n, mid) >= n) {
- high = mid;
- } else {
- low = mid;
- }
- }
- return high;
- }
- ll slow(ll n) {
- for (ll k = 1; k <= n; ++k) {
- if (2*sum(n,k) >= n) {
- return k;
- }
- }
- throw 1;
- }
- void test() {
- for (ll n = 1; n <= 100; ++n) {
- assert(slow(n) == solve(n));
- }
- std::cout << "ok!";
- std::exit(0);
- }
- int main() {
- //test();
- std::ios_base::sync_with_stdio(false);
- std::cin.tie(0); std::cout.tie(0); std::cerr.tie(0);
- ll n;
- std::cin >> n;
- std::cout << solve(n);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement