JOI 2009 Representative Selection - Ngày 4

Ủy ban Olympic Tin học Nhật Bản có một hệ thống cấp bậc rất nghiêm ngặt. Có đúng một chủ tịch; mỗi người khác có đúng một cấp trên trực tiếp. Mỗi thành viên có một giá trị thể hiện mức độ nhiệt tình của mình.

Ủy ban sắp triển khai một dự án mới. Sự thành công của dự án được cho là phụ thuộc vào tổng mức độ nhiệt tình của những người tham gia, chứ không phụ thuộc vào số người tham gia.

Chủ tịch đã làm \(m\) cuốn sách nhỏ giải thích chi tiết về dự án. Mỗi người tham gia bắt buộc phải đọc sách và bất kỳ ai đọc sách đều phải tham gia dự án.

Ban đầu, chủ tịch giữ cả \(m\) cuốn. Chủ tịch và mỗi người nhận được ít nhất một cuốn sẽ đọc sách trước, rồi chuyển sách cho cấp dưới nếu có. Cấp dưới của một người là những người có cấp trên trực tiếp là người đó. Mỗi cuốn sách có thể được chuyển cho một cấp dưới. Có thể đưa nhiều cuốn cho cùng một cấp dưới, và cũng có thể có cấp dưới không nhận được cuốn nào. Sau khi đọc, một người không cần giữ lại cuốn sách nào cho mình.

Yêu cầu

Cho cấp trên trực tiếp và mức độ nhiệt tình của mỗi người, cùng số sách \(m\), hãy tìm tổng mức độ nhiệt tình lớn nhất của những người tham gia dự án.

Dữ liệu vào

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

• Dòng đầu chứa hai số nguyên \(n,m\), là số thành viên của ủy ban và số cuốn sách.
• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(s_i,a_i\), nghĩa là người \(i\) có cấp trên trực tiếp là người \(s_i\) và mức độ nhiệt tình là \(a_i\). Giá trị \(s_i=0\) cho biết người \(i\) là chủ tịch.

Các số trên cùng một dòng cách nhau bởi dấu cách. Cấp trên luôn có số hiệu nhỏ hơn cấp dưới, và người \(1\) là chủ tịch.

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên là tổng mức độ nhiệt tình lớn nhất của những người tham gia.

Ràng buộc

• \(1\le n\le10\,000\).
• \(1\le m\le1000\).
• \(0\le s_i<i\), \(1\le a_i\le10\,000\) với \(1\le i\le n\).
• Chỉ có một chủ tịch; mọi người khác đều có đúng một cấp trên trực tiếp.
• Giới hạn thời gian: \(2\) giây cho mỗi test.
• Giới hạn bộ nhớ: \(256\) MB.

Phân nhóm

Bài có \(20\) nhóm chấm, mỗi nhóm gồm đúng một test: lần lượt là 01, 02, ..., 20. Mỗi nhóm được \(5\) điểm nếu trả lời đúng, tổng cộng \(100\) điểm.

Các test tương ứng với \(50\%\) tổng số điểm thỏa mãn \(n\le500\) và \(m\le100\).

Ví dụ

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

22

Hiệp hội Đũa Sơn mài Nhật Bản (Japan Ohashi Institute) chuẩn bị những chiếc đũa có thiết kế riêng để quảng bá việc sử dụng đũa trên thế giới. Phần cần tô màu kéo dài \(N\) mm từ một đầu chiếc đũa. Mỗi đoạn dài \(1\) mm đã được chỉ định một màu và không có đoạn nào được để trống. Có tất cả \(52\) màu sơn.

Là một nghệ nhân sơn mài, bạn được yêu cầu tô chiếc đũa đúng theo thiết kế. Vì mỗi lần sơn đều tốn công, bạn muốn hoàn thành với ít thao tác nhất.

Trong một thao tác, bạn chọn một đoạn liên tiếp rồi tô toàn bộ đoạn đó bằng một màu. Những vị trí đã có màu cũng bị đổi sang màu mới khi được tô đè.

Yêu cầu

Hãy tìm số thao tác ít nhất cần thực hiện để tô chiếc đũa đúng theo thiết kế.

Dữ liệu vào

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

• Dòng đầu chứa số nguyên \(N\), là chiều dài phần cần tô, tính bằng mm.
• Dòng thứ hai chứa một xâu gồm \(N\) chữ cái trong A–Z và a–z. Ký tự thứ \(i\) biểu diễn màu của đoạn từ vị trí \((i-1)\) mm đến \(i\) mm tính từ đầu chiếc đũa. Chữ hoa và chữ thường biểu diễn các màu khác nhau.

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên là số thao tác ít nhất.

Ràng buộc

• \(1\le N\le300\).
• Giới hạn thời gian: \(1\) giây cho mỗi test.
• Giới hạn bộ nhớ: \(64\) MB.

Phân nhóm

Bài có \(25\) nhóm chấm, mỗi nhóm \(4\) điểm, tổng cộng \(100\) điểm. Để nhận điểm của một nhóm, chương trình phải trả lời đúng cả hai test trong nhóm. Các mã dưới đây là số hiệu test trong bộ dữ liệu:

• Các test tương ứng với \(20\%\) tổng số điểm thỏa mãn \(N\le20\).
• Các test tương ứng với \(40\%\) tổng số điểm thỏa mãn \(N\le120\).

Các bảo đảm trên có thể bao hàm nhau, không phải các phân nhóm điểm tách biệt để cộng lại.

Ví dụ

6
JOIIOI

4

15
PlovdivBulgaria

12

Hiệp hội Đài thiên văn Nhật Bản (Japan Observatory Institution, viết tắt là JOI) vừa lắp đặt một kính thiên văn hiệu năng cao. Để quảng bá khả năng của kính và nâng cao danh tiếng của hiệp hội, JOI muốn công bố một bức ảnh có càng nhiều ngôi sao đủ sáng càng tốt.

Vũ trụ rất rộng lớn. Nếu chụp một vùng quá rộng, độ sáng của từng ngôi sao sẽ không được thể hiện đầy đủ. Phóng to giúp các ngôi sao hiện lên đủ sáng, nhưng lại làm giảm số sao có thể nằm trong ảnh.

Mỗi ngôi sao \(i\) được mô tả bởi tọa độ \((x_i,y_i)\) và một giá trị \(L_i\). Kính có thể chụp một vùng hình vuông với kích thước tùy ý, có các cạnh song song với trục tọa độ. Nếu cạnh hình vuông dài \(\ell\), ngôi sao \(i\) chỉ được tính là đủ sáng khi \(\ell\le L_i\).

Một ngôi sao được tính vào kết quả khi vừa nằm trong vùng hình vuông, vừa đủ sáng. Sao nằm trên cạnh hình vuông cũng được tính nếu đủ sáng. Một sao ở trong ảnh nhưng không đủ sáng không được tính.

Với hai ngôi sao khác nhau bất kỳ, tọa độ \(x\) của chúng khác nhau, tọa độ \(y\) của chúng khác nhau và giá trị \(L\) của chúng cũng khác nhau.

Yêu cầu

Hãy tìm số ngôi sao đủ sáng lớn nhất có thể xuất hiện trong một bức ảnh.

Dữ liệu vào

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

• Dòng đầu chứa số nguyên \(N\), là số ngôi sao.
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(x_i,y_i,L_i\) cách nhau bởi dấu cách. Giá trị \(L_i\) là độ dài cạnh lớn nhất của vùng hình vuông cho phép ngôi sao \(i\) hiện lên đủ sáng.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa số nguyên là số ngôi sao đủ sáng lớn nhất có thể chụp được.

Ràng buộc

• \(1\le N\le4000\).
• \(0\le x_i,y_i\le10^9\).
• \(1\le L_i\le10^9\).
• Với \(i\ne j\): \(x_i\ne x_j\), \(y_i\ne y_j\) và \(L_i\ne L_j\).
• Giới hạn thời gian: \(3\) giây cho mỗi test.
• Giới hạn bộ nhớ: \(256\) MB.

Phân nhóm

Bài có \(20\) nhóm chấm, mỗi nhóm \(5\) điểm, tổng cộng \(100\) điểm. Để nhận điểm của một nhóm, chương trình phải trả lời đúng tất cả các test trong nhóm. Các mã dưới đây là số hiệu test trong bộ dữ liệu:

Các test có những bảo đảm về điểm sau:

• \(15\%\) tổng số điểm: \(N\le100\).
• \(25\%\) tổng số điểm: \(N\le400\).
• \(35\%\) tổng số điểm: \(N\le700\).
• \(50\%\) tổng số điểm: \(N\le1000\).
• \(20\%\) tổng số điểm: \(x_i,y_i,L_i\le1000\) với mọi \(i\).

Các bảo đảm này có thể chồng lấn; không cộng chúng như những phân nhóm điểm tách biệt.

Ví dụ

4
1 2 6
4 3 3
3 1 4
5 5 2

3

5
11 6 7
12 13 8
15 16 18
2 2 13
3 4 11

2