<span class='text_page_counter'>(1)</span><div class='page_container' data-page=1>

<b>HẢI PHÒNG</b>



<b>HỘI TIN HỌC VIỆT NAM</b>



<b>OLYMPIC TIN HỌC SINH VIÊN LẦN THỨ XIII,</b>

<b>2004</b>

<b>Khối thi: Đồng đội không chuyên</b>

<i><b>Thời gian làm bài: 180 phút</b></i>

<b>Ngày thi: 8-5-2004</b>

<b>Nơi thi: Đại học Hàng hải</b>

<b>Tên bài</b> <b>Tên file </b>

<b>chương trình</b> <b>Tên file dữ liệu</b> <b>Tên filekết quả</b> <b>gian cho mỗi testHạn chế thời</b> <b>Tổng điểm cho bài</b>
<b>AGAME</b> <b>AGAME.???</b> <b>AGAME.INP</b> <b>AGAME.OUT</b> <b>1 giây</b> <b>20</b>
<b>Dầu khí</b> <b>PETRO.???</b> <b>PETRO.INP</b> <b>PETRO.OUT</b> <b>1 giây</b> <b>40</b>
<b>Cờ lật</b> <b>REVERSY.???</b> <b>REVERSY.INP</b> <b>REVERSY.OUT</b> <b>1 giây</b> <b>40</b>

<b>Dấu ??? được thay thế bởi đuôi ngầm định của ngôn ngữ được sử dụng để cài đặt</b>
<b>chương trinh.</b>

<i><b>Hãy lập trình giải các bài sau đây</b></i><b>:</b>

<b>Bài 1: AGAME </b> <i>Tên chương trình: AGAME.???</i>

Sơ đồ để các robot di chuyển trong cuộc thi AGAME là một
bảng hình chữ nhật được chia thành M x N ô vuông đơn vị.
Các dòng của bảng được đánh số từ trên xuống dưới, còn các
cột được đánh số từ trái qua phải và đều bắt đầu từ 1. Mục
đích của cuộc chơi là tìm ra robot có tốc độ nhanh nhất di
chuyển từ (1,1) di chuyển qua các ô của bảng theo hình xoắn
ốc theo chiều kim đồng hồ, sao cho mỗi ơ đi qua đúng một
lần (Xem hình 1). Như vậy trong quá trình di chuyển, robot rẽ
phải tại K ô nào đó. Tại những ô robot cần rẽ phải chương
trình điều khiển robot phải cho robot giảm tốc độ để tránh cho robot không bị lật.

<b>Yêu cầu: </b>

a. Với kích thước của bảng cho trước, hãy tìm số lần rẽ phải của robot,
b. Với một số q cho trước, hãy đưa ra toạ độ của ô rẽ phải thứ q.
<b>Dữ liệu vào</b> từ file văn bản AGAME.INP:

 Dòng đầu chứa hai số M và N khoảng trắng (2 ≤ M, N, 1000),
 Dòng thứ hai chứa số q (qK).

<b>Kết quả </b>ghi vào file AGAME.OUT trong đó:

 Dịng đầu ghi ra số nguyên K (kết quả câu <i>a</i>),

 Dòng thứ hai ghi ra hai số nguyên x và y tương ứng là chỉ số dòng và chỉ số cột của ơ

rẽ phải thứ q (kết quả câu <i>b</i>).
Ví d :ụ

AGAME.INP AGAME.OUT

<b>4 5</b>

<b>5</b> <b>62 4</b>

<b>Bài 2: DẦU KHÍ</b>

</div>
<span class='text_page_counter'>(2)</span><div class='page_container' data-page=2>

Thềm lục địa Việt Nam là một khu vực có nhiều tiềm năng tìm thấy dầu mỏ. Sau một thời
gian nghiên cứu, phân tích số liệu, các nhà khoa học đã xác định được một khu vực thềm lục
địa hình chữ nhật. Khu vực này được chia thành một lưới NxM ơ. Để thuận tiện,ta đánh số
các dịng trên lưới theo trình tự từ trên xuống dưới (từ 1 đến N), và các cột từ trái qua phải (từ
1 đến M). Ơ ở góc trên trái là ơ (1,1), ơ góc dưới phải là ơ (N,M). Từ số liệu thăm dò, ta biết
số liệu về trữ lượng dầu dự báo tại mỗi ô trên lưới. Như vậy, vùng thềm lục địa đang xét có
thể mơ tả như một bảng A kích thước NxM. Giá trị của phần tử trên dịng i cột j của A cho
biết số liệu về trữ lượng dầu dự báo tại ô lưới tương ứng.

Để đảm bảo hiệu quả khai thác, người ta quyết định chia khu thềm lục địa thành 4 lơ hình chữ
nhật và cho tiến hành đấu thầu độc lập từng lô một. Việc chia lô được thực hiện theo cách cắt
khu vực bằng một đường dọc và một đường ngang trên cạnh các ô lưới. Giá trị của mỗi lô
tương ứng với tổng số trữ lượng dầu dự báo tại các ô thuộc lô này.

<b>Yêu cầu:</b> Chỉ ra phương án chia khu thềm lục địa sao cho chênh lệch T về trữ lượng dự báo ở
lơ có trữ lượng lớn nhất và lơ có trữ lượng dự báo nhỏ nhất là tối thiểu. Nếu có nhiều phương
án, chỉ cần đưa ra một. Biết các phần tử của bảng A là các số ngun khơng âm có giá trị
khơng vượt q 1000.

<b>Dữ liệu vào</b> từ file văn bản PETRO.INP trong đó:

 Dòng đầu chứa hai số N và M (2 ≤ N, M ≤ 125)

 Dòng thứ i trong N dòng tiếp theo chứa dòng i của bảng A.
 Các số trên cùng một dòng cách nhau bởi một khoảng trắng.

<b>Kết quả </b>ghi ra file văn bản PETRO.OUT với 3 số T, R và C tương ứng là độ chênh lệch ít
nhất, vị trí dòng, cột cần chọn để chia khu thềm lục địa. Với cách chia này, lô trên trái sẽ gồm
các ô (i,j) với 1 ≤ i ≤ R, 1 ≤ j ≤ C, , lô trên phải sẽ gồm các ô (i,j) với 1 ≤ i ≤ R, C+1 ≤ j ≤ M,
lô dưới trái sẽ gồm các ô (i,j) với R+1 ≤ i ≤ N, 1 ≤ j ≤ C, lô dưới phải sẽ gồm các ô (i,j) với
R+1 ≤ i ≤ N, C+1 ≤ j ≤ M. Xem hình 2.

Ví dụ:

<b>Sơ đồ khu thềm lục địa</b> PETRO.INP PETRO.OUT

1 2 3 <b>4 3</b> <b>2 2 2</b>

1 4 2 8 <b>4 2 8</b>

2 2 3 4 <b>2 3 4</b>

3 3 4 5 <b>3 4 5</b>

4 1 5 6 <b>1 5 6</b>

1
2

1 2 C

R

M

N

</div>
<span class='text_page_counter'>(3)</span><div class='page_container' data-page=3>

<b>Bài 3: CỜ LẬT</b> <i>Tên chương trình</i>: REVERSY.???
Cờ lật được chơi trên bàn cờ NxN (3≤N≤100), các cột được đánh số từ 1 tới N từ trái sang
phải, các hàng được đánh số từ 1 đến N từ trên xuống dưới. Quân cờ có 2 mặt: đen và trắng.
Hai người lần lượt đặt quân vào ô trống tuỳ ý, một người đặt mặt trắng, người kia - mặt đen.
Mục tiêu của trò chơi là lật được càng nhiều quân của đối phương càng tốt. Một dãy quân
cùng màu liên tiếp nhau theo cột, hàng hoặc đường chéo bị kẹp ở hai đầu quân khác màu thì
sẽ bị lật, trở thành quân màu khác. Ở hình 3 là trạng thái các quân cờ trước và sau khi đặt
qn đen vào vị trí dịng 5 cột 2.

<b>u cầu:</b> Cho trạng thái bàn cờ. Hãy xác định một vị trí đặt qn đen để có thể lật được
nhiều quân trắng nhất nhờ nước đi này.

<b>Dữ liệu vào</b> từ file văn bản REVERSY.INP trong đó dịng đầu chứa số N. Dòng thứ i trong N
dòng tiếp theo chứa 1 xâu gồm N ký tự cho biết trạng thái dòng thứ i trên bàn cờ: <b>B</b> là quân
đen, <b>W</b> là quân trắng và <b>.</b> là ô trống.

<b>Kết quả</b> ghi ra file văn bản REVERSY.OUT trên một dòng gồm 3 số i, j và k với i là chỉ số
dòng, j là chỉ số cột cần đặt quân đen và k là số lượng qn lật được nhờ nước đi đó.

<i><b>Ví dụ</b></i>:

REVERSY.INP REVERSY.OUT

<b>8</b>

<b>BBW...</b>
<b>.WW.B...</b>
<b>.W.W.... </b>
<b>.WWWW...</b>
<b>..WBW...</b>
<b>...</b>
<b>...</b>
<b>...</b>

<b>5 2 6</b>

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

</div>
<span class='text_page_counter'>(4)</span><div class='page_container' data-page=4></div>

<!--links-->