Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1
4. Bumêrăng In E-mail
(2 votes)
Người viết: Ngô Minh Đức   
27/03/2008

Bumêran là công cụ đi săn bằng đá hoặc gỗ của thổ dân Úc. Nếu ném một cách thích hợp, bumêran sẽ bay tới đích rồi lượn về tay người ném. Để đáp ứng nhu cầu thể thao rèn luyện kỹ năng sử dụng bumêran, một công ty quyết định chế tạo bumêran bằng nhựa. Mỗi khi được ném với một lực nào đó về phía trước, bumêran sẽ bay theo một quĩ đạo nhất định và không nhất thiết quay trở về điểm ban đầu.

Theo thiết kế, với mỗi bumêran, quĩ đạo bay của mỗi cách ném nó đều có thể mô tả được bởi xâu ký tự nhận được bằng cách xoá bớt một số ký tự của một xâu S gồm không quá 250 ký tự lấy từ tập {‘F’,’R’}, trong đó mỗi ký tự cho biết  bumêran bay qua một khoảng độ dài 1 về hướng nào:
  • F –  bumêran bay về phía trước,
  • R –  bumêran bay ngược trở lại.

Một cách ném gọi là an toàn nếu thoả mãn 2 điều kiện:

  • Điều kiện Bumêran: vị trí bắt đầu và kết thúc của quĩ đạo bay là trùng nhau.
  • Điều kiện an toàn: Nếu vị trí ban đầu xuất hiện trên quĩ đạo bay và quá trình bay còn chưa kết thúc thì chuyển động tiếp theo phải là ‘F’.

Hai cách ném gọi là khác nhau nếu hai xâu mô tả quĩ đạo bay của chúng là khác nhau. Với mỗi bumêran, có thể có nhiều cách ném an toàn khác nhau. Ví dụ, với bumêran có xâu S = ‘FFFRRRRRF’, ta có 3 cách ném an toàn: ‘FR’, ‘FFRR’ và ‘FFFRRR’.

Lưu ý là trong quĩ đạo bay của bumêran vị trí ban đầu có thể xuất hiện nhiều lần.

Yêu cầu: Cho xâu S, hãy xác định số cách ném an toàn khác nhau có thể thực hiện.

Dữ liệu: Vào từ file văn bản BUMERAN.INP chứa xâu S.

Kết quả: Đưa ra file văn bản BUMERAN.OUT một số nguyên – số lượng cách ném an toàn có thể thực hiện.

Ví dụ:

BUMERAN.INP

 

BUMERAN.OUT

FFFRRRRRF

 

3

 

Hạn chế: Có 50% số lượng test với xâu S có độ dài không quá 100.
 
< Trước   Tiếp >