USACO 2022 - Tháng 12 - Hạng Bạc

Lưu ý: Giới hạn thời gian là 4 giây. Giới hạn bộ nhớ là 512MB.

Nông dân John có \(N\) chuồng bò \((2 \le N \le 2 \times 10^5)\) được đánh số \(1 \dots N\). Có \(N - 1\) con đường hai chiều nối các cặp chuồng bò, và từ một chuồng bò có thể đi đến \(N - 1\) chuồng còn lại. Hiện tại, chuồng \(j\) có \(h_j\) kiện có khô \((1 \le h_j \le 10^9)\).

Để làm hài lòng lũ bò, nông dân John muốn di chuyển các kiện này sao cho số lượng cỏ khô mà các chú bò có là bằng nhau. Bác ta có thể chọn \(1\) cặp chuồng bất kì có đường nối giữa chúng và ra lệnh cho cấp dưới di chuyển các kiện hàng với số lượng nguyên dương bất kì bé hơn hoặc bằng so với số kiện cỏ hiện tại đang có trong chuồng sang chuồng còn lại.

Hãy xác định dãy các mệnh lệnh để nông dân John có thể hoàn thành nhiệm vụ sao cho độ dài dãy là bé nhất. Dữ liệu đảm bảo thấy rằng đáp án luôn tồn tại.

Input

• Dòng đầu tiên là số \(N\).
• Dòng thứ hai là \(N\) số \(h_1, h_2, \dots, h_N\).
• \(N - 1\) dòng cuối cùng là các cặp \(u_i, v_i\) thoả mãn có một đường nối giữa chuồng \(u_i\) và chuồng \(v_i\).

Output

• Dòng đầu tiên là số lượng mệnh lệnh ít nhất bác John cần thực hiện (Gọi là \(T\)).
• Trong \(T\) dòng tiếp theo, dòng thứ \(i\) là bộ ba số \(a_i, b_i, c_i\), trong đó: \(a_i\) là chuồng lấy kiện cỏ, \(b_i\) là chuồng các kiện cỏ được chuyển đến, \(c_i\) là số lượng kiện cỏ được lấy.

Scoring

• Subtask \(1\): \(N \le 5000\).
• Subtask \(2\): \(v_i = u_i + 1 \forall i\).
• Subtask \(3\): Không còn ràng buộc.

4
2 1 4 5
1 2
2 3
2 4

3
3 2 1
4 2 2
2 1 1

Nông dân John và kẻ thù không đội trời chung của bác - Nông dân Nhoj đang chơi một trò chơi trong chuồng bò được xây thành đường tròn. Có \(N\) \((1 \le N \le 10^5)\) căn phòng trong chuồng, phòng thứ \(i\) ban đầu có \(a_i\) con bò \((1 \le a_i \le 5 \times 10^6)\). Trò chơi diễn ra như sau:

• Cả hai nông dân đều ở trong cùng một phòng. Sau khi vào phòng, mỗi nông dân sẽ chơi chính xác một lượt, trong đó nông dân John đi trước. Ban đầu cả \(2\) nông dân ở sẽ vào phòng \(1\).
• Nếu như không có con bò nào trong phòng, người nào đi lượt này sẽ thua. Ngược lại, người chơi có thể chọn một số nguyên \(P\) trong đó \(P\) chỉ có thể là \(1\) hoặc là một số nguyên tố không vượt quá số lượng bò hiện tại trong phòng và đuổi \(P\) chú bò này ra ngoài.
• Sau khi cả hai đều thực hiện lượt chơi, họ sẽ sang phòng tiếp theo (phòng \(i\) sang phòng \(i + 1\), phòng \(N\) sang phòng \(1\)).

Hãy tìm ra người chiến thắng nếu cả \(2\) chơi tối ưu.

Input

• Input có \(T\) test cases. Dòng đầu tiên là số \(T\) \((1 \le T \le 1000)\).
• Mỗi test sẽ gồm một dòng chứa số \(N\) theo sau bởi \(N\) số \(a_1, a_2, \dots, a_N\).
• Dữ liệu đảm bảo tổng \(N\) trong tất cả các test không vượt quá \(2 \times 10^5\).

Output

• Với mỗi test case, xuất ra tên của người thắng cuộc "Farmer John" hoặc "Farmer Nhoj".

Scoring

• Subtask \(1\): \(N = 1\).
• Subtask \(2\): \(a_i \le 1000\).
• Subtask \(3\): Không có ràng buộc gì thêm.

5
1
4
1
9
2
2 3
2
7 10
3
4 9 4

Farmer Nhoj
Farmer John
Farmer John
Farmer John
Farmer Nhoj

Bessie có một dãy \(a_1, a_2, \dots, a_N\), trong đó \(1 \le N \le 300\) và \(0 \le a_i \le 10^9\) với mọi \(i\). Cô nàng sẽ không nói thẳng cho bạn dãy \(a\) mà lại thích vòng vo Tam Quốc, chỉ nói cho bạn khoảng xác định của dãy. Nghĩa là, với mỗi cặp chỉ số \(i \le j\), Bessie sẽ nói cho bạn \(r_{i, j} = \max a[i \dots j] - \min a[i \dots j]\). Cho các giá trị của \(r\), hãy xây dựng lại một dãy mà có thể là dãy ban đầu của Bessie. Các giá trị trong dãy phải nằm trong đoạn \([-10^9, 10^9]\).

Input

• Dòng đầu tiên là số \(N\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) là các số \(r_{i, i}, r_{i, i + 1}, \dots r_{i, n}\).
• Dữ liệu đảm bảo luôn có dãy \(a\) với các giá trị nằm trong đoạn \([0, 10^9]\) thoả mãn điều kiện của test.

Output

• In ra một dòng là \(N\) số nguyên \(b_1, b_2, \dots, b_N \in [-10^9, 10^9]\) thoả mãn \(r_{i, j} = \max a[i \dots j] - \min a[i \dots j] \forall i \le j\).

Scoring

• Subtask \(1\): \(r_{1, N} \le 1\).
• Subtask \(2\): \(r_{i, i + 1} = 1 \forall 1 \le i \le N\).
• Subtask \(3\): Không có ràng buộc thêm.

3
0 2 2
0 1
0

1 3 2

3
0 1 1
0 0
0

0 1 1

4
0 1 2 2
0 1 1
0 1
0

1 2 3 2

4
0 1 1 2
0 0 2
0 2
0

1 2 2 0