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

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 $N$ điểm trên mặt phẳng $Oxy$. Input đảm bảo không có 2 điểm nào có cùng tọa độ. Hãy đếm số cách chọn ra 3 điểm bất kỳ để tạo thành một tam giác có diện tích lớn hơn 0.

Input

• Dòng đầu tiên chứa số nguyên $N$ ($3 \le N \le 300$).
• $N$ dòng tiếp theo, mỗi dòng gồm 2 số nguyên $X_i$ và $Y_i$ mô tả tọa độ của một điểm ($-10^9 \le X_i, Y_i \le 10^9$).

Output

• In ra một số nguyên là số lượng tam giác tìm được có diện tích lớn hơn $0$.

Example

Giải thích test 1:

Có $\binom{4}{3} = 4$ bộ ba điểm, nhưng một trong số đó tạo tam giác có diện tích bằng $0$ (thẳng hàng). Vì vậy, chỉ còn lại 3 tam giác thực sự.

Hint

• Với mỗi bộ ba điểm $(i, j, k)$, kiểm tra xem chúng có thẳng hàng không.
• Nếu không thẳng hàng, thì bộ ba này tạo được tam giác có diện tích $> 0$.
• Cách kiểm tra thẳng hàng:
  • Diện tích tam giác $(i, j, k)$ là 0 khi:

    $$(x_j - x_i)(y_k - y_i) = (y_j - y_i)(x_k - x_i)$$

  • Nếu không bằng, tức là tạo thành tam giác hợp lệ.

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; vector<ll> x(n), y(n); for (int i = 0; i < n; ++i) cin >> x[i] >> y[i]; ll ans = 0; for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) for (int k = j + 1; k < n; ++k) if ((x[j] - x[i]) * (y[k] - y[i]) != (y[j] - y[i]) * (x[k] - x[i])) ++ans; cout << ans; return 0;
}

Problem B

Cho xâu $S$ độ dài $N$ và $K$ từ trong từ điển.
Tính số cách ghép các từ trong từ điển để tạo thành xâu $S$ (một từ có thể sử dụng nhiều lần).

Input:

• Dòng đầu: xâu $S$ có độ dài $N$ ($1 \le N \le 5000$).
• Dòng thứ hai: số nguyên $K$ ($1 \le K \le 10^5$).
• $K$ dòng tiếp theo: mỗi dòng là một từ trong từ điển. Các từ trong từ điển là phân biệt.

Output:

• In ra số cách ghép từ để tạo thành xâu $S$ modulo $10^9 + 7$.

Example:

Giải thích:

Có 2 cách tách xâu ababc bằng từ trong từ điển:

1. ab + ab + c
2. abab + c

Hint

• Đây là bài toán quy hoạch động (Dynamic Programming).

• Gọi dp[i] là số cách tạo ra prefix đầu tiên có độ dài i.

• Đáp án bài toán: dp[n].

• Bài toán đơn giản nhất: dp[0] = 1 (Không chọn cũng là 1 cách).

• Duyệt từ i = 0 đến n - 1:

  • Nếu dp[i] > 0:
    • Bắt đầu từ vị trí i, mở rộng theo Trie từ điển.
    • Nếu tại vị trí j, chuỗi s[i..j] tạo thành từ hợp lệ $\rightarrow$ cộng dp[i] vào dp[j + 1].

• Sử dụng Trie để lưu từ điển để truy vấn từ nhanh hơn.

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--) { string s; int k; cin >> s >> k; int n = s.size(); vector<array<int, 26>> trie; vector<bool> leaf; trie.reserve(100005); leaf.reserve(100005); trie.push_back({}); leaf.push_back(0); for (int i = 0; i < k; ++i) { string w; cin >> w; if ((int)w.size() > n) continue; int u = 0; for (char c : w) { int x = c - 'a'; if (!trie[u][x]) { trie[u][x] = trie.size(); trie.push_back({}); leaf.push_back(0); } u = trie[u][x]; } leaf[u] = 1; } int dp[n + 5]; memset(dp, 0, sizeof(dp)); dp[0] = 1; for (int i = 0; i < n; ++i) { if (!dp[i]) continue; int u = 0; for (int j = i; j < n; ++j) { int x = s[j] - 'a'; u = trie[u][x]; if (!u) break; if (leaf[u]) { dp[j + 1] = dp[j + 1] + dp[i]; if (dp[j + 1] >= MOD) dp[j + 1] -= MOD; } } } cout << dp[n]; } return 0;
}

Problem C

Cho một xâu $S$.
Nhiệm vụ của bạn là tìm xâu con dài nhất (liên tiếp) sao cho xâu đó bắt đầu bằng ký tự A và kết thúc bằng ký tự Z.

Input:

• Một xâu $S$ chỉ gồm các chữ cái in hoa (từ A đến Z), độ dài không quá $2 \cdot 10^5$.

Output:

• In ra độ dài xâu con dài nhất thỏa mãn điều kiện.

Example:

Giải thích:

• Với ZABCDZ: đoạn A B C D Z có độ dài 5 là xâu con bắt đầu bằng A và kết thúc bằng Z.
• Với TXASDFZXCUV: đoạn A S D F Z dài 5 là dài nhất thỏa yêu cầu.

Hint

• Duyệt chuỗi $S$, tìm chỉ số đầu tiên có ký tự A, gọi là minA.
• Tìm chỉ số cuối cùng có ký tự Z, gọi là maxZ.
• Nếu không có A hoặc không có Z, thì không tồn tại xâu con thỏa yêu cầu $\rightarrow$ in ra 0.
• Nếu có, thì độ dài lớn nhất cần tìm là:

  $$\text{maxZ} - \text{minA} + 1$$

Solution

#include <bits/stdc++.h> #pragma GCC optimize("Ofast") using namespace std; int main()
{ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); string s; cin >> s; int minA = 1e9, maxZ = -1; for (int i = 0; i < s.size(); ++i) { if (s[i] == 'A') minA = min(minA, i); if (s[i] == 'Z') maxZ = max(maxZ, i); } if (minA == 1e9 || maxZ == -1) cout << 0; else cout << maxZ - minA + 1; return 0;
}

Problem D

Cho dãy số $A$ có $N$ phần tử.
Mỗi phần tử sẽ được gán cho một màu sao cho với 2 phần tử $A_i$ và $A_j$ ($i < j$), nếu chúng được tô cùng một màu, thì bắt buộc phải có $A_i < A_j$.

Nhiệm vụ của bạn là xác định xem ít nhất cần bao nhiêu màu để tô dãy số đã cho thỏa mãn điều kiện.

Input:

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

Output:

• In ra số nguyên là số lượng màu ít nhất cần dùng.

Example:

Giải thích:

• Test 1: (3, 4, 5) được tô một màu (theo thứ tự tăng), và (1, 2) được tô một màu khác.
  Tổng cộng cần 2 màu.
• Test 2: Vì tất cả phần tử bằng nhau nên không thể tô 2 phần tử giống nhau vào cùng màu $\rightarrow$ cần 4 màu.

Hint

• Yêu cầu của đề bài tương đương với việc phân chia mảng thành nhiều dãy con tăng.
• Mỗi dãy con sẽ là một nhóm cùng màu.
• Do đó, cần tìm số dãy con tăng nhiều nhất có thể phân chia mảng ban đầu.
• Kỹ thuật hiệu quả:
  • Lật dấu các phần tử: thay $A_i$ thành $-A_i$ $\rightarrow$ tìm độ dài dãy giảm dài nhất.
  • Sử dụng kỹ thuật tương tự như LIS (Longest Increasing Subsequence) với upper_bound.

Solution

#include <bits/stdc++.h> #pragma GCC optimize("Ofast") using namespace std; int main()
{ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; int a[n]; for (int i = 0; i < n; ++i) cin >> a[i]; vector<int> d; d.reserve(n); for (int i = 0; i < n; ++i) { int x = -a[i]; auto it = upper_bound(d.begin(), d.end(), x); if (it == d.end()) d.emplace_back(x); else *it = x; } cout << d.size(); return 0;
}

Problem E

Tí và Tèo cùng chơi trò chơi đối kháng như sau:

1. Có $n$ viên sỏi trong rổ. Mỗi lượt, người chơi sẽ bốc ít nhất 1 viên và nhiều nhất là n viên còn lại. Tí đi trước, hai người chơi luân phiên nhau.
2. Mỗi lượt, người chơi chỉ được bốc nhiều nhất bằng 2 lần số viên sỏi mà người chơi trước đó đã bốc.
3. Người chơi nào lấy được viên sỏi cuối cùng sẽ là người chiến thắng.

Yêu cầu: Hãy xác định số viên sỏi ít nhất Tí nên bốc ở lượt đầu tiên để chắc chắn giành chiến thắng, bất kể Tèo chơi như thế nào.

Input

• Một số nguyên dương duy nhất $n$ ($1 \le n \le 10^{15}$) - số viên sỏi ban đầu.

Output

• In ra số viên sỏi ít nhất mà Tí phải bốc ở lượt đầu tiên để đảm bảo chắc chắn thắng.

Example

Giải thích

• Test 1: Nếu Tí bốc 1 viên, Tèo chỉ có thể bốc 1 hoặc 2 viên. Sau đó Tí luôn còn thế thắng nhờ kiểm soát lượt cuối.
• Test 2: Nếu Tí bốc 2 viên, Tèo bị rơi vào thế thua (Tí luôn giữ quyền kiểm soát).
• Test 3: Tí phải bốc toàn bộ (8 viên) mới chắc thắng, vì mọi nước nhỏ hơn đều dẫn đến thua.

Hint

• Đây là biến thể của trò chơi Fibonacci Nim.
• Gọi $F = \{1, 2, 3, 5, 8, 13, 21, \dots\}$ là dãy Fibonacci.
• Nếu tổng số sỏi $n$ được viết theo tổng không liên tiếp các số Fibonacci, thì:
  • Người đi trước sẽ thắng nếu lượt đi đầu tiên là số Fibonacci lớn nhất không vượt quá $n$.
• Áp dụng Chiến lược Zeckendorf:
  • Biểu diễn $n$ thành tổng của các số Fibonacci không liên tiếp.
  • Số đầu tiên trong biểu diễn này chính là số sỏi ít nhất Tí nên bố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 n; cin >> n; vector<ll> f{1, 2}; while (f.back() <= n) f.emplace_back(f[f.size() - 1] + f[f.size() - 2]); ll r = n, a = n; for (int i = (int)f.size() - 1; i >= 0; --i) { if (f[i] <= r) { r -= f[i]; a = f[i]; } if (r == 0) break; } cout << a; return 0;
}

Problem F

Cho hai số nguyên $a$ và $b$ với:

• $1 \le a \le 10^{12}$
• $1 \le b \le 10^{250}$

Nhiệm vụ của bạn là tìm ước số chung lớn nhất (GCD) của hai số $a$ và $b$.

Input

• Dòng đầu tiên là số nguyên $T$ — số lượng test ($1 \le T \le 100$).
• Với mỗi test gồm 2 dòng:
  • Dòng đầu tiên chứa số nguyên $a$.
  • Dòng thứ hai chứa số nguyên lớn $b$ (là chuỗi ký tự).

Output

• Với mỗi test, in ra GCD(a, b) trên một dòng.

Example

Hint

• Vì $b$ rất lớn (tới $250$ chữ số), không thể đọc trực tiếp bằng kiểu số nguyên thông thường.
• Nhưng bạn có thể tính $b \bmod a$ bằng cách duyệt từng chữ số của $b$:
  • Với mỗi chữ số $c$: $r = (r \times 10 + c) \bmod a$
• Sau đó dùng công thức:

  $$\gcd(a, b) = \gcd(a, b \bmod a)$$

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 t; cin >> t; while (t--) { ll a; string b; cin >> a >> b; ll rem = 0; for (char ch : b) rem = (rem * 10 + (ch - '0')) % a; cout << __gcd(a, rem) << endl; // cout << gcd(a, rem) << endl; (C++17 trở lên) } return 0;
}

Problem G

Cho dãy số $A$ gồm $N$ số nguyên $A_1, A_2, \dots, A_N$, mỗi phần tử có giá trị từ $0$ đến $M - 1$.

Trong một thao tác, bạn có thể:

• Chọn một số nguyên $K$ và một dãy chỉ số $i_1, i_2, \dots, i_K$ sao cho $1 \le i_1 < i_2 < \dots < i_K \le N$.
• Với mỗi chỉ số $i_x$ đã chọn, thay đổi giá trị $A_{i_x} := (A_{i_x} + 1) \bmod M$.

Nhiệm vụ:
Tìm số thao tác tối thiểu để biến dãy số $A$ thành một dãy không giảm, tức là $A_1 \le A_2 \le \dots \le A_N$.

Input

• Dòng đầu tiên chứa hai số nguyên $N$ và $M$ ($1 \le N \le 3 \cdot 10^5$, $1 \le M \le 3 \cdot 10^5$).
• Dòng tiếp theo gồm $N$ số nguyên $A_i$ ($0 \le A_i < M$).

Output

• In ra số nguyên là số thao tác tối thiểu cần thực hiện.
• Nếu dãy đã không giảm từ đầu, in ra 0.

Example

Giải thích

• Test 2: Chọn các chỉ số (2, 5) để tăng 1 đơn vị:
  0 6 1 3 2 $\rightarrow$ 0 0 1 3 3 $\rightarrow$ dãy tăng dần $\rightarrow$ chỉ cần 1 thao tác.

Hint

Ý tưởng chính:

Ta không được phép thay đổi thứ tự các phần tử trong mảng, chỉ được tăng giá trị từng phần tử (theo modulo M) thông qua các thao tác.

Mục tiêu là tìm số thao tác tối thiểu sao cho dãy sau khi biến đổi trở thành không giảm.

Phân tích thao tác

Mỗi thao tác cho phép chọn một tập con bất kỳ các chỉ số trong mảng và tăng mỗi phần tử tại các chỉ số đó thêm 1 đơn vị, theo modulo M.

Điều này tương đương với: sau T thao tác, mỗi phần tử $A_i$ sẽ trở thành: $A_i := (A_i + T) \bmod M$

Do đó, bài toán trở thành:

Tìm giá trị T nhỏ nhất ($0 \le T < M$) sao cho dãy $A := [(A_1 + T) \bmod M, \dots, (A_N + T) \bmod M]$ là không giảm.

Chiến lược

1. Xây dựng hàm check(T) kiểm tra xem sau T thao tác thì mảng A có không giảm hay không.
2. Dùng tìm kiếm nhị phân trên T từ 0 đến M - 1 để tìm giá trị nhỏ nhất thoả mãn điều kiện.

Kiểm tra một giá trị T bất kỳ có thỏa mãn là kết quả của bài toán hay không?

Ý tưởng: kiểm tra từ trái qua phải xem dãy A sau khi biến đổi có không giảm không.

Ta duyệt từ trái sang phải với biến p lưu giá trị đã chuẩn hoá ở bước trước.

Gọi x = A[i].

Có hai trường hợp cần xét:

1. Trường hợp 1: x + T < M

• Khi đó: (x + T) mod M = x + T (không bị xoay vòng).
• Điều kiện cần: x + T >= p (đảm bảo không giảm).
• Nếu không thỏa mãn, trả về false.

2. Trường hợp 2: x + T >= M

• Khi đó: (x + T) mod M = x + T - M

• Giá trị sau phép cộng modulo có thể bị "quay vòng" về nhỏ hơn.

• Nếu p <= (x + T - M): không sao, vì vẫn không giảm sau khi vòng lại.

• Nếu p > (x + T - M): ta buộc phải dùng lại x (trước khi cộng), nhưng khi đó:

  • Nếu x < p: không thể đảm bảo không giảm $\rightarrow$ trả về false
  • Nếu x >= p: cập nhật p = x

Lưu ý: cần cập nhật p đúng theo từng trường hợp.

Tìm kiếm nhị phân

• Áp dụng nhị phân trên T trong đoạn [0, M - 1].
• Với mỗi T, gọi check(T).
• Nếu check(T) == true, tiếp tục tìm T nhỏ hơn (vì cần tối thiểu).
• Nếu check(T) == false, tăng T lên.

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, m; cin >> n >> m; vector<int> a(n); for (int& x : a) cin >> x; auto check = [&](int T) { int p = 0; for (int i = 0; i < n; ++i) { int x = a[i]; if (x + T < m) { if (x + T < p) return false; p = max(p, x); } else { int wrap = x + T - m; if (p > wrap) p = max(p, x); } } return true; }; int l = 0, r = m - 1; while (l < r) { int mid = (l + r) >> 1; if (check(mid)) r = mid; else l = mid + 1; } cout << l; return 0;
}

Problem H

Cho hai số nguyên $A$ và $B$. Bạn có thể thực hiện một chuỗi các phép tính như sau:

• Trong phép tính thứ nhất, chọn một trong hai số và tăng nó lên $1$.
• Trong phép tính thứ hai, chọn một trong hai số và tăng nó lên $2$.
• Trong phép tính thứ ba, chọn một trong hai số và tăng nó lên $3$, v.v...

Bạn có thể chọn bao nhiêu phép tính tùy ý, nhưng mỗi phép tăng chỉ được dùng đúng một lần và theo đúng thứ tự.

Input

• Dòng đầu tiên là số nguyên $T$ — số lượng test ($1 \le T \le 100$).
• Với mỗi test, gồm một dòng chứa hai số nguyên $A$ và $B$ ($1 \le A, B \le 10^9$).

Output

• Với mỗi test, in ra một số nguyên là số phép tính tối thiểu cần thực hiện để biến $A$ và $B$ thành bằng nhau.

Example

Giải thích

• Test 1: $A = 1$, $B = 3$, hiệu là $2$. Ta có thể thực hiện:

  • Cộng $1$ vào $A$: $1 \to 2$
  • Cộng $2$ vào $A$: $2 \to 4$
  • Cộng $3$ vào $B$: $3 \to 6$
  • Như vậy không hiệu quả. Nhưng thực tế chỉ cần:
    • Cộng $1$ vào $A$: $1 \to 2$
    • Cộng $2$ vào $A$: $2 \to 4$
    • Cộng $3$ vào $B$: $3 \to 6$
    • Rồi điều chỉnh tiếp, nhưng rõ ràng với $1+2=3$, tổng đủ để bù hiệu $2$, nên $k = 3$ là đáp án tối ưu.

• Test 2: $A = B = 11$, không cần thao tác nào.

• Test 3: $A = 30$, $B = 20$, hiệu là $10$.

  • Cần tổng các bước từ $1$ đến $4$: $1 + 2 + 3 + 4 = 10$.

Hint

Gọi $d = |A - B|$ là hiệu tuyệt đối giữa hai số. Ta cần tìm số nhỏ nhất $k$ sao cho:

• Tổng $S = \dfrac{k(k+1)}{2} \ge d$
• Và $(S - d)$ là số chẵn, tức $(S - d) \bmod 2 = 0$

Ước lượng $k$ ban đầu:

Bắt đầu từ nghiệm gần đúng của bất phương trình:

$$\frac{k(k+1)}{2} \ge d \Rightarrow k^2 + k - 2d \ge 0$$

Nghiệm nhỏ nhất:

$$k = \left\lceil \frac{-1 + \sqrt{1 + 8d}}{2} \right\rceil$$

Tính $S = \dfrac{k(k+1)}{2}$.
Nếu $(S - d)$ lẻ → tiếp tục tăng $k$ cho đến khi $(S - d) \bmod 2 = 0$

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 t = 1; cin >> t; while (t--) { long long a, b; cin >> a >> b; long long d = llabs(a - b); if (d == 0) { cout << 0 << endl; continue; } long long k = ceil((sqrt(1 + 8.0 * d) - 1) / 2); long long S = k * (k + 1) >> 1; while ((S - d) & 1) { ++k; S += k; } cout << k << endl; } return 0;
}

Problem I

Với hai số tự nhiên $N$ và $K$ ($0 \le K < N$), số tổ hợp chập $K$ của $N$ phần tử được ký hiệu là $C(K, N) = \binom{N}{K}$.

Nhiệm vụ: Hãy đếm số lượng ước số nguyên dương của $C(K, N)$.

Input

• Có nhiều test. Mỗi test nằm trên một dòng, gồm hai số nguyên $N$ và $K$ ($0 \le K \le N < 500$).
• Dữ liệu kết thúc khi không còn dòng nào để đọc.

Output

• Với mỗi test, in ra một dòng là số lượng ước số của $\binom{N}{K}$.

Example

Giải thích

• $\binom{5}{1} = 5$ → có 2 ước: 1, 5.
• $\binom{6}{3} = 20$ → có 6 ước: 1, 2, 4, 5, 10, 20.
• $\binom{10}{4} = 210$ → có 16 ước.

Hint

• Với $C = \binom{N}{K}$, ta cần phân tích $C$ thành tích các lũy thừa nguyên tố:

  $$C = p_1^{e_1} \cdot p_2^{e_2} \cdot \dots \cdot p_k^{e_k}$$

• Số ước của $C$ là:

  $$(e_1 + 1)(e_2 + 1) \dots (e_k + 1)$$

• Tận dụng bảng số mũ các thừa số nguyên tố trong phân tích giai thừa:

  $$\binom{N}{K} = \frac{N!}{K!(N-K)!}$$

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); const int M = 500; vector<int> pr; vector<bool> isPrime(M + 5, true); for (int i = 2; i <= M; ++i) { if (isPrime[i]) { pr.push_back(i); for (int j = i * i; j <= M; j += i) isPrime[j] = false; } } int P = pr.size(); vector<vector<ll>> f(M + 1, vector<ll>(P)); for (int i = 1; i <= M; ++i) { for (int j = 0; j < P; ++j) { int p = pr[j], t = i; ll c = 0; while (t /= p) c += t; f[i][j] = c; } } int t = 1; // cin >> t; while (t--) { int n, k; while (cin >> n >> k) { int r = min(k, n - k); ll ans = 1; for (int j = 0; j < P; ++j) { ll e = f[n][j] - f[r][j] - f[n - r][j]; ans *= (e + 1); } cout << ans << endl; } } return 0;
}

Problem J

Một khu du lịch có $n$ hòn đảo, hòn đảo $i$ có độ cao $h_i$.
Để di chuyển từ hòn đảo $i$ đến hòn đảo $j$, du khách có thể sử dụng tàu lượn với chi phí:

$$\text{cost}_{i \to j} = \max(0, h_j - h_i)$$

Tuy nhiên, sau một thời gian, các nhà thầu đã áp dụng giá sàn thuê tàu lượn cho mỗi đảo $i$ là $p_i$. Khi đó, chi phí mới để bay từ $i$ đến $j$ là:

$$\text{cost}_{i \to j} = \max(p_i, h_j - h_i)$$

Nhiệm vụ: Một du khách muốn thăm tất cả $n$ hòn đảo, bắt đầu từ $1$ hòn đảo, sử dụng tàu lượn để đến các đảo khác theo thứ tự tùy ý. Sau đó quay lại đảo xuất phát. Tính tổng chi phí nhỏ nhất để hoàn thành hành trình.

Input

• Dòng đầu tiên chứa số nguyên $n$ ($1 \le n \le 10^5$).
• $n$ dòng tiếp theo, mỗi dòng gồm hai số nguyên không âm $h_i$ và $p_i$ ($0 \le h_i, p_i \le 10^9$).

Output

• Ghi ra một số nguyên: tổng chi phí nhỏ nhất để đi qua tất cả các đảo và quay lại đảo xuất phát.

Example

Giải thích

• Khởi hành từ đảo $1$.
• Chi phí thuê tàu ở mỗi đảo là tổng các $p_i$: $1 + 2 + 2 + 1 = 6$.
• Nếu các đảo đã được sắp xếp theo độ cao, ta chỉ cần thêm phần chi phí tăng độ cao nếu chưa đủ tầm bay (khoảng vượt quá).
• Trong ví dụ này, tổng chi phí không cần thêm vì các tầm bay $p_i$ đã đủ để đến các đảo cao hơn.

Hint

Tổng chi phí cơ bản

• Du khách cần thuê tàu tại mỗi hòn đảo ít nhất một lần, vì thế chi phí tối thiểu ban đầu là:

$$\text{base cost} = \sum_{i=1}^{n} p_i$$

• Đây là chi phí thuê tàu để thực hiện các lượt bay từ mỗi đảo.

Chi phí phát sinh do độ cao

• Khi bay từ đảo $i$ đến đảo $j$, du khách phải đảm bảo có thể đạt tới độ cao $h_j$.
• Nếu chiều cao đạt được từ $h_i + p_i$ vẫn thấp hơn $h_j$, thì cần trả thêm chi phí nâng tầm bay.

$$\text{extra cost} = \max(0, h_j - (h_i + p_i))$$

Cách tối ưu hành trình

• Để đơn giản, hãy sắp xếp các hòn đảo theo độ cao tăng dần.
• Bắt đầu từ đảo thấp nhất (đảo 1), mô phỏng việc bay đến các đảo cao hơn:
  • Nếu đang có tầm bay chưa đủ đến đảo kế tiếp, ta cần thêm chi phí để "bù độ cao".
  • Tại mỗi bước, cập nhật tầm bay hiện tại là:

$$\text{reach} = \max(\text{reach}, h_i + p_i)$$

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 t = 1; // cin >> t; while (t--) { int n; cin >> n; if (n == 1) { ll h, p; cin >> h >> p; cout << 0; return 0; } vector<ll> h(n), p(n); ll base = 0; for (int i = 0; i < n; ++i) { cin >> h[i] >> p[i]; base += p[i]; } vector<int> id(n); iota(id.begin(), id.end(), 0); sort(id.begin(), id.end(), [&](int a, int b) { return h[a] < h[b]; }); ll reach = h[id[0]] + p[id[0]]; ll add = 0; for (int k = 1; k < n; ++k) { int i = id[k]; if (h[i] > reach) { add += h[i] - reach; reach = h[i]; } reach = max(reach, h[i] + p[i]); } cout << base + add; } return 0;
}

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