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
Danh sách này được sắp xếp r đúng ko mn
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);
}
}
}
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
𝐴
=
[
1
,
2
,
3
]
A=[1,2,3] thì
𝐵
=
[
3
,
4
,
5
]
B=[3,4,5] và nếu
𝐴
=
[
1
,
3
,
3
,
3
]
A=[1,3,3,3] thì
𝐵
=
[
4
,
4
,
4
,
6
,
6
,
6
]
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
𝑛
(
𝑛
−
1
)
2
2
n(n−1)
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
,
𝐾
]
[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
≤
𝑛
≤
100
1≤n≤100.
1
≤
𝐾
≤
1
0
9
1≤K≤10
9
.
Example
Sample input
Copy
4
4 4 4 6 6 6
Sample output
Copy
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
]
[1,3,3,3] hoặc
[
2
,
2
,
2
,
4
]
[2,2,2,4] và cả 2 giải pháp đều được chấp nhận.
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
Output
Example
Test 1
Input
Output