JOI 2014 Final Camp - Ngày 3

JOIOJI là chú của cậu bé JOI. Ông rất thích tên của mình vì tên ấy chứa đúng hai chữ cái J, hai chữ cái O và hai chữ cái I.

Gần đây, JOIOJI vừa có một người con. Ông muốn đặt cho con một cái tên giống tên mình: chỉ gồm các chữ cái J, O, I, với số lần xuất hiện của ba chữ cái bằng nhau.

JOIOJI có một cuộn giấy được truyền lại qua nhiều đời trong gia đình. Trên cuộn giấy có một bài thơ. Bài thơ là một xâu độ dài \(N\), chỉ gồm ba loại chữ cái J, O, I. JOIOJI định chọn xâu con liên tiếp dài nhất trong bài thơ mà số lần xuất hiện của J, O, I bằng nhau để đặt tên cho con mình.

Yêu cầu

Cho thông tin về bài thơ trên cuộn giấy của JOIOJI. Hãy viết chương trình tìm độ dài lớn nhất của một xâu con liên tiếp trong bài thơ mà số lần xuất hiện của J, O, I bằng nhau.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa số nguyên \(N\), là độ dài bài thơ trên cuộn giấy của JOIOJI.
• Dòng thứ hai chứa xâu \(S\) có độ dài \(N\), biểu diễn bài thơ trên cuộn giấy của JOIOJI. Mỗi ký tự của \(S\) là J, O hoặc I.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên: độ dài lớn nhất của một xâu con liên tiếp trong bài thơ mà số lần xuất hiện của J, O, I bằng nhau. Nếu không tồn tại xâu con như vậy, in ra \(0\).

Ràng buộc

Tất cả dữ liệu vào đều thỏa mãn:

• \(1 \le N \le 200\,000\).

Phân nhóm

• Subtask 1 (5 điểm): \(N \le 200\).
• Subtask 2 (15 điểm): \(N \le 4\,000\).
• Subtask 3 (80 điểm): Không có ràng buộc bổ sung.

Ví dụ

10
JOIIJOJOOI

6

8
IOIIJIIO

0

20
JJIOOIJIJOIOJIOJOOIJ

15

Trên một vùng đất hoang rộng lớn ở làng JOI có \(N\) con bù nhìn. Mỗi năm vài lần, dân làng lại quây quần quanh những con bù nhìn để tổ chức lễ hội. Một hôm, trưởng làng JOI nói rằng mình đã nghe được lời phán truyền của những con bù nhìn và lập kế hoạch tạo một thửa ruộng trên vùng đất hoang. Theo lời phán truyền, thửa ruộng phải thỏa mãn các điều kiện sau:

• Có hình chữ nhật, mỗi cạnh nằm theo hướng đông–tây hoặc nam–bắc.
• Có một con bù nhìn đứng ở đỉnh phía tây nam và một con bù nhìn đứng ở đỉnh phía đông bắc.
• Không có con bù nhìn nào đứng trong phần bên trong của thửa ruộng (không tính đường biên).

Tất nhiên, không được phép di chuyển những con bù nhìn quý giá này. Có bao nhiêu vị trí đặt thửa ruộng thỏa mãn lời phán truyền?

Yêu cầu

Cho vị trí của các con bù nhìn. Hãy viết chương trình tìm số vị trí đặt thửa ruộng thỏa mãn lời phán truyền.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa số nguyên \(N\), cho biết có \(N\) con bù nhìn.
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo (\(1 \le i \le N\)) chứa hai số nguyên \(X_i\), \(Y_i\), cách nhau bởi một dấu cách. Vùng đất hoang của làng JOI được biểu diễn trên mặt phẳng tọa độ \(xy\), với chiều dương của trục \(x\) hướng về phía đông và chiều dương của trục \(y\) hướng về phía bắc. Con bù nhìn thứ \(i\) đứng tại tọa độ \((X_i, Y_i)\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa số vị trí đặt thửa ruộng thỏa mãn lời phán truyền.

Ràng buộc

Tất cả dữ liệu vào đều thỏa mãn:

• \(1 \le N \le 200\,000\).
• \(0 \le X_i \le 1\,000\,000\,000\) với mọi \(1 \le i \le N\).
• \(0 \le Y_i \le 1\,000\,000\,000\) với mọi \(1 \le i \le N\).
• Các giá trị \(X_i\) (\(1 \le i \le N\)) đôi một khác nhau.
• Các giá trị \(Y_i\) (\(1 \le i \le N\)) đôi một khác nhau.

Phân nhóm

• Subtask 1 (5 điểm): \(N \le 400\).
• Subtask 2 (10 điểm): \(N \le 5\,000\).
• Subtask 3 (85 điểm): Không có ràng buộc bổ sung.

Ví dụ

4
0 0
2 2
3 4
4 3

3

10
2 1
3 0
6 3
10 2
16 4
0 8
8 12
11 14
14 11
18 10

15

Bạn có biết công ty Just Odd Inventions không? Công việc của công ty này là tạo ra “những phát minh kỳ quặc” (just odd inventions). Trong bài này, ta gọi tắt là công ty JOI.

Trong một phòng thí nghiệm của công ty JOI có một mạch điện phức tạp. Mạch điện gồm \(N\) nút và \(M\) điện trở dài, mảnh. Các nút được đánh số từ \(1\) đến \(N\). Mỗi nút có thể được đặt ở một trong hai trạng thái: “điện áp cao” hoặc “điện áp thấp”. Mỗi điện trở nối hai nút và có dòng điện chạy qua khi một trong hai nút ở trạng thái “điện áp cao”, còn nút kia ở trạng thái “điện áp thấp”. Không có dòng điện chạy qua điện trở nối hai nút cùng ở trạng thái “điện áp cao” hoặc cùng ở trạng thái “điện áp thấp”.

Một ngày nọ, để bảo trì mạch điện này, công ty JOI quyết định chọn một điện trở và đặt điện áp cho từng nút sao cho chỉ điện trở được chọn không có dòng điện chạy qua, còn \(M - 1\) điện trở còn lại đều có dòng điện chạy qua. Có bao nhiêu điện trở có thể được chọn làm điện trở không có dòng điện chạy qua để thỏa mãn điều kiện này?

Công ty JOI đang dùng mạch điện kỳ quặc này để tạo ra phát minh gì là bí mật tuyệt đối ngay cả trong nội bộ công ty; ngoài giám đốc ra, không ai biết được.

Yêu cầu

Cho thông tin về mạch điện. Hãy viết chương trình tìm số điện trở có thể được chọn làm điện trở không có dòng điện chạy qua khi bảo trì.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa hai số nguyên \(N\), \(M\), cách nhau bởi một dấu cách, cho biết mạch điện có \(N\) nút và \(M\) điện trở.
• Dòng thứ \(i\) trong \(M\) dòng tiếp theo (\(1 \le i \le M\)) chứa hai số nguyên \(A_i\), \(B_i\), cách nhau bởi một dấu cách, với \(1 \le A_i \le N\), \(1 \le B_i \le N\) và \(A_i \ne B_i\). Điện trở thứ \(i\) nối nút \(A_i\) với nút \(B_i\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa số điện trở có thể được chọn làm điện trở không có dòng điện chạy qua khi bảo trì.

Ràng buộc

Tất cả dữ liệu vào đều thỏa mãn:

• \(2 \le N \le 100\,000\).
• \(1 \le M \le 200\,000\).

Phân nhóm

• Subtask 1 (10 điểm): \(N \le 1\,000\) và \(M \le 2\,000\).
• Subtask 2 (10 điểm): Từ bất kỳ nút nào cũng có thể đến bất kỳ nút nào khác bằng cách đi qua một số điện trở nối các nút; đồng thời, \(M = N\).
• Subtask 3 (35 điểm): Từ bất kỳ nút nào cũng có thể đến bất kỳ nút nào khác bằng cách đi qua một số điện trở nối các nút; đồng thời, \(M \le N + 100\).
• Subtask 4 (45 điểm): Không có ràng buộc bổ sung.

Ví dụ

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

1

4 4
1 2
2 3
3 2
4 3

2

13 16
1 6
2 6
3 1
3 2
4 7
4 7
5 9
6 5
8 2
8 13
9 11
10 3
11 10
11 12
12 8
13 6

3