Kỳ thi Học sinh giỏi Quốc gia 2020 - Ngày 2

VOI 20 Bài 4 - Giàn đèn

Giới hạn thời gian: 0.38s / Giới hạn bộ nhớ: 512M

Điểm: 7

Đọc đề gốc tại đây.

Một giàn đèn trang trí kích thước ~m \times n~, các hàng đánh số từ ~1~ đến ~m~ từ trên xuống dưới, các cột đánh số từ ~1~ đến ~n~ từ trái sang phải. Ô nằm giao giữa hàng ~r~ và cột ~c~ gọi là ô ~(r, c)~. Trên mỗi ô có một bóng đèn, mỗi bóng đèn có ba trạng thái: hoặc tắt, hoặc bật sáng màu xanh, hoặc bật sáng màu đỏ. Có ~k~ ô phân biệt ~(r_1, c_1), (r_2, c_2), \dots, (r_k, c_k)~ của giàn đèn, mỗi ô có một công tắc điều khiển. Khi tác động vào công tắc của ô ~(r_t, c_t)~ thì những đèn nằm trong các ô thuộc hình chữ nhật có ô trái trên là ~(r_t, c_t)~ và ô phải dưới là ~(x_t, y_t)~ sẽ đổi trạng thái ~(t = 1, 2, \dots, k)~. Cụ thể, các đèn nằm trong các ô ~(u, v)~ mà ~r_t \leq u \leq x_t~ và ~c_t \leq v \leq y_t~ sẽ thay đổi theo quy tắc: nếu đèn đang ở trạng thái tắt sẽ chuyển sang trạng thái bật sáng màu xanh, nếu đang ở trạng thái bật sáng màu xanh sẽ chuyển sang trạng thái bật sáng màu đỏ, còn nếu đèn đang ở trạng thái bật sáng màu đỏ sẽ chuyển sang trạng thái tắt. Mỗi công tắc có thể tác động nhiều lần.

Yêu cầu: Cho thông tin trạng thái ban đầu các đèn trên giàn và các công tắc. Hãy tìm cách đưa tất cả các đèn về cùng một trạng thái bật sáng màu xanh hoặc bật sáng màu đỏ với số lần tác động là ít nhất.

Input

Dòng đầu chứa ba số nguyên dương ~m~, ~n~, ~k~ ~(k \leq m \times n)~;
Dòng thứ ~i~ trong số ~m~ dòng tiếp theo chứa ~n~ số nguyên nhận giá trị ~0~, ~1~ hoặc ~2~. Số thứ ~j~ ~(j = 1, 2, \dots, n)~ mô tả trạng thái đèn ở ô ~(i, j)~ là tắt, bật sáng màu xanh hoặc bật sáng màu đỏ tương ứng với các giá trị ~0~, ~1~ hoặc ~2~;
Dòng thứ ~t~ trong số ~k~ dòng tiếp theo chứa bốn số nguyên dương ~r_t, c_t, x_t, y_t~ (~1 \leq r_t \leq x_t \leq m~ và ~1 \leq c_t \leq y_t \leq n~).

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

Ghi ra duy nhất một số nguyên là số lần tác động ít nhất để các đèn về cùng một trạng thái sáng màu xanh hoặc sáng màu đỏ, nếu không tồn tại cách tác động thì ghi số ~-1~.

Giới hạn

Có ~40\%~ số test ứng với ~40\%~ số điểm của bài thỏa mãn điều kiện: ~m = 1~; ~n \leq 10~;
~40\%~ số test khác ứng với ~40\%~ số điểm của bài thỏa mãn điều kiện: ~m \times n \leq 10^3~;
~20\%~ số test còn lại ứng với ~20\%~ số điểm của bài thỏa mãn điều kiện: ~m \times n \leq 10^5~.

Sample Input

Sample Output

Note

Trước tiên tác động vào công tắc ở ô ~(1~, ~3)~, sau đó tác động vào công tắc ở ô ~(1~, ~2)~, khi đó tất cả các đèn trên giàn đều sáng màu đỏ.

VOI 20 Bài 5 - Tòa nhà

Nộp bài

Giới hạn thời gian: 1.12s / Giới hạn bộ nhớ: 512M

Điểm: 7

Đọc đề gốc tại đây.

Thành phố nơi Alice sinh sống có ~n~ toà nhà. Trên bản thiết kế, mặt bằng nền mỗi tòa nhà đều là hình chữ nhật có các cạnh song song với trục tọa độ, với các đỉnh đều có tọa độ nguyên trên hệ trục tọa độ. Hai tòa nhà gọi là liền kề nếu có hai đường biên của hai hình chữ nhật mặt nền tương ứng hai tòa nhà đó có ít nhất một điểm chung. Để thuận tiện đi lại giữa các tòa nhà, người ta xây dựng một lối đi tắt hai chiều giữa mỗi cặp tòa nhà liền kề.

Alice rất thích thú với cách thiết kế các tòa nhà của thành phố và thường xuyên đi lại giữa các tòa nhà thông qua các lối đi tắt này. Sau một thời gian khám phá, Alice nhận thấy có một số lối đi tắt là độc đạo. Một lối đi tắt giữa hai tòa nhà ~u~ và ~v~ gọi là độc đạo nếu như sau khi đi từ ~u~ sang ~v~ qua lối đi này thì không có cách đi nào quay trở lại ~u~ thông qua các lối đi tắt khác ngoài lối đi tắt từ ~v~ về ~u~.

Với mỗi cặp tòa nhà ~(u, v)~ có lối đi tắt là độc đạo, Alice tiếp tục khám phá nếu như đóng cửa lối đi độc đạo này thì xuất phát từ ~u~ Alice có thể tham quan được tối đa ~d_u~ tòa nhà, và nếu xuất phát từ ~v~ Alice có thể tham quan được tối đa ~d_v~ tòa nhà. Khoảng chênh lệch giữa ~d_u~ và ~d_v~ là giá trị ~|d_u - d_v|~.

Yêu cầu: Biết tọa độ các đỉnh hình chữ nhật mặt nền tương ứng của các tòa nhà, hãy giúp Alice tìm cặp tòa nhà ~(u, v)~ có lối đi tắt độc đạo sao cho khoảng chênh lệch giữa ~d_u~ và ~d_v~ là nhỏ nhất.

Input

Dòng thứ nhất chứa một số nguyên dương ~n~ là số lượng tòa nhà cao tầng;
Dòng thứ ~i~ trong số ~n~ dòng tiếp theo chứa ~4~ số nguyên không âm ~x_i, y_i, p_i, q_i~ với ~(x_i, y_i)~ là tọa độ của đỉnh trái trên và ~(p_i, q_i)~ là tọa độ của đỉnh phải dưới của hình chữ nhật biểu thị mặt nền tòa nhà thứ ~i~ trên bản đồ quy hoạch. Dữ liệu đảm bảo ~x_i < p_i~ và ~y_i > q_i~ và hai hình chữ nhật bất kỳ có thể tiếp xúc nhưng không giao nhau.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

Ghi ra một số nguyên duy nhất là khoảng chênh lệch nhỏ nhất tìm được. Nếu không tồn tại lối đi tắt độc đạo thì in ra số ~-1~.

Giới hạn

Có ~30\%~ số test ứng với ~30\%~ số điểm của bài thỏa mãn điều kiện: ~n \leq 10^3~, các tọa độ không vượt quá ~10^9~;
~30\%~ số test khác ứng với ~30\%~ số điểm của bài thỏa mãn điều kiện: ~n \leq 10^5~, các tọa độ không vượt quá ~10^3~;
~40\%~ số test còn lại ứng với ~40\%~ số điểm của bài thỏa mãn điều kiện: ~n \leq 10^5~, các tọa độ không vượt quá ~10^9~.

Sample Input

Sample Output

Note

Có ~2~ lối đi độc đạo là lối đi giữa cặp tòa nhà ~(4, 5)~ và ~(5, 6)~. Nếu đóng cửa lối đi độc đạo qua ~(4, 5)~, ta có ~d_4 = 4~ và ~d_5 = 2~, do đó ~|d_4 - d_5| = 2~. Nếu đóng cửa lối đi độc đạo qua ~(5, 6)~, ta có ~d_5 = 5~ và ~d_6 = 1~, do đó ~|d_5 - d_6| = 4~.

VOI 20 Bài 6 - Động đất

Nộp bài

Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 512M

Điểm: 6

Đọc đề gốc tại đây.

Đất nước AZ có ~n~ thành phố vừa phải hứng chịu một trận động đất mạnh. Nhiều tòa nhà và các công trình công cộng bị phá hủy, làm tê liệt toàn bộ hệ thống giao thông giữa các thành phố. Sau những nỗ lực của chính phủ, có ~n - 1~ con đường hai chiều nối giữa ~n~ thành phố được sửa chữa để đảm bảo tính liên thông đi lại giữa ~n~ thành phố. Các thành phố được đánh số từ ~1~ đến ~n~. Con đường thứ ~k~ ~(k = 1, 2, \dots, n - 1)~ nối hai thành phố ~i_k~ và ~j_k~ có độ dài ~d(i_k, j_k)~ km. Theo dự báo, trong thời gian tới có thể xảy ra một trận động đất nữa, do đó, chính phủ đang lên kế hoạch ứng phó. Theo thông tin thu nhận được, hiện tại thành phố ~i~ ~(i = 1, 2, \dots, n)~ đang có ~p_i~ nhân viên cứu hộ. Chính phủ muốn điều chỉnh lại số lượng nhân viên cứu hộ ở các thành phố sao cho độ chênh lệch nhân viên cứu hộ giữa các thành phố là nhỏ nhất. Độ chênh lệch nhân viên cứu hộ giữa các thành phố được tính bằng hiệu số nhân viên cứu hộ ở thành phố có nhiều nhân viên nhất với thành phố có ít nhân viên nhất.

Tại mỗi thành phố đều có xe dùng để vận chuyển nhân viên cứu hộ (giả thiết số xe tại mỗi thành phố đủ nhiều để phục vụ vận chuyển), mỗi xe có khả năng vận chuyển không quá ~c~ nhân viên cứu hộ. Nếu muốn vận chuyển ~q~ nhân viên cứu hộ từ thành phố ~i~ sang thành phố ~j~ bằng đường nối trực tiếp thì thành phố ~i~ sẽ cần ~\lceil q/c \rceil~ xe, trong đó ~\lceil x \rceil~ là số nguyên nhỏ nhất không nhỏ hơn ~x~ và độ dài đường đi mà mỗi xe phải đi là ~d(i, j)~. Sau khi đến thành phố ~j~, các nhân viên cứu hộ sẽ ở lại hoặc có thể tiếp tục di chuyển sang thành phố khác bằng xe của thành phố ~j~. Để tiết kiệm chi phí vận chuyển, chính phủ cần xây dựng phương án vận chuyển sao cho tổng độ dài đường đi của các xe dùng để vận chuyển là ngắn nhất mà vẫn thỏa mãn yêu cầu nêu trên.

Yêu cầu: Cho thông tin về ~n -1~ con đường và số nhân viên cứu hộ tại mỗi thành phố. Hãy tìm phương án vận chuyển nhân viên cứu hộ mà tổng độ dài đường đi của các xe dùng vận chuyển là ngắn nhất mà vẫn đảm bảo yêu cầu độ chênh lệch nhân viên cứu hộ giữa các thành phố là nhỏ nhất.

Input

Dòng đầu chứa hai số nguyên dương ~n~ và ~c~ ~(c \leq 10^6)~;
Dòng thứ hai gồm ~n~ số nguyên không âm ~p_1, p_2, \dots, p_n~ ~(p_i \leq 10^6)~;
Dòng thứ ~k~ trong số ~n - 1~ dòng tiếp theo chứa ba số nguyên ~i_k, j_k, d(i_k, j_k)~ thỏa mãn ~1 \leq i_k < j_k \leq n~ và ~0 < d(i_k, j_k) \leq 10^6~.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

Dòng đầu chứa một số nguyên là tổng độ dài ngắn nhất của các xe dùng để vận chuyển đảm bảo yêu cầu độ chênh lệch nhân viên cứu hộ giữa các thành phố là nhỏ nhất;
Dòng thứ hai chứa số nguyên ~s~ là số lượng đợt vận chuyển;
Dòng thứ ~h~ trong ~s~ dòng tiếp theo chứa ba số nguyên dương ~i_h, j_h, q_h~, nghĩa là thành phố ~i_h~ sẽ có các xe vận chuyển ~q_h~ nhân viên cứu hộ sang thành phố ~j_h~ (giá trị ~q_h~ phải nhỏ hơn hoặc bằng số lượng nhân viên của thành phố ~i_h~ tại thời điểm vận chuyển).

Giới hạn

Có ~20\%~ số test ứng với ~20\%~ số điểm của bài thỏa mãn điều kiện: ~n = 3~;
~40\%~ số test khác ứng với ~40\%~ số điểm của bài thỏa mãn điều kiện: ~n \leq 3\,000~ và mỗi thành phố có không quá ~2~ đường nối trực tiếp tới thành phố khác;
~40\%~ số test còn lại ứng với ~40\%~ số điểm của bài thỏa mãn điều kiện: ~n \leq 3\,000~.

Đối với mỗi test, nếu thí sinh đưa ra đúng giá trị tổng độ dài ngắn nhất của các xe dùng để vận chuyển, thí sinh sẽ được ~70\%~ số điểm của test đó, nếu tiếp tục đưa ra được một phương án vận chuyển đúng, thí sinh sẽ được ~30\%~ số điểm còn lại.

Sample Input

Sample Output

Note

Giải thích: Cần hai xe vận chuyển ~19~ nhân viên cứu hộ từ thành phố ~3~ về thành phố ~1~ và hai xe vận chuyển ~20~ nhân viên cứu hộ từ thành phố ~4~ về thành phố ~2~, cuối cùng cần một xe vận chuyển ~1~ nhân viên từ thành phố ~1~ sang thành phố ~2~. Độ chênh lệch nhân viên cứu hộ giữa các thành phố bằng ~1~ và tổng độ dài đường đi của các xe là ~2 \times 1 + 2 \times 2 + 1 \times 1 = 7~ (km).