ĐỀ Thi HỌc Sinh GiỎi Tin HỌc CẤp TỈnh VÒng 1 NĂm HỌc 2007-2008

[phanthuyen]

Bài 1: (5 điểm) Cho một lưới gồm n ô vuông được đánh dấu thứ tự từ 1 đến n. ban đầu mỗi ô vuông không chứa hòn sỏi nào, người ta bỏ vào cá cô vuông những hòn sỏi theo k lần qui tắc sau:
Mỗi lần bỏ thêm vào ô vuông thứ nhất, ô vuông thứ 2 mỗi ô đúng 1 hòn sỏi, từ ô vuông thứ 3 trở đi số hòn sỏi bỏ thêm vào bẳng tổng số hòn sỏi của các ô vuông phía trước.
Yêu cầu : Nhập vào số tự nhiên n, k, m (m ≤ n) trong đó n là số ô vuông của lưới, k là số lần thực hiện qui tắc. Hãy cho biết ô vuông thứ m có bao nhiêu hòn sỏi?


Ví dụ : Có n = 5, k = 3, m= 4. Thực hiện k lần qui tắc ta có

k=1 1 1 2 4 8

k=2 2 2 6 14 32

k=3 3 3 12 32 82

Với k=1 số hòn sỏi của từng ô vuông như trên
Với k=2 số hòn sỏi của từng ô vuông như trên
Với k=3 số hòn sỏi của từng ô vuông như trên
Ta được ô vuông thứ m=4 có số hòn sỏi là 32

Bài 2: (5điểm) Cho chuỗi S có n kí tự, để chọn kí tự đại diện cho chuỗi S người ta thực hiện qui tắc sau:
- Đếm kí tự liên tục theo chiều từ trái sang phải, hết chuỗi đếm tiếp kí tự từ đầu
- Đầu tiên kí tự thứ nhất đếm 1, đếm liên tục đến 5 bỏ kí tự tại vị trí này ra khỏi chuỗi S. Kí tự kế tiếp đếm 1, đếm đến 6 bỏ kí tự tại vị trí này ra khỏi chuỗi S. Kí tự kế tiếp đếm 1, đếm đến 5 bỏ kí tự tại vị trí này ra khỏi chuỗi S. Kí tự kế tiếp đếm 1, đếm đến 6 bỏ kí tự tại vị trí này ra khỏi chuỗi S.
… tiếp tục đến khi chuỗi còn đúng 1 kí tự, kí tự này là kí tự đại diện cho chuỗi S.
Yêu cầu : Nhập vào số tự nhiên n là số kí tự của chuỗi S. Hãy cho biết kí tự đại diện của chuỗi S là kí tự thứ mấy trong chuỗi S ban đầu.
Ví dụ: Nhập n=4 giả sử chuỗi S= ‘abcd’
Đầu tiên từ kí tự thứ nhất là a đếm 1, đếm đến 5 là kí tự a, bỏ kí tự này là kí tự a ra khỏi chuỗi S ta được S= ‘bcd’.
Kí tự kế tiếp là b đếm 1, đếm đến 6 là kí tự d, bỏ kí tự này là kí tự d ra khỏi chuỗi S ta có S= ‘bc’.
Kí tự kế tiếp là b đếm 1, đếm đến 5 là kí tự b, bỏ kí tự này là kí tự b ra khỏi chuõi S ta có S= ‘c’.
Vậy kí tự đại diện của chuỗi S là kí tự thứ 3 của chuỗi