bµi tëp tin häc bµi tëp tin häc 21121999 §æi tiòn níc silverland sö dông hö thèng tiòn xu trong ®ã c¸c xu cã mönh gi¸ lµ mét sè chýnh ph¬ng 1 4 9 289 172 víi hö thèng nµ
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 (76.04 KB, 2 trang )
<span class='text_page_counter'>(1)</span><div class='page_container' data-page=1>
bài tập tin học
21/12/1999
ắắắắắắ
{
¾¾¾¾¾¾<i><b>§ỉi tiỊn </b></i>
Nớc Silverland sử dụng hệ thống tiền xu trong đó các xu có mệnh giá là một số chính
phơng: 1, 4, 9, . . ., 289 ( = 172<sub> ). Với hệ thống này, để trả 10 xu ta có 4 cách:</sub>
n Trả 10 đồng 1 xu,
n Trả 1 đồng 4 xu và 6 đồng 1 xu,
n Trả 2 đồng 4 xu và 2 đồng 1 xu,
n Trả 1 đồng 9 xu và 1 đồng 1 xu.
Nhiệm vụ của bạn là xác định xem có bao nhiêu cách trả một số tiền cho trc
Silverland.
<i>Dữ liệu</i>: vào từ file văn bản COIN.INP, gồm nhiều dòng, mỗi dòng một số nguyên
d-ơng không vợt quá 300.
<i>Kết quả:</i> đa ra file văn bản COIN.OUT số cách trả ứng với từng trờng hợp.
<i>Ví dụ</i>:
COIN.INP COIN.OUT
2
10
30
1
4
27
<i><b>Bng đèn</b></i>
Cho bảng hình vng, trên đó gắn N*N đèn tạo thành lới ô vuông. Các hàng và cột
đ-ợc đánh số từ 1 đến N từ trên xuốn dới và từ tráI qua phải. Mỗi hàng và mỗi cột có
một công tắc bấm. Ký hiệu Ri là công tắc bấm của hàng i và Cj - công tắc bấm của cột
j. Khi bấm vào một công tắc của một hàng ( cột) nào đó thì tất cả các đèn của hàng
(cột ) ấy đổi trạng tháI: từ sáng thành tắt hoặc ngợc lại.
Cho trớc hai trạng thái đầu và cuối của bảng, hãy chỉ cách bấm ít nhất có thể đ ợc các
nút để chuyển trạng thái của bảng từ trạng thái đầu sang trạng thái cuối hoặc cho biết
không tn ti cỏch chuyn.
<i>Dữ liệu</i>: vào từ file văn bản LAMP.INP, dòng đầu là số nguyên N ( 1 < N Ê 50), N
dòng sau mô tả trạng thái đầu của bảng, mỗi dòng N số 0 hoặc 1, 0 ứng với trạng thái
tắt, 1 ứng với trạng thái bật, các số trên một dòng cách nhau ít nhất 1 dấu cách. N
dòng tiếp theo mô tả trạng thái cuối của bảng (theo quy cách nh trên).
<i>Kt qu:</i> a ra file LAMP.OUT. Dòng đầu tiên là số nguyên xác định số lần bấm nút.
Nếu khơng có cách bấm thì dịng này chứa số -1. Các dòng tiếp theo: mỗi dòng ghi
một nút cần bấm, dới dạng <i>R i</i> hoặc <i>C j</i>.
<i>VÝ dô:</i>
LAMP.INP LAMP.OUT
4
0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0
4
R 1
C 4
C 1
R 4
0 0 0 0
</div>
<span class='text_page_counter'>(2)</span><div class='page_container' data-page=2>
<i><b>Khôi phục ngoặc</b></i>
Cho mt biu thc toỏn học có nhiều ngoặc trịn lồng nhau. Biểu thức ban đầu đợc viết
đúng. Ai đó tinh nghịch xố hết các tốn hạng và phép tính, chỉ để lại ngoặc. Một ngời
khác viết dới mỗi ngoặc mở một số nguyên cho biết có bao nhiêu ngoặc ( cả đóng lẫn
mở ) nằm giữ ngoặc mở này và ngoặc đóng tơng ứng của nó. Ví dụ, từ một biểu thức
ta có:
( ( ) ( ( ) ( ) ) ( ( ) ) ( ) )
14 0 4 0 0 2 0 0
HÃy khôi phục lại dÃy các ngoặc dựa vào dÃy các số nguyên cho trớc.
Dữ liệu: vào từ file văn bản BALANC.INP:
n Dòng đầu số nguyên N - số lợng các số trong dÃy, ( 0 < N Ê 1000),
n Các dòng sau: Các số nguyên không âm của dÃy.
Kt qu: a ra file BALANC.OUT chuỗi các ngoặc tìm đợc dới dạng xâu văn bản.
Ví dụ:
BALANC.INP BALANC.OUT
8 ( ( ) ( ( ) ( ) ) ( ( ) ) ( ) )
14 0 4 0 0
</div>
<!--links-->
