PreVOI 24 - Bắc Giang
PreVOI 2024 - Recs
Nộp bàiPoint: 6
Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Gia Huy muốn mua một mảnh đất hình chữ nhật và xây dựng ba tòa nhà trên mảnh đất đó.
Các tòa nhà phải là hình chữ nhật có kích thước ~a_1 \times b_1~, ~a_2 \times b_2~, và ~a_3 \times b_3~. Các tòa nhà có thể chạm vào nhau nhưng không được chồng lên nhau. Chúng cũng có thể được xoay miễn là các cạnh song song với trục tọa độ.
Tính diện tích đất tối thiểu Gia Huy cần mua?
Input
Dòng đầu tiên ghi số test ~t~ ~(1 \le t \le 1000)~. Sau đó là ~t~ dòng, mỗi dòng ghi ~6~ số nguyên ~a_1, b_1, a_2, b_2, a_3~ và ~b_3~ ~(1 \le a_1, b_1, a_2, b_2, a_3, b_3 \le 10^9)~.
Output
Đối với mỗi test, in ra diện tích đất tối thiểu Gia Huy cần mua để có thể xây dựng ba tòa nhà.
Sample Input 1
2
2 3 2 2 1 1
2 4 5 1 2 3
Sample Output 1
12
21
Notes

(Trong ví dụ 2, hình chữ nhật ~5 \times 1~ được quay góc ~90^\circ~).
PreVOI 2024 - Chameleon
Nộp bàiPoint: 7
Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Đất nước Sanguinesia là nơi sinh sống của hàng chục loài tắc kè hoa khác nhau. Nhân dịp sinh nhật, bạn Khoa quyết định tự thưởng cho mình một chuyến đi đến đất nước này để được tận mắt nhìn thấy những con tắc kè hoa sặc sỡ và dễ thương!
Đất nước Sanguinesia có ~N~ thành phố khác nhau, đánh số từ ~1~ đến ~N~. Có ~M~ con đường ~2~ chiều, mỗi con đường nối ~2~ thành phố khác nhau. Đối với ~2~ thành phố bất kì, có nhiều nhất một con đường nối giữa chúng. Các thành phố đều liên thông với nhau, có nghĩa là từ một thành phố bất kì, luôn tồn tại một tuyến đường để đến các thành phố còn lại.
Bạn Khoa sẽ bắt đầu chuyến đi của mình ở thành phố ~X~, và bạn ấy sẽ kết thúc chuyến đi của mình ở một thành phố ~Y~ có chỉ số lớn hơn ~X~. Có thể có nhiều cách để di chuyển từ thành phố ~X~ đến thành phố ~Y~. Vì vậy, trước khi lên đường, bạn ấy cần biết trước những con đường và thành phố nào là tất yếu cho chuyến đi của bạn.
Một con đường được gọi là tất yếu giữa thành phố ~X~ và thành phố ~Y~ khi mọi tuyến đường từ thành phố ~X~ đến thành phố ~Y~ đều bắt buộc phải đi qua con đường đó. Nói cách khác, nếu con đường đó bị bỏ đi, thì không còn đường đi nào từ thành phố ~X~ đến thành phố ~Y~ nữa. Bạn Khoa đặt ~F(X, Y)~ là số lượng con đường tất yếu giữa thành phố ~X~ và thành phố ~Y~.
Tương tự như vậy, một thành phố được gọi là tất yếu giữa thành phố ~X~ và thành phố ~Y~ khi mọi tuyến đường đi từ thành phố ~X~ đến thành phố ~Y~ đều bắt buộc phải đi qua thành phố đó. Bạn Khoa đặt ~G(X, Y)~ là số lượng thành phố tất yếu giữa thành phố ~X~ đến thành phố ~Y~. Lưu ý theo định nghĩa này, thành phố ~X~ và thành phố ~Y~ đều được coi là thành phố tất yếu.
Cuối cùng, bạn Khoa gọi ~H(X, Y)~ là độ vui của chuyến đi. Độ vui của chuyến đi được tính theo công thức sau:
~H(X, Y) = (F(X, Y) \cdot A + G(X, Y) \cdot B)^C~,
trong đó ~A~, ~B~, và ~C~ là những hằng số cố định cho trước.
Bạn Khoa chưa quyết định được thành phố ~X~ và thành phố ~Y~ sẽ là hai thành phố nào. Là người tò mò, bạn muốn biết tổng độ vui của tất cả các chuyến đi có thể diễn ra. Hãy giúp Khoa.
Cụ thể hơn, hãy tính tổng của ~H(X, Y)~ với mọi cặp số ~(X, Y)~ thỏa mãn ~1 \le X < Y \le N~. Vì tổng này có thể rất lớn, nên hãy in ra phần dư của tổng đó khi chia cho số ~(10^9 + 7)~.
Input
Dòng đầu tiên ghi ~5~ số nguyên ~N, M, A, B, C~. (~2 \le N \le 10^5~, ~N-1 \le M \le \min(N \cdot (N-1)/2, 2 \cdot 10^5)~, ~0 \le A \le 10^9~, ~0 \le B \le 10^9~, ~1 \le C \le 2~)
Dòng thứ ~i~ trong ~M~ dòng tiếp theo ghi ~2~ số nguyên ~U_i~ và ~V_i~ ~(1 \le U_i \le N, 1 \le V_i \le N, U_i \ne V_i)~, là chỉ số của hai thành phố được nối bởi con đường thứ ~i~.
Dữ liệu đảm bảo cách bố trí các con đường thỏa mãn điều kiện của đề bài.
Output
In ra phần dư của đáp án của bài toán khi chia cho số ~(10^9 + 7)~.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~20\%~ | ~2 \le N \le 100~ |
| 2 | ~10\%~ | ~A = 0, C = 1~ |
| 3 | ~20\%~ | ~A = 0, C = 2~ |
| 4 | ~10\%~ | ~B = 0, C = 1~ |
| 5 | ~20\%~ | ~B = 0, C = 2~ |
| 6 | ~20\%~ | Không có giới hạn gì thêm |
Sample Input 1
4 3 10 12 2
1 2
2 3
3 4
Sample Output 1
15824
Notes
Giá trị của ~F(X, Y)~, ~G(X, Y)~, và ~H(X, Y)~ như sau:
~F(1, 2) = 1~, ~G(1, 2) = 2~, ~H(1, 2) = (1 \cdot 10 + 2 \cdot 12)^2 = 1156~
~F(1, 3) = 2~, ~G(1, 3) = 3~, ~H(1, 3) = (2 \cdot 10 + 3 \cdot 12)^2 = 3136~
~F(1, 4) = 3~, ~G(1, 4) = 4~, ~H(1, 4) = (3 \cdot 10 + 4 \cdot 12)^2 = 6084~
~F(2, 3) = 1~, ~G(2, 3) = 2~, ~H(2, 3) = (1 \cdot 10 + 2 \cdot 12)^2 = 1156~
~F(2, 4) = 2~, ~G(2, 4) = 3~, ~H(2, 4) = (2 \cdot 10 + 3 \cdot 12)^2 = 3136~
~F(3, 4) = 1~, ~G(3, 4) = 2~, ~H(3, 4) = (1 \cdot 10 + 2 \cdot 12)^2 = 1156~
Đáp án của bài toán là ~1156 + 3136 + 6084 + 1156 + 3136 + 1156 = 15824~.
PreVOI 2024 - Money
Nộp bàiPoint: 7
Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Nhật là một đại gia với lượng tài sản khổng lồ. Nhật không thể mang theo toàn bộ số tiền của mình, nên hôm nay Nhật chỉ mang ~N~ mệnh giá khác nhau, bao gồm ~10^{100}~ tờ tiền có mệnh giá ~a_1~ đồng, ~10^{100}~ tờ tiền có mệnh giá ~a_2~ đồng, ~\dots~, ~10^{100}~ tờ tiền có mệnh giá ~a_N~ đồng.
Nhật muốn mua một mảnh đất có trị giá là ~K~. Với số tiền mà Nhật mang đi hôm nay, hãy tính số cách mà Nhật có thể mua mảnh đất.
Hai cách mua được coi là khác nhau nếu tồn tại một mệnh giá mà một cách mua sử dụng nhiều hoặc ít tờ tiền hơn cách mua còn lại.
Do số cách mua có thể rất lớn, hãy in ra phần dư của số cách mua sau khi chia lấy cho ~10^9 + 7~.
Input
Dòng đầu tiên ghi ~2~ số nguyên ~N, K~ ~(1 \le N \le 5000, 1 \le K \le 10^{18})~.
Dòng tiếp theo gồm ~N~ số nguyên phân biệt ~a_1, a_2, \dots, a_N~ ~(1 \le a_i \le K)~.
Output
In ra phần dư của đáp án của bài toán khi chia cho số ~(10^9 + 7)~.
Scoring
Gọi ~S~ là tổng ~a_1 + a_2 + \dots + a_N~.
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~10\%~ | ~1 \le N \le 10, 1 \le K \le 10~. |
| 2 | ~40\%~ | ~1 \le N \le 500, 1 \le K \le 5000~. |
| 3 | ~10\%~ | ~N = 2, 1 \le K \le 10^9~. |
| 4 | ~40\%~ | ~S \le 100~. |
Sample Input 1
3 6
1 2 3
Sample Output 1
7
Notes
Có ~7~ cách mua như sau:
Dùng ~2~ tờ tiền ~3~ đồng
Dùng ~1~ tờ tiền ~3~ đồng, ~1~ tờ tiền ~2~ đồng, ~1~ tờ tiền ~1~ đồng
Dùng ~1~ tờ tiền ~3~ đồng, ~3~ tờ ~1~ đồng
Dùng ~1~ tờ ~2~ đồng, ~4~ tờ ~1~ đồng
Dùng ~2~ tờ ~2~ đồng, ~2~ tờ ~1~ đồng
Dùng ~3~ tờ ~2~ đồng
Dùng ~6~ tờ ~1~ đồng
PreVOI 2024 - Bức ảnh
Nộp bàiPoint: 7
Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Alice đã dán một số bức ảnh hình chữ nhật lên bức tường trong phòng làm việc. Mỗi lần dán, Alice luôn dán sao cho các cạnh của bức ảnh song song với trục ngang hoặc dọc của bức tường và ghi lại tọa độ trái dưới, phải trên của bức ảnh. Mỗi bức ảnh có thể bị che một phần hoặc bị che toàn bộ bởi các bức ảnh khác. Nếu chỉ quan tâm đến những phần phủ lên bức tường thì các bức ảnh tạo thành những hình ảnh độc đáo. Sau lúc làm việc căng thẳng, Alice nhìn lên bức tường và tự hỏi, tổng độ dài đường biên của các hình tạo thành là bao nhiêu.

Yêu cầu: Cho vị trí dán của ~n~ bức ảnh, hãy tính tổng độ đường biên của các hình tạo thành.
Input
Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 10^5)~ là số bức ảnh được dán lên tường;
Dòng thứ ~i~ ~(1 \le i \le n)~ chứa bốn số nguyên ~x_i, y_i, u_i, v_i~ ~(-10^9 \le x_i < u_i \le 10^9; -10^9 \le y_i < v_i \le 10^9)~, trong đó ~x_i, y_i~ là tọa độ trái dưới và ~u_i, v_i~ là tọa độ phải trên của hình chữ nhật mô tả bức ảnh được dán lên tường.
Output
- Ghi ra một số nguyên là tổng độ dài đường biên của các hình tạo thành.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~30\%~ | ~n \le 100~ và ~\lvert x_i\rvert, \lvert y_i\rvert, \lvert u_i\rvert, \lvert v_i\rvert \le 10^2~ |
| 2 | ~40\%~ | ~n \le 5000~ và ~\lvert x_i\rvert, \lvert y_i\rvert, \lvert u_i\rvert, \lvert v_i\rvert \le 10^4~ |
| 3 | ~30\%~ | Không có giới hạn gì thêm |
Sample Input 1
4
0 1 1 2
1 0 2 1
2 1 3 2
1 2 2 3
Sample Output 1
16
Sample Input 2
7
-15 0 5 10
-5 8 20 25
15 -4 24 14
0 -6 16 4
2 15 10 22
30 10 36 20
34 0 40 16
Sample Output 2
228
PreVOI 2024 - Đổi chỗ
Nộp bàiPoint: 7
Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Sample Output đúng của bài được đính chính ở dưới.
Alice có một dãy số nguyên ~a_1, a_2, \dots, a_n~ là một hoán vị của dãy ~1, 2, \dots, n~. Dãy ~a_1, a_2, \dots, a_n~ được gọi là dãy hình nón tại vị trí ~k~ ~(1 \le k \le n)~ nếu dãy tăng dần từ đầu đến vị trí thứ ~k~ và giảm dần từ vị trí ~k~ đến ~n~, cụ thể: ~a_1 < a_2 < \dots < a_{k-1} < a_k > a_{k+1} > \dots > a_n~.
Alice nhận thấy, với một vị trí ~k~ ~(1 \le k \le n)~ bất kì luôn có thể thực hiện một dãy thao tác đổi chỗ hai phần tử cạnh nhau để nhận được dãy hình nón tại vị trí ~k~, nhưng để thực hiện với ít thao tác nhất thì không dễ dàng.
Yêu cầu: Với mỗi vị trí ~k~ ~(1 \le k \le n)~, hãy giúp Alice thực hiện ít thao tác đổi chỗ hai phần tử cạnh nhau nhất để từ dãy ban đầu nhận được dãy hình nón tại vị trí ~k~.
Input
Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 5 \cdot 10^5)~ là độ dài của dãy hoán vị;
Dòng thứ hai chứa ~n~ số ~a_i~ ~(1 \le a_i \le n)~ mô tả dãy hoán vị được cho.
Output
- Ghi ra trên một dòng gồm ~n~ số nguyên, số thứ ~k~ là số thao tác đổi chỗ ít nhất cần sử dụng để nhận được dãy hình nón tại vị trí ~k~.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~15\%~ | ~n \le 8~ |
| 2 | ~15\%~ | ~n \le 18~ |
| 3 | ~20\%~ | ~n \le 100~ |
| 4 | ~15\%~ | ~n \le 500~ |
| 5 | ~15\%~ | ~n \le 5000~ |
| 6 | ~20\%~ | Không có giới hạn gì thêm |
Sample Input 1
7
1 6 7 2 5 4 3
Sample Output 1
10 4 3 2 4 7 11
PreVOI 2024 - Khôi phục cây
Nộp bàiPoint: 6
Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Sample Input đúng của bài được đính chính ở dưới.
Alice đã tạo dữ liệu kiểm thử cho một bài toán liên quan đến đồ thị có dạng cây. Cụ thể, đồ thị dạng cây có ~n~ đỉnh, trong đó ~1~ là gốc, có ~n-1~ cạnh, cạnh thứ ~k~ ~(1 \le k \le n-1)~, nối hai đỉnh phân biệt ~u_k, v_k~ ~(1 \le u_k, v_k \le n)~ với trọng số là ~w_k~ (chú ý rằng, ~w_k~ có thể âm). Tuy nhiên, dữ liệu về các cạnh đã bị mất mà Alice chỉ nhớ được các thông tin sau:
Tổng trọng số của tất cả các cạnh bằng ~s~;
Với đỉnh ~i~ ~(1 < i \le n)~, tổng trọng số các cạnh đi từ đỉnh gốc ~1~ xuống đỉnh ~i~ bằng ~d_i~;
Yêu cầu: Hãy giúp Alice khôi phục lại cây.
Input
Dòng đầu tiên chứa hai số nguyên ~n~ và ~s~ ~(1 \le n \le 2 \cdot 10^5; 0 \le s \le 2 \cdot 10^5)~;
Dòng thứ hai chứa ~n~ số nguyên ~d_i~ ~(|d_1| + |d_2| + \dots + |d_n| \le 2 \cdot 10^5)~.
Output
- Gồm ~n-1~ dòng, dòng thứ ~k~ ~(1 \le k \le n-1)~ chứa ba số nguyên ~u_k~ ~v_k~ ~w_k~.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~20\%~ | ~n \le 10~; ~s \le 5000~; ~|d_1| + |d_2| + \dots + |d_n| \le 5000~ |
| 2 | ~20\%~ | Tồn tại cây dạng chuỗi thỏa mãn |
| 3 | ~20\%~ | ~n \le 1000~; ~s \le 5000~; ~|d_1| + |d_2| + \dots + |d_n| \le 5000~ |
| 4 | ~40\%~ | Không có giới hạn gì thêm |
Sample Input 1
5 2
0 1 -1 0 0
Sample Output 1
1 2 1
1 3 -1
3 4 1
3 5 1