JOI 2015 Final Camp - Ngày 1

Ban đầu nội dung tệp là xâu \(S\). Có \(N\) thao tác. Thao tác \(i\) sao chép đoạn từ vị trí \(A_i\) đến ngay trước vị trí \(B_i\), rồi chèn bản sao tại vị trí \(C_i\). Vị trí \(x\) là khe ngay sau \(x\) ký tự đầu tiên, nên vị trí 0 ở đầu xâu và vị trí bằng độ dài ở cuối xâu. Các chỉ số trong thao tác đều được hiểu trên xâu trước thao tác.

Nếu sau khi chèn, độ dài vượt quá \(M\), các ký tự bên phải bị xóa cho đến khi còn đúng \(M\) ký tự. Hãy tìm \(K\) ký tự đầu sau tất cả thao tác.

Dữ liệu vào

• Dòng 1: \(K,M\).
• Dòng 2: xâu ban đầu \(S\).
• Dòng 3: \(N\).
• \(N\) dòng tiếp: \(A_i,B_i,C_i\).

Dữ liệu ra

In \(K\) ký tự đầu của xâu cuối cùng.

Ràng buộc

• \(1\le K\le200,\quad1\le M\le10^9,\quad1\le N\le200\,000\).

\(S\) chỉ gồm chữ thường a đến z, và

• \(K\le |S|\le\min(M,200\,000)\).

Nếu \(L_i\) là độ dài ngay trước thao tác \(i\) thì

• \(0\le A_i<B_i\le L_i,\qquad0\le C_i\le L_i\).

Phân nhóm

• Nhóm 1 (10 điểm): \(M,N\le2000\).
• Nhóm 2 (90 điểm): không có ràng buộc bổ sung.

Ví dụ

2 18
copypaste
4
3 6 8
1 5 2
4 12 1
17 18 0

ac

6 100
jjooii
3
5 6 2
4 6 1
1 2 3

joioji

Với số nguyên \(k\ge0\), một dãy JOI cấp \(k\) được định nghĩa như sau:

• Cấp 0 là một ký tự J, O hoặc I.
• Dãy cấp \(k+1\) dài \(4^{k+1}\): \(4^k\) ký tự đầu đều là J, \(4^k\) ký tự tiếp đều là O, \(4^k\) ký tự tiếp đều là I, và \(4^k\) ký tự cuối tạo thành một dãy JOI cấp \(k\).

Có \(4^K\) ký tự J, O, I viết trên một vòng tròn. Được phép thay đổi một số ký tự. Hãy tìm số thay đổi ít nhất để khi chọn một điểm bắt đầu thích hợp và đọc một vòng theo chiều kim đồng hồ, ta được một dãy JOI cấp \(K\).

Dữ liệu vào

Dòng đầu chứa \(K\). Dòng sau là xâu dài \(4^K\), thu được khi đọc vòng tròn từ một điểm cố định theo chiều kim đồng hồ.

Dữ liệu ra

In số ký tự ít nhất phải thay đổi.

Ràng buộc

Phân nhóm

• Nhóm 1 (30 điểm): \(K\le5\).
• Nhóm 2 (70 điểm): không có ràng buộc bổ sung.

Ví dụ

1
IJOI

0

2
JJOIJJOJOIOJOOOI

7

Khu vườn có \(N\) ô từ tây sang đông; cây IOI \(i\) cao \(H_i\), bán được \(P_i\) yên nếu ra quả. Vào mùa xuân, JOI có thể nhổ cây \(i\) với chi phí \(C_i\); cây bị nhổ sẽ chết.

Một cây còn lại ra quả khi và chỉ khi không có cây còn lại cao hơn nó ở phía tây, hoặc không có cây còn lại cao hơn nó ở phía đông. Lợi nhuận bằng tổng giá bán cây ra quả trừ tổng chi phí nhổ. Hãy tối đa hóa lợi nhuận.

Dữ liệu vào

Dòng đầu chứa \(N\). Mỗi trong \(N\) dòng sau chứa \(H_i,P_i,C_i\).

Dữ liệu ra

In lợi nhuận lớn nhất.

Ràng buộc

Phân nhóm

• Nhóm 1 (10 điểm): \(N\le20\).
• Nhóm 2 (10 điểm): \(N\le300\).
• Nhóm 3 (10 điểm): \(N\le5000\).
• Nhóm 4 (50 điểm): mọi \(H_i\) đôi một khác nhau.
• Nhóm 5 (20 điểm): không có ràng buộc bổ sung.

Ví dụ

7
22 60 30
46 40 30
36 100 50
11 140 120
38 120 20
24 90 60
53 50 20

320

5
18 150 180
18 380 250
18 140 170
17 180 900
14 150 520

1000

8
52 156 59
15 166 185
16 122 115
24 161 154
44 252 678
32 225 557
44 155 254
59 57 253

854

Có các thẻ ghi I ở mặt trước và O ở mặt sau. Ban đầu xếp lần lượt \(A\) thẻ ngửa, \(B\) thẻ úp, \(C\) thẻ ngửa, \(D\) thẻ úp, rồi \(E\) thẻ ngửa.

Có \(N\) loại thao tác. Loại \(i\) lật mọi thẻ từ vị trí \(L_i\) đến \(R_i\), tốn \(R_i-L_i+1\) giây. Phải thực hiện ít nhất một thao tác; được chọn thứ tự tùy ý và dùng một loại nhiều lần. Hãy tìm thời gian nhỏ nhất để mọi thẻ đều ngửa, hoặc xác định rằng không thể.

Dữ liệu vào

• Dòng 1: \(A,B,C,D,E\).
• Dòng 2: \(N\).
• \(N\) dòng tiếp: \(L_i,R_i\).

Dữ liệu ra

In thời gian nhỏ nhất, hoặc -1 nếu không thể thành công.

Ràng buộc

Phân nhóm

• Nhóm 1 (15 điểm): \(N\le10\).
• Nhóm 2 (50 điểm): \(A,B,C,D,E\le50\).
• Nhóm 3 (35 điểm): không có ràng buộc bổ sung.

Ví dụ

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

12

1 1 1 1 1
1
1 1

-1