USACO 2013 - Tháng 1 - Hạng Vàng

Với mỗi submission AC trong thời gian chính thức của contest LQDOJ Cup 2024 - Round #1, các bạn đã đóng góp 12.500 VNĐ vào quỹ ủng hộ đồng bào khắc phục sự cố cơn bão Yagi. Số tiền này sẽ được tổng hợp và chuyển tới Mặt trận Tổ quốc Việt Nam sau khi việc kiểm tra được hoàn tất.

Bạn Trung có \(n\) viên bi đầy màu sắc xếp thành một hàng, viên bi thứ \(i\) có màu \(a_i\), màu của một viên bi là một số nguyên dương có giá trị không quá \(1024\).

Độ đẹp của một hàng bi là độ dài dãy con liên tiếp dài nhất mà các viên bi trong dãy có cùng màu.

Bạn Trung có thể chọn một số viên bi bất kì trong hàng và đưa chúng ra khỏi hàng bi (các viên bi còn lại được giữ nguyên vị trí) sao cho các viên bị đưa ra ngoài thuộc không quá \(k\) màu khác nhau.

Hãy giúp bạn Trung tìm độ đẹp lớn nhất có thể của hàng bi.

Input

• Dòng đầu tiên gồm \(2\) số nguyên dương \((1 \leq n \leq 131072, 1 \leq k \leq 1024)\) - độ dài của hàng bi và số lượng màu riêng biệt tối đa của các viên bi bị đưa ra khỏi hàng.
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((1 \leq a_i \leq 1024)\) - màu của các viên bi.

Output

• Số nguyên duy nhất là độ đẹp lớn nhất có thể của hàng bi.

Scoring

• Subtask \(1\) (\(11\%\) số điểm): \(k = 1, n \leq 128\).
• Subtask \(2\) (\(12\%\) số điểm): \(k = 2\), có tối đa \(8\) màu.
• Subtask \(3\) (\(13\%\) số điểm): \(n \leq 512\), có tối đa \(16\) màu.
• Subtask \(4\) (\(15\%\) số điểm): \(n \leq 512\).
• Subtask \(5\) (\(16\%\) số điểm): \(n \leq 8192\).
• Subtask \(6\) (\(16\%\) số điểm): có tối đa \(64\) màu.
• Subtask \(7\) (\(17\%\) số điểm): không có rằng buộc gì thêm.

Example

5 1
1 3 3 2 3

3

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

3

22 3
3 3 3 3 2 1 1 1 4 5 1 1 1 3 3 6 7 10 3 3 3 3

6

Farmer John đã đưa đàn bò đi nghỉ ngoài biển! Đàn bò đang sống trên \(N\) hòn đảo (\(1 \le N \le 15\)), nằm trên một lưới \(R \times C\) (\(1 \le R, C \le 50\)). Một hòn đảo là một nhóm tối đại các ô được đánh dấu X và liên thông trên lưới, trong đó hai ô X liên thông nếu chúng có chung một cạnh. (Do đó, hai ô X chung một góc không nhất thiết liên thông.)

Tuy nhiên, Bessie đến muộn nên cô đang cùng FJ bay đến bằng trực thăng. Vì thế, ban đầu cô có thể hạ cánh trên bất kỳ hòn đảo nào mình chọn. Cô muốn ghé thăm tất cả những con bò ít nhất một lần, nên sẽ di chuyển giữa các hòn đảo cho đến khi đã ghé thăm cả \(N\) hòn đảo ít nhất một lần.

Trực thăng của FJ không còn nhiều nhiên liệu, vì vậy ông không muốn sử dụng nó cho đến khi đàn bò quyết định về nhà. May mắn thay, một số ô trên lưới là vùng nước nông, được ký hiệu bằng S. Bessie có thể bơi qua các ô này theo bốn hướng chính (bắc, đông, nam, tây) để di chuyển giữa các hòn đảo. Cô cũng có thể di chuyển (theo bốn hướng chính) từ một hòn đảo sang vùng nước nông và ngược lại.

Hãy tìm quãng đường tối thiểu Bessie phải bơi để ghé thăm tất cả các hòn đảo. (Quãng đường Bessie phải bơi là số lần cô đứng trên một ô được đánh dấu S.) Sau khi xem bản đồ khu vực, Bessie biết rằng điều này là khả thi.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(R\) và \(C\), cách nhau bởi dấu cách.
• \(R\) dòng tiếp theo: dòng thứ \(i\) chứa \(C\) ký tự mô tả hàng thứ \(i\) của lưới. Các ô nước sâu được đánh dấu ., các ô thuộc đảo được đánh dấu X, và các ô nước nông được đánh dấu S.

Dữ liệu ra

In ra một số nguyên duy nhất biểu thị quãng đường tối thiểu Bessie phải bơi để ghé thăm tất cả các hòn đảo.

Ví dụ

5 4
XX.S
.S..
SXSS
S.SX
..SX

3

Nguồn

USACO 2013 January Contest, Gold — Problem 2: Island Travels

Tác giả đề: Neal Wu, 2007.

Để kiếm thêm tiền, những con bò đã mở một nhà hàng chuyên phục vụ sữa lắc trong chuồng của chúng. Nhà hàng có \(N\) chỗ ngồi (\(1 \le N \le 500\,000\)) xếp thành một hàng. Ban đầu, tất cả các chỗ đều trống.

Trong ngày, có \(M\) sự kiện khác nhau xảy ra tuần tự tại nhà hàng (\(1 \le M \le 300\,000\)). Có hai loại sự kiện:

1. Một đoàn khách có \(p\) thành viên đến (\(1 \le p \le N\)). Bessie muốn xếp đoàn khách vào một khối liên tiếp gồm \(p\) chỗ ngồi trống. Nếu có thể, cô xếp họ vào vị trí thấp nhất có thể trong dãy ghế. Nếu không thể, đoàn khách bị từ chối.
2. Một đoạn \([a,b]\) được cho trước (\(1 \le a \le b \le N\)), và tất cả mọi người ngồi trong đoạn ghế đó rời đi.

Hãy giúp Bessie đếm tổng số đoàn khách bị từ chối trong suốt cả ngày.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\), cách nhau bởi dấu cách.
• \(M\) dòng tiếp theo, mỗi dòng mô tả một sự kiện. Dòng có dạng A p (nghĩa là một đoàn khách có \(p\) thành viên đến) hoặc L a b (nghĩa là tất cả những con bò trong đoạn ghế \([a,b]\) rời đi).

Dữ liệu ra

In ra số đoàn khách bị từ chối.

Ví dụ

10 4
A 6
L 2 4
A 5
A 2

1

Nguồn

USACO 2013 January Contest, Gold — Problem 3: Seating

Tác giả đề: Travis Hance, 2012.