fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using int64 = long long;
  4. int main(){
  5.     ios::sync_with_stdio(false);
  6.     cin.tie(nullptr);
  7.     int T;
  8.     if(!(cin >> T)) return 0;
  9.     while(T--){
  10.         int N;
  11.         int64 K;
  12.         cin >> N >> K;
  13.  
  14.         // compute denom = 2^{N-1} - 1, but cap early: once 2^{k} > K we don't need exact big value
  15.         __int128 pw = 1; // will hold 2^{t}
  16.         int needed = N - 1;
  17.         for(int i = 0; i < needed; ++i){
  18.             // if pw already exceeded K (i.e., pw > K), then pw-1 > K-1, so denom > K and ceil(K/denom)=1
  19.             if(pw > (__int128)K) {
  20.                 // we can stop; keep pw as-is (some power of two > K)
  21.                 // no need to multiply further
  22.                 break;
  23.             }
  24.             pw *= 2;
  25.             // continue until we've done needed multiplications or pw > K
  26.         }
  27.         __int128 denom = pw - 1;
  28.         if(denom <= 0) denom = 1; // safety
  29.  
  30.         // compute a = 1 + ceil(K / denom)
  31.         __int128 a_minus1 = ( (__int128)K + denom - 1 ) / denom;
  32.         int64 a = (int64)(1 + a_minus1);
  33.  
  34.         vector<int64> A;
  35.         A.reserve(N);
  36.         A.push_back(a);
  37.         int64 rem = K;
  38.         for(int i = 1; i <= N-1; ++i){
  39.             int64 cur = A.back();
  40.             int64 can = cur - 1; // m_i <= A_i -1
  41.             int64 take = min(can, rem);
  42.             int64 next = cur + take;
  43.             A.push_back(next);
  44.             rem -= take;
  45.         }
  46.         // rem should be zero
  47.         // Output
  48.         for(int i = 0; i < N; ++i){
  49.             if(i) cout << ' ';
  50.             cout << A[i];
  51.         }
  52.         cout << '\n';
  53.     }
  54.     return 0;
  55. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
2
5 3
2 3
stdout
copy 
2 3 5 5 5
4 7
https://ideone.com/WIMx3i
language:
C++ 4.3.2 (gcc-4.3.2)
created:
11 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!