JOI 2015 Final Camp - Ngày 3

IOI 2015 được tổ chức tại Kazakhstan. Từ "Kazakh" đôi khi được viết bằng bảng chữ cái là QAZAQ, và QAZAQ là một chuỗi đối xứng. Sau khi biết điều này, JOI-kun bắt đầu yêu thích các chuỗi đối xứng và muốn tạo một chuỗi như vậy từ một chuỗi mà cậu nhìn thấy.

Chuỗi JOI-kun tìm thấy có độ dài \(N\). Mỗi ký tự được biểu diễn bởi một số nguyên từ \(1\) đến \(C\), do đó chuỗi được biểu diễn bằng dãy

Với \(1 \le i \le j \le N\), dãy \((S_i,S_{i+1},\ldots,S_j)\) được gọi là đoạn \((i,j)\). Đoạn \((i,j)\) là đối xứng nếu nó bằng dãy đảo ngược của chính nó, tức là

JOI-kun thực hiện các bước sau để tạo một đoạn đối xứng:

1. Chọn một đoạn của \(S\), gọi đoạn đó là \(T\).
2. Sắp xếp \(T\) theo thứ tự tăng dần, thu được \(T'\).
3. Thay đoạn \(T\) trong \(S\) bằng \(T'\), thu được dãy \(S'\). Cụ thể, nếu chọn đoạn \((i,j)\) và dãy đã sắp xếp là \(T'_i \le T'_{i+1} \le \cdots \le T'_j\), thì

1. Tìm một đoạn đối xứng trong \(S'\).

JOI-kun muốn tạo được một đoạn đối xứng dài nhất có thể.

Yêu cầu

Cho dãy \(S\) biểu diễn chuỗi JOI-kun tìm thấy. Hãy tìm độ dài lớn nhất của một đoạn đối xứng có thể tạo được bằng thao tác trên.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên \(N,C\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa số nguyên \(S_i\).

Dữ liệu ra

In ra một số nguyên là độ dài lớn nhất cần tìm.

Ràng buộc

• \(1 \le N \le 3\,000\).
• \(1 \le C \le 3\,000\).
• \(1 \le S_i \le C\) với mọi \(1 \le i \le N\).

Phân nhóm

• Nhóm 1 (10 điểm): \(N \le 50\), \(C \le 50\)
• Nhóm 2 (90 điểm): Không có ràng buộc bổ sung

Ví dụ

12 26
26
17
17
17
1
26
1
17
19
20
1
14

8

    Sắp xếp đoạn $(4,8)$ theo thứ tự tăng dần thu được

    Đoạn $(1,8)$ của $S'$ là đối xứng và có độ dài $8$. Không thể tạo đoạn đối xứng dài hơn.

4 3
1
2
3
2

3

Anna thường chơi bài cùng người bạn Bruno. Sau khi chán các trò chơi dành cho hai người, cô nghĩ ra một trò chơi bài có thể chơi một mình.

Ban đầu có \(N\) lá bài nhiều màu được xếp thành một hàng. Mỗi lá bài có một số nguyên được viết trên đó và có một giá trị. Màu sắc cũng được biểu diễn bằng số nguyên. Lá bài thứ \(i\) tính từ đầu hàng có màu \(C_i\), số \(A_i\) và giá trị \(V_i\).

Ban đầu chồng bài của Anna rỗng. Cô lặp lại thao tác sau:

• Chọn lá bài thứ nhất hoặc thứ ba tính từ đầu hàng. Nếu chồng bài đang không rỗng, cô chỉ được chọn một lá bài có màu hoặc số ghi trên bài trùng với lá trên cùng của chồng bài. Lấy lá đã chọn khỏi hàng và đặt nó lên trên cùng chồng bài.

Trò chơi kết thúc khi không còn lá bài nào có thể chọn. Điểm của Anna là tổng giá trị các lá trong chồng bài khi trò chơi kết thúc.

Yêu cầu

Cho thông tin các lá bài lúc bắt đầu. Hãy tìm số điểm lớn nhất Anna có thể đạt được.

Dữ liệu vào

• Dòng đầu chứa số nguyên \(N\).
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(C_i,A_i,V_i\), lần lượt là màu, số ghi trên bài và giá trị của lá bài thứ \(i\).

Dữ liệu ra

In ra một số nguyên là số điểm lớn nhất Anna có thể đạt được.

Ràng buộc

• \(1 \le N \le 500\).
• \(1 \le C_i \le 500\) với mọi \(1 \le i \le N\).
• \(1 \le A_i \le 500\) với mọi \(1 \le i \le N\).
• \(1 \le V_i \le 1\,000\,000\) với mọi \(1 \le i \le N\).

Phân nhóm

• Nhóm 1 (10 điểm): \(N \le 20\)
• Nhóm 2 (15 điểm): \(N \le 50\)
• Nhóm 3 (75 điểm): Không có ràng buộc bổ sung

Ví dụ

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

15

8
11 5 31
2 8 19
2 9 2
11 8 45
4 8 22
4 2 23
6 9 58
6 2 5

160

Anna sống tại quần đảo IOI và mời người bạn Bruno đến chơi. Quần đảo gồm \(N\) đảo, được đánh số từ \(1\) đến \(N\), và \(N-1\) cây cầu, được đánh số từ \(0\) đến \(N-2\). Cầu \(i\) nối hai chiều đảo \(A[i]\) và đảo \(B[i]\). Có thể đi giữa hai đảo bất kỳ qua các cây cầu.

Nhà Anna nằm trên đảo \(T\), nhưng Bruno không biết số hiệu đảo này. Để giúp Bruno, Anna sẽ cắm trên mỗi đảo đúng một lá cờ ghi một số nguyên. Anna không biết Bruno sẽ cập bến ở đảo nào.

Bruno cập bến tại đảo \(S\). Anh chỉ được biết:

• số hiệu \(S\) và số ghi trên lá cờ tại đảo \(S\);
• số hiệu của tất cả các đảo nối trực tiếp với \(S\) và số ghi trên cờ tại các đảo đó.

Bruno phải đi từ \(S\) đến \(T\) theo đường dùng ít cầu nhất. Dựa chỉ trên thông tin được cung cấp, Bruno phải xác định \(S\) có phải đảo \(T\) hay không; nếu không, anh phải chọn đúng đảo tiếp theo trên đường đi ngắn nhất duy nhất đến \(T\).

Yêu cầu

Cài đặt chiến lược đặt cờ của Anna và chiến lược chọn hành động tiếp theo của Bruno.

Giao diện nộp bài

Nộp một tệp C++ có chứa hai hàm sau:

#include "navigation.h"

void Anna(int K, int N, int T, int A[], int B[]);
void Bruno(int K, int S, int F, int L, int P[], int Q[]);

Tệp navigation.h cung cấp hai hàm hệ thống:

void Flag(int I, int V);
void Answer(int X);

Hệ thống liên kết cùng mã nguồn thí sinh thành hai tiến trình độc lập: một tiến trình chỉ gọi Anna, tiến trình còn lại chỉ gọi Bruno. Hai tiến trình không chia sẻ biến toàn cục hay trạng thái bộ nhớ.

Hàm Anna

void Anna(int K, int N, int T, int A[], int B[]);

Hàm được gọi đúng một lần:

• K là số hiệu nhóm chấm.
• N là số đảo.
• T là đảo có nhà Anna.
• A và B là hai mảng dài \(N-1\); cầu \(i\) nối A[i] với B[i], với \(0 \le i \le N-2\).

Trong Anna, phải gọi:

void Flag(int I, int V);

để đặt cờ. Các lời gọi phải thỏa mãn:

• \(1 \le I \le N\); nếu không, kết quả là Wrong Answer [1].
• Không được gọi hai lần với cùng I; nếu không, kết quả là Wrong Answer [2].
• \(0 \le V \le N\); nếu không, kết quả là Wrong Answer [3].
• Phải gọi đúng \(N\) lần, tức đúng một lần cho mỗi đảo; nếu không, kết quả là Wrong Answer [4].

Hàm Bruno

void Bruno(int K, int S, int F, int L, int P[], int Q[]);

Hàm được gọi đúng một lần, trong một tiến trình mới, sau khi hệ thống hoàn tất việc chạy Anna:

• K là số hiệu nhóm chấm.
• S là đảo Bruno cập bến.
• F là số ghi trên cờ tại đảo \(S\).
• L là số đảo nối trực tiếp với \(S\).
• P là mảng dài \(L\) chứa số hiệu các đảo kề \(S\).
• Q là mảng dài \(L\); Q[j] là số ghi trên cờ ở đảo P[j], với \(0 \le j < L\).

Trong Bruno, phải gọi đúng một lần:

void Answer(int X);

• Nếu \(S=T\), phải trả lời X = S.
• Nếu \(S \ne T\), X phải là đảo kề \(S\) nằm trên đường đi ngắn nhất duy nhất từ \(S\) đến \(T\).
• X phải bằng S hoặc là một phần tử của P; nếu không, kết quả là Wrong Answer [5].
• Gọi Answer từ hai lần trở lên cho kết quả Wrong Answer [6].
• Không gọi Answer cho kết quả Wrong Answer [7].
• Nếu \(S=T\) nhưng X != T, kết quả là Wrong Answer [8].
• Nếu \(S \ne T\) nhưng chọn sai đảo tiếp theo, kết quả là Wrong Answer [9].

Bài nộp không được đọc hoặc ghi dữ liệu qua đầu vào chuẩn, đầu ra chuẩn hay bất kỳ tệp nào.

Ràng buộc

• \(2 \le N \le 100\,000\).
• \(1 \le S,T \le N\).
• \(1 \le A[i],B[i] \le N\) với mọi \(0 \le i \le N-2\).
• \(1 \le K \le 4\).
• Có thể đi giữa mọi cặp đảo bằng các cây cầu.

Phân nhóm

• Nhóm 1 (10 điểm): \(K=1\)
• Nhóm 2 (15 điểm): \(K=2\); mọi giá trị V truyền cho Flag phải thuộc \([0,2]\)
• Nhóm 3 (20 điểm): \(K=3\); mọi V thuộc \(\{0,1\}\); không có đảo nào có đúng hai đảo kề; \(S \ne T\)
• Nhóm 4 (55 điểm): \(K=4\); mọi V thuộc \(\{0,1\}\)

Ví dụ

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

Accepted : V_max = 1

Anna(1, 5, 2, {1, 3, 3, 4}, {3, 2, 4, 5})
Flag(1, 1)
Flag(2, 1)
Flag(3, 0)
Flag(4, 0)
Flag(5, 1)

Bruno(1, 3, 0, 3, {2, 1, 4}, {1, 1, 0})
Answer(2)