Đề thi tin học trẻ bảng B quốc gia năm 2011

 Mời các bạn tham khảo

Đề thi tin học trẻ bảng B quốc gia năm 2011

HỘI THI TIN HỌC TRẺ TOÀN QUỐC

LẦN THỨ XVII – 2011

ĐỀ CHÍNH THỨC

ĐỀ THI BẢNG B – TRUNG HỌC CƠ SỞ

Thời gian làm bài 180 phút, không kể thời gian phát đề

Địa điểm thi: Tp. Hồ Chí Minh

Bài 1. DIGIT358 Tìm chữ số thập phân

Xét biểu diễn thập phân của phân số a/b. Biểu diễn này có thể là một số thập phân hữu hạn hoặc một

số thập phân vô hạn tuần hoàn. Nếu phân số có thể biểu diễn bởi một số thập phân hữu hạn, ta có

thể viết thêm một dãy vô hạn các chữ số 0 vào sau chữ số cuối cùng sau dấu chấm thập phân và coi

đó cũng là một số thập phân vô hạn tuần hoàn. Ví dụ:

 100/8 = 12,500...0...

 17/3 = 5,66 ... 6 ...

 99/140 = 0,70714285714285 ... 714285

Yêu cầu: Sau khi đánh số từ 1 trở đi, từ trái qua phải các chữ số đứng sau dấu “,” trong biểu diễn

thập phân của a/b. Hãy xác định chữ số thứ k.

Ví dụ:

 Với a = 100, b = 8, k = 2, chữ số đứng thứ 2 sau dấu chấm thập phân của giá trị 100/8 là chữ

số 0.

 Với a = 99, b = 140, k = 12, chữ số đứng thứ 12 sau dấu chấm thập phân của giá trị 99/140 là

chữ số 2.

Input: Mỗi dòng 1 test, gồm 3 số a, b, k

Output: Mỗi dòng 1 kết quả ứng với test tương ứng

Input Output

100 8 2 0

99 140 12 2

1 240 5

100 89 9

48 49 22

3333 1234 56

4444 5678 90

55555 12345 67890

666666 13579 24680

7777777 9999991 999999999

999999999999999999 987654321987654321 123456789123456789

999999999999999967 999999999999999989 999999999999999999

chuyentin.pro

2

Bài 2. KIEN Kiến thông minh

Kiến chúa tổ chức cuộc thi “kiến thông minh” trên một đoạn thẳng nằm ngang độ dài n đơn

vị, tổ kiến nằm ở một đầu mút đoạn thẳng đó. Khi mỗi chú kiến thợ vào thi, Kiến chúa rải n miếng

đường đánh số từ 1 đến n. Miếng đường thứ i có trọng lượng wi được đặt trên đoạn thẳng ở vị trí

cách tổ kiến đúng i đơn vị độ dài (i = 1, 2, ..., n)

Mỗi chú kiến thợ cần thực hiện đúng 3 lượt kiếm mồi trong bài thi của mình. Ở mỗi lượt chú

kiến thợ xuất phát từ tổ, đi tới vị trí một miếng đường và tha miếng đường đó về tổ, lượt chơi tiếp

theo tiến hành tương tự, tất nhiên những miếng đường đã tha về tổ sẽ không còn trên đoạn đường

thẳng ở vị trí cũ nữa.

Một bài thi của chú kiến thợ là hợp lệ nếu tổng quãng đường di chuyển của chú kiến trong cả

ba lượt kiếm mồi không vượt quá T. Điểm của bài thi là tổng trọng lượng của ba miếng đường mà

chú kiến thợ kiếm được.

Em được cho trước số nguyên dương n, số nguyên dương T, hai số nguyên dương a, m để

xác định dãy w1, w2, ..., wn theo công thức:

wi = ai

mod m + 1

Yêu cầu: Xác định điểm tối đa mà một chú kiến thợ có thể kiếm được trong bài thi của kiến chúa.

Ví dụ: với n = 5, T = 15, a = 4, m = 9. Dãy w1 .. 5 = (5, 8, 2, 5, 8). Các miếng đường được bố trí theo

sơ đồ sau

Phương án kiếm được nhiều điểm nhất (18 điểm) cho chú kiến thợ là tha 3 miếng đường số 1, 2 và 4

về tổ. Tổng quãng đường di chuyển là 14.

Input: 4 số n ≤ 106

, T≤ 2*106

, a ≤ 3*106

, m ≤ 109

Output: kết quả tìm được.

Em cần tạo 10 file kết quả các tên dạng ANT?.TXT, trong mỗi file, ghi một số nguyên duy nhất là

kết quả tìm được ứng với một bộ giá trị (n, T, m) cho dưới đây

n T a m kq

3 12 2 5

5 15 4 9 18

10 25 9 20

100 100 11 135

1000 3000 2 9999

2222 1234 5 99991

3333 5678 99 999983

9999 9999 9999 99999

999999 5555555 789 999999929

1000000 2000000 3000000 999999937a