BOI 2010 - Ngày 2

Trong kho của một nhà máy có rất nhiều thùng rỗng xếp thành một hàng. Người quản lý muốn đặt một số thùng vào trong các thùng khác để tạo khoảng trống ở đầu bên trái của kho. Robot có thể nhấc một thùng, mang nó sang phải rồi đặt vào một thùng lớn hơn. Chuỗi ba thao tác này là cách duy nhất được phép dùng để di chuyển thùng.

Theo quy định an toàn, mỗi thùng chỉ được chứa nhiều nhất một thùng khác, và thùng được chứa phải rỗng. Người quản lý cũng muốn những cặp thùng lồng vào nhau nằm ở đầu bên trái của hàng còn lại để dễ theo dõi.

Hãy tìm số nguyên \(K\) lớn nhất sao cho có thể đặt \(K\) thùng ngoài cùng bên trái vào \(K\) thùng ngay tiếp theo, theo một thứ tự nào đó.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(M\) và \(N\), lần lượt là kích thước thùng lớn nhất và số thùng. Dòng thứ hai chứa \(N\) số nguyên \(A_i\), là kích thước các thùng theo thứ tự từ trái sang phải.

Dữ liệu ra

In một số nguyên là giá trị lớn nhất của \(K\) sao cho robot có thể đặt \(K\) thùng đầu tiên vào \(K\) thùng ngay tiếp theo.

Ràng buộc

• \(1 \le M \le 1000\).
• \(1 \le N \le 20\,000\).
• \(1 \le A_i \le M\) với \(1 \le i \le N\).

Ví dụ

5 10
2 2 1 4 3 2 5 4 2 3

4

Kristian là người bán hàng trong một cửa hàng kẹo. Cửa hàng có \(N\) gói kẹo, mỗi gói có thể chứa một số viên kẹo khác nhau. Khi khách muốn mua \(K\) viên, Kristian phải chọn một số gói sao cho tổng số viên kẹo trong các gói đó đúng bằng \(K\). Nếu không làm được, khách thường bực mình rồi bỏ đi. Chẳng hạn, nếu khách muốn mua \(4\) viên nhưng cửa hàng chỉ có \(5\) gói, mỗi gói chứa \(3\) viên, thì Kristian không thể đáp ứng.

Kristian đã tính được có bao nhiêu số lượng kẹo khác nhau mà mình có thể bán cho vị khách tiếp theo bằng những gói hiện có. Bây giờ, anh muốn mở một gói và thay đổi số viên kẹo trong đó để số lượng lựa chọn khác nhau dành cho khách tăng lên nhiều nhất có thể.

Dữ liệu vào

Dòng đầu chứa số nguyên \(N\). Dòng thứ hai chứa \(N\) số nguyên \(B_i\), là số viên kẹo trong từng gói.

Dữ liệu ra

In hai số nguyên \(P\) và \(Q\), cách nhau bởi một dấu cách. Kristian sẽ lấy một gói đang chứa \(P\) viên kẹo và thay đổi số viên trong gói đó thành \(Q\). Giá trị \(P\) phải bằng một trong các giá trị \(B_i\).

Nếu có nhiều cách thay đổi tối ưu, hãy chọn cách có \(P\) nhỏ nhất. Trong số các cách tối ưu có \(P\) nhỏ nhất đó, hãy chọn cách có \(Q\) nhỏ nhất.

Ràng buộc

• \(2 \le N \le 100\).
• \(1 \le B_i \le 7000\) với \(1 \le i \le N\).
• Luôn có thể tăng số lượng đơn hàng khác nhau đáp ứng được bằng cách thay đổi một gói.

Ví dụ

4
1 3 4 4

4 9

5
3 3 3 3 3

3 1

Heino vẽ một bảng ô vuông gồm \(H\) hàng và \(W\) cột. Mỗi ô hoặc trống, hoặc chứa một quả mìn. Indrek, một người bạn thân của Heino, vẽ một bảng khác cùng kích thước. Trong mỗi ô của bảng mình, Indrek ghi tổng số mìn trong ô tương ứng của bảng Heino và tất cả các ô kề với ô đó. Hai ô được xem là kề nhau nếu chúng có ít nhất một điểm chung.

Sau đó, Indrek xóa bảng của Heino. Cho bảng của Indrek, hãy giúp Heino khôi phục bảng mìn ban đầu. Luôn tồn tại ít nhất một cách khôi phục hợp lệ.

Dữ liệu vào

Dòng đầu của mỗi tệp chứa hai số nguyên \(H\) và \(W\), lần lượt là số hàng và số cột. Mỗi dòng trong \(H\) dòng tiếp theo chứa \(W\) chữ số, mô tả bảng của Indrek.

Dữ liệu ra

Tệp kết quả tương ứng phải chứa \(H\) dòng, mỗi dòng gồm \(W\) ký tự: X biểu thị một ô có mìn và . biểu thị một ô trống.

Nếu có nhiều cách khôi phục hợp lệ, có thể nộp bất kỳ cách nào.

Ràng buộc

• \(1 \le H \le 600\).
• \(1 \le W \le 600\).

Nộp bài

Đây là bài chỉ nộp kết quả. Bạn được cung cấp \(10\) tệp dữ liệu vào, từ mines.01.in đến mines.10.in. Hãy tạo các tệp kết quả tương ứng từ mines.01.out đến mines.10.out và nộp chúng trong một tệp ZIP, với các tệp kết quả nằm trực tiếp trong ZIP. Không nộp chương trình.

Ví dụ

3 5
24531
46631
34310

.XXX.
.XX..
XX...