Tin hoc tre khong chuyen Pascal 1
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (176.15 KB, 3 trang )
<span class='text_page_counter'>(1)</span><div class='page_container' data-page=1>
Hội thi tin học trẻ không chuyên toàn quốc lần thứ IX, 2003
<b>Địa điểm thi: Thành phố Đà nẵng</b>
<b>Đề thi lập trình Bảng C: Trung học phổ thông</b>
<i><b>Thời gian làm bài: 120 phút</b></i>
<b>Tng quan v thi</b>
<b>Bài toán</b> <b>DÃy TF</b> <b>Đánh cờ</b>
<b>Tên file bài làm</b>
DAYTF.??? TICTAC.???<b>Tên file dữ liệu</b>
DAYTF.INP TICTAC.INP<b>Tên file kết quả</b>
DAYTF.OUT TICTAC.OUT<b>Hạn chÕ thêi gian</b>
<b>cho mét test</b>
2 gi©y
3 gi©y
<b>Sè lợng test</b>
10
10
<b>Điểm của một test</b>
4
4
<b>Tổng điểm</b>
<b>40</b>
<b>40</b>
<i><b>Chó ý: </b></i>
<i><b>Dấu ??? trong tên file bài làm phải đợc thay thế bởi đuôi ngầm định của ngơn ngữ</b></i><i><b>lập trình mà em lựa chọn để thực hiện.</b></i>
<i><b> Tên file bài làm, file dữ liệu và file kết quả phải đợc đặt theo đúng yêu cầu</b></i>
<i><b>của đề bài (không đợc đặt đờng dẫn cho các file dữ liệu và file kết quả).</b></i>
<i><b>Đề thi gồm 3 trang. Giám thị khơng cần giải thích gì thêm. Thí sinh khơng s</b></i><i><b>dụng tài liệu trong khi thi.</b></i>
</div>
<span class='text_page_counter'>(2)</span><div class='page_container' data-page=2>
<b>Lập trình thực hiện các công việc sau đây</b>
<b>Bài 1. D y TF</b>· <b> </b> <b> Tên file chơng trình: DAYTF.???</b>
Bờm và Cuội tham gia vào việc phát triển phần mềm tuyển sinh cho trờng Đại học Công nghệ XYZ.
Cuội phát hiện ra bài toán sau đây và thách đố Bờm: “Nếu chỉ quan tâm đến cột giới tính trong danh
<i><b>sách thí sinh dự thi ta thu đợc một dãy ký tự b = b</b></i>1<i>b</i>2<i>...bN chỉ gồm hai chữ cái T (True) và F (False).</i>
<i><b>Hãy tìm dãy con dài nhất gồm các phần tử liên tiếp của dãy ký tự b và có số lợng chữ cái T đúng</b></i>
bằng số lợng chữ cái F”.
<i><b>Yêu cầu: Cho trớc dãy b</b></i>1<i>b</i>2<i>...bN với bi {T, F} (i = 1,2,...,N), hãy tìm một dóy con tho món yờu</i>
cu t ra.
<b>Dữ liệu: Vào từ file văn bản DAYTF.INP:</b>
<i>Dòng đầu tiên chứa số nguyên N (2 N 10000);</i>
<i>Dßng thø i trong N dßng tiÕp theo chøa ký tù bi cđa d·y ký tù b, i = 1, 2,..., N.</i>
<i><b>Kết quả: Ghi ra file văn bản DAYTF.OUT hai số nguyên p, s theo thứ tự là độ dài của dãy con tìm</b></i>
<i>đợc và chỉ số của phần tử đầu tiên của dãy con tìm đợc trong dãy đã cho. Qui ớc nếu p = 0 thì ghi s</i>
= 0.
VÝ dơ:
DAYTF.INP DAYTF.OUT DAYTF.INP DAYTF.OUT
<b>3</b>
<b>T</b>
<b>F</b>
<b>T</b>
<b>2 1</b> <b>2</b>
<b>T</b>
<b>T</b>
<b>0 0</b>
<b>Bài 2. Đánh cờ</b> <b> </b> <b> Tên file chơng trình: TICTAC.???</b>
Trũ chi ỏnh c tic-tac là trị chơi giữa hai đấu thủ, trong đó một người cầm quân trắng, người còn
<i>lại cầm quân đen. Bàn cờ là một bảng hình chữ nhật có M dòng và N cột. Các dòng của bàn cờ</i>
<i>được đánh số từ 1 đến M theo trình tự từ dưới lên trên và các cột được đánh số từ 1 đến N theo trình</i>
tự từ trái qua phải (xem hình vẽ bên dưới). Bàn cờ đặt dựng đứng. Quân cờ là các hình trịn có một
trong hai màu đen, hoặc trắng. Mỗi ô của bàn cờ chứa không quá một quân cờ. Ban đầu bàn cờ
hoàn toàn rỗng. Hai người lần lượt thực hiện nước đi. Người cầm quân trắng đi trước.
<b>Luật chơi như sau:</b>
Một cột gọi là đầy nếu mỗi ơ của nó đều chứa qn cờ. Khi đến lượt đi của mình, người chơi sẽ
chọn một cột chưa đầy và thả một quân cờ vào 1 ô trống của cột đó. Quân cờ sẽ trượt theo cột
<i>được chọn và dừng lại ở ơ trống trên dịng thứ i nếu ơ ở dịng i-1 của cột có qn cờ (i > 1) hoặc</i>
dừng lại ở ơ trên dịng 1 nếu cột đó khơng có qn cờ nào.
Người thắng là người đầu tiên đặt được 4 quân cờ của mình liên tiếp trên một dịng, hoặc một
cột hoặc một trong hai đường chéo (xem hình 1).
Nếu tất cả các cột của bàn cờ đều đầy mà không có người nào thắng, thì ván cờ được coi là hồ.
5
</div>
<span class='text_page_counter'>(3)</span><div class='page_container' data-page=3>
1
1 2 3 4 5
Hình 1. Dịng cột và các đường chéo
<i><b>Yêu cầu: Cho một dãy K nước đi của hai người chơi (được đánh số từ 1 đến K), hãy xác định xem</b></i>
<i>ở nước thứ bao nhiêu sẽ có người thắng hay hồ. Trong trường hợp sau khi đi hết K nước đi, ván cờ</i>
chưa chấm dứt, hãy xác định xem nếu tiếp tục chơi thì tình huống nào trong hai kết cục sau đây là
xảy ra:
i) Ván cờ chắc chắn có kết thúc hồ với mọi cách đi tuỳ ý của hai người chơi;
ii) Tồn tại cách đi của hai đấu thủ dẫn đến thắng lợi của một trong hai người.
<b>Dữ liệu: Vào từ file văn bản TICTAC.INP có nội dung như sau:</b>
<i>Dòng đầu chứa 3 số nguyên dương M, N, K (0 < M, N 50).</i>
<i>Dòng thứ hai chứa K số nguyên dương mỗi số cho biết chỉ số cột ứng với một nước đi.</i>
<b>Kết quả: Ghi ra file văn bản TICTAC.OUT có nội dung như sau:</b>
<i>Dòng đầu chứa 2 số nguyên T và S. Số T cho biết trạng thái của ván cờ: T bằng 0 cho biết</i>
ván cờ hoà, bằng 1 cho biết người cầm quân trắng thắng, bằng 2 nếu người cầm quân đen
<i>thắng. Nếu sau khi thực hiện xong K nước đi, ván cờ chưa chấm dứt, T sẽ bằng -1. Khi T </i>
<i>0, S cho biết số thứ tự của nước đi dẫn đến tình trạng kết thúc ván cờ. </i>
<i>Trong trường hợp T=-1: ghi S=0 để khẳng định kết cục i) và ghi S>0 để khẳng định kết cục</i>
<i>ii). Nếu S>0 thì trên dịng thứ hai ghi tiếp S số mô tả S nước đi dẫn đến thắng lợi của một</i>
trong hai đấu thủ mà chương trình tìm được.
<i>Các số trên cùng một dòng được ghi cách nhau bởi ít nhất một dấu cách</i>
<b>Ví dụ: </b>
TICTAC.INP TICTAC.OUT
<b>4 5 13</b> <b>-1 2</b>
<b>4 3 4 2 4 4 3 2 2 1 3 5 2</b> <b>1 1</b>
<b>Giải thích: Với dãy 13 nước đi: 4 3 4 2 4 4 3 2 2 1 3 5 2, trạng thái bàn cờ sau khi thực hiện các</b>
nước đi được cho trong hình 2.1. Tồn tại cách chơi của hai đấu thủ dẫn đến thắng lợi của một trong
hai người, chẳng hạn, đấu thủ 1 có thể thắng sau 2 nước đi nữa (hình 2.2).
4
<sub></sub>
4 <sub></sub><sub></sub>
3 <sub></sub> <sub></sub> <sub></sub> 3
<sub></sub>
<sub></sub> <sub></sub> <sub></sub>2 <sub></sub>
<sub></sub>
<sub></sub> <sub></sub> 2 <sub></sub><sub></sub>
<sub></sub> <sub></sub>1
<sub> </sub>
<sub></sub><sub></sub>
1<sub> </sub>
<sub></sub><sub></sub>
1 2 3 4 5 1 2 3 4 5
</div>
<!--links-->
