JOIG 2026 - Chung kết - Cuộc thi 1

Tại chợ JOI có \(K\) loại macaron. Một hộp gồm \(N\) chiếc được xếp thành một hàng; chiếc thứ \(i\) có loại \(A_i\).

Bitaro muốn phủ một tấm che lên nhiều nhất một đoạn liên tiếp để che các chiếc macaron trong đoạn đó. Nếu phủ từ vị trí \(l\) đến vị trí \(r\) (\(1\le l\le r\le N\)), độ dài tấm che là \(r-l+1\).

Bibako chỉ lấy macaron khi cả \(K\) loại đều còn nhìn thấy. Bitaro muốn ngăn Bibako lấy hộp bằng một tấm che ngắn nhất. Hãy tìm độ dài nhỏ nhất phải che. Nếu ngay từ đầu đã có ít nhất một loại không xuất hiện, không cần che gì cả.

Dữ liệu vào

Dòng đầu gồm hai số nguyên \(N,K\). Dòng thứ hai gồm \(N\) số nguyên \(A_1,A_2,\ldots,A_N\).

Dữ liệu ra

In độ dài nhỏ nhất của tấm che. Nếu không cần che, in \(0\).

Ràng buộc

• \(1\le K\le N\le500000\).
• \(1\le A_i\le K\).
• Mọi giá trị đầu vào đều là số nguyên.

Phân nhóm

1. \(20\) điểm: \(N\le100\).
2. \(30\) điểm: \(K\le100\).
3. \(50\) điểm: không có ràng buộc thêm.

Ví dụ

7 3
1 3 2 3 1 2 3

4

7 4
1 3 4 4 1 3 1

0

Nguồn

JOIG 2025/2026 - Chung kết, Cuộc thi 1, bài Macaron.

Tài liệu gốc của Japanese Committee for IOI được phát hành theo giấy phép CC BY-SA 4.0.

Trường JOIG có \(N\) lớp, được đánh số từ \(1\) đến \(N\). Ngay trước nội dung cuối của hội thao, lớp \(i\) có \(A_i\) điểm. Ở nội dung cuối, tất cả \(N\) lớp đều tham gia và nhận các hạng khác nhau từ \(1\) đến \(N\). Lớp đứng hạng \(j\) được cộng \(N-j+1\) điểm.

Sau đó, hạng chung cuộc được xác định theo điểm giảm dần; nếu bằng điểm thì lớp có số nhỏ hơn đứng trước. Với mọi kết quả có thể có của nội dung cuối, hãy tính số lượng hạng chung cuộc khác nhau mà mỗi lớp có thể đạt được.

Dữ liệu vào

Dòng đầu chứa \(N\). Dòng thứ hai chứa \(N\) số nguyên \(A_1,A_2,\ldots,A_N\).

Dữ liệu ra

In \(N\) số nguyên trên một dòng, cách nhau bởi dấu cách. Số thứ \(i\) là số hạng chung cuộc khác nhau mà lớp \(i\) có thể đạt được.

Ràng buộc

• \(1\le N\le1000000\).
• \(1\le A_i\le10^9\).
• Mọi giá trị đầu vào đều là số nguyên.

Phân nhóm

1. \(12\) điểm: \(N\le9\).
2. \(27\) điểm: \(N\le300\).
3. \(21\) điểm: \(N\le5000\).
4. \(29\) điểm: \(N\le200000\).
5. \(11\) điểm: không có ràng buộc thêm.

Ví dụ

4
5 2 3 6

3 2 3 3

3
1000000000 1 1

1 2 2

7
11 10 17 10 15 7 11

7 6 3 6 5 4 6

Nguồn

JOIG 2025/2026 - Chung kết, Cuộc thi 1, bài Sports Festival.

Tài liệu gốc của Japanese Committee for IOI được phát hành theo giấy phép CC BY-SA 4.0.

JOI-kun mua \(N\) chiếc bánh, được đánh số từ \(1\) đến \(N\). Bánh \(i\) có kích thước \(A_i\). Kế hoạch thứ \(i\) là đặt lên bánh \(i\) một quả dâu có độ ngọt \(V_i\).

Hãy chọn thực hiện không hoặc nhiều kế hoạch sao cho với mọi hai bánh khác nhau đã được đặt dâu:

• tổng kích thước của chúng không bằng \(S\);
• hiệu tuyệt đối giữa kích thước của chúng không bằng \(D\).

Tìm tổng độ ngọt lớn nhất có thể. Nếu không chọn kế hoạch nào, tổng độ ngọt bằng \(0\).

Dữ liệu vào

Dòng đầu gồm \(N,S,D\). Dòng thứ hai gồm \(A_1,A_2,\ldots,A_N\). Dòng thứ ba gồm \(V_1,V_2,\ldots,V_N\).

Dữ liệu ra

In tổng độ ngọt lớn nhất có thể.

Ràng buộc

• \(1\le N\le200000\).
• \(1\le S,D,A_i,V_i\le10^9\).
• Mọi giá trị đầu vào đều là số nguyên.

Phân nhóm

1. \(7\) điểm: \(N\le20\).
2. \(14\) điểm: \(S\le40\), \(D\le20\), \(A_i\le20\).
3. \(18\) điểm: \(S=1\).
4. \(30\) điểm: \(D=1\) và \(S\) lẻ.
5. \(15\) điểm: \(D=1\).
6. \(16\) điểm: không có ràng buộc thêm.

Ví dụ

5 8 3
3 4 5 6 7
10 6 7 5 4

18

3 1 3
4 7 10
3 10 8

11

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

25

Nguồn

JOIG 2025/2026 - Chung kết, Cuộc thi 1, bài Cake 4.

Tài liệu gốc của Japanese Committee for IOI được phát hành theo giấy phép CC BY-SA 4.0.