//
you're reading...
00 - Chủ đề chung

Bài tập huấn luyện: Xếp hàng

[Bộ đề huấn luyện vòng tỉnh Đồng Tháp]


HSG 12 THPT – 2014 – Ngày thi: 29/9/2014 – Bài 1


Đề 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

BGGBG

GBGGB

3

5 2

BGGBG

GGBGB

3

4 1

GGGB

GGGB

0


Hướng dẫn


[]


Chương trình


[]

Advertisements

About pascalteacher

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

Thảo luận

Không có bình luận

Trả lờ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 Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s

Các tác giả

Categories

Tháng Mười Hai 2016
H B T N S B C
« Th11   Th1 »
 1234
567891011
12131415161718
19202122232425
262728293031  

NCT Computer

Flickr Photos

Thống kê

  • 180,806 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: