USACO 2015 - Tháng 2 - Hạng Đồng

Anh và Tiên là một đôi bạn thân. Nhân ngày sinh nhật của Tiên, Anh quyết định sẽ tặng cô bạn thân một món quà bất ngờ. Từ một nguồn tin thân cận, Anh biết rằng Tiên rất thích học tiếng Anh và các xâu kí tự đẹp, do đó Anh dự định sẽ mua tặng Tiên xâu kí tự mà cô bạn thích. Không may, sau khi mua xong Anh mới biết rằng Tiên cũng không thích một vài xâu kí tự xấu. Không muốn làm bạn mình buồn, Anh sẽ tạo ra một xâu kí tự mới từ xâu cũ mà không có các xâu kí tự xấu đó. Để làm được điều này, Anh sẽ làm như sau:

Anh đang có một xâu kí tự độ dài \(S\). Anh muốn xóa sự xuất hiện xâu con \(T\) trong \(S\). Để làm điều này, Anh sẽ tìm lần xuất hiện đầu tiên của \(T\) và xóa nó khỏi xâu \(S\), sau đó gộp 2 phần còn lại vào với nhau. Anh sẽ làm như thế cho đến khi trong xâu \(S\) không còn sự xuất hiện của xâu \(T\) nữa. Lưu ý rằng việc xóa một lần xuất hiện có thể tạo ra một lần xuất hiện mới của xâu \(T\) mà trước đó không tồn tại.

Anh không biết rằng liệu xâu \(S\) cuối cùng sau khi thực hiện các thao tác có đủ đẹp để tặng Tiên không. Nếu xâu \(S\) đó không ưng ý thì Anh sẽ mua một xâu khác và thực hiện, thay vì bỏ thời gian ra để thực hiện với xâu cũ. Bạn hãy giúp Anh xác định xâu \(S\) cuối cùng sau khi thực hiện các thao tác là gì nhé.

Input:

• Dòng đầu tiên chứa xâu kí tự \(S\) \((1 \leq |S| \leq 10^6)\)
• Dòng tiếp theo chứa xâu kí tự \(T\) \((1 \leq |T| \leq |S|)\).
• Các kí tự trong xâu \(S\) và \(T\) là các kí tự thường (từ \('a'\) đến \('z'\))

Output:

In ra xâu \(S\) cuối cùng sau khi thực hiện thao tác. Dữ liệu đảm bảo rằng xâu \(S\) cuối cùng không rỗng.

Example

anhnnhihiandtien
nhi

anhandtien

Bò Bessie tình cờ bắt gặp một dòng chữ kỳ lạ được khắc trên một tảng đá lớn giữa cánh đồng gặm cỏ yêu thích của cô. Dòng chữ dường như được viết bằng một ngôn ngữ cổ bí ẩn, sử dụng bảng chữ cái chỉ gồm ba ký tự C, O và W. Dù không thể giải mã nội dung, Bessie rất thích việc ba ký tự C, O và W theo đúng thứ tự tạo thành từ yêu thích của mình, và cô tự hỏi COW xuất hiện bao nhiêu lần trong dòng chữ.

Bessie không bận tâm nếu có các ký tự khác xen giữa C, O và W, miễn là chúng xuất hiện theo đúng thứ tự. Cô cũng không bận tâm nếu những lần xuất hiện khác nhau của COW dùng chung một số ký tự. Chẳng hạn, COW xuất hiện một lần trong CWOW, hai lần trong CCOW và tám lần trong CCOOWW.

Cho nội dung dòng chữ, hãy giúp Bessie đếm số lần COW xuất hiện.

Dữ liệu vào

Tệp cow.in:

Dòng đầu tiên chứa một số nguyên duy nhất \(N \leq 10^5\). Dòng thứ hai chứa một xâu gồm \(N\) ký tự, mỗi ký tự là C, O hoặc W.

Dữ liệu ra

Tệp cow.out:

In số lần COW xuất hiện dưới dạng một dãy con, không nhất thiết liên tiếp, của xâu đầu vào.

Lưu ý rằng đáp án có thể rất lớn, vì vậy hãy sử dụng số nguyên 64 bit (long long trong C++, long trong Java) để tính toán.

Ví dụ

6
COOWWW

6

Nguồn

USACO 2015 February Contest, Bronze — COW

Tác giả bài: Ben Cousins và Brian Dean, 2015.

Giống như con người thích chơi nhảy lò cò, những con bò của Nông dân John đã sáng tạo ra một biến thể của trò chơi này dành riêng cho mình. Vì người chơi là những con vật vụng về nặng gần một tấn, trò nhảy lò cò của bò hầu như luôn kết thúc trong thảm họa, nhưng đáng ngạc nhiên là điều đó vẫn không ngăn đàn bò cố gắng chơi trò này gần như mỗi buổi chiều.

Trò chơi diễn ra trên một lưới \(R \times C\) (\(2 \leq R \leq 15\), \(2 \leq C \leq 15\)), trong đó mỗi ô được tô màu đỏ hoặc xanh dương. Những con bò bắt đầu ở ô trên cùng bên trái và di chuyển đến ô dưới cùng bên phải bằng một dãy các bước nhảy. Một bước nhảy hợp lệ khi và chỉ khi:

1. Ô đích có màu khác với ô hiện tại.

2. Ô đích nằm dưới ô hiện tại ít nhất một hàng.

3. Ô đích nằm bên phải ô hiện tại ít nhất một cột.

Hãy giúp đàn bò tính số dãy bước nhảy hợp lệ khác nhau có thể đưa chúng từ ô trên cùng bên trái đến ô dưới cùng bên phải.

Dữ liệu vào

Tệp hopscotch.in:

Dòng đầu tiên chứa hai số nguyên \(R\) và \(C\). Mỗi dòng trong \(R\) dòng tiếp theo chứa \(C\) ký tự. Mỗi ký tự là R hoặc B, lần lượt biểu thị một ô màu đỏ hoặc màu xanh dương.

Dữ liệu ra

Tệp hopscotch.out:

In số cách khác nhau để nhảy từ ô trên cùng bên trái đến ô dưới cùng bên phải.

Ví dụ

4 4
RRRR
RRBR
RBBR
RRRR

3

Nguồn

USACO 2015 February Contest, Bronze — Cow Hopscotch (Bronze)

Tác giả bài: Nick Wu, 2015.