fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. const ll NMAX = 1000000000000LL; // 1e12
  5.  
  6. // Số phần tử còn lại trong [1..m] sau x lần
  7. ll survivors(ll m, ll y, ll x) {
  8.     if (m <= 0) return 0;
  9.     if (y == 1) {
  10.         // nếu có 1 lần trở lên thì xoá hết
  11.         return 0;
  12.     }
  13.     ll cur = m;
  14.     ll remSteps = x;
  15.     while (remSteps > 0 && cur > 0) {
  16.         ll rem = cur / y; // số bị xoá mỗi bước ở trạng thái này
  17.         if (rem == 0) break;
  18.         // tìm s lớn nhất sao cho trong s bước tiếp theo, rem vẫn giữ nguyên
  19.         // điều kiện: floor((cur - (s-1)*rem) / y) == rem
  20.         // suy ra: (cur - (s-1)*rem) / y >= rem
  21.         // => (s-1) <= (cur - rem*y) / rem
  22.         ll s_max;
  23.         if (cur - rem * y < 0) {
  24.             s_max = 0; // không có (s-1) >=0 thỏa, tức rem sẽ đổi ngay bước sau => ta chỉ làm 1 bước
  25.         } else {
  26.             s_max = (cur - rem * y) / rem; // đây là (s-1) max
  27.         }
  28.         ll s = s_max + 1; // số bước mà rem giữ nguyên tối đa
  29.         if (s <= 0) s = 1;
  30.         if (s > remSteps) s = remSteps;
  31.         // apply s steps
  32.         // cur -= s * rem
  33.         // careful not overflow: rem and s fit in ll, product <= cur <= 1e12
  34.         cur -= s * rem;
  35.         remSteps -= s;
  36.     }
  37.     return cur;
  38. }
  39.  
  40. int main() {
  41.     ios::sync_with_stdio(false);
  42.     cin.tie(nullptr);
  43.     int T;
  44.     if (!(cin >> T)) return 0;
  45.     while (T--) {
  46.         ll x, y, k;
  47.         cin >> x >> y >> k;
  48.  
  49.         // nếu tổng phần tử còn lại trong toàn bộ dãy < k thì -1
  50.         ll total = survivors(NMAX, y, x);
  51.         if (total < k) {
  52.             cout << -1 << '\n';
  53.             continue;
  54.         }
  55.  
  56.         ll lo = 1, hi = NMAX, ans = -1;
  57.         while (lo <= hi) {
  58.             ll mid = lo + (hi - lo) / 2;
  59.             if (survivors(mid, y, x) >= k) {
  60.                 ans = mid;
  61.                 hi = mid - 1;
  62.             } else lo = mid + 1;
  63.         }
  64.         cout << ans << '\n';
  65.     }
  66.     return 0;
  67. }
  68.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
6
2 3 5
2 5 1
20 2 1000000000000
175 10 28
1000000000 998244353 1999999999
1 1 1
stdout
copy 
10
1
-1
2339030304
4672518823
-1
https://ideone.com/LIu6Go
language:
C++14 (gcc 8.3)
created:
10 days 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!