fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. int main() {
  6.     ios::sync_with_stdio(false);
  7.     cin.tie(nullptr);
  8.  
  9.     int t;
  10.     cin >> t;
  11.     while (t--) {
  12.         int n;
  13.         cin >> n;
  14.         vector<ll> h(n + 1);
  15.         for (int i = 1; i <= n; ++i) cin >> h[i];
  16.  
  17.         // Thử đặt c1 = 0, sẽ tính c2...cn theo công thức
  18.         // hi + ci + 2c(i-1) = H  =>  ci = H - hi - 2c(i-1)
  19.         // Cuối cùng điều kiện vòng: H - h1 - 2c_n = c1 (=0)
  20.         // => H = h1 + 2c_n
  21.  
  22.         vector<ll> c(n + 1);
  23.         c[1] = 0; // giả định
  24.         ll H = 0;
  25.  
  26.         // H chưa biết nên ta tạm tính theo công thức tuyến tính chứa H
  27.         // ci = a_i * H + b_i
  28.         vector<ll> a(n + 1), b(n + 1);
  29.         a[1] = 0; b[1] = 0;
  30.         for (int i = 2; i <= n; ++i) {
  31.             a[i] = 1 - 2 * a[i - 1];
  32.             b[i] = -h[i] - 2 * b[i - 1];
  33.         }
  34.  
  35.         // Từ điều kiện vòng: H - h1 - 2c_n = c1
  36.         // => H - h1 - 2(a_n*H + b_n) = 0
  37.         // => H * (1 - 2a_n) = h1 + 2b_n
  38.         ll denom = (1 - 2 * a[n]);
  39.         if (denom == 0) {
  40.             cout << -1 << "\n";
  41.             continue;
  42.         }
  43.  
  44.         if ((h[1] + 2 * b[n]) % denom != 0) {
  45.             cout << -1 << "\n";
  46.             continue;
  47.         }
  48.  
  49.         H = (h[1] + 2 * b[n]) / denom;
  50.  
  51.         // Tính lại toàn bộ c[i]
  52.         for (int i = 1; i <= n; ++i)
  53.             c[i] = a[i] * H + b[i];
  54.  
  55.         bool ok = true;
  56.         for (int i = 1; i <= n; ++i)
  57.             if (c[i] < 0) ok = false;
  58.  
  59.         if (!ok) {
  60.             cout << -1 << "\n";
  61.             continue;
  62.         }
  63.  
  64.         ll total = accumulate(c.begin() + 1, c.end(), 0LL);
  65.         cout << total << "\n";
  66.         for (int i = 1; i <= n; ++i)
  67.             cout << c[i] << (i == n ? '\n' : ' ');
  68.     }
  69. }
  70.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
2
4
3 3 0 2
3
1 2 4
stdout
copy 
4
0 2 1 1
-1
https://ideone.com/aotURS
language:
C++14 (gcc 8.3)
created:
5 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!