JOI 2011/2012 - Vòng chung kết

Trong khi luyện lập trình để chuẩn bị cho vòng chung kết JOI, bạn nhận ra rằng các bài ở vòng sơ khảo năm nay đều xử lý số và không có bài nào xử lý xâu. Bạn quyết định âm thầm luyện các bài về xâu để vượt lên các đối thủ.

Xem lại các đề JOI trước đây, bạn thấy cần làm quen với những xâu chỉ gồm ba ký tự J, O, I. Bài toán kiểm tra một xâu có chứa xâu con JOI quá dễ, nên bạn nghĩ ra bài toán khó hơn dưới đây.

Xâu \(t\) là xâu con của xâu \(s\) nếu có thể thêm một số ký tự (có thể là \(0\)) vào đầu và cuối \(t\) để thu được \(s\). Nói cách khác, các ký tự của \(t\) phải xuất hiện liên tiếp trong \(s\). Chẳng hạn, JJOOII là xâu con của OJJOOIIOJOI, nhưng JOI không phải là xâu con của JOOI.

Với số nguyên \(k\ge0\), xâu JOI cấp \(k\) là xâu gồm \(k\) ký tự J, tiếp theo là \(k\) ký tự O, rồi \(k\) ký tự I. Ví dụ, JJOOII là xâu JOI cấp \(2\). Xâu JOI cấp \(0\) là xâu rỗng.

Yêu cầu

Cho xâu \(S\) có độ dài \(N\), chỉ gồm các ký tự J, O, I. Hãy tìm số nguyên \(k\) lớn nhất sao cho xâu JOI cấp \(k\) là xâu con của \(S\).

Dữ liệu vào

Đọc từ đầu vào chuẩn một dòng chứa xâu \(S\). Độ dài \(N\) không được cho riêng trong đầu vào.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa số nguyên \(k\) lớn nhất thỏa mãn yêu cầu.

Ràng buộc

• \(1\le N\le1\,000\,000\).
• \(S\) chỉ gồm các ký tự J, O, I.

Phân nhóm

• \(20\%\) số điểm dành cho các dữ liệu thỏa mãn \(N\le100\).

Ví dụ

OJJOOIIOJOI

2

IJJIIJJJ

0

JOIJOIJOIJOIJOI

1

OOJJJJJJJOOOOIIIII

4

Có nhiều lá bài, mỗi lá được ghi một số nguyên từ \(1\) đến \(1000\). Anna và Bruno dùng những lá bài này để chơi trò chơi sau.

Anna có một chồng gồm \(A\) lá bài, còn Bruno có một chồng gồm \(B\) lá bài. Anna được bỏ đi một số lá tùy ý, có thể không bỏ lá nào. Bruno được bỏ đi một số lá ở trên cùng và một số lá ở dưới cùng của chồng bài, mỗi số lượng đều có thể bằng \(0\). Cả hai không được thay đổi thứ tự những lá còn lại.

Nếu hai chồng bài sau khi bỏ giống nhau, điểm của hai người là số lá còn lại trong một chồng. Hai chồng giống nhau khi có cùng số lá \(n\) và, với mọi \(1\le i\le n\), số ghi trên lá thứ \(i\) từ trên xuống của hai chồng bằng nhau.

Ví dụ, các số trên chồng bài của Anna từ trên xuống là \(1,2,3,4,5\), còn chồng của Bruno là \(3,1,4,1\). Anna bỏ các lá mang số \(2,3,5\); Bruno bỏ lá \(3\) trên cùng và lá \(1\) dưới cùng. Hai chồng còn lại đều là \(1,4\), nên hai người được \(2\) điểm. Hình minh họa thao tác này được đặt trong phần giải thích Ví dụ 1.

Yêu cầu

Cho thông tin hai chồng bài, hãy tìm số điểm lớn nhất mà Anna và Bruno có thể đạt được.

Dữ liệu vào

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

• Dòng đầu tiên chứa hai số nguyên \(A,B\).
• Dòng thứ hai chứa \(A\) số nguyên; số thứ \(i\) là số ghi trên lá thứ \(i\) từ trên xuống trong chồng của Anna.
• Dòng thứ ba chứa \(B\) số nguyên; số thứ \(j\) là số ghi trên lá thứ \(j\) từ trên xuống trong chồng của Bruno.

Các số trên cùng một dòng được phân cách bởi dấu cách.

Dữ liệu ra

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

Ràng buộc

• \(1\le A\le5000\).
• \(1\le B\le5000\).
• Số ghi trên mỗi lá bài là số nguyên từ \(1\) đến \(1000\).

Phân nhóm

• \(10\%\) số điểm dành cho các dữ liệu thỏa mãn \(A\le10\) và \(B\le10\).
• \(50\%\) số điểm dành cho các dữ liệu thỏa mãn \(A\le100\) và \(B\le100\).

Ví dụ

5 4
1 2 3 4 5
3 1 4 1

2

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

3

Taro đến lễ hội mùa hè tại đền JOI. Dọc đường đến đền có \(N\) gian hàng chợ đêm, được đánh số từ \(1\) đến \(N\) theo thứ tự. Chơi tại gian hàng \(i\) mang lại mức độ vui thích \(A_i\) và mất \(B_i\) đơn vị thời gian.

Lễ hội còn có màn trình diễn pháo hoa. Quả pháo hoa lớn nhất được bắn vào thời điểm \(S\), và Taro muốn xem nó. Cậu lập kế hoạch từ khi đến lễ hội ở thời điểm \(0\) đến khi lễ hội kết thúc ở thời điểm \(T\).

Taro chọn \(k\) gian hàng, với \(1\le k\le N\), không chọn gian hàng nào hai lần. Gọi số hiệu các gian hàng đã chọn theo thứ tự tăng dần là \(y_1,y_2,\ldots,y_k\). Cậu chọn một thời điểm nguyên \(x_{y_i}\) để đến gian hàng \(y_i\), và chơi ở đó từ thời điểm \(x_{y_i}\) đến thời điểm \(x_{y_i}+B_{y_i}\).

Taro phải chơi theo thứ tự số hiệu gian hàng tăng dần và không thể chơi ở hai gian hàng cùng lúc. Có thể bỏ qua thời gian di chuyển giữa các gian hàng. Sau thời điểm \(T\), cậu không được chơi nữa. Trong lúc chơi, cậu không thể xem pháo hoa; tuy nhiên, nếu thời điểm \(S\) đúng bằng lúc bắt đầu hoặc kết thúc chơi tại một gian hàng thì cậu vẫn xem được pháo hoa.

Như vậy, một kế hoạch hợp lệ phải thỏa mãn:

• \(y_1<y_2<\cdots<y_k\).
• Các thời điểm \(x_{y_1},x_{y_2},\ldots,x_{y_k}\) đều là số nguyên.
• Các khoảng thời gian chơi nằm trong thời gian lễ hội và không chồng lấn:

• Không tồn tại chỉ số \(i\) sao cho \(x_{y_i} < S < x_{y_i}+B_{y_i}\).

Gọi \(M\) là tổng mức độ vui thích của các gian hàng được chọn:

Yêu cầu

Cho thông tin \(N\) gian hàng cùng các thời điểm \(S,T\), hãy tìm giá trị lớn nhất của \(M\) trong một kế hoạch hợp lệ.

Dữ liệu vào

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

• Dòng đầu tiên chứa ba số nguyên \(N,T,S\), lần lượt là số gian hàng, thời điểm kết thúc lễ hội và thời điểm bắn quả pháo hoa lớn nhất.
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(A_i,B_i\) mô tả gian hàng \(i\).

Các số trên cùng một dòng được phân cách bởi dấu cách. Bảo đảm có ít nhất một kế hoạch hợp lệ.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa giá trị lớn nhất của \(M\).

Ràng buộc

• \(1\le N\le3000\).
• \(1\le T\le3000\).
• \(0\le S\le T\).
• \(0\le A_i\le100\,000\) với mọi \(1\le i\le N\).
• \(1\le B_i\le3000\) với mọi \(1\le i\le N\).
• Mọi giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

• \(10\%\) số điểm dành cho các dữ liệu thỏa mãn \(N\le20\).
• \(20\%\) số điểm dành cho các dữ liệu thỏa mãn \(S=0\).

Tổng cộng \(30\%\) số điểm dành cho các dữ liệu thỏa mãn ít nhất một trong hai điều kiện \(N\le20\) hoặc \(S=0\). Không có dữ liệu chấm nào đồng thời thỏa mãn cả hai điều kiện này.

Ví dụ

5 20 14
8 9
2 4
7 13
6 3
5 8

16

JOI đang chơi bằng cách đóng đinh lên một tấm ván. Cậu xếp các đinh thành một tam giác đều, mỗi cạnh có \(N\) chiếc đinh. Hàng thứ \(a\) từ trên xuống (\(1\le a\le N\)) có \(a\) chiếc đinh. Chiếc đinh thứ \(b\) từ trái sang trong hàng đó (\(1\le b\le a\)) được ký hiệu là \((a,b)\).

Một tam giác đều có các đỉnh là những chiếc đinh được gọi là tam giác đều tốt nếu các cạnh của nó song song với các cạnh của tam giác lớn và nó có cùng hướng với tam giác lớn. Cụ thể, ba đỉnh của nó có dạng

trong đó \(1\le a<N\), \(1\le b\le a\) và \(1\le x\le N-a\).

JOI dùng dây chun để bao quanh các tam giác đều tốt. Một chiếc đinh được tính là được bao quanh nếu nằm bên trong hoặc trên biên của ít nhất một tam giác được dây chun bao quanh. Hình 2 minh họa cách đặt dây chun và được đặt trong phần giải thích Ví dụ 1.

Yêu cầu

Cho số đinh trên mỗi cạnh \(N\), số dây chun \(M\) và thông tin các tam giác mà \(M\) dây chun bao quanh. Hãy đếm số chiếc đinh được ít nhất một dây chun bao quanh. Mỗi chiếc đinh chỉ được đếm một lần, kể cả khi thuộc nhiều tam giác.

Dữ liệu vào

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

• Dòng đầu tiên chứa hai số nguyên \(N,M\).
• Trong \(M\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(A_i,B_i,X_i\). Dây chun thứ \(i\) bao quanh tam giác có ba đỉnh \((A_i,B_i)\), \((A_i+X_i,B_i)\) và \((A_i+X_i,B_i+X_i)\).

Các số trên cùng một dòng được phân cách bởi dấu cách.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa số chiếc đinh được ít nhất một dây chun bao quanh.

Ràng buộc

• \(2\le N\le5000\).
• \(1\le M\le500\,000\).
• \(1\le A_i<N\), \(1\le B_i\le A_i\), \(1\le X_i\le N-A_i\) với mọi \(1\le i\le M\).
• Mọi giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

• \(30\%\) số điểm dành cho các dữ liệu thỏa mãn \(M\le10\,000\).

Ví dụ

5 2
2 2 1
2 1 3

12

Vương quốc JOI có \(N\) thành phố được nối với nhau bằng \(M\) con đường hai chiều. Người dân di chuyển giữa các thành phố bằng những con đường này.

Nhiều người dân thích lễ hội, và hiện có \(K\) thành phố đang tổ chức lễ hội rất nhộn nhịp. Tuy nhiên, một số người lại thấy lễ hội ồn ào và muốn tránh đến gần những nơi tổ chức lễ hội nhất có thể. Nhà vua nhờ bạn, một lập trình viên giỏi, viết chương trình trả lời nhanh các câu hỏi về việc di chuyển cho những người này.

Khoảng cách từ một thành phố đến lễ hội là độ dài đường đi ngắn nhất từ thành phố đó đến một thành phố đang tổ chức lễ hội. Khoảng cách đến lễ hội của một lộ trình là giá trị nhỏ nhất trong các khoảng cách đến lễ hội của tất cả thành phố trên lộ trình, bao gồm cả thành phố xuất phát và thành phố đích.

Yêu cầu

Cho thông tin các con đường, các thành phố đang tổ chức lễ hội và \(Q\) truy vấn. Truy vấn thứ \(i\) cho hai thành phố \(S_i,T_i\). Trong tất cả lộ trình từ \(S_i\) đến \(T_i\), hãy tìm khoảng cách đến lễ hội lớn nhất có thể đạt được.

Dữ liệu vào

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

• Dòng đầu tiên chứa bốn số nguyên \(N,M,K,Q\). Các thành phố được đánh số từ \(1\) đến \(N\).
• Trong \(M\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(A_i,B_i,L_i\), cho biết con đường hai chiều thứ \(i\) nối hai thành phố \(A_i,B_i\) và có độ dài \(L_i\).
• Trong \(K\) dòng tiếp theo, dòng thứ \(i\) chứa một số nguyên \(F_i\), cho biết thành phố \(F_i\) đang tổ chức lễ hội.
• Trong \(Q\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(S_i,T_i\), là thành phố xuất phát và thành phố đích của truy vấn thứ \(i\).

Các số trên cùng một dòng được phân cách bởi dấu cách.

Dữ liệu ra

Ghi ra đầu ra chuẩn \(Q\) dòng. Dòng thứ \(i\) chứa một số nguyên là khoảng cách đến lễ hội lớn nhất trong tất cả lộ trình từ \(S_i\) đến \(T_i\).

Ràng buộc

• \(2\le N\le100\,000\).
• \(1\le M\le200\,000\).
• \(1\le K\le N\).
• \(1\le Q\le100\,000\).
• \(1\le A_i,B_i\le N\) và \(1\le L_i\le1000\) với mọi \(1\le i\le M\).
• Không có đường nối một thành phố với chính nó. Giữa mỗi cặp thành phố có nhiều nhất một con đường.
• Có thể đi từ bất kỳ thành phố nào đến bất kỳ thành phố nào khác qua các con đường.
• \(1\le F_i\le N\) với mọi \(1\le i\le K\); các giá trị \(F_i\) đôi một khác nhau.
• \(1\le S_i,T_i\le N\) và \(S_i\ne T_i\) với mọi \(1\le i\le Q\).
• Mọi giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

• \(10\%\) số điểm dành cho các dữ liệu thỏa mãn \(Q=1\).
• \(20\%\) số điểm dành cho các dữ liệu thỏa mãn \(N\le5000\) và \(Q\le5000\).

Tổng cộng \(30\%\) số điểm dành cho các dữ liệu thỏa mãn ít nhất một trong hai điều kiện: \(Q=1\); hoặc đồng thời \(N\le5000\) và \(Q\le5000\). Không có dữ liệu chấm nào đồng thời thỏa mãn cả hai điều kiện này.

Ví dụ

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

7
5
0

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

8
8
11
0
6