Sizə k elementdən ibarət a massivi verilib hansı ki, elementləri artan sıradadır.…
- User
Sizə k elementdən ibarət a massivi verilib hansı ki, elementləri artan sıradadır. a1<a2<⋯<ak .
Massivin xarakteri onun qonşu elementlərinin fərqləri arasındakı [a2−a1,a3−a2,…,ak−ak−1] müxtəlif elementlərin sayı ilə təyin olunur. Məsələn [1,3,4,7,8] massivin xarakteri 3 dür. Çünki massivdəki qonşu elementlərin fərqi [2,1,3,1] 3 müxtəlif elementdən ibarətdir: 2 , 1 and 3 .
Sizə verilmiş k və n üçün xarakteri maksimum olan 1-n aralığında dəyərlər ala bilən artan sıralı massiv qurun.
Input t (1≤t≤819 )
k and n (2≤k≤n≤40 ).
Example InputCopy 7 5 9 4 12 3 3 3 4 4 4 4 6 8 11 OutputCopy 1 3 4 7 8 2 4 7 12 1 2 3 1 3 4 1 2 3 4 2 4 5 6 1 2 3 5 6 7 8 11 c++da yaz
- Assistant
To solve this problem, we need to construct an increasing sequence of
kdistinct integers within the range[1, n]such that the number of unique differences between consecutive elements is maximized. This number of unique differences is referred to as the "character" of the array.Steps to Solve the Problem:
-
Determine the Maximum Number of Unique Differences (
m):- Given the constraints, we first need to determine the maximum possible number of unique differences
mfor each test case. - This is derived by solving the inequality ( m(m - 1)/2 \leq n - k ), ensuring that we can fit
mdistinct differences within the allowable range.
- Given the constraints, we first need to determine the maximum possible number of unique differences
-
Select the Differences:
- Using dynamic programming, we select
mdistinct integers from[1, n-1]whose sum is as large as possible without exceeding the limit ( n - 1 - (k - 1 - m) ). - This ensures that the sum of the selected differences plus the remaining differences (set to 1) does not cause the final element to exceed
n.
- Using dynamic programming, we select
-
Construct the Sequence:
- Start with the first element set to 1.
- For each subsequent element, add the selected differences in ascending order to ensure the array remains increasing.
- This guarantees that the sequence ends at or before
n.
-
Output the Sequence:
- Finally, output the constructed sequence for each test case.
Here's the implementation of the solution in C++:
#include <bits/stdc++.h> using namespace std; // Function to compute m and sum_limit pair<int, int> compute_m_and_limit(int k, int n){ int p = k-1; // floor((1 + sqrt(1 +8*(n -k)))/2) double temp = (1.0 + sqrt(1.0 + 8.0*(n - k))) / 2.0; int m_max = floor(temp); m_max = min(p, m_max); return {m_max, n -1 - (p - m_max)}; } // Function to select m numbers from 1 to n_limit with maximum sum <=sum_limit vector<int> select_differences(int m, int n_limit){ // DP[j][s] = last number to reach j numbers with sum s vector<vector<int>> dp(m+1, vector<int>(n_limit+1, -1)); dp[0][0] = -2; // base case for(int num=1; num<=n_limit; ++num){ for(int j = min(m, num); j >=1; --j){ for(int s = n_limit; s >= num; --s){ if(dp[j-1][s-num] != -1 && dp[j][s] == -1){ dp[j][s] = num; } } } } // Find the maximum s <=n_limit such that dp[m][s]!=-1 int s_max = n_limit; while(s_max >=0 && dp[m][s_max]==-1) s_max--; // Backtrack to find the numbers vector<int> diffs; int current_j =m; int current_s =s_max; while(current_j >0){ int num = dp[current_j][current_s]; diffs.push_back(num); current_j--; current_s -=num; } return diffs; } int main(){ ios::sync_with_stdio(false); cin.tie(0); int t; cin >> t; while(t--){ int k, n; cin >> k >> n; // Compute m and sum_limit pair<int, int> mp = compute_m_and_limit(k, n); int m = mp.first; int sum_limit = mp.second; // Select differences vector<int> diffs; if(m >0){ diffs = select_differences(m, sum_limit); } // Sort diffs ascendingly sort(diffs.begin(), diffs.end()); // Assign the rest differences as 1 int p =k-1; int extra = p -m; for(int i=0;i<extra;i++) diffs.push_back(1); // Now, sort diffs to have some order, optional // sort(diffs.begin(), diffs.end()); // Construct the sequence // Start from a1=1 vector<int> sequence; sequence.push_back(1); for(auto d: diffs){ int next = sequence.back() + d; sequence.push_back(next); } // If the last element exceeds n, adjust // But according to sum_d + extra <=n-1, so a_k =1 + sum_d + extra <=n // So it's already <=n // Output the sequence for(int i=0;i<sequence.size();i++){ if(i>0) cout << ' '; cout << sequence[i]; } cout << '\n'; } } -