IOI 2005 - Ngày 1

Byteman sở hữu khu vườn đẹp nhất Bytetown và đã trồng \(n\) cây hoa hồng trong vườn. Mùa hè đến, hoa đã lớn và nở rất đẹp, nhưng ông nhận ra mình không thể tự chăm sóc tất cả. Ông quyết định thuê hai người làm vườn và chọn hai khu vực hình chữ nhật, mỗi người phụ trách hoa hồng trong một khu vực. Hai khu vực không được có ô chung và mỗi khu vực phải chứa đúng \(k\) cây hoa hồng.

Byteman muốn dựng hàng rào quanh cả hai khu vực. Vì kinh phí hạn hẹp, ông muốn tổng chiều dài hàng rào nhỏ nhất có thể.

Khu vườn là một hình chữ nhật dài \(l\) mét, rộng \(w\) mét, được chia thành \(l\cdot w\) ô vuông kích thước \(1\times 1\) mét. Chọn hệ tọa độ có các trục song song với các cạnh của khu vườn. Mỗi ô có tọa độ nguyên \((x,y)\) với \(1\le x\le l\) và \(1\le y\le w\). Một ô có thể chứa nhiều cây hoa hồng.

Các khu vực cần chọn có cạnh song song với các cạnh của khu vườn. Với \(1\le l_1\le l_2\le l\) và \(1\le w_1\le w_2\le w\), khu vực có các ô ở bốn góc là \((l_1,w_1)\), \((l_1,w_2)\), \((l_2,w_1)\) và \((l_2,w_2)\) chứa tất cả các ô \((x,y)\) thỏa mãn \(l_1\le x\le l_2\) và \(w_1\le y\le w_2\). Chu vi của khu vực này là \(2(l_2-l_1+1)+2(w_2-w_1+1)\).

Hai khu vực không được chứa chung bất kỳ ô nào. Chúng có thể chung một cạnh hoặc một phần cạnh, nhưng vẫn phải được bao quanh bởi hai hàng rào riêng biệt; phần ranh giới chung được tính cho cả hai hàng rào.

Hãy tìm tổng chu vi nhỏ nhất của hai khu vực thỏa mãn các điều kiện trên, hoặc xác định rằng không tồn tại cách chọn như vậy.

Dữ liệu vào

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

• Dòng đầu chứa hai số nguyên \(l,w\), lần lượt là chiều dài và chiều rộng khu vườn.
• Dòng thứ hai chứa hai số nguyên \(n,k\), lần lượt là tổng số cây hoa hồng và số cây cần có trong mỗi khu vực.
• \(n\) dòng tiếp theo mô tả vị trí các cây hoa hồng. Dòng thứ \(i+2\) chứa hai số nguyên \(l_i,w_i\), là tọa độ ô chứa cây thứ \(i\). Hai hoặc nhiều cây có thể nằm trong cùng một ô.

Các số trên cùng một dòng được phân cách bởi một dấu cách.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa đúng một số nguyên: tổng chu vi nhỏ nhất của hai khu vực không có ô chung, mỗi khu vực chứa đúng \(k\) cây hoa hồng. Nếu không tồn tại hai khu vực như vậy, ghi từ NO.

Ràng buộc

• \(1\le l,w\le 250\).
• \(2\le n\le 5000\).
• \(1\le k\le n/2\).
• \(1\le l_i\le l\) và \(1\le w_i\le w\) với mọi \(1\le i\le n\).

Phân nhóm

Trong \(50\%\) số bộ dữ liệu kiểm tra, cả hai kích thước khu vườn đều thỏa mãn \(l,w\le 40\).

Ví dụ

6 5
7 3
3 4
3 3
6 1
1 1
5 5
5 5
3 1

22

Nguồn

IOI 2005.

Xét một dãy số nguyên không giảm \(s_1,\ldots,s_{n+1}\), nghĩa là \(s_i\le s_{i+1}\) với mọi \(1\le i\le n\). Dãy \(m_1,\ldots,m_n\) được xác định bởi \(m_i=\frac{s_i+s_{i+1}}{2}\) với \(1\le i\le n\) được gọi là dãy trung bình của dãy \(s_1,\ldots,s_{n+1}\).

Ví dụ, dãy trung bình của dãy \((1,2,2,4)\) là \((1.5,2,3)\). Các phần tử của dãy trung bình có thể không nguyên. Tuy nhiên, trong bài toán này, chỉ xét các dãy trung bình có tất cả phần tử là số nguyên.

Cho một dãy không giảm gồm \(n\) số nguyên \(m_1,\ldots,m_n\). Hãy tính số dãy không giảm gồm \(n+1\) số nguyên \(s_1,\ldots,s_{n+1}\) có dãy trung bình là dãy đã cho. Các phần tử của dãy \(s\) có thể là số âm.

Dữ liệu vào

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

• Dòng đầu chứa số nguyên \(n\).
• \(n\) dòng tiếp theo chứa dãy \(m_1,\ldots,m_n\). Dòng thứ \(i+1\) chứa duy nhất số nguyên \(m_i\).

Dãy \(m\) được bảo đảm không giảm.

Dữ liệu ra

Ghi ra đầu ra chuẩn đúng một số nguyên: số dãy số nguyên không giảm có dãy trung bình là dãy đầu vào.

Ràng buộc

• \(2\le n\le 5\,000\,000\).
• \(0\le m_i\le 1\,000\,000\,000\) với mọi \(1\le i\le n\).
• \(m_i\le m_{i+1}\) với mọi \(1\le i<n\).

Phân nhóm

Trong \(50\%\) số bộ dữ liệu kiểm tra, \(n\le 1000\) và \(0\le m_i\le 20\,000\) với mọi \(1\le i\le n\).

Ví dụ

3
2
5
9

4

Nguồn

IOI 2005.

Công viên giải trí Mountain vừa mở một trò tàu lượn mô phỏng. Đường ray gồm \(n\) đoạn ray nối tiếp nhau, đầu đoạn ray thứ nhất được cố định ở độ cao \(0\). Byteman, người vận hành, có thể thay đổi cấu hình đường ray bằng cách điều chỉnh độ chênh cao của một số đoạn ray liên tiếp. Độ chênh cao của các đoạn ray khác không đổi. Sau mỗi lần điều chỉnh, phần đường ray phía sau được nâng lên hoặc hạ xuống để các đoạn vẫn nối liền nhau, còn điểm bắt đầu vẫn ở độ cao \(0\).

Mỗi lượt chơi bắt đầu bằng việc phóng xe từ đầu đường ray với năng lượng đủ để đạt đến độ cao \(h\). Xe tiếp tục di chuyển chừng nào độ cao của đường ray không vượt quá \(h\) và xe chưa đến cuối đường ray. Với mỗi lượt chơi, hãy tính số đoạn ray mà xe đi qua trọn vẹn trước khi dừng lại.

Bộ mô phỏng biểu diễn đường ray bằng dãy \(n\) độ chênh cao \(d_1,\ldots,d_n\). Giá trị \(d_i\) là độ chênh cao, tính bằng xentimét, của đoạn ray thứ \(i\). Nếu sau khi đi qua \(i-1\) đoạn ray, xe ở độ cao \(H\), thì sau khi đi qua đoạn thứ \(i\), xe ở độ cao \(H+d_i\).

Ban đầu, tất cả các đoạn ray đều nằm ngang, tức là \(d_i=0\) với mọi \(i\). Các lượt chơi và các lần điều chỉnh diễn ra xen kẽ. Mỗi lần điều chỉnh được mô tả bởi ba số \(a,b,D\): đặt độ chênh cao của từng đoạn ray từ \(a\) đến \(b\), kể cả hai đầu, bằng \(D\). Nói cách khác, gán \(d_i=D\) với mọi \(a\le i\le b\).

Mỗi lượt chơi được mô tả bởi một số \(h\), là độ cao lớn nhất xe có thể đạt đến. Hãy xử lý các lần điều chỉnh và lượt chơi theo đúng thứ tự được cho.

Dữ liệu vào

Đọc từ đầu vào chuẩn. Dòng đầu chứa số nguyên dương \(n\), là số đoạn ray.

Các dòng tiếp theo mô tả những lần điều chỉnh xen kẽ với các lượt chơi, kết thúc bằng dấu hiệu hết dữ liệu. Mỗi dòng có một trong ba dạng:

• I a b D: chữ cái in hoa I và ba số nguyên \(a,b,D\), yêu cầu gán \(d_i=D\) cho mọi \(a\le i\le b\).
• Q h: chữ cái in hoa Q và số nguyên \(h\), mô tả một lượt chơi với độ cao tối đa \(h\).
• E: chỉ chứa chữ cái in hoa E, đánh dấu kết thúc dữ liệu vào.

Các thành phần trên cùng một dòng được phân cách bởi một dấu cách.

Dữ liệu ra

Với mỗi lượt chơi, ghi ra đầu ra chuẩn một dòng chứa một số nguyên: số đoạn ray xe đi qua trọn vẹn trong lượt đó. Dòng thứ \(i\) của kết quả ứng với lượt chơi thứ \(i\) trong dữ liệu vào.

Ràng buộc

• \(1\le n\le 1\,000\,000\,000\).
• Trong mỗi lệnh I, \(1\le a\le b\le n\) và \(-1\,000\,000\,000\le D\le 1\,000\,000\,000\).
• Trong mỗi lệnh Q, \(0\le h\le 1\,000\,000\,000\).
• Tại mọi thời điểm, độ cao của mọi điểm trên đường ray nằm trong đoạn \([0,1\,000\,000\,000]\) xentimét.
• Toàn bộ dữ liệu vào có không quá \(100\,000\) dòng.

Phân nhóm

Trong \(50\%\) số bộ dữ liệu kiểm tra, \(n\le 20\,000\) và toàn bộ dữ liệu vào có không quá \(1000\) dòng.

Ví dụ

4
Q 1
I 1 4 2
Q 3
Q 1
I 2 2 -1
Q 3
E

4
1
0
3

Nguồn

IOI 2005.