ICPC PTIT 2025 - VÒNG LUYỆN TẬP SỐ 2

Hi anh em, đây sẽ là series chia sẻ lời giải các contest ICPC Học viện Công nghệ Bưu chính Viễn thông Hà Nội (ICPC PTIT).

Lưu ý: Các hints và solutions trong bài viết có thể chưa phải là tối ưu nhất, do đó chỉ mang tính tham khảo. Và đừng quên là hãy thử tự suy nghĩ và làm thử trước khi xem solution nhé!

Bắt đầu thôi! 🤩

Problem A

Cho dãy số $A$ có $N$ phần tử. Hãy xác định xem có tồn tại một đa giác (không nhất thiết phải lồi) có độ dài các cạnh tương ứng là tập hợp $A$ hay không?

Gợi ý điều kiện cần và đủ: Một đa giác có N cạnh có tính chất: độ dài của cạnh dài nhất phải nhỏ hơn tổng của N - 1 cạnh còn lại.

Input:

• Dòng đầu tiên là số lượng cạnh $N$ ($1 \le N \le 100$).
• Dòng tiếp theo gồm $N$ số nguyên $A_i$ ($1 \le A_i \le 100$).

Output:

• In ra Yes nếu tồn tại đa giác.
• In ra No nếu không tồn tại đa giác.

Example:

Hint:

• Tính tổng tất cả các phần tử trong $A$.
• Tìm phần tử lớn nhất.
• Nếu phần tử lớn nhất nhỏ hơn tổng các phần tử còn lại $\Rightarrow$ In Yes.
• Ngược lại, in No.

Solution:

#include <bits/stdc++.h> #pragma GCC optimize("Ofast") using namespace std; using ll = long long;
#define endl '\n' const int MOD = 1e9 + 7; int main()
{ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; // cin >> t; while (t--) { int n; cin >> n; ll s = 0, mx = 0, x; for (int i = 0; i < n; ++i) { cin >> x; s += x; mx = max(mx, x); } cout << ((n >= 3 && mx < s - mx) ? "Yes" : "No"); } return 0;
}

Problem B

Cho dãy số $A$ có $N$ phần tử.

Cho dãy số $B$ ban đầu rỗng. Hãy thực hiện $N$ thao tác sau đây:

• Ở bước thứ $i$, thêm phần tử $A_i$ vào cuối của dãy $B$, sau đó đảo ngược dãy $B$.

Nhiệm vụ của bạn là xác định dãy số $B$ sau khi thực hiện $N$ thao tác.

Input:

• Dòng đầu tiên là số nguyên dương $N$ ($1 \le N \le 2 \cdot 10^5$).
• Dòng tiếp theo gồm $N$ số nguyên $A_i$ ($0 \le A_i \le 10^9$).

Output:

• In ra dãy số $B$ cuối cùng.

Example:

Giải thích test 1:

• Sau bước 1: B = (1)
• Sau bước 2: B = (1 2) $\rightarrow$ đảo ngược $\rightarrow$ (2 1)
• Sau bước 3: B = (2 1 3) $\rightarrow$ đảo ngược $\rightarrow$ (3 1 2)

Hint

Ta có thể tối ưu bằng cách:

• Duy trì một deque (hàng đợi hai đầu).
• Với mỗi phần tử mới:
  • Nếu lượt là chẵn: chèn vào đầu.
  • Nếu lượt là lẻ: chèn vào cuối.
• Cuối cùng, nếu tổng số thao tác là lẻ $\rightarrow$ đảo ngược kết quả.

Solution

#include <bits/stdc++.h> #pragma GCC optimize("Ofast") using namespace std; using ll = long long;
#define endl '\n' const int MOD = 1e9 + 7; int main()
{ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; // cin >> t; while (t--) { int n, x; cin >> n; deque<int> dq; for (int i = 1; i <= n; ++i) { cin >> x; if (i & 1) dq.emplace_back(x); else dq.emplace_front(x); } if (n & 1) { for (int i = n - 1; ~i; --i) cout << dq[i] << ' '; } else { for (int& i : dq) cout << i << ' '; } } return 0;
}

Problem C

Cánh đồng của nông dân John gồm nhiều thửa ruộng. Mỗi thửa ruộng là một đa giác khép kín, được bao quanh bởi các hàng rào (đoạn thẳng), và chỉ giao nhau tại các đỉnh chung là đầu mút.

Ngoài yếu tố diện tích, anh John quan tâm tới yếu tố năng suất, được anh quy đổi theo tỉ lệ thuận $1:1$ với bình phương diện tích của mỗi thửa ruộng.

Các bạn hãy giúp anh John tính tổng năng suất trên tất cả các thửa ruộng?

Input:

• Dòng đầu là số nguyên $N$ ($3 \le N \le 1000$), là số lượng các hàng rào.
• $N$ dòng tiếp theo, mỗi dòng gồm 4 số nguyên $x_1, y_1, x_2, y_2$ ($0 \le x_i, y_i \le 1000$) mô tả một hàng rào (đoạn thẳng).

Input đảm bảo rằng:

• Không có hai đoạn nào cắt nhau.
• Tất cả đoạn đều cần thiết để tạo thành các thửa ruộng.
• Toàn bộ hệ thống hàng rào là đồ thị phẳng, liên thông, không có cầu.

Output:

• In ra một số thực là tổng năng suất của cả cánh đồng, với độ chính xác 6 chữ số sau dấu phẩy.

Example:

Hint

• Mỗi đoạn thẳng tạo thành một cạnh của đồ thị phẳng.
• Với mỗi đoạn, xây dựng hai cung có hướng (đi xuôi và ngược) kèm góc phương vị.
• Duyệt qua tất cả các cạnh chưa được thăm theo hướng ngược chiều kim đồng hồ để tìm các mặt (face) thực sự đại diện cho các thửa ruộng.
• Áp dụng công thức diện tích đa giác:

  $$S = \frac{1}{2} \left| \sum_{i=1}^{n} (x_i y_{i+1} - x_{i+1} y_i) \right|$$

• Với mỗi mặt có diện tích $S > 0$, cộng $S^2$ vào tổng năng suất.

Solution

#include <bits/stdc++.h> #pragma GCC optimize("Ofast") using namespace std; using ll = long long;
using ld = long double;
#define endl '\n' const int MOD = 1e9 + 7; struct P
{ double x, y;
}; struct E
{ int a, b, rev; double ang;
}; int main()
{ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; // cin >> t; while (t--) { int n; cin >> n; vector<P> p; map<pair<int, int>, int> myMap; auto get = [&](int x, int y) { auto k = make_pair(x, y); auto it = myMap.find(k); if (it != myMap.end()) return it->second; int v = p.size(); myMap[k] = v; p.push_back({(double)x, (double)y}); return v; }; vector<E> e; vector<vector<int>> adj; adj.reserve(n << 1); for (int i = 0; i < n; ++i) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; int u = get(x1, y1), v = get(x2, y2); if ((int)adj.size() < (int)p.size()) adj.resize(p.size()); E e1{u, v, (int)e.size() + 1, atan2(p[v].y - p[u].y, p[v].x - p[u].x)}; E e2{v, u, (int)e.size(), atan2(p[u].y - p[v].y, p[u].x - p[v].x)}; e.emplace_back(e1); e.emplace_back(e2); adj[u].emplace_back(e.size() - 2); adj[v].emplace_back(e.size() - 1); } int m = e.size(); for (int v = 0; v < adj.size(); ++v) { auto& a = adj[v]; sort(a.begin(), a.end(), [&](int i, int j) { return e[i].ang < e[j].ang; }); } vector<int> nxt(m); for (int v = 0; v < adj.size(); ++v) { auto& a = adj[v]; int s = a.size(); for (int i = 0; i < s; ++i) { int idx1 = a[i]; int idx2 = a[(i - 1 + s) % s]; nxt[e[idx1].rev] = idx2; } } vector<bool> visited(m, false); double ans = 0; vector<int> f; for (int i = 0; i < m; ++i) if (!visited[i]) { f.clear(); int cur = i; while (!visited[cur]) { visited[cur] = true; f.emplace_back(e[cur].a); cur = nxt[cur]; } double tmp = 0; int k = f.size(); for (int j = 0; j < k; ++j) { P A = p[f[j]], B = p[f[(j + 1) % k]]; tmp += A.x * B.y - B.x * A.y; } tmp *= 0.5; if (tmp > 0) ans += tmp * tmp; } cout << fixed << setprecision(6) << ans << endl; } return 0;
}

Problem D

Một nhà hàng hiện đại có các món thức ăn chuyển động theo dây chuyền. Có tất cả $N$ vị trí chỗ ngồi, đánh dấu từ $1, 2, \dots, N$. Vì nhà hàng rất nổi tiếng, nhiều đoàn khách tới cần phải đúng giờ và có đủ slot trống thì nhà hàng mới phục vụ.

Trong một ngày nọ, có $M$ sự kiện diễn ra, thuộc 1 trong 2 nhóm như sau:

• Một đoàn có $K_i$ khách đến và họ muốn ngồi liền kề nhau. Nhân viên phục vụ muốn xếp nhóm này vào một dãy liên tiếp $K_i$ ghế trống. Nếu có thể, nhóm được xếp vào vị trí thấp nhất trong dãy ghế. Nếu không thể, nhóm khách sẽ bị từ chối phục vụ.
• Các khách ở vị trí ghế từ $A_i$ đến $B_i$ đã ăn xong và họ rời đi, những vị trí còn lại sẽ trở thành ghế trống.

Nhiệm vụ của bạn là đếm số lượng đoàn khách bị từ chối phục vụ trong ngày?

Input:

• Dòng đầu tiên là hai số nguyên dương $N$ và $M$ ($1 \le N, M \le 5 \cdot 10^5$).
• $M$ dòng tiếp theo, mỗi dòng mô tả một sự kiện theo thứ tự thời gian tăng dần:
  • Sự kiện loại 1: A K là có một đoàn $K$ khách tới nhà hàng.
  • Sự kiện loại 2: L a b là tất cả các khách từ vị trí $[a, b]$ sẽ rời đi.

Output:

• In ra một số nguyên là số lượng nhóm khách bị từ chối.

Example:

Giải thích test 1:

• Sự kiện 1: [1 1 1 1 1 1 0 0 0 0 0 0]
• Sự kiện 2: [1 0 0 0 1 1 0 0 0 0 0 0]
• Sự kiện 3: Không đủ chỗ, nhóm khách bị từ chối.
• Sự kiện 4: [1 1 0 0 1 1 1 0 0 0 0 0]

Hint

Bài toán yêu cầu bạn xử lý hai loại sự kiện động trên một dãy ghế có trạng thái "trống" hoặc "đã ngồi". Cần hỗ trợ:

• Tìm đoạn liên tiếp dài ít nhất $K$ chỗ trống (cho khách ngồi).
• Đánh dấu đoạn đã ngồi hoặc trả lại thành trống (sau khi rời đi).

Đây là bài toán quản lý đoạn liên tiếp điển hình, cần một cấu trúc dữ liệu mạnh để đảm bảo thời gian xử lý tốt (vì $M$ có thể tới $5 \cdot 10^5$).

Giải pháp: Segment Tree với Lazy Propagation (Đọc thêm tại Cây Phân Đoạn (Segment Tree) "Vỡ Lòng")

Dùng Segment Tree để quản lý đoạn ghế trống, với mỗi node lưu:

Ý tưởng xử lý:

Sự kiện A K (một nhóm $K$ khách đến):

1. Gọi query(1, 1, N, K) để tìm vị trí bắt đầu của đoạn ghế trống dài ít nhất $K$.
2. Nếu không tồn tại đoạn phù hợp, tăng biến ans (đếm nhóm bị từ chối).
3. Nếu tìm được, gọi update() để đánh dấu đoạn từ i đến i + K - 1 là đã ngồi (ghế bận).

Sự kiện L a b (trả lại chỗ từ $a$ đến $b$):

• Gọi upd(1, 1, N, a, b, 1) để đánh dấu đoạn này là trống.

Tại sao cần dùng segment tree?

• Cần truy vấn nhanh đoạn có $K$ ghế trống liên tiếp.
• Cần cập nhật trạng thái của cả một đoạn (bận hoặc trống).
• Với segment tree có lazy propagation:
  • Truy vấn và cập nhật đều có độ phức tạp $O(\log N)$.
  • Phù hợp với $N, M$ lên tới $5 \cdot 10^5$.

Mô phỏng đơn giản: Giả sử ban đầu tất cả ghế trống: [0 0 0 0 0 0]

• Sự kiện A 3: Tìm đoạn 000 và đánh dấu [1 1 1 0 0 0]
• Sự kiện L 2 3: Trả lại ghế 2 và 3 $\rightarrow$ [1 0 0 0 0 0]
• Sự kiện A 4: Tìm 0000 từ vị trí 2 $\rightarrow$ đánh dấu [1 1 1 1 0 0]

Solution

#include <bits/stdc++.h> #pragma GCC optimize("Ofast") using namespace std; using ll = long long;
#define endl '\n' const int MOD = 1e9 + 7; int n, m, ans;
int pfx[2000005], sfx[2000005], bst[2000005], lz[2000005]; void build(int o, int l, int r)
{ lz[o] = -1; pfx[o] = sfx[o] = bst[o] = r - l + 1; if (l == r) return; int m = (l + r) >> 1; build(o << 1, l, m); build(o << 1 | 1, m + 1, r);
} void apply(int o, int l, int r, int v)
{ lz[o] = v; if (v) pfx[o] = sfx[o] = bst[o] = r - l + 1; else pfx[o] = sfx[o] = bst[o] = 0;
} void push(int o, int l, int r)
{ if (lz[o] != -1) { int m = (l + r) >> 1; apply(o << 1, l, m, lz[o]); apply(o << 1 | 1, m + 1, r, lz[o]); lz[o] = -1; }
} void pull(int o, int l, int r)
{ int m = (l + r) >> 1, lc = o << 1, rc = o << 1 | 1; pfx[o] = pfx[lc] == m - l + 1 ? pfx[lc] + pfx[rc] : pfx[lc]; sfx[o] = sfx[rc] == r - m ? sfx[rc] + sfx[lc] : sfx[rc]; bst[o] = max({bst[lc], bst[rc], sfx[lc] + pfx[rc]});
} void update(int o, int l, int r, int ql, int qr, int v)
{ if (ql > r || qr < l) return; if (ql <= l && r <= qr) { apply(o, l, r, v); return; } push(o, l, r); int m = (l + r) >> 1; update(o << 1, l, m, ql, qr, v); update(o << 1 | 1, m + 1, r, ql, qr, v); pull(o, l, r);
} int query(int o, int l, int r, int k)
{ if (bst[o] < k) return -1; if (l == r) return l; push(o, l, r); int m = (l + r) >> 1; if (bst[o << 1] >= k) return query(o << 1, l, m, k); if (sfx[o << 1] + pfx[o << 1 | 1] >= k) return m - sfx[o << 1] + 1; return query(o << 1 | 1, m + 1, r, k);
} int main()
{ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; fill(lz, lz + 4 * n, -1); build(1, 1, n); while (m--) { char c; cin >> c; if (c == 'A') { int k; cin >> k; int i = query(1, 1, n, k); if (i < 0) ++ans; else update(1, 1, n, i, i + k - 1, 0); } else { int l, r; cin >> l >> r; update(1, 1, n, l, r, 1); } } cout << ans; return 0;
}

Problem E

Cho dãy số $A$ gồm $N$ phần tử và một số nguyên dương $K$. Hãy đếm số dãy con khác rỗng trong $A$ sao cho không có hai phần tử nào trong dãy con này có giá trị tuyệt đối hiệu của chúng bằng đúng $K$.

Vì kết quả có thể rất lớn, hãy in ra đáp án modulo $998244353$.

Input:

• Dòng đầu là số lượng bộ test $T$ ($1 \le T \le 100$).
• Mỗi test bắt đầu bởi hai số nguyên $N$ và $K$ ($1 \le N \le 2 \cdot 10^5$, $1 \le K \le 10^9$).
• Dòng thứ hai của mỗi test gồm $N$ số nguyên $A_i$ ($1 \le A_i \le 10^9$).

Output:

• Với mỗi test, in ra số lượng dãy con tìm được trên một dòng.

Example:

Giải thích test 3: Có 8 tập thỏa mãn là (2), (4), (7), (9), (2 7), (4 9), (4 7), (2 9)

Hint

• Nếu không có ràng buộc nào, thì một tập con có $n$ phần tử sẽ có $2^n - 1$ tập con khác rỗng.
• Nhưng ràng buộc ở đây là: không có cặp nào có hiệu tuyệt đối bằng đúng $K$.
• Để xử lý:
  1. Đếm số lần xuất hiện của từng phần tử: cnt[x].
  2. Xét từng chuỗi số dạng $x, x+K, x+2K, \dots$ (tức là các dãy cách đều nhau bởi $K$).
  3. Với mỗi chuỗi:
     • Nếu phần tử trước đó $(x-K)$ không tồn tại, ta bắt đầu từ $x$.
     • Duyệt các phần tử trong chuỗi theo thứ tự tăng, mỗi bước:
       • Gọi dp0 là số cách chọn các phần tử trước mà không chọn phần tử hiện tại.
       • Gọi dp1 là số cách chọn có phần tử hiện tại (phải không chọn phần tử trước đó).
     • Cập nhật bằng quy tắc động như:
       • $new\_dp0 = dp0 + dp1$
       • $new\_dp1' = dp0 * (2^{cnt[x]} - 1)$
  4. Vì mỗi chuỗi là độc lập, nên ta tính kết quả bằng cách nhân số cách với nhau.

Solution

#include <bits/stdc++.h> #pragma GCC optimize("Ofast") using namespace std; using ll = long long;
#define endl '\n' const int MOD = 998244353; int addMod(int a, int b)
{ int s = a + b; return s >= MOD ? s - MOD : s;
} int subMod(int a, int b)
{ int s = a - b; return s < 0 ? s + MOD : s;
} int mulMod(ll a, ll b)
{ return int((a * b) % MOD);
} int main()
{ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int pwr[200005]; pwr[0] = 1; for (int i = 1; i < 200005; ++i) pwr[i] = addMod(pwr[i - 1], pwr[i - 1]); int t; cin >> t; while (t--) { int n; ll k; cin >> n >> k; unordered_map<ll, int> cnt; cnt.reserve(n << 1); for (int i = 0; i < n; ++i) { ll x; cin >> x; ++cnt[x]; } vector<ll> val; val.reserve(cnt.size()); for (auto& p : cnt) val.emplace_back(p.first); sort(val.begin(), val.end()); int ans = 1; for (ll x : val) { if (cnt.find(x - k) != cnt.end()) continue; int dp0 = 1; int dp1 = subMod(pwr[cnt[x]], 1); ll y = x + k; while (cnt.find(y) != cnt.end()) { int c = cnt[y]; int ndp0 = addMod(dp0, dp1); int ndp1 = mulMod(dp0, subMod(pwr[c], 1)); dp0 = ndp0; dp1 = ndp1; y += k; } ans = mulMod(ans, addMod(dp0, dp1)); } ans = subMod(ans, 1); cout << ans << endl; } return 0;
}

Problem F

Cho $N$ chai soda. Chai thứ $i$ hiện chứa $A_i$ đơn vị soda và có dung tích tối đa là $B_i$ ($A_i \le B_i$). Cần thực hiện thao tác đổ soda giữa các chai để dồn toàn bộ lượng soda hiện có vào số lượng chai ít nhất có thể.

Mục tiêu:

• Sử dụng ít chai nhất (gọi là $K$ chai).
• Trong số các cách đạt được $K$ chai, hãy chọn cách tốn ít thời gian nhất (gọi là $T$).
• Biết rằng việc đổ $X$ đơn vị soda từ một chai sang chai khác mất $X$ giây.

Lưu ý:

• Lượng soda trong mỗi chai sau khi đổ không được vượt quá dung tích $B_i$.
• Tổng lượng soda ban đầu được bảo toàn.

Input:

• Dòng đầu tiên chứa số nguyên dương $N$ ($1 \le N \le 100$): số lượng chai.
• Dòng thứ hai gồm $N$ số nguyên $A_i$ ($1 \le A_i \le 100$): lượng soda còn lại trong chai thứ $i$.
• Dòng thứ ba gồm $N$ số nguyên $B_i$ ($1 \le B_i \le 100$): dung tích của chai thứ $i$.

Output:

• In ra hai số nguyên $K$ và $T$, trong đó $K$ là số lượng chai tối thiểu có thể chứa tất cả soda, và $T$ là thời gian tối thiểu để dồn soda vào $K$ chai đó.

Example:

Giải thích test 1:

• Đổ chai thứ nhất sang chai thứ hai (mất 2 giây),
• Đổ từ chai thứ tư 2 đơn vị sang chai thứ ba và 1 đơn vị sang chai thứ hai (3 giây),
• Tổng: 5 giây. Chỉ cần 2 chai để chứa toàn bộ soda.

Hint

• Gọi tổng lượng soda là $S = \sum A_i$.
• Sắp xếp $B_i$ giảm dần, cộng dồn từ lớn nhất đến khi tổng $\ge S$, ta tìm được số chai tối thiểu $K$.
• Bây giờ cần chọn ra $K$ chai có tổng dung tích $\ge S$ sao cho:
  • Soda dồn vào các chai đó là nhiều nhất (tức là đổ đi ít nhất).
  • Dùng kỹ thuật quy hoạch động kiểu Knapsack (balo - Có thể tham khảo ví dụ 2 tại Nhập Môn Quy Hoạch Động Cơ Bản):
    • Duyệt qua tất cả tập con $K$ chai, dùng mảng dp[k][c] để lưu lượng soda tối đa có thể đưa vào tổng dung tích $c$.
• Thời gian $T = S - m$, với $m$ là lượng soda đã đưa vào $K$ chai mục tiêu.

Solution

#include <bits/stdc++.h> #pragma GCC optimize("Ofast") using namespace std; using ll = long long;
#define endl '\n' int main()
{ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; int a[n], b[n]; int S = 0; for (int i = 0; i < n; ++i) { cin >> a[i]; S += a[i]; } for (int i = 0; i < n; ++i) cin >> b[i]; vector<int> sb(b, b + n); sort(sb.begin(), sb.end(), greater<int>()); int k = 0, sum = 0; while (sum < S) sum += sb[k++]; int C = sum; const int INF = 2e9; vector<vector<int>> dp(k + 1, vector<int>(C + 1, -INF)); dp[0][0] = 0; for (int i = 0; i < n; ++i) { int bi = b[i], ai = a[i]; for (int j = min(k, i + 1); j >= 1; --j) for (int c = C; c >= bi; --c) dp[j][c] = max(dp[j][c], dp[j - 1][c - bi] + ai); } int m = 0; for (int c = S; c <= C; ++c) m = max(m, dp[k][c]); cout << k << ' ' << S - m; return 0;
}

Problem G

Số Lucas được định nghĩa theo công thức đệ quy như sau:

• $L_0 = 2$
• $L_1 = 1$
• $L_i = L_{i-1} + L_{i-2}$ (với $i \ge 2$)

Nhiệm vụ của bạn là xác định số Lucas thứ $N$.

Input:

• Một số nguyên $N$ duy nhất ($1 \le N \le 86$)

Output:

• In ra số nguyên là số Lucas thứ $N$.

Example:

Hint

• Đây là một chuỗi giống như Fibonacci nhưng với hai giá trị khởi đầu khác: $L_0 = 2$, $L_1 = 1$.
• Tính toán bằng cách dùng biến tạm (không cần mảng) do mỗi testcase chỉ tính 1 lần.
• Dùng vòng lặp từ 2 đến $N$ để cập nhật dần $L_i = L_{i-1} + L_{i-2}$.

Solution

#include <bits/stdc++.h> #pragma GCC optimize("Ofast") using namespace std; using ll = long long;
#define endl '\n' int main()
{ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; if (n == 0) cout << 2; else if (n == 1) cout << 1; else { long long p = 2, q = 1, r; for (int i = 2; i <= n; ++i) { r = p + q; p = q; q = r; } cout << q; }
}

Problem H

Lớp học Cấu trúc dữ liệu & Giải thuật có $N$ sinh viên, trong đó có một số nhóm sinh viên chơi thân với nhau.
Nếu $X$ và $Y$ là bạn, $Y$ và $Z$ là bạn, theo tính chất bắc cầu, $X$ và $Z$ cũng là bạn.

Để tránh việc trao đổi bài, các thầy cô đã sắp xếp phòng thi cho các bạn sinh viên sao cho không có bất kỳ 2 sinh viên nào là bạn của nhau ở cùng một phòng.
Các bạn hãy thử tính xem các thầy cô cần sử dụng ít nhất bao nhiêu phòng thi?

Input:

• Dòng đầu tiên chứa hai số nguyên $N$ và $M$ ($N, M \le 200000$).
• $M$ dòng tiếp theo, mỗi dòng gồm 2 số nguyên $A_i$ và $B_i$, cho biết $A_i$ và $B_i$ là bạn của nhau ($A_i \ne B_i$).

Output:

• In ra một số nguyên duy nhất là số phòng thi ít nhất cần sử dụng.

Example:

Giải thích test 1:

Chia sinh viên thành các nhóm bạn:

• Nhóm 1: (1, 3, 5)
• Nhóm 2: (2, 4)
• Nhóm 3: (5) đã vào rồi

Tổng cộng cần 3 phòng thi vì mỗi nhóm bạn cần phòng riêng.

Hint

• Đây là bài toán tìm số thành phần liên thông trong đồ thị vô hướng.
• Mỗi sinh viên là 1 đỉnh, mỗi cặp bạn bè là 1 cạnh.
• Các nhóm bạn là các thành phần liên thông $\rightarrow$ cần tách nhau ra phòng thi.
• Giải bằng Disjoin Set Union (DSU) để gộp nhóm bạn:
  • Ban đầu mỗi sinh viên là 1 nhóm.
  • Duyệt các cặp bạn, gộp nhóm lại.
• Cuối cùng đếm số nhóm độc lập (tức là số đại diện không bị gộp vào nhóm khác).

Solution

#include <bits/stdc++.h> #pragma GCC optimize("Ofast") using namespace std; using ll = long long;
#define endl '\n' int findRoot(vector<int>& root, int x)
{ return root[x] == x ? x : root[x] = findRoot(root, root[x]);
} int main()
{ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t = 1; // cin >> t; while (t--) { int n, m; cin >> n >> m; vector<int> root(n + 1), sz(n + 1, 1); for (int i = 1; i <= n; ++i) root[i] = i; int ans = 1; while (m--) { int u, v; cin >> u >> v; int rootU = findRoot(root, u), rootV = findRoot(root, v); if (rootU != rootV) { root[rootV] = rootU; sz[rootU] += sz[rootV]; ans = max(ans, sz[rootU]); } } cout << ans; } return 0;
}

Problem I

Cho ba số nguyên $A$, $B$ và $K$. Trong các xâu có độ dài đúng bằng $A + B$, gồm $A$ ký tự a và $B$ ký tự b, hãy tìm xâu có thứ tự từ điển đúng bằng $K$.

Input

• Một dòng gồm 3 số nguyên $A$, $B$ và $K$ ($1 \le A, B \le 30$, $1 \le K \le S$).
• $S$ là số lượng xâu có $A$ ký tự a và $B$ ký tự b.
• $K$ đảm bảo không vượt quá phạm vi của số nguyên 64 bit.

Output

• In ra xâu thứ $K$ trong thứ tự từ điển.

Example

Giải thích test 1 và 2:

• Thứ tự các xâu lần lượt là: aabb, abab, abba, baab, baba, bbaa.

Hint

• Tổng số xâu hợp lệ là tổ hợp $C_{A + B}^{A}$.

• Với mỗi ký tự đầu tiên:

  • Nếu ta chọn a, thì còn lại cần tạo $A - 1$ ký tự a và $B$ ký tự b $\Rightarrow$ có $C_{A+B-1}^{A-1}$ xâu như vậy.
  • Nếu $K \le C_{A+B-1}^{A-1}$, thì ký tự đầu tiên là a.
  • Ngược lại, ký tự đầu tiên là b thì ta trừ đi số lượng xâu bắt đầu bằng a.

• Lặp lại quá trình này cho đến khi xâu được hình thành đầy đủ.

Solution

#include <bits/stdc++.h> #pragma GCC optimize("Ofast") using namespace std; using ll = long long;
#define endl '\n' int main()
{ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int a, b; unsigned long long k; cin >> a >> b >> k; int n = a + b; unsigned long long C[65][65]; for (int i = 0; i <= n; ++i) { C[i][0] = C[i][i] = 1; for (int j = 1; j < i; ++j) C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; } string s; while (a > 0 || b > 0) { if (a == 0) { s += 'b'; --b; } else if (b == 0) { s += 'a'; --a; } else { unsigned long long cnt = C[a + b - 1][a - 1]; if (k <= cnt) { s += 'a'; --a; } else { s += 'b'; k -= cnt; --b; } } } cout << s; return 0;
}

Problem J

Một bộ ba số $(a, b, c)$ được gọi là bộ ba số Pytago nếu:

$$a^2 = b^2 + c^2$$

Người ta mở rộng khái niệm này, gọi là "siêu Pytago", nếu thỏa mãn:

$$2a^2 = b^2 + c^2$$

với điều kiện $a$, $b$, $c$ đôi một khác nhau.

Input:

• Gồm một số nguyên dương $a$ duy nhất ($1 \le a \le 10^5$).

Output:

• In ra YES nếu tồn tại $b$ và $c$ khác nhau sao cho $2a^2 = b^2 + c^2$, ngược lại in NO.

Example:

Hint

• Gọi $T = 2a^2$, ta cần kiểm tra xem có tồn tại hai số nguyên dương $b \ne a$, $c \ne a$ sao cho $b^2 + c^2 = T$.
• Vì $1 \le a, b, c \le 10^5$, nên ta có thể áp dụng hai con trỏ (two pointers):
  1. Duyệt $b$ từ 1 tăng lên.
  2. Duyệt $c$ từ $\lfloor\sqrt{T}\rfloor$ giảm xuống.
  3. Bỏ qua nếu $b = a$ hoặc $c = a$.
  4. Nếu $b^2 + c^2 == T$ $\rightarrow$ in YES.
  5. Nếu nhỏ hơn $\rightarrow$ tăng $b$, nếu lớn hơn $\rightarrow$ giảm $c$.

Solution

#include <bits/stdc++.h> #pragma GCC optimize("Ofast") using namespace std; using ll = long long;
#define endl '\n' int main()
{ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll a; cin >> a; ll t = 2LL * a * a; ll l = 1, r = min(100000LL, (ll)sqrt(t)); while (l < r) { if (l == a) { ++l; continue; } if (r == a) { --r; continue; } ll s = l * l + r * r; if (s == t) { cout << "YES"; return 0; } if (s < t) ++l; else --r; } cout << "NO"; return 0;
}

Chúc anh em đạt thành tích cao, see ya~ 🫡