//
you're reading...
Đề thi cấp tỉnh - Đồng Tháp

Bài tập huấn luyện: Vượt sông

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


HSG 12 THPT – 2015 – Ngày thi: 22/3/2015 – Bài 2


Đề bài


Nhà của bé Hằng Nga nằm ở bên bờ trái của con sông quê, còn nhà ngoại của bé nằm ở bên bờ phải của sông. Con đường dọc bờ sông còn có rất nhiều nhánh sông bên trái và bên phải, có nhánh chảy về bên trái, có nhánh chảy về bên phải, có nhánh chảy cả về bên trái và bên phải.

Yêu cầu: Bạn có được sơ đồ đoạn sông từ nhà bé Hằng Nga đến nhà ngoại của bé, hãy chỉ giúp bé Hằng Nga phương án đi đến nhà ngoại sao cho số lần “vượt sông” là ít nhất.

Dữ liệu vào: Cho từ tệp văn bản VUOTSONG.INP gồm một xâu kí tự độ dài N (N ≤ 106) mô tả bản đồ con sông từ nhà bé Hằng Nga đến nhà ngoại. Kí tự ‘L’ kí hiệu có nhánh sông bên trái, kí tự ‘R’ kí hiệu có nhánh sông bên phải, kí tự ‘B’ kí hiệu có nhánh sông cả bên trái và bên phải.

Dữ liệu ra: Ghi vào tệp văn bản VUOTSONG.OUT một số duy nhất là số lần ít nhất mà bé Hằng Nga phải vượt sông để đến nhà ngoại của bé.

Ví dụ:

2016_12_bai_02

VUOTSONG.INP VUOTSONG.OUT
LLBLRRBRL 5

 

Hạn chế kĩ thuật:

– Có 50% số test tương ứng 50% số điểm của bài có N ≤ 20

– Có 20% số test tương ứng 20% số điểm của bài có N ≤ 250

– Có 30% số test tương ứng 30% số điểm của bài có 250 < N ≤ 106


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 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ả

Danh mục

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

NCT Computer

Flickr Photos

Merle running

Sentinels

Papilio Machaon...

More Photos

Thống kê

  • 136,495 lượt xem

pascalteacher.nct@gmail.com


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

%d bloggers like this: