Đề thi Tin học trẻ toàn quốc năm 2009

HỘI THI TIN HỌC TRẺ TOÀN QUỐC
LẦN THỨ XV - 2009
ĐỀ THI THỰC HÀNH BẢNG B - THCS
BÀI 1: HỆ THỐNG ĐÈN MẦU
Để trang trí cho lễ kỷ niệm 15 năm hội thi Tin học trẻ toàn quốc, ban tô chức đã dùng một hệ thống đèn mầu gồm n đèn đánh số từ 1 đến n. Mỗi đèn có khả năng sáng màu xanh hoặc màu đỏ. Các đèn được điều khiển theo quy tắc sau:
- Ban đầu tất cả các đèn đều sáng màu xanh.
- Sau khi kết thúc chương trình thứ nhất của lễ kỹ niệm, tất cả các đèn có số thứ tự chia hết cho 2 sẽ đổi màu… Sau khi kết thúc chương trình thứ i, tất cả các đèn có số thứ tự chia hết cho i+1 sẽ đổi màu (đèn xanh đổi thành màu đỏ còn đèn đỏ sẽ đổi thành màu xanh).

Minh, một thí sinh dự lễ kỹ niệm đã phát hiện được quy luật điều khiển đèn và rất thích thú với hệ thống đèn trang trí này. Vào lúc chương trình thứ k của buổi lễ vừa kết thúc, Minh đã nhẫm tính được tại thời điểm đó có bao nhiêu đèn đỏ. Tuy nhiên vì không có máy tính nên Minh không chắc chắn kết quả của mình là đúng. Cho biết hai số n và k, em hãy tính lại giúp Minh xem khi chương trình thứ k của buổi lễ tổng kết vừa kết thúc, có bao nhiêu đèn màu đỏ.

Ví dụ với n=10, k=3.

Thời điểm
Trạng thái các đèn

Bắt đầu
Xanh: 1 2 3 4 5 6 7 8 9 10
Đỏ:

Sau chương trình 1
Xanh: 1 3 5 7 9
Đỏ: 2 4 6 8 10

Sau chương trình 2
Xanh: 1 5 6 7
Đỏ: 2 3 4 8 9 10

Sau chương trình 3
Xanh: 1 4 5 6 7 8
Đỏ: 2 3 9 10

Vậy có 4 đèn đỏ sau chương trình thứ 3.
Em cần tạo 10 file kết quả có tên dạng DENMAU.?. Trong mỗi file, ghi kết quả (là số lượng đèn màu đỏ tính được) tương ứng với một cặp giá trị (n, k) cho dưới đây:

File kết quả
n
K

DENMAU.A
10
5

DENMAU.B
20
6

DENMAU.C
50
10

DENMAU.D
100
50

DENMAU.E
9999
100

DENMAU.F
99999
1234

DENMAU.G
999999
1007

DENMAU.H
12345678
56789

DENMAU.I
99999999
1234567

DENMAU.J
1234567890
1234567890

BÀI 2: Đếm số tam giác

Cho ba số nguyên dương a, b, m và n đoạn thẳng đánh số từ 1 đến n. Đoạn thẳng thứ I có độ dài (Ai: 1<=i<=n), ở đây các độ dài (d1, d2, … , dn) được cho như sau:
b, nếu i=1
Di= (*)
(a x di-1 + b) mod m+1, nếu 1<=i<=n
Hãy cho biết có bao nhiêu tam giác khác nhau có thể được tạo ra bằng cách lấy đúng 3 đoạn trong số n đoạn thẳng đã cho làm 3 cạnh (hai tam giác bằng nhau nếu chúng có 3 cặp cạnh tương ứng bằng nhau, nếu không chúng được coi là khác nhau).

Ví dụ với a=6; b=3; m=4; n=5. Ta có 5 đoạn thẳng với độ dài của chúng tính theo công thức (*) là (3,2,4,4,4). Với 5 đoạn thẳng này có thể tạo ra được 4 tam giác với độ dài các cạnh được chỉ như sau:

Tam giác 1: (2, 3, 4)
Tam giác 2: (2, 4, 4)
Tam giác 3: (3, 4, 4)
Tam giác 4: (4, 4, 4)
Em cần tạo 10 file kết quả có tên dạng TAMGIAC.?. trong mỗi file, ghi kết quả tìm được ứng với một bộ giá trị (a,b,m,n) cho dưới đây:

File kết quả
a
b
m
n

TAMGIAC.A
3
5
7
5

TAMGIAC.B
11
12
13
9

TAMGIAC.C
199
10
59
20

TAMGIAC.D
1
11
111
40

TAMGIAC.E
11
22
101
555

TAMGIAC.F
29
7
2009
6666

TAMGIAC.G
24
68
123456789
7777