//
you're reading...
Bài tập huấn luyện, Đề ôn luyện thi học kỳ, Đề thi cấp tỉnh - Đồng Tháp

Bài tập huấn luyện: XẾP HÀNG


Đề bài


Trong giờ học thể dục, thầy giáo xếp n học sinh của lớp thành một hàng và vị trí của các học sinh được đánh số từ 1 đến n từ trái sang phải. Ban đầu các học sinh đứng tùy ý trong hàng. Tuy nhiên, để tôn trọng các bạn nữ, thầy muốn các bạn nam không được đứng liền trước bạn nữ nào (đứng liền trước ở đây được hiểu rằng vị trí của các bạn nam là i và vị trí của các bạn nữ là i+1). Để thực hiện quy định này, thầy bắt đầu đi từ đầu hàng đến cuối hàng, khi gặp bạn nam nào đó đứng liền trước một bạn nữ, thầy sẽ yêu cầu bạn nam này đổi chỗ cho bạn nữ rồi đi tiếp đến các bạn sau đó. Chú ý rằng trong một lượt sắp xếp, thầy chỉ đi theo một chiều và mỗi bạn nam sẽ chỉ được đổi chỗ một lần. Tất nhiên là chỉ đi theo một chiều và mỗi bạn nam chỉ được đổi chỗ một lần. Tất nhiên là chỉ lượt sắp xếp như vậy thì vẫn có thể có nhiều vị trí mà bạn nam đứng trước nữ xuất hiện thêm nên cần phải làm đi làm lại thao tác sắp xếp này nhiều lần.

Yêu cầu: Cho hai số nguyên dương n,t với 0<n,t≤50 và một dãy kí tự G và B, trong đó G là kí hiệu bạn nữ và B là kí hiệu bạn nam thể hiện vị trí các học sinh của lớp ban đầu. Hỏi sau bao lần thay đổi thứ t thì vị trí của các học sinh thế nào và sau bao nhiêu lần thao tác thì thầy giáo sẽ hoàn tất việc sắp xếp này?

Dữ liệu vào: Trong file XEPHANG.INP gồm có: Dòng thứ nhất chứa 2 số nguyên dương n và t cách nhau bởi một khoảng trắng, dòng thứ hai gồm một dãy n kí tự ‘G’ và ‘B’ biểu thị vị trí đứng của các học sinh trong hàng (từ trái qua phải tương ứng với chỉ số vị trí tăng dần).

Kết quả: In ra file XEPHANG.OUT hai dòng: Dòng thứ nhất gồm một dãy n kí tự ‘G’ và ‘B’ biểu thị vị trí đứng của các học sinh sau khi thầy giáo sắp xếp lại lần thứ t, dòng thứ hai là một số nguyên cho biết số lần thầy giáo cần sắp xếp.

Chú ý rằng số t có thể lớn hơn số lần thầy giáo cần sắp xếp.

Ví dụ:

XEPHANG.INP XEPHANG.OUT
5 1 GBGGB
BGGBG 3
5 2 GGBGB
BGGBG 3
4 1 GGGB
GGGB 0

Hướng dẫn


[Chương trình mẫu]

Bổ sung giải thuật tìm kiếm chuỗi

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Tháng Mười Một 2016
M T W T F S S
« Oct   Dec »
 123456
78910111213
14151617181920
21222324252627
282930  

NCT Computer

Flickr Photos

A bellezza di a natura (C☺rsica)

Southern White-faced Owl D75_5752.jpg

2016 Lake Yamanaka winter Fuji

More Photos

Thống kê

  • 78,768 lượt xem

%d bloggers like this: