fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using int64 = long long;
  4. const long long INF64 = (long long)4e18;
  5.  
  6. int main(){
  7.     ios::sync_with_stdio(false);
  8.     cin.tie(nullptr);
  9.     int T;
  10.     if(!(cin >> T)) return 0;
  11.     while(T--){
  12.         int64 N, K;
  13.         cin >> N >> K;
  14.  
  15.         // Helper: given start x = A1, can we achieve total sum >= K using greedy r_i <= A_i-1 ?
  16.         auto can = [&](int64 x)->bool{
  17.             long long rem = K;
  18.             long long Ai = x;
  19.             for(int i = 1; i <= N-1; ++i){
  20.                 long long cap = Ai - 1;
  21.                 if(cap < 0) cap = 0;
  22.                 long long take = min(rem, cap);
  23.                 rem -= take;
  24.                 // Ai+1 = Ai + take
  25.                 // cap Ai can grow large; cap values and Ai may overflow, cap to INF64
  26.                 if(i != N-1){ // only update Ai when needed for next iteration
  27.                     Ai = Ai + take;
  28.                     if(Ai > INF64/2) Ai = INF64; // cap to avoid overflow
  29.                 }
  30.                 if(rem == 0) return true;
  31.             }
  32.             return rem == 0;
  33.         };
  34.  
  35.         // Binary search minimal A1 >= 1 such that can(A1) == true
  36.         int64 lo = 1, hi = (long long)2e18; // hi big enough
  37.         while(lo < hi){
  38.             int64 mid = lo + (hi - lo) / 2;
  39.             if(can(mid)) hi = mid;
  40.             else lo = mid + 1;
  41.         }
  42.         int64 A1 = lo;
  43.  
  44.         // Build actual sequence using greedy fill (r_i = min(rem, A_i - 1))
  45.         vector<long long> A(N);
  46.         A[0] = A1;
  47.         long long rem = K;
  48.         for(int i = 0; i < N-1; ++i){
  49.             long long cap = A[i] - 1;
  50.             if(cap < 0) cap = 0;
  51.             long long r = min(rem, cap);
  52.             A[i+1] = A[i] + r;
  53.             rem -= r;
  54.         }
  55.         // rem must be 0
  56.         for(int i = 0; i < N; ++i){
  57.             if(i) cout << ' ';
  58.             cout << A[i];
  59.         }
  60.         cout << '\n';
  61.     }
  62.     return 0;
  63. }
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/T8ng7u
language:
C++ (gcc 8.3)
created:
8 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!