fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. void solve() {
  9.     long long x, y, k;
  10.     cin >> x >> y >> k;
  11.  
  12.     if (y == 1) {
  13.         cout << -1 << "\n";
  14.         return;
  15.     }
  16.  
  17.     vector<long long> n_history;
  18.     long long n = 1000000000000LL;
  19.     n_history.push_back(n);
  20.  
  21.     for (int i = 0; i < x; ++i) {
  22.         long long n_prev = n;
  23.         n = n - n / y;
  24.         n_history.push_back(n);
  25.         if (n == n_prev) {
  26.             break;
  27.         }
  28.     }
  29.  
  30.     long long J = n_history.size() - 1;
  31.     long long current_k = k;
  32.     long long c = y - 1;
  33.  
  34.     long long n_final;
  35.     if (x <= J) {
  36.         n_final = n_history[x];
  37.     } else {
  38.         n_final = n_history[J];
  39.     }
  40.  
  41.     if (current_k > n_final) {
  42.         cout << -1 << "\n";
  43.         return;
  44.     }
  45.  
  46.     long long t = 0;
  47.     if (x > J) {
  48.         t = x - J;
  49.     }
  50.  
  51.     long long m = current_k - 1;
  52.     long long n_limit = n_history[J] - 1;
  53.     bool possible = true;
  54.  
  55.     while (t > 0) {
  56.         if (m > n_limit) {
  57.             possible = false;
  58.             break;
  59.         }
  60.         long long q = m / c;
  61.         if (q == 0) {
  62.             break;
  63.         }
  64.  
  65.         long long steps_to_limit = (n_limit - m) / q;
  66.         if (steps_to_limit == 0) {
  67.             possible = false;
  68.             break;
  69.         }
  70.  
  71.         long long next_m_boundary = (q + 1) * c;
  72.         long long steps_to_boundary = (next_m_boundary - m + q - 1) / q;
  73.         long long steps = min({steps_to_boundary, t, steps_to_limit});
  74.  
  75.         m += steps * q;
  76.         t -= steps;
  77.     }
  78.  
  79.     if (m > n_limit) {
  80.         possible = false;
  81.     }
  82.  
  83.     current_k = m + 1;
  84.  
  85.     long long i_start_loop = min(x, J);
  86.  
  87.     if (possible) {
  88.         for (long long i = i_start_loop - 1; i >= 0; --i) {
  89.             current_k = current_k + (current_k - 1) / c;
  90.             if (current_k > n_history[i]) {
  91.                 possible = false;
  92.                 break;
  93.             }
  94.         }
  95.     }
  96.  
  97.     if (possible) {
  98.         cout << current_k << "\n";
  99.     } else {
  100.         cout << -1 << "\n";
  101.     }
  102. }
  103.  
  104. int main() {
  105.     ios_base::sync_with_stdio(false);
  106.     cin.tie(NULL);
  107.     int t;
  108.     cin >> t;
  109.     while (t--) {
  110.         solve();
  111.     }
  112.     return 0;
  113. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin 
6
2 3 5
2 5 1
20 2 1000000000000
175 10 28
100000 998244353 1999999999
1 1 1
stdout 
10
1
-1
2339030304
2000199999
-1
https://ideone.com/i4Uku8
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!