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.         // denom = 2^{N-1} (we'll use denom-1 later). cap to avoid overflow:
  15.         // we only need denom-1 up to at most K (because if denom-1 >= K then ceil(K/denom-1)=1)
  16.         int64 denom = 1;
  17.         for(int i = 0; i < N-1; ++i){
  18.             // multiply by 2 but cap to K+1 to avoid uselessly large numbers
  19.             if(denom > (K + 1)) { // already larger than K+1, keep it capped
  20.                 denom = K + 1;
  21.                 break;
  22.             }
  23.             denom = denom * 2;
  24.             if(denom > (K + 1)) { denom = K + 1; break; }
  25.         }
  26.         int64 denom_minus1 = denom - 1; // this is 2^{N-1} - 1 but possibly capped
  27.         if(denom_minus1 > K) denom_minus1 = K; // if it's > K, treat as K so ceil gives 1
  28.  
  29.         // compute minimal A1
  30.         // A1 = 1 + ceil(K / denom_minus1)
  31.         // denom_minus1 >= 1 because N >= 2
  32.         int64 A1 = 1 + ( (K + denom_minus1 - 1) / denom_minus1 );
  33.  
  34.         vector<int64> A(N);
  35.         A[0] = A1;
  36.         int64 rem = K;
  37.         for(int i = 0; i < N-1; ++i){
  38.             int64 can = A[i] - 1; // upper bound for r_i
  39.             int64 r = min(rem, can);
  40.             A[i+1] = A[i] + r;
  41.             rem -= r;
  42.         }
  43.         // rem should be 0
  44.         for(int i = 0; i < N; ++i){
  45.             if(i) cout << ' ';
  46.             cout << A[i];
  47.         }
  48.         cout << '\n';
  49.     }
  50.     return 0;
  51. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
2
5 3
2 3
stdout
copy 
2 3 5 5 5
4 7
https://ideone.com/09CJuU
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!