JOI 2008 Representative Selection - Ngày 2

Trong \(D\) ngày liên tiếp, người bạn đời của bạn mua một loại hàng mỗi ngày trên chợ trực tuyến Nile.com. Chợ có \(N\) cửa hàng được đánh số từ \(1\) đến \(N\); mỗi ngày chọn đúng một cửa hàng để mua. Giá mỗi cửa hàng có thể thay đổi theo ngày và đã được thông báo trước.

Nếu mua tại cùng một cửa hàng trong hai ngày liên tiếp, giá ngày thứ hai được giảm \(10\%\). Nếu mua tại cùng cửa hàng từ ba ngày liên tiếp trở lên, giá ngày thứ ba và các ngày tiếp theo được giảm \(30\%\). Khi đổi cửa hàng, chuỗi ngày liên tiếp bắt đầu lại. Mọi giá niêm yết đều là bội của \(10\).

Hãy lập kế hoạch sao cho tổng tiền trả trong \(D\) ngày nhỏ nhất và tính tổng tiền đó.

Dữ liệu vào

Đọc từ đầu vào chuẩn gồm \(D+1\) dòng.

Dòng đầu chứa \(N,D\), với \(2 \le N \le 3000\), \(2 \le D \le 365\).

\(D\) dòng tiếp theo lần lượt ứng với các ngày. Mỗi dòng chứa \(N\) giá trước giảm, theo thứ tự cửa hàng. Mỗi giá là bội của \(10\) trong đoạn từ \(10\) đến \(100000\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa tổng tiền nhỏ nhất.

Chấm điểm

Giới hạn thời gian: \(1\) giây mỗi bộ dữ liệu. Giới hạn bộ nhớ: \(64\) MB.

Có \(10\) bộ dữ liệu, mỗi bộ \(10\) điểm; tổng cộng \(100\) điểm. \(40\%\) số điểm ứng với \(N \le 200\); \(20\%\) toàn bộ dữ liệu có \(N \le 10\), \(D \le 10\). Các bảo đảm này không được hiểu là các nhóm rời nhau.

Ví dụ

4 5
50 30 80 70
50 30 50 40
50 50 60 50
30 90 40 50
70 30 70 80

152

4 5
110 160 80 200
150 170 80 120
80 150 160 160
160 110 200 110
150 190 160 190

481

Phòng thi Olympic Tin học là một hình chữ nhật. Chọn hai trục tọa độ song song với các bức tường và gốc tọa độ tại một góc phòng. Ủy ban đã chế tạo \(n\) thiết bị để theo dõi \(m\) thí sinh cần được giám sát.

Mỗi thiết bị \(i\) có thể được đặt theo một trong hai hướng:

• Theo hướng trục \(x\): theo dõi mọi thí sinh trong dải \(p_i \le y \le p_i+d_i\).
• Theo hướng trục \(y\): theo dõi mọi thí sinh trong dải \(p_i \le x \le p_i+d_i\).

Các giá trị \(p_i,d_i\) là số nguyên, có thể chọn riêng cho từng thiết bị, với \(d_i \ge 0\). \(d_i\) càng nhỏ thì giám sát càng chính xác. Có thể không dùng hết các thiết bị.

Mỗi thí sinh trong danh sách phải được ít nhất một thiết bị hướng \(x\) và ít nhất một thiết bị hướng \(y\) theo dõi. Thí sinh đứng trên biên dải vẫn được theo dõi. Các thí sinh không di chuyển và có tọa độ đôi một khác nhau.

Gọi \(d_{\max}\) là giá trị \(d_i\) lớn nhất của các thiết bị. Hãy tìm giá trị nhỏ nhất có thể của \(d_{\max}\).

Dữ liệu vào

Đọc từ đầu vào chuẩn.

Dòng đầu chứa \(n,m\), với \(2 \le n \le 200000\), \(1 \le m \le 100000\).

\(m\) dòng tiếp theo, mỗi dòng chứa tọa độ nguyên \(x_j,y_j\) của một thí sinh, với \(0 \le x_j,y_j \le 1000000000\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên là giá trị nhỏ nhất của \(d_{\max}\).

Chấm điểm

Giới hạn thời gian: \(1\) giây mỗi bộ dữ liệu. Giới hạn bộ nhớ: \(64\) MB.

Có \(10\) bộ dữ liệu, mỗi bộ \(10\) điểm; tổng cộng \(100\) điểm. \(30\%\) số điểm ứng với \(n,m \le 100\) và mọi tọa độ không quá \(10000\). Một phần \(20\%\) khác ứng với \(n,m \le 1000\).

Ví dụ

4 5
4 9
2 4
7 8
6 1
4 4

3

Thành phố JOI muốn xây một lối đi bộ tự động chạy theo đường thẳng từ đầu này đến đầu kia thành phố. Một cư dân hài lòng nếu khoảng cách từ nhà mình đến đường này không quá \(d\), và không hài lòng nếu khoảng cách lớn hơn \(d\).

Hãy chọn vị trí và hướng của đường sao cho số cư dân hài lòng lớn nhất, rồi tính số đó. Mỗi ngôi nhà là một điểm trên mặt phẳng; lối đi có chiều rộng bằng \(0\). Lối đi có thể đi qua nhà, khi đó cư dân vẫn hài lòng. Khoảng cách được hiểu là khoảng cách Euclid từ điểm đến đường thẳng.

Dữ liệu vào

Đọc từ đầu vào chuẩn.

Dòng đầu chứa số cư dân \(n\) và khoảng cách \(d\), với \(1 \le n \le 1000\), \(0.001 \le d \le 10000\). \(d\) là số thực dương, có thể có tới ba chữ số sau dấu thập phân.

\(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x_i,y_i\), với \(-1000 \le x_i,y_i \le 1000\). Các vị trí nhà đôi một khác nhau.

Cả ví dụ lẫn dữ liệu chấm đều bảo đảm: nếu thay \(d\) bằng bất kỳ số thực nào trong đoạn \([d-0.0005,d+0.0005]\), số cư dân hài lòng tối đa không thay đổi.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa số cư dân hài lòng lớn nhất.

Chấm điểm

Giới hạn thời gian: \(10\) giây mỗi bộ dữ liệu. Giới hạn bộ nhớ: \(64\) MB.

Có \(10\) bộ dữ liệu, mỗi bộ \(10\) điểm; tổng cộng \(100\) điểm. \(60\%\) số điểm ứng với \(n \le 100\).

Ví dụ

10 8.000
-2 1
-10 2
-2 3
-7 -8
7 5
10 -5
-9 -6
-6 10
-5 8
4 -2

9