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

Time limit: 2.0s / Memory limit: 512M

Points: 7

Hưởng ứng phong trào thi đua học tập của trường, cô giáo chủ nhiệm lớp của Nam muốn chọn các cặp đôi bạn giúp đỡ nhau cùng tiến. Lớp của Nam có ~n~ học sinh, được đánh số từ ~1~ đến ~n~, học sinh thứ ~i~ có chỉ số học lực ~a_i~. Để có được sự cân bằng giữa các cặp bạn cùng tiến, cô giáo muốn chọn các cặp bạn có tổng chỉ số học lực đôi một giữa các cặp chênh nhau không quá một giá trị nhỏ ~d~ sao cho mỗi bạn xuất hiện trong không quá một cặp. Cô giáo mong muốn chọn được nhiều cặp như vậy nhất.

Yêu cầu: Cho biết số học sinh của lớp và chỉ số học lực của từng học sinh, hãy tính số cặp bạn cùng tiến nhiều nhất mà có tổng chỉ số học lực đôi một giữa các cặp chênh nhau không quá ~d~.

Dữ liệu

Vào từ file văn bản PAIR.INP:

  • Dòng đầu tiên chứa hai số nguyên không âm ~n, d~ (~n \ge 2~);
  • Dòng thứ hai chứa ~n~ số nguyên dương, số thứ ~i~ là chỉ số học lực ~a_i~ của học sinh thứ ~i~ (~1 \le i \le n~, ~a_i \le 10^9~).

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

Kết quả

Ghi ra file văn bản PAIR.OUT một số nguyên duy nhất là số cặp nhiều nhất tìm được.

Ràng buộc

  • Có ~20\%~ số test ứng với ~20\%~ số điểm của bài thỏa mãn: ~n \le 10~; ~d = 0~;
  • ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thỏa mãn: ~n \le 200~; ~d = 0~;
  • ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thỏa mãn: ~n \le 2000~; ~d = 0~;
  • ~30\%~ số test khác ứng với ~30\%~ số điểm của bài thỏa mãn: ~n \le 200~; ~d = 1~;
  • ~10\%~ số test còn lại ứng với ~10\%~ số điểm của bài thỏa mãn: ~n \le 2000~; ~d = 1~.

Ví dụ

Input
7 1
9 1 2 4 5 6 8
Output
3
Giải thích

Một phương án chọn được nhiều nhất cặp các bạn học sinh với tổng học lực đôi một chênh nhau không quá ~1~ là:

$$\begin{array}{rcl} 1 + 8 &=& 9; \\ 2 + 6 &=& 8; \\ 4 + 5 &=& 9. \end{array}$$

Một phương án khác cũng chọn được ~3~ cặp là:

$$\begin{array}{rcl} 1 + 9 &=& 10; \\ 2 + 8 &=& 10; \\ 4 + 6 &=& 10. \end{array}$$


Time limit: 1.0s / Memory limit: 512M

Points: 7

Khi nghiên cứu về lý thuyết đồ thị, Nam đã tìm ra một đặc trưng cho đồ thị vô hướng. Cụ thể, với đồ thị vô hướng ~G~ gồm ~n~ đỉnh, xét lần lượt từng đỉnh từ ~1~ đến ~n~, với đỉnh ~i~, Nam tính được số ~a_i~ bằng số lượng đỉnh ~j~, thỏa mãn ~1 \le j < i~, mà ~j~ có cạnh nối với ~i~. Dãy số nguyên ~a_1, a_2, \ldots, a_n~ được gọi là dãy đặc trưng của đồ thị. Dễ nhận thấy rằng một đồ thị chỉ có duy nhất một dãy đặc trưng, tuy nhiên, có thể có nhiều đồ thị khác nhau nhưng có cùng một dãy đặc trưng.

Bẵng đi một thời gian, một hôm, Nam tìm lại được một file văn bản ghi một dãy số là một dãy đặc trưng của một đồ thị vô hướng. Tuy nhiên, dãy bị khuyết mất một số số và biết rằng bậc mỗi đỉnh của đồ thị này đều nhỏ hơn hoặc bằng ~b~. Nam muốn tính số lượng cách điền các số vào các vị trí bị khuyết để nhận được dãy ~f~ là dãy đặc trưng biết rằng:

  1. Tồn tại ít nhất một đồ thị có dãy đặc trưng là ~f~;
  2. Tất cả các đồ thị có dãy đặc trưng là ~f~ đều có bậc của mỗi đỉnh trong đồ thị nhỏ hơn hoặc bằng ~b~.

Yêu cầu: Cho số nguyên ~b~ và dãy đặc trưng bị khuyết, gọi ~S~ là số lượng cách điền các số vào các vị trí bị khuyết để nhận được dãy ~f~ là dãy đặc trưng thỏa mãn, hãy tính ~S \bmod (10^9 + 7)~, trong đó ~\bmod~ là phép toán chia lấy dư. Hai cách điền gọi là khác nhau nếu như tồn tại một vị trí khuyết mà giá trị điền vào trong cách này khác với giá trị điền vào trong cách kia.

Dữ liệu

Vào từ file văn bản GRAPH.INP:

  • Dòng đầu tiên chứa hai số nguyên dương ~n, b~ (~b \le n~);
  • Dòng thứ hai chứa ~n~ số nguyên, số thứ ~i~ có giá trị ~a_i~ (~1 \le i \le n~; ~0 \le a_i \le i - 1~ hoặc ~a_i = -1~) mô tả dãy đặc trưng. Giá trị ~a_i = -1~ có nghĩa là vị trí thứ ~i~ bị khuyết.

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

Kết quả

Ghi ra file văn bản GRAPH.OUT một số nguyên duy nhất là giá trị ~S \bmod (10^9 + 7)~.

  • Có ~25\%~ số test ứng với ~25\%~ số điểm của bài thỏa mãn: ~n \le 6~;
  • ~30\%~ số test khác ứng với ~30\%~ số điểm của bài thỏa mãn: ~n \le 200~ và chỉ có duy nhất một ô bị khuyết;
  • ~25\%~ số test khác ứng với ~25\%~ số điểm của bài thỏa mãn: ~n \le 200~;
  • ~20\%~ số test còn lại ứng với ~20\%~ số điểm của bài thỏa mãn: ~n \le 2000~.

Ví dụ

Input
4 1
-1 -1 1 -1
Output
1
Giải thích

Có duy nhất một dãy đặc trưng thỏa mãn là ~(0, 0, 1, 0)~ và có tất cả ~2~ đồ thị cùng có dãy đặc trưng này như trong hình sau:


Time limit: 1.0s / Memory limit: 512M

Points: 6

Thành phố nơi Nam sinh sống đã xay dựng hệ thống Wi-Fi công cộng để phục vụ khách du lịch và người dân trong thành phố. Hệ thống bao gồm ~n~ trạm phát sóng được đánh số từ ~1~ đến ~n~, trạm thứ ~i~ được đặt ở vị trí tương ứng với tọa độ ~(x_i, y_i)~ trên bản đồ mặt phẳng tọa độ của thành phố. Các trạm phát sóng này đều có mức độ phủ sóng là ~s~. Hai trạm phát sóng ~i~ và ~j~ có thể truyền thông tin cho nhau bằng sóng nếu ~\left|x_i - x_j \right| + \left| y_i - y_j \right| \le s~, hoặc trạm phát sóng ~i~ có thể truyền thông tin qua một số trạm phát sóng trung gian để tới được trạm phát sóng ~j~. Một nhóm các trạm phát sóng gọi là liên thông nếu như hai trạm bất kỳ trong nhóm có thể truyền thông tin cho nhau. Mỗi nhóm liên thông chỉ cần một đường truyền cung cấp internet để tất cả các trạm phát sóng này đều có thể phát được mạng internet cho người dân sử dụng.

Tuy nhiên, sau một thời gian sử dụng, chi phí duy trì hoạt động của hệ thống này là rất lớn, trong đó chi phí sử dụng mạng internet hàng tháng là chiếm nhiều nhất. Chi phí sử dụng mạng internet tỉ lệ thuận với số đường truyền cung cấp internet. Do đó, chính quyền thành phố muốn giảm thiểu số lượng truyền cung cấp internet mà vẫn bảo đảm tất cả các trạm đều có mạng internet bằng cách thiết kế các đường dây cáp kết nối trực tiếp một số trạm phát sóng với nhau. Với hai trạm phát sóng ~u~ và ~v~ chưa truyền được thông tin cho nhau, khi kết nối trực tiếp chúng bằng đường dây cáp, hai trạm phát sóng này có thể truyền tin cho nhau, vì vậy, nếu một trong hai trạm có mạng internet thì trạm còn lại cũng có mạng internet và toàn bộ nhóm liên thông chứa trạm này đều phát được mạng internet, do đó, có thể giảm độ một đường truyền cung cấp internet. Chi phí để kết nối hai trạm phát sóng ~u~ và ~v~ bằng đường dây cáp là ~\left | x_u - x_v \right| + \left| y_u - y_v \right|~. Chính quyền thành phố muốn xây dựng phương án giảm đi ~k~ đường truyền cung cấp internet mà vẫn bảo đảm trạm phát sóng nào cũng có mạng internet bằng cách sử dụng thêm ~k~ đường dây cáp kết nối trực tiếp sao cho tổng chi phí kết nối bằng dây cáp là nhỏ nhất.

Yêu cầu: Cho biết số lượng và vị trí của ~n~ trạm phát sóng, mức độ phủ sóng ~s~ của các trạm phát sóng và số lượng ~k~ đường truyền cung cấp internet cần giảm đi, hãy tính chi phí nhỏ nhất để kết nối các trạm phát sóng bằng dây cáp sao cho trạm phát sóng nào cũng có mạng internet.

Dữ liệu

Vào từ file văn bản INTERNET.INP:

  • Dòng đầu tiên chứa ba số nguyên dương ~n, s, k~ (~n \le 10^5~; ~s \le 10^9~; ~k \le 20~);
  • Dòng thứ ~i~ trong số ~n~ dòng tiếp theo chứa hai số nguyên không âm ~x_i, y_i~ mô tả vị trí trạm phát sóng thứ ~i~ (~1 \le i \le n~; ~x_i, y_y \le 10^9~). Dữ liệu bảo đảm không có hai trạm phát sóng nào có tọa độ trùng nhau và số lượng đường truyền cung cấp internet cần sử dụng cho hệ thống ban đầu lớn hơn ~k~.

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

Kết quả

Ghi ra file văn bản INTERNET.OUT một số nguyên duy nhất là chi phí nhỏ nhất để kết nối các trạm phát sóng thỏa mãn yêu cầu.

  • Có ~20\%~ số test ứng với ~20\%~ số điểm của bài thỏa mãn: ~n \le 1000~;
  • ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thỏa mãn tọa độ tất cả các trạm phát sóng đều nằm trên một đường thẳng;
  • ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thỏa mãn giá trị tọa độ mỗi trạm phát sóng không vượt quá ~1000~;
  • ~40\%~ số test còn lại ứng với ~40\%~ số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input
5 4 1
1 1
3 4
8 5
5 5
7 1
Output
5
Giải thích

Ban đầu có ~3~ nhóm liên thông là {Trạm 1}, {Trạm 2, Trạm 3, Trạm 4} và {Trạm 5}. Phương án cho chi phí nhỏ nhất để giảm bớt một đường truyền cung cấp internet là nối cặp giữa Trạm 3 và Trạm 5 cho chi phí bằng ~|8 - 7| + |5 - 1| = 5~.