CSES - List of Sums | Danh sách tổng
Xem PDF
Điểm:
2000 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Danh sách \(A\) gồm \(n\) số nguyên dương và danh sách \(B\) chứa tổng của mỗi cặp phần tử trong danh sách \(A\).
Ví dụ: nếu \(A=[1,2,3]\) thì \(B = [3,4,5]\) và nếu \(A = [1,3,3,3]\) thì \(B = [4,4,4,6,6,6]\).
Cho danh sách \(B\), nhiệm vụ của bạn là tạo lại danh sách \(A\).
Input
- Dòng đầu tiên nhập số nguyên \(n\) là kích thước của danh sách \(A\).
- Dòng tiếp theo chứa \(\frac{n(n-1)}{2}\) số nguyên là các số trong danh sách \(B\).
- Bạn có thể giả định rằng có một danh sách \(A\) tương ứng với đầu vào và mỗi giá trị trong \(A\) nằm trong khoảng \([1,K]\).
Output
- In ra \(n\) số nguyên trên cùng 1 dòng, cách nhau bởi dấu cách.
- Bạn có thể in ra theo bất kỳ thứ tự nào. Nếu có nhiều giải pháp, bạn có thể in bất kỳ giải pháp nào trong số chúng.
Constraints
- \(1 \le n \le 100\).
- \(1 \le K \le 10^9\).
Example
Sample input
4
4 4 4 6 6 6
Sample output
1 3 3 3
Note
- Giải thích: trong trường hợp này, danh sách \(A\) có thể là \([1,3,3,3]\) hoặc \([2,2,2,4]\) và cả 2 giải pháp đều được chấp nhận.
Bình luận
include<bits/stdc++.h>
using namespace std;
typedef long long Int;
const int N = 105;
const int NN = NN;
const Int INF = 2e9;
int n, sz;
Int a[N], sum[NN];
int low[N][N], high[N][N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
sz = n(n-1)/2;
for (int i = 1; i <= sz; i++) cin >> sum[i];
sort(sum+1, sum+1+sz);
for (int i = 1; i < n; i++) {
for (int j = i+1; j <= n; j++) {
int cnt_le = 0, cnt_ge = 0;
for (int k = 1; k <= i; k++)
cnt_le += j-k;
for (int k = i; k < n; k++)
cnt_ge += n-max(k+1,j)+1;
}
}
Int diff_23 = sum[2]-sum[1];
for (int i23 = 3; i23 <= min(3+n,sz); i23++) {
fill(a, a+1+n, 0);
Int sum_23 = sum[i23];
sum_23 += diff_23;
if (sum_23&1) continue;
a[3] = sum_23/2;
a[2] = a[3] - diff_23;
if (max(a[2],a[3]) > INF or min(a[2],a[3]) < 1) continue;
a[1] = sum[1] - a[2];
if (a[1] > INF or a[1] < 1) continue;
if (a[1] > a[2] or a[2] > a[3]) continue;
bool dbg = 1;
if (dbg)
cerr << a[1] << ' ' << a[2] << ' ' << a[3] << '\n';
bool okay = 1;
multiset<Int> remaining(sum+1, sum+1+sz);
remaining.erase(remaining.find(sum[1]));
remaining.erase(remaining.find(sum[2]));
remaining.erase(remaining.find(sum[i23]));
priority_queue<int, vector\<int>, greater\<int>> good_pos;
for (int i = 1, j=1; i <= sz; i++) {
while (j <= sz && sum[j]-sum[i] < a[2]-a[1]) ++j;
if (j > sz) break;
if (sum[j]-sum[i] == a[2]-a[1]) good_pos.push(i);
}
for (int id = 4; id <= n && okay; id++) {
bool ok = 0;
while (!good_pos.empty()) {
int first = good_pos.top(); good_pos.pop();
if (!remaining.count(sum[first])) continue;
bool chk = 1;
for (int i = 2; i < id && chk; i++)
chk &= remaining.count(sum[first]+a[i]-a[1])>0;
if (!chk) continue;
a[id] = sum[first]-a[1];
remaining.erase(remaining.find(sum[first]));
for (int i = 2; i < id && chk; i++)
remaining.erase(remaining.find(a[id]+a[i]));
ok = 1;
break;
}
okay &= ok;
}
if (okay) {
vector<Int> cur_sums;
for (int i = 1; i < n; i++)
for (int j = i+1; j <= n; j++)
cur_sums.push_back(a[i]+a[j]);
sort(cur_sums.begin(), cur_sums.end());
for (int i = 1; i <= sz; i++)
okay &= (cur_sums[i-1] == sum[i]);
}
if (okay) {
cerr << "Hello\n";
for (int i = 1; i <= n; i++)
cout << a[i] << ' ';
exit(0);
}
}
}
3 bình luận nữa