USACO 2023 - US Open - Hạng Đồng

Bessie và Elsie đang âm mưu lật đổ bác John! Đôi bạn lên kế hoạch thông qua \(N\) \((1 \le N \le 2 \times 10^5)\) tin nhắn. Cuộc trò chuyện của hai cô bò có thể biểu diễn dưới dạng một xâu \(S\) chỉ gồm hai kí tự 'B' hoặc 'E' nghĩa là tin nhắn thứ \(i\) được gửi bởi Bessie hoặc Elsie theo thứ tự.

Tuy nhiên, nông dân John đã nghe về kế hoạch của họ và nhắm tới việc ngăn chặn cuộc trò chuyện của hai cô bò. Do vậy, một số kí tự trong xâu \(S\) là \(F\), nghĩa là bác John đã xáo trộn tin nhắn này và người gửi là vô danh.

"Độ phấn khích" của cuộc trò chuyện không bị xáo trộn là số lần một bạn bò gửi hai lần, hay nói cách khác là số lần xuất hiện của xâu con "BB" hoặc "EE" trong xâu \(S\). Bạn muốn tìm "độ phấn khích" của cuộc trò chuyện gốc, nhưng không thể biết được tin nhắn bác John xáo trộn là của Bessie hay Elsie. Trong tất cả các trường hợp có thể xảy ra, hãy cho biết tất cả "độ phấn khích" khác nhau có thể đạt được của xâu \(S\).

Input

• Dòng đầu tiên là số \(N\).
• Dòng tiếp theo là xâu \(S\).

Output

• Dòng đầu tiên là \(K\) nghĩa là số lượng "độ phấn khích" khác nhau có thể đạt được. \(K\) dòng tiếp theo là giá trị của các "độ phấn khích" này theo thứ tự tăng dần.

Scoring

• Subtask \(1\): \(N \le 10\).
• Subtask \(2\): Không có thêm ràng buộc.

4
BEEF

2
1
2

9
FEBFEBFEB

2
2
3

10
BFFFFFEBFE

3
2
4
6

Nông dân John rất thích thú trong việc tương tác với các chú bò của mình, vì vậy bác ta quyết định học ngôn ngữ Moo (loại ngôn ngữ chỉ bò mới hiểu).

Ngôn ngữ Moo có đôi chút giống giống với tiếng Anh nhưng tối giản hơn. Chỉ có \(4\) loại từ: danh từ, ngoại động từ, nội động từ và liên từ. Mỗi \(2\) từ liên tiếp phải được ngăn cách bằng một khoảng trắng. Và cũng chỉ có \(2\) loại dấu câu: dấu phẩy và dấu chấm câu. Khi câu có dấu chấm hoặc dấu phẩy thì các dấu này được đặt ngay đằng sau một từ theo sau là một dấu khoảng trắng nếu có một từ mới xuất hiện đằng sau (bạn có thể xem cách tác giả viết trình bày đề bài để hiểu nhé <333).

Một câu đơn trong ngôn ngữ này tuân thủ một trong những dạng sau:

• Dạng \(1\): danh từ + ngoại động từ.
• Dạng \(2\): danh từ + nội động từ + một số danh từ. Cụ thể hơn, cần có ít nhất \(1\) danh từ theo sau nội động từ, và mỗi danh từ được ngăn cách nhau bằng một dấu phẩy.

Hai câu đơn có thể hợp lại với nhau để trở thành một câu ghép nếu có một liên từ nối giữa chúng. Câu ghép thu được sẽ không thể kết hợp thêm với một câu đơn hoặc một câu ghép khác. Tất cả câu đơn (hoặc câu ghép) cần được kết thúc bằng một dấu chấm câu.

Nông dân John có ngân hàng từ gồm \(N\) từ, \(C\) dấu phẩy, \(P\) dấu chấm câu \((1 \le P, C \le N \le 10^3)\). Bác chỉ có thể sử dụng từ và dấu câu không quá số lần xuất hiện của chúng trong ngân hàng từ của mình. Hãy giúp bác John xuất ra một dãy các câu chứa nhiều từ nhất có thể.

Mỗi input sẽ bao gồm \(T\) \((1 \le T \le 100)\) test độc lập.

Input

Dòng đầu tiên chứa số \(T\) là số lượng test. Mỗi test sẽ được xác định như sau:

• Dòng đầu tiên gồm \(3\) số nguyên \(N\), \(C\), và \(P\) theo thứ tự.
• \(N\) dòng tiếp theo, mỗi dòng gồm \(2\) xâu kí tự. Xâu đầu tiên là từ mà nông dân John có thể dùng (gồm ít nhất \(1\) và nhiều nhất \(10\) chữ cái in thường). Xâu thứ hai sẽ là một trong các xâu sau: "noun" (danh từ), "transitive-verb" (ngoại động từ), "intransitive-verb" (nội động từ), hoặc "conjunction" (liên từ) cho biết loại từ của từ này. Một từ có thể xuất hiện nhiều lần trong ngân hàng từ của bác John, nhưng mọi lần xuất hiện đều sẽ cùng loại từ.

Output

• Dòng đầu tiên in ra số lượng từ tối đa được dùng
• Dòng thứ hai in ra dãy bất kì các câu văn tạo được với số lượng từ sử dụng là tối đa. Mọi câu văn hợp lệ đều được chấp nhận.

Note: Chương trình chấm rất nhạy với khoảng trắng, hãy chắc chắn rằng không in ra bất kì khoảng trắng thừa nào, nhất là ở cuối mỗi dòng.

Scoring

• Subtask \(1\): \(N \le 10\).
• Subtask \(2\): \(N \le 100\).
• Subtask \(3\): \(N \le 1000\).
• Subtask \(4\): Không có ngoại động từ.
• Subtask \(5\): Không có nội động từ.
• Subtask \(6\): Không có liên từ.

3
1 1 1
bessie noun
10 5 4
bessie noun
taught transitive-verb
flew intransitive-verb
elsie noun
farmer noun
john noun
and conjunction
and conjunction
nhoj noun
mooed intransitive-verb
24 5 4
but conjunction
bessie noun
taught transitive-verb
flew intransitive-verb
elsie noun
farmer noun
john noun
and conjunction
and conjunction
nhoj noun
mooed intransitive-verb
bob noun
impressed transitive-verb
cow noun
impressed transitive-verb
leaped intransitive-verb
elsie noun
bella noun
buttercup noun
pushed transitive-verb
mooed intransitive-verb
envy noun
john noun
nhoj noun

0

9
nhoj mooed. farmer taught elsie, bessie and john flew.
23
nhoj mooed. nhoj impressed john, farmer, elsie, bessie and cow impressed bob. bella pushed elsie and buttercup flew. envy mooed but john leaped.

Note: giới hạn thời gian cho bài này là 4s, gấp đôi so với thông thường

Để chào mừng dịp lập xuân, \(N\) \((1 \le N \le 2 \times 10^5)\) chú bò của nông dân John đã sáng tạo ra điệu nhảy chào mừng mới, chúng đứng thành một vòng tròn và thay đổi thứ tự của mình theo một cách có thể đoán trước.

Cụ thể hơn, có \(N\) vị trí xung quanh vòng tròn đánh số từ \(0\) đến \(N - 1\), vị trí \(0\) ở bên phải vị trí \(N - 1\). Mỗi vị trí có \(1\) chú bò. Mỗi chú bò cũng được đánh số lần lượt từ \(0\) đến \(N - 1\). Ban đầu, chú bò \(i\) đứng ở vị trí \(i\). Bạn được cho một dãy \(K\) vị trí \(0 = A_1 < A_2 < \ldots < A_K < N - 1\) được gọi là "hoạt động", nghĩa là những chú bò ở vị trí này sẽ di chuyển ở lượt tiếp theo \((1 \le K \le N)\).

Mỗi phút trong điệu nhảy, hai sự việc xảy ra. Đầu tiên, các chú bò trong các vị trí hoạt động sẽ xoay vòng: chú bò ở vị trí \(A_1\) sẽ di chuyển đến vị trí \(A_2\), chú bò ở vị trí \(A_2\) sẽ di chuyển đến vị trí \(A_3\), và cứ tiếp tục như vậy, chú bò ở vị trí \(A_K\) sẽ di chuyển đến vị trí \(A_1\). \(K\) bước di chuyển này sẽ được thực hiện đồng thời, cho nên sau khi hoàn thành việc xoay vòng, mỗi vị trí vẫn chứa đúng \(1\) chú bò. Sau đó, các vị trí này sẽ tự động dịch lên \(1\) đơn vị: \(A_1\) sẽ thành \(A_1 + 1\), \(A_2\) sẽ thành \(A_2 + 1\), và cứ như thế cho đến \(A_N\) (nếu tồn tại \(A_i = N - 1\) thì sau sự việc này, \(A_i\) sẽ quay trở về \(0\)).

Tính toán thứ tự của các chú bò sau \(T\) phút \((1 \le T \le 10^9)\) của điệu nhảy.

Input

• Dòng đầu gồm \(3\) số nguyên \(N\), \(K\) và \(T\).
• Dòng thứ hai gồm \(K\) số nguyên \(A_1, A_2, \ldots, A_K\) thoả mãn \(A_1 = 0\) và \(A_i < A_{i + 1}\) \(\forall i\) \((1 \le i \le K - 1)\).

Output

• In ra \(N\) số là thứ tự của các chú bò sau \(T\) phút, bắt đầu với vị trí của chú bò \(0\).

Scoring

• Subtask \(1\): \(N \le 1000, T \le 10000\).
• Subtask \(2\): Không có thêm ràng buộc.

5 3 4
0 2 3

1 2 3 4 0