phần 7 : đề bài
kho tin học :khotinhoc.com
Bài 39/2000 - Ô chữ
(Dành cho học
sinh THCS và THPT)
Trò chơi ô chữ
thông dụng 30 năm trước của trẻ em gồm một khung ô chữ kích thước 5x5 chứa 24
hình vương nhỏ kích thước như nhau. Trên mặt mỗi hình vuông nhỏ có in một chữ
cái trong bảng chữ cái. Vì chỉ có 24 hình vuông trong ô chữ nên trong ô chữ còn
thừa ra một ô trống, có kích thước đúng bằng kích thước các hình vuông. Một
hình vuông có thể đẩy trượt vào ô trống đó nếu nó nằm ngay sát bên trái, bên
phải, bên trên hay bên dưới ô trống. Mục tiêu của trò chơi là trượt các hình
vuông vào ô trống sao cho cuối cùng các chữ cái trong ô chữ được xếp theo đúng
thứ tự của chúng trong bảng chữ cái. Hình sau đây minh hoạ một ô chữ với cấu
hình ban đầu và cấu hình của nó sau 6 nước đi sau:
1.Trượt hình
vuông phía trên ô trống.
2.Trượt hình
vuông bên phải ô trống.
3.Trượt hình
vuông bên phải ô trống.
4.Trượt hình
vuông phía dưới ô trống.
5.Trượt hình
vuông phía dưới ô trống.
6.Trượt hình
vuông bên trái ô trống.
|
TT |
RR |
GG |
SS |
JJ |
|
XX |
OO |
KK |
LL |
II |
|
MM |
DD |
VV |
BB |
NN |
|
WW |
PP |
|
AA |
EE |
|
UU |
QQ |
HH |
CC |
FF |
|
T |
R |
G |
S |
J |
|
X |
D |
O |
K |
I |
|
M |
|
V |
L |
N |
|
W |
P |
A |
B |
E |
|
U |
Q |
H |
C |
F |
|
Cấu hình ban đầu của ô chữ
Bạn hãy viết một
chương trình của bạn chứa cấu hình ban đầu của ô chữ cùng các nước đi để vẽ ra
ô chữ kết quả.
Input
Đầu
vào của chương trình của bạn chứa cấu hình ban đầu của một ô chữ và một dẫy các
nước đi trong ô chữ đó.
Năm dòng đầu tiên mô tả cấu hình ban đầu của
ô chữ, mỗi dòng tương ứng với một hàng của ô chữ và chứa đúng 5 ký tự tương ứng
với 5 hình vuông của ô chữ trên hàng đó. Ô trống được diễn tả bằng một dấu
cách.
Các dòng tiếp theo sau là dẫy các nước đi.
Dãy các nước đi được ghi bằng dãy các chữ A,B,R và L để thể hiện hình vuông nào
được trượt vào ô trống. A thể hiện hình vuông phía trên ô trống được trượt vào
ô trống, tương ứng: B-phía dưới, R-bên phải, L-bên trái. Có thể có những nước đi
không hợp cách, ngay cả khi nó được biểu thị bằng những chữ cái trên. Nếu xuất
hiện một nước đi không hợp cách thì ô chữ coi như không có cấu hình kết quả.
Dãy các nước đi có thể chiếm một số dòng, nhưng nó sẽ được xem là kết thúc ngay
khi gặp một số 0.
Out put
Nếu
ô chữ không có cấu hình kết quả thì thông báo 'This puzzle has no final
configuration.'; ngược lại thì hiển thị cấu hình ô chữ kết quả. Định dạng mỗi
dòng kết quả bằng cách đặt một dấu cách vào giữa hai kí tự kế tiếp nhau. Ô
trống cũng được sử lý như vậy. Ví dụ nếu ô trống nằm bên trong hàng thì nó được
xuất hiện dưới dạng 3 dấu cách: một để ngăn cách nó với kí tự bên trái, một để
thể hiện chính ô trống đó, còn một để ngăn cách nó với kí tự bên phải.
Chú ý: Input mẫu đầu tiên tương ứng với ô chữ
được minh hoạ trong ví dụ trên.
Sample Input 1
TRGSJ
XDOKI
M VLN
WPABE
UQHCF
ARRBBL0
Sample Output 1
T
R G S J
X O K
L I
M D V B N
W P
A E
U Q H C
F
Sample Input 2
AB C DE
F G H I J
KLMNO
PQRS
TUVWX
AAA
LLLL0
Sample Output 2
A B C D
F G H I E
K L M N J
P Q R S O
T U V W X
Sample Input 3
ABCDE
FGHIJ
KLMNO
PQRS
TUVWX
AAAAABBRRRLL0
Sample Output 3
This puzzle has
no final configuration.
Bài 40/2000 - Máy định vị
Radio
Một
con tàu được trang bị ăng-ten định hướng có thể xác định vị trí hiện thời của
mình nhờ các lần đọc đèn hiệu địa phương. Mỗi đèn hiệu được đặt ở một vị trí đã
biết và phát ra một tín hiệu đơn nhất. Mỗi khi bắt được tín hiệu, tàu liền quay
ăng-ten của mình cho đến khi đạt được tín hiệu cực đại. Điều đó cho phép xác định
được phương vị tương đối của đèn hiệu. Cho biết dữ liệu của lần đọc trước (thời
gian, phương vị tương đối, vị trí của đèn), một lần đọc mới đủ để xác định vị
trí hiện thời của tàu. Bạn phải viết một chương trình xác định vị trí hiện thời
của tàu từ hai lần đọc đèn hiệu.
Vị
trí của các đèn hiệu và các con tàu được cho trong hệ toạ độ vuông góc, trục Ox
hướng về phía đông, còn Oy hướng về phía bắc. Hướng đi của con tàu được đo bằng
độ, theo chiều kim đồng hồ tính từ hướng bắc. Như vậy, hướng bắc sẽ là 00,
hướng đông là 900, hướng nam là 1800 và hướng tây là 2700.
Phương vị tương đối của đèn hiệu cũng được đo bằng độ, tương đối với hướng đi
của tàu và theo chiều kim đồng hồ. ăng ten không thể chỉ ra đèn hiệu nằm ở
hướng nào trên phương vị. Như vậy, một phương vị 900 có nghĩa là đèn
hiệu có thể nằm ở hướng 900 hoặc 2700.
Input
Dòng đầu tiên
của input là một số nguyên chỉ số lượng các đèn hiệu (nhiều nhất là 30). Mỗi
dòng tiếp theo cho một đèn hiệu. Mỗi dòng bắt đầu bằng tên đèn (là một chuỗi kí
tự không vượt quá 20 kí tự), sau đó là vị trí của đèn cho bằng hoành độ và tung
độ. Các trường này phân cách bởi một dấu cách.
Dòng tiếp theo
ngay sau các dữ liệu về đèn hiệu là một số nguyên chỉ số lượng các kịch bản đường
đi của tàu. Mỗi kịch bản chứa 3 dòng gồm một dòng cho biết hướng đi của tàu so
với hướng Bắc và vận tốc vận tốc thực của tàu, và hai dòng chỉ hai lần đọc đèn
hiệu. Thời gian được đo bằng phút, tính từ lúc nửa đêm trong vòng 24 giờ. Vận
tốc đo bằng đơn vị độ dài (như các đơn vị của hệ trục toạ độ) trên đơn vị thời
gian. Dòng thứ hai của kịch bản là lần đọc thứ nhất gồm thời gian (là một số
nguyên), tên đèn và góc phương vị tương đối với hướng đi của tàu. Ba trường được
ngăn cách nhau bởi một dấu cách. Dòng thứ ba của kịch bản là lần đọc thứ hai.
Thời gian của lần đọc này luôn lớn hơn lần đọc thứ nhất.
Output
Với mỗi kịch
bản, chương trình của bạn phải chỉ ra được số thứ tự của kịch bản (Scenario 1,
Scenario 2,...),
và một thông báo về vị trí của con tàu (được làm tròn đến hai chữ số thập phân)
tại thời điểm của lần đọc thứ hai.
Nếu vị trí của tàu không thể xác định thì thông báo: ”Position cannot be determined.”
Mẫu input và output chính xác tương
ứng được cho như sau:
Sample Input
4
First 2.0 4.0
Second 6.0 2.0
Third 6.0 7.0
Fourth 10.0 5.0
2
0.0 1.0
1 First 270.0
2 Fourth 90.0
116.5651 2.2361
4 Third 126.8699
5 First 319.3987
Sample Output
Scenario 1: Position cannot be determined
Scenario 2: Position is (6.00, 5.00)
Bài
41/2000 - Cờ Othello
(Dành cho học
sinh THCS và THPT)
Cờ
Othello là trò chơi cho 2 người trên một bàn cờ kích thước 8x8 ô, dùng những
quân tròn một mặt đen, một mặt trắng. Các đấu thủ sẽ được lần lượt đi một quân
vào ô còn trống trên bàn cờ. Khi đi một quân, đấu thủ phải lật được ít nhất một
quân của đấu thủ kia. Các quân sẽ lật được nếu chúng nằm liên tiếp trên cùng
một đường thẳng (ngang, dọc hoặc chéo) mà ở hai đầu của đường đó là hai quân có
mầu của đấu thủ đang đi. Khi xong một lượt đi, tất cả các quân đã bị lật đã được
đổi sang màu của đấu thủ vừa đi. Trong một lượt đi có thể lật được nhiều hàng.
Ví dụ: Nếu thế
cờ hiện thời ở bàn cờ bên trái và lượt đi là của đấu thủ trắng, thì anh ta có
thể đi được một trong các nước sau: (3,5) (4,6) (5,3) (6,4). Nếu anh ta đi nước
(3,5) thì sau nước đi thế cờ sẽ như ở bàn cờ bên phải.
Vẽ bàn cờ
Bạn
hãy viết một chương trình để đọc một ván cờ từ một text file có qui cách:
8 dòng đầu tiên
là bàn cờ thế, mỗi dòng chứa 8 kí tự, mỗi kí tự có thể là:
'-' thể hiện một ô trống,
'B' thể hiện một ô có quân đen,
'W' thể hiện một ô có quân trắng.
Dòng thứ 9 chứa
một trong hai kí tự 'B' hoặc 'W' để chỉ nước đi thuộc về đấu thủ nào.
Các dòng tiếp
theo là các lệnh. Mỗi lệnh có thể là: liệt kê tất cả các nước đi có thể của đấu
thủ hiện thời, thực hiện một nước đi, hay thôi chơi ván cờ đó. Mỗi lệnh ghi
trên một dòng theo qui cách sau:
Liệt kê tất
cả các nước đi có thể của đấu thủ hiện thời:
Lệnh
là một chữ 'L' ở cột đầu tiên của dòng. Chương trình phải kiểm tra cả bàn cờ và
in ra tất cả các nước đi hợp lệ của đấu thủ hiện thời theo dạng (x,y) trong đó
x là hàng và y là cột của nước đi. Các nước đi này phải được in theo qui cách:
+
Mọi nước đi trên hàng i sẽ được in trước mỗi nước đi trên hàng j nếu j>i.
+
Nếu trên hàng i có nhiều hơn 1 nước đi thì các nước đi được in theo thứ tự của
cột.
Mọi
nước đi hợp lệ phải in trên một dòng. Nếu không có nước đi nào hợp lệ vì đấu
thủ hiện thời không thể lật bất cứ một quân nào thì phải in ra thông báo 'No
legal move'.
Thực
hiện một nước đi
Lệnh
là một chữ 'M' ở cột đầu tiên của dòng, tiếp theo sau là 2 chữ số ở cột thứ hai
và thứ ba của dòng. Các chữ số chỉ ra hàng và cột của ô trống trên bàn cờ nơi đấu
thủ hiện thời sẽ đặt quân của mình, trừ
phi anh ta không có nước đi hơp lệ nào. Nếu đấu thủ hiện thời không có nước đi
hợp lệ nào thì anh ta được thay bởi đấu thủ kia và bây giờ nước đi là của đấu
thủ mới. Chương trình phải kiểm tra khi đó nước đi là hợp lệ. Bạn sẽ phải ghi
nhận sự thay đổi trên bàn cờ, kể cả việc thêm các quân mới lẫn việc thay đổi
màu sắc quân cờ bị lật. Cuối mỗi nước đi hãy in ra số lượng tất cả các quân cờ
mỗi màu trên bàn cờ theo qui cách 'Black - xx White - yy, trong đó xx là số
lượng các quân đen còn yy là số lượng các quân trắng. Sau một nước đi, đấu thủ
hiện thời được thay bởi đấu thủ kia.
Thôi
chơi ván cờ đó
Lệnh
là một chữ 'Q' ở cột đầu tiên của dòng, dòng lệnh này kết thúc Input cho ván cờ
đang xét. Chương trình phải in thế cờ cuối cùng của ván cờ theo qui cách được
dùng ở input.
Bạn
phải kiểm tra tính chính xác của các lệnh. Không được để dòng trắng ở bất cứ
nơi nào trong output.
Bài 42/2000 - Một chút về tư duy số học
(Dành cho học sinh Tiểu học)
Tìm
số tự nhiên nhỏ nhất khi chia cho 2, 3, 4, 5, 6, 7, 8, 9, 10 cho phần dư tương
ứng là 1, 2, 3, 4, 5, 6, 7, 8, 9.
Bài 43/2000 - Kim giờ và phút gặp nhau bao nhiêu lần trong ngày
(Dành cho học sinh Tiểu học)
Đồng
hồ quả lắc có 2 kim: giờ và phút. Tính xem trong vòng 1 ngày đêm (từ 0h - 24h)
có bao nhiêu lần 2 kim gặp nhau và đó là những lúc nào.
Bài 44/2000 - Tạo ma trận số
(Dành cho học sinh THCS)
Cho
trước số nguyên dương N bất kỳ. Hãy viết thuật toán và chương trình để tạo lập
bảng NxN phần tử nguyên dương theo quy luật được cho trong ví dụ sau:
1 2 3 4 5 6
2 4 6 8 10 12
3 6 9 12 2 4
4 8 12 2 4 6
5 10 2 4 6 8
6 12 4 6 8 10
Thực hiện chương
trình đó trên máy với N=12, đưa ra màn hình ma trận kết quả (có dạng như trong
ví dụ).
0 Nhận xét