# Graphs #1
*Viết bài: Trần Gia Huy.*
## A. Mocha and Hiking
Link [https://codeforces.com/problemset/problem/1559/C].
**Đề bài**
Thành phố mà Mocha sống được gọi là Zhijiang. Có tổng cộng $n+1$ ngôi làng và $2n-1$ con đường chỉ hướng trong thành phố này. Có hai loại đường:
* $n-1$ con đường từ ngôi làng thứ $i$ đến ngôi làng thứ $i+1$, cho tất cả các giá trị $1 \leq i \leq n-1$.
* $n$ con đường còn lại có thể được mô tả bởi một dãy số $a_1, a_2, \ldots, a_n$. Nếu $a_i=0$, con đường thứ $i$ đi từ ngôi làng thứ $i$ đến ngôi làng thứ $n+1$, ngược lại nó đi từ ngôi làng thứ $n+1$ đến ngôi làng thứ $i$, cho tất cả các giá trị $1 \leq i\leq n$.
Mocha lên kế hoạch đi bộ đường dài cùng Taki vào cuối tuần này. Để tránh chuyến đi trở nên nhàm chán, họ lên kế hoạch đi qua mỗi ngôi làng chính xác một lần. Họ có thể bắt đầu và kết thúc ở bất kỳ ngôi làng nào. Bạn có thể giúp họ lập kế hoạch không?
**Input**
Mỗi bộ test gồm nhiều bộ test con. Dòng đầu tiên chứa một số nguyên $t$ ($1 \leq t \leq 20$) - số lượng bộ test con. Mỗi bộ test con bao gồm hai dòng.
Dòng đầu tiên của mỗi bộ test con chứa một số nguyên $n$ ($1 \leq n \leq 10^4$) - cho biết số lượng ngôi làng là $n+1$.
Dòng thứ hai của mỗi bộ test con chứa $n$ số nguyên $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 1$). Nếu $a_i=0$, điều đó có nghĩa là có một con đường từ ngôi làng thứ $i$ đến ngôi làng thứ $n+1$. Nếu $a_i=1$, điều đó có nghĩa là có một con đường từ ngôi làng thứ $n+1$ đến ngôi làng thứ $i$.
Đảm bảo tổng của $n$ trên tất cả các bộ test con không vượt quá $10^4$.
**Output**
Đối với mỗi bộ test con, in ra một dòng chứa $n+1$ số nguyên, trong đó số thứ $i$ là ngôi làng thứ $i$ họ sẽ đi qua. Nếu không tồn tại câu trả lời, in ra $-1$. Nếu có nhiều câu trả lời đúng, bạn có thể in ra bất kỳ một câu trả lời nào.
**Sample input:**
```
2
3
0 1 0
3
1 1 0
```
**Sample output:**
```
1 4 2 3
4 1 2 3
```
**Giải thích**
Trong trường hợp thử nghiệm đầu tiên, thành phố trông giống như biểu đồ sau:
Vì vậy các câu trả lời có thể là: $(1 \to 4 \to 2 \to 3)$ hoặc $(1 \to 2 \to 3 \to 4)$.
Trong trường hợp thử nghiệm thứ hai, thành phố trông giống như biểu đồ sau:
Vì vậy các câu trả lời có thể là: $(4 \to 1 \to 2 \to 3)$, $(1 \to 2 \to 3 \to 4)$, $(3 \to 4 \to 1 \to 2)$, hoặc $(2 \to 3 \to 4 \to 1)$.
**Ý tưởng**
Ta luôn có đường đi từ làng $i$ đến làng $i + 1$. Nhận thấy rằng nếu $a_i = 0$ thì ta có đường đi từ làng $i$ đến làng cuối cùng $n + 1$, nên ta sẽ lưu nó vào một biến $x$.
Khởi tạo một biến $y = 0$ với ý nghĩa là ngôi làng đang xét ở thời điểm hiện tại, duyệt lại $i$ từ $0$ đến $n$, nếu $i = x$ thì in ra $n + 1$, ngược lại in ra $y + 1$ sau đó tăng $y$ lên một đơn vị.
**Code**
```cpp=1
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1000005;
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tt; cin >> tt;
while (tt--) {
int n, x = 0, y = 0; cin >> n;
int a[n];
for (int i = 0; i < n; i++) {
cin >> a[i];
if (!a[i]) x = i + 1;
}
for (int i = 0; i <= n; i++) {
if (i == x) cout << n + 1 << ' ';
else cout << y + 1 << ' ', ++y;
}
cout << '\n';
}
return 0;
}
```
## B. Running for Gold
Link [https://codeforces.com/problemset/problem/1552/B]
**Đề bài**
Cuộc thi Olympic vừa mới bắt đầu và Federico rất háo hức để xem cuộc đua marathon. Sẽ có $n$ vận động viên, được đánh số từ $1$ đến $n$, tham gia cuộc marathon và tất cả đều đã tham gia vào $5$ cuộc marathon quan trọng, được đánh số từ $1$ đến $5$, trong quá khứ. Đối với mỗi $1 \leq i \leq n$ và $1 \leq j \leq 5$, Federico nhớ rằng vận động viên $i$ đạt vị trí thứ $r_{i,j}$ trong marathon $j$ (ví dụ, $r_{2,4}=3$ có nghĩa là vận động viên $2$ đạt vị trí thứ ba trong marathon $4$).
Federico coi vận động viên $x$ là vượt trội hơn vận động viên $y$ nếu vận động viên $x$ đạt thành tích tốt hơn vận động viên $y$ trong ít nhất $3$ cuộc marathon trong quá khứ, tức là $r_{x,j} < r_{y,j}$ cho ít nhất $3$ giá trị $j$ khác nhau.
Federico tin rằng một vận động viên có khả năng giành huy chương vàng tại Olympic nếu anh ta vượt trội hơn tất cả các vận động viên khác. Hãy tìm một vận động viên có khả năng giành huy chương vàng (tức là vận động viên vượt trội hơn tất cả các vận động viên khác), hoặc xác định rằng không có vận động viên nào như vậy.
**Input**
Dòng đầu tiên chứa một số nguyên $t$ ($1 \leq t \leq 1000$) - số lượng test case. Tiếp theo là $t$ test case.
Dòng đầu tiên của mỗi test case chứa một số nguyên $n$ ($1 \leq n \leq 50,000$) - số lượng vận động viên.
Tiếp theo là $n$ dòng, mô tả vị trí xếp hạng của từng vận động viên. Dòng thứ $i$ chứa $5$ số nguyên $r_{i,1}$, $r_{i,2}$, $r_{i,3}$, $r_{i,4}$, $r_{i,5}$ ($1 \leq r_{i,j} \leq 50,000$) - vị trí xếp hạng của vận động viên $i$ trong $5$ cuộc marathon trong quá khứ. Đảm bảo rằng trong mỗi cuộc marathon trong quá khứ, $n$ giá trị $r_{1,j}$, $r_{2, j}$, ..., $r_{n, j}$ khác nhau.
Đảm bảo tổng của $n$ trên tất cả các test case không vượt quá $50,000$.
**Output**
Đối với mỗi test case, in ra một số nguyên duy nhất - số hiệu của vận động viên có khả năng giành huy chương vàng (tức là vận động viên vượt trội hơn tất cả các vận động viên khác). Nếu không có vận động viên nào như vậy, in ra $-1$. Nếu có nhiều hơn một vận động viên như vậy, in ra bất kỳ một trong số chúng.
**Sample input**
```
4
1
50000 1 50000 50000 50000
3
10 10 20 30 30
20 20 30 10 10
30 30 10 20 20
3
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3
6
9 5 3 7 1
7 4 1 6 8
5 6 7 3 2
6 7 8 8 6
4 2 2 4 5
8 3 6 9 4
```
**Sample output**
```
1
-1
1
5
```
**Giải thích**
**Test case 1:**
Chỉ có một vận động viên, do đó anh ta vượt trội hơn tất cả mọi người (vì không có người khác), và do đó có khả năng giành huy chương vàng.
**Test case 2:**
Có 3 vận động viên. Vận động viên 1 vượt trội hơn vận động viên 2. Thực sự, vận động viên 1 đạt hạng tốt hơn vận động viên 2 trong các cuộc marathon 1, 2 và 3.
Vận động viên 2 vượt trội hơn vận động viên 3. Thực sự, vận động viên 2 đạt hạng tốt hơn vận động viên 3 trong các cuộc marathon 1, 2, 4 và 5.
Vận động viên 3 không vượt trội hơn bất kỳ vận động viên nào khác.
**Test case 3:**
Có 3 vận động viên. Vận động viên 1 vượt trội hơn tất cả các vận động viên khác. Vì anh ta vượt trội hơn tất cả các vận động viên khác, anh ta có khả năng giành huy chương vàng.
Vận động viên 2 vượt trội hơn vận động viên 3.
Vận động viên 3 không vượt trội hơn bất kỳ vận động viên nào khác.
**Test case 4:**
Có 6 vận động viên.
Vận động viên 1 vượt trội hơn vận động viên 3, 4 và 6.
Vận động viên 2 vượt trội hơn vận động viên 1, 4 và 6.
Vận động viên 3 vượt trội hơn vận động viên 2, 4 và 6.
Vận động viên 4 không vượt trội hơn bất kỳ vận động viên nào khác.
Vận động viên 5 vượt trội hơn vận động viên 1, 2, 3, 4 và 6. Vì anh ta vượt trội hơn tất cả các vận động viên khác, anh ta có khả năng giành huy chương vàng.
Vận động viên 6 chỉ vượt trội hơn vận động viên 4.
**Ý tưởng**
Ta sẽ duy trì một biến $idx$ ban đầu gán bằng 0, nghĩa là là vận động viên thứ $idx$ để so sánh với các vận động viên còn lại.
Ví dụ với **testcase 3**:
Sau đó ta duyệt nếu $a[i][j]$ có hạng về đích tốt hơn $a[idx][j]$ thì ta đếm xem có bao nhiêu lần như thế giữa hai vận động viên đang xét vào biến $cnt$.
Nếu $cnt \geq 3$ nghĩa là vận động viên thứ $i$ hiện tại tốt hơn vận động viên $idx$ đang xét nên ta cập nhật $idx = i$.
Vì bài yêu cầu tìm vận động viên có khả năng là người thắng cuộc nên sẽ xảy ra trường hợp có hai hoặc nhiều người đều có khả năng thắng cuộc nên ta sẽ phải duyệt lại một lần nữa.
Khởi tạo biến $ok = false$ để kiểm tra. Sau đó duyệt lại nếu $i = idx$ thì ta không cần kiểm tra, nếu $a[i][j] > a[idx][j]$ thì $cnt += 1$. Nghĩa là giải của vận động viên thứ $i$ thua vận động viên $idx$ từ 3 giải trở lên thì không có gì, ngược lại tức là vận động viên $i$ cũng có khả năng thắng nên ta cho $ok = true$.
**Code**
```cpp=1
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define int long long
#define setConstant memset
const int maxn = 1000005;
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tt; cin >> tt;
while (tt--) {
int n; cin >> n;
int a[n][5];
for (int i = 0; i < n; i++) {
for (int j = 0; j < 5; j++) {
cin >> a[i][j];
}
}
int idx = 0;
for (int i = 0; i < n; i++) {
int tmp = 0;
for (int j = 0; j < 5; j++) {
if (a[i][j] < a[idx][j]) ++tmp;
}
if (tmp >= 3) idx = i;
}
bool ok = false;
for (int i = 0; i < n; i++) {
if (i == idx) continue;
int tmp = 0;
for (int j = 0; j < 5; j++) {
if (a[i][j] > a[idx][j]) ++tmp;
}
if (tmp < 3) ok = true;
}
if (ok) cout << -1 << '\n';
else cout << idx + 1 << '\n';
}
return 0;
}
```
## C. Great Graphs
Link [https://codeforces.com/problemset/problem/1541/C]
**Đề bài**
Nông dân John có một trang trại gồm $n$ đồng cỏ được kết nối bởi các con đường một chiều. Mỗi con đường có một trọng số, biểu thị thời gian để đi từ đầu đến cuối con đường. Các con đường có thể có trọng số âm, trong đó bò đi nhanh đến mức nó quay trở lại quá khứ! Tuy nhiên, Nông dân John đảm bảo rằng không thể có trường hợp bò bị mắc kẹt trong một vòng lặp thời gian, trong đó chúng có thể vô tận quay lại quá khứ bằng cách đi qua một chuỗi con đường. Ngoài ra, mỗi cặp đồng cỏ được kết nối bởi tối đa một con đường trong mỗi hướng.
Rất tiếc, Nông dân John đã mất bản đồ của trang trại. Mọi thứ ông nhớ chỉ là một mảng $d$, trong đó $d_i$ là thời gian nhỏ nhất mà bò mất để đến đồng cỏ thứ $i$ từ đồng cỏ thứ 1 bằng cách đi qua một chuỗi con đường. Giá trị của trang trại của ông là tổng của trọng số của mỗi con đường, và Nông dân John cần biết giá trị tối thiểu của một trang trại mà phù hợp với ký ức của ông.
**Input**
Dòng đầu tiên chứa một số nguyên $t$ ($1 \leq t \leq 10^4$) - số lượng test. Tiếp theo là $t$ test.
Dòng đầu tiên của mỗi test chứa một số nguyên $n$ ($1 \leq n \leq 10^5$) - số lượng đồng cỏ.
Dòng thứ hai của mỗi test chứa $n$ số nguyên $d_1, d_2, \ldots, d_n$ ($0 \leq d_i \leq 10^9$) - mảng $d$. Đảm bảo rằng $d_1 = 0$.
Đảm bảo tổng của $n$ trên tất cả các test không vượt quá $10^5$.
**Output**
Đối với mỗi test, in ra giá trị tối thiểu của một trang trại mà phù hợp với ký ức của Nông dân John.
**Sample input**
```
3
3
0 2 3
2
0 1000000000
1
0
```
**Sample output**
```
-3
0
0
```
**Giải thích**
Testcase 1:
**Ý tưởng**
Ta sẽ lưu trọng số của đồng cỏ thứ $i$ là $d[i]$.
Sử dụng mảng prefix sum ví dụ $sum[i]$ nghĩa là tổng thời gian đi từ đồng cỏ $1$ đến đồng cỏ $i$.
Ta có $(i - 1) \times d[i]$ là thời gian đi từ đồng cỏ thứ $i - 1$ đến đồng cỏ thứ $i$ nếu chọn đi trực tiếp từ $i - 1$ đến $i$.
Suy ra tổng hai giá trị trên cho ta tổng thời gian đi từ đồng cỏ $1$ đến đồng cỏ $i$ bao gồm cả việc đi trực tiếp từ $i - 1$ đến $i$.
**Code**
```cpp=1
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define int long long
#define setConstant memset
const int maxn = 1000005;
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tt; cin >> tt;
while (tt--) {
int n; cin >> n;
int d[n + 1], sum[n + 1] = {0};
for (int i = 1; i <= n; i++) cin >> d[i];
sort(d + 1, d + n + 1);
for (int i = 1; i <= n; i++) {
sum[i] += sum[i - 1] + d[i];
}
int ans = d[n];
for (int i = 1; i <= n; i++) {
ans += sum[i - 1] - (i - 1) * d[i];
}
cout << ans << '\n';
}
return 0;
}
```
## D. Minimum Ties
Link [https://codeforces.com/problemset/problem/1487/C]
**Đề bài**
Sắp tới sẽ diễn ra một giải đấu bóng đá lớn! Có $n$ đội bóng tham gia, và mỗi cặp đội bóng sẽ đấu chính xác một trận đấu với nhau. Có hai kết quả có thể xảy ra trong một trận đấu: trận đấu có thể kết thúc hòa, khi đó cả hai đội đều nhận được $1$ điểm; hoặc một đội bóng có thể thắng trong một trận đấu, khi đó đội thắng nhận được $3$ điểm và đội thua không nhận điểm. Điểm của một đội bóng là tổng số điểm nó nhận được trong tất cả các trận đấu mà đội đó đã thi đấu.
Bạn quan tâm đến một tình huống giả định khi tất cả các đội đều có cùng số điểm vào cuối giải đấu. Một ví dụ đơn giản của tình huống đó là khi tất cả các trận đấu đều kết thúc hòa, nhưng bạn cũng muốn giảm thiểu số trận đấu hòa.
Nhiệm vụ của bạn là mô tả một tình huống (chọn kết quả của mỗi trận đấu) sao cho tất cả các đội đều có cùng số điểm, và số trận đấu hòa là ít nhất có thể.
**Input**
Dòng đầu tiên chứa một số nguyên $t$ ($1 \leq t \leq 100$) - số lượng test case.
Tiếp theo là $t$ dòng, mỗi dòng chứa một số nguyên $n$ ($2 \leq n \leq 100$) - số lượng đội bóng trong mỗi test case.
**Output**
Đối với mỗi test case, in ra $\frac{n(n - 1)}{2}$ số nguyên mô tả kết quả của các trận đấu theo thứ tự sau: số nguyên đầu tiên tương ứng với trận đấu giữa đội 1 và đội 2, số nguyên thứ hai tương ứng với trận đấu giữa đội 1 và đội 3, sau đó đến trận đấu giữa đội 1 và đội 4, ..., trận đấu giữa đội 1 và đội $n$, trận đấu giữa đội 2 và đội 3, trận đấu giữa đội 2 và đội 4, ..., đến trận đấu giữa đội 2 và đội $n$, và cứ tiếp tục như vậy cho đến trận đấu giữa đội $n-1$ và đội $n$.
Số nguyên tương ứng với trận đấu giữa đội $x$ và đội $y$ sẽ là $1$ nếu đội $x$ thắng, $-1$ nếu đội $y$ thắng, hoặc $0$ nếu trận đấu kết thúc hòa.
Tất cả các đội phải có số điểm như nhau và số lần hòa phải ở mức tối thiểu có thể. Nếu có nhiều câu trả lời tối ưu, hãy in bất kỳ câu trả lời nào trong số đó. Có thể chứng minh rằng luôn có cách để tất cả các đội có số điểm bằng nhau.
**Sample input**
```
2
2
3
```
**Sample output**
```
0
1 -1 1
```
**Giải thích**
Trong trường hợp thử nghiệm đầu tiên của ví dụ, cả hai đội nhận được $1$ điểm vì trận đấu giữa họ hòa.
Trong trường hợp thử nghiệm thứ hai của ví dụ, đội $1$ thắng đội $2$ (đội $1$ được $3$ điểm), đội $1$ thua đội $3$ (đội $3$ được $3$ điểm), đội $2$ thắng đội $3$ (đội $2$ được $3$ điểm).
Sign in with Wallet
Connect another wallet