BCPENNY spoj PTIT – Penny Game

Nguồn đề bài: http://www.spoj.com/PTIT/problems/BCPENNY/

1. Đề bài BCPENNY spoj PTIT

Penny Game là một trò chơi đơn giản cho hai người chơi. Trò chơi này yêu cầu mỗi người chơi chọn một dãy duy nhất ba mặt đồng xu ví dụ như HEADS TAILS HEADS (HTH). Các đồng xu sẽ được tung liên tiếp cho cho đến khi xuất hiện một trong hai dãy đã được chọn lúc đầu. Người chơi nào chọn được dãy xuất hiện đầu tiên sẽ là người thắng cuộc.

Bạn hãy viết một chương trình đọc một chuỗi 40 giá trị tung đồng xu liên tiếp và xác định mỗi một chuỗi ba mặt đồng xu xuất hiện bao nhiêu lần. Hiển nhiên, ta sẽ có 8 chuỗi 3 mặt đồng xu lần lượt là: TTT, TTH, THT, THH, HTT, HTH, HHT và HHH. Các chuỗi này có thể xếp chồng lên nhau. Ví dụ ta có 40 xu liên tiếp ở mặt HEADS thì sẽ có 38 chuỗi HHH xuất hiện

Dữ liệu

Dòng đầu tiên ghi số 1 ≤ P ≤ 1000 là tổng số bộ test. Mỗi bộ test gồm 2 dòng:

  • Dòng đầu tiên chứa số N là thứ tự bộ test.
  • Dòng thứ hai là dãy 40 ký tự mô tả chuỗi giá trị tung đồng xu trong đó chỉ gồm hai ký tự là H và T. Không có bất cứ dấu cách nào trong các dòng dữ liệu vào.

Kết quả

Ghi ra màn hình một dòng cho mỗi bộ test trong số đầu tiên là thứ tự bộ test. Tiếp theo là 8 số cho biết số lần xuất hiện của mỗi chuỗi 3 đồng xu theo thứ tự ở trên. Mỗi số viết cách nhau một dấu cách. Sẽ có 9 dấu cách trong mỗi dòng kết quả.

Example

Input:
4
1
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
2
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
3
HHTTTHHTTTHTHHTHHTTHTTTHHHTHTTHTTHTTTHTH
4
HTHTHHHTHHHTHTHHHHTTTHTTTTTHHTTTTHTHHHHT


Output:
1 0 0 0 0 0 0 0 38

2 38 0 0 0 0 0 0 0

3 4 7 6 4 7 4 5 1
4 6 3 4 5 3 6 5 6

2. Code tham khảo BCPENNY spoj PTIT

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *