fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using int64 = long long;
  4.  
  5. int main(){
  6.     ios::sync_with_stdio(false);
  7.     cin.tie(nullptr);
  8.     int T;
  9.     if(!(cin >> T)) return 0;
  10.     while (T--){
  11.         int64 N, K;
  12.         cin >> N >> K;
  13.  
  14.         vector<int64> A(N);
  15.         if (N == 2){
  16.             // A1 minimal so that (A2 mod A1) = K; with monotonicity minimal A2 is A1+K
  17.             // Minimal A1 is K+1 -> A2 = A1 + K
  18.             A[0] = K + 1;
  19.             A[1] = A[0] + K;
  20.         } else {
  21.             // Compute denom = 2^{N-1}, but cap to K+1 to avoid overflow
  22.             long long denom = 1;
  23.             long long cap = K + 1; // if denom > K+1 then denom-1 >= K, good enough
  24.             for (int i = 0; i < N-1; ++i){
  25.                 if (denom > cap) { denom = cap; break; }
  26.                 denom = denom * 2;
  27.                 if (denom > cap) { denom = cap; break; }
  28.             }
  29.             long long denom_minus1 = denom - 1;
  30.             if (denom_minus1 <= 0) denom_minus1 = 1; // safety (though N>=2 so denom>=2 normally)
  31.  
  32.             if (denom_minus1 > K) denom_minus1 = K; // if denom-1 > K then ceil(K/denom_minus1)=1
  33.  
  34.             // minimal A1 = 1 + ceil(K / denom_minus1)
  35.             int64 A1 = 1 + ( (K + denom_minus1 - 1) / denom_minus1 );
  36.             A[0] = A1;
  37.  
  38.             long long rem = K;
  39.             for (int i = 0; i < N-1; ++i){
  40.                 long long cap_r = A[i] - 1;
  41.                 if (cap_r < 0) cap_r = 0;
  42.                 long long take = min(rem, cap_r);
  43.                 A[i+1] = A[i] + take;
  44.                 rem -= take;
  45.             }
  46.             // rem should be zero now
  47.         }
  48.  
  49.         for (int i = 0; i < N; ++i){
  50.             if (i) cout << ' ';
  51.             cout << A[i];
  52.         }
  53.         cout << '\n';
  54.     }
  55.     return 0;
  56. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
2
5 3
2 3
stdout
copy 
2 3 5 5 5
4 7
https://ideone.com/AbsX1c
language:
C++ (gcc 8.3)
created:
7 hours 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!