Đề thi không chuyên toàn quốc

HỘI THI TIN HỌC TRẺ KHÔNG CHUYÊN TOÀN QUỐC LẦN THỨ IX, 2003.
Địa Điểm Thi: Thành Phố Đà Nẵng.

Đề Thi Lập Trình Bảng B: Trung Học Cơ Sở.
Thời Gian Làm Bài: 120 Phút.

ĐỀ CHÍNH THỨC

TỔNG QUAN VỀ ĐỀ THI
BÀI TOÁN
Sáo Trúc
Mã cá nhân

Tên file bài làm
Flute.???
ID.???

Tên file dữ liệu
FLUTE.INP
ID.INP

Tên file kết quả
FLUTE.OUT
IN.OUT

Hạn chế thời gian cho một test
1 giây
2 giây

Số lượng test
10
10

Điểm của một test
4
4

Tổng điểm
40
40


Chú ý:
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ữ lập trình mà em lựa chọn thực hiện.
Đề thi gồm ba trang. Giám thị không cần giải thích gì thêm. Thí sinh không sử dụng tài liệu trong khi thi.
HỘI THI TIN HỌC TRẺ KHÔNG CHUYÊN TOÀN QUỐC LẦN THỨ IX, 2003
Đề thi lập trình bảng B: Trung Học Cơ Sở

Bài 1. Sáo trúc.
Tên file chương trình: FLUTE.???
Sáo là một nhạc cụ dân tộc phổ biến do tính đơn giản của nó: gọn nhẹ, rẻ tiền, dễ sử dụng. Tuy vậy để chơi hay thì hoàn toàn không đơn giản và phải cần có các bài tập cơ sở tạo kỹ năng sử dụng. Có nhiều loại sao, một trong những loại đó là sáo có một đầu để thổi hơi. Để chơi một bản nhạc, người ta thổi vào đầu và dùng ngón tay bịt một số lỗ này hay khác trên sáo thì sẽ được các nốt nhạc khác nhau. Bảy nốt nhạc: Đồ , Rê, Mi, Pha, Son, La, Si, thấp được kí hiệu c d e f g a b và bảy nốt cao la C D E F G A B. Các ngón tay được đánh số từ 1 đến 10. Để bấm các nốt người ta phải sử dụng các ngón tay như sau:
c: các ngón 2, 3, 4, 7, 8, 9, 10.
d: các ngón 2, 3, 4, 7, 8, 9.
e: các ngón 2, 3, 4, 7, 8.
f: các ngón 2, 3, 4, 7.
g: các ngón 2, 3, 4.
a: các ngón 2, 3.
b: ngón 2.
C: ngón 3.
D: các ngón 1, 2, 3, 4, 7, 8, 9.
E: các ngón 1, 2, 3, 4, 7, 8.
F: các ngón 1, 2, 3, 4, 7.
G: các ngón 1, 2, 3, 4.
A: các ngón 1, 2, 3.
B: các ngón 1, 2.
Yêu cầu: Hãy đếm số lần mỗi ngón tay phải bấm phím khi chơi một bản nhạc. Một lần bấm được tính khi ngón tay được sử dụng cho một nốt nhạc nào đó đến khi gặp nốt nhạc không sử dụng ngón tay đó hoặc kết thúc bản nhạc.

Dữ liệu: Vào từ file FLUTE.INP gồm nhiều dòng, mỗi dòng một xâu không quá 255 ký tự, xác định một bản nhạc.

Kết quả: Đưa ra file văn bản FLUTE.OUT mỗi bản nhạc tương ứng với một dòng gồm 10 số nguyên, số nguyên thứ I cho biết số lần bấm của ngón i.

Ví dụ:
FLUTE.INP

FLUTE.OUT

Cdefgab
BAGFEDC

0 1 1 1 0 0 1 1 1 1
1 1 1 1 0 0 1 1 1 0


HỘI THI TIN HỌC TRẺ KHÔNG CHUYÊN TOÀN QUỐC LẦN THỨ IX, 2003
Đề thi lập trình bảng B: Trung Học Cơ Sở

Bài 2. Mã cá nhân.
Tên file chương trình: ID.???
1
2
3

4
5
6

7
8
9


0


Để quản lý các vận động viên và khách mời cho SEAGAMES 2002 sắp tới, Ban Tổ Chức cần đánh mã số cho từng vận động viên cũng như các khách mời. Để gợi nhớ mã số cho từng người, Ban Tổ Chức quyết định đánh mã số theo nước đi con mã của cờ vua trên các phím bấm chữ số của điện thoại di động (Hình 1).







Hình 1. Hình 2.
Con mã di chuyển một bước trên các nước này như sau:
Từ ô số 1 có thể di chuyển đến các ô có 6 hoặc 8 và ngược lại.
Từ ô số 2 có thể di chuyển đến các ô có 7 hoặc 9 và ngược lại.
Từ ô số 3 có thể di chuyển đến các ô có 4 hoặc 8 và ngược lại.
Từ ô số 4 có thể di chuyển đến các ô có 3, 9 hoặc 0 và ngược lại.
Từ ô số 6 có thể di chuyển đến các ô có 1, 7 hoặc 0 và ngược lại.
Mã số của một người là một số có N chữ số, không bắt đầu bằng 0 và hai chữ số đứng kề nhau tương ứng với 2 ô mà thì con mã có thể di chuyển từ ô này sang ô kia bằng một bước. Ví dụ với N=4 thì số 1672 là không hợp lệ (Hình 2), còn số 1860 là một mã hợp lệ bởi vì từ ô 8 con mã không di chuyển tới ô 6 bằng 1 bước. Để thuận lợi cho việc quản lý Ban tổ chức muốn mã số không quá dài, vì vậy ban tổ chức cần biết với độ dài của mã N cho trước thì có thể mã số tối đa được cho bao nhiêu người.

Yêu cầu: Với N cho trước, hãy tìm số lượng lớn nhất S các mã số có thể có gồm N chữ số (1
Dữ liệu: Vào từ file văn bản ID.INP trong đó chứa một số duy nhất N.

Kết quả: Đưa ra file văn bản ID.OUT trong đó ghi ra số S tìm được.

ID.INP

ID.OUT

3

40

Ví dụ: