Bảng B 2018 - Chung kết toàn quốc

HỘI THI TIN HỌC TRẺ TOÀN QUỐC
Lần thứ XXIV – Năm 2018

ĐỀ THI CHUNG KẾT - BẢNG B – TRUNG HỌC CƠ SỞ
Thời gian làm bài: 150 phút
Địa điểm thi: Trường THPT chuyên Lê Quý Đôn, TP Vũng Tàu, tỉnh Bà Rịa – Vũng Tàu

Bài 1. Nén dãy số (30 điểm)

Cho số nguyên dương N, ta có dãy số A gồm các số nguyên từ 1 đến N. Phép nén dãy số là tạo ra dãy số mới mà các phần tử được tạo ra bằng cách lần lượt cộng 2 số cạnh nhau của dãy số ban đầu.

Mỗi lần nén dãy số, dãy số mới sẽ ít hơn dãy trước 1 phần tử. Ta nén dãy số đến khi chỉ còn 1 phần tử, phần tử đó là giá trị nén dãy số.

Yêu cầu: In ra giá trị nén dãy số. Vì kết quả có thể rất lớn, nên chỉ cần in ra số dư của phép tính chia giá trị nén dãy số cho 1000000000 (10⁹).

Ví dụ: với N = 4, dãy 1,2,3,4 → nén lần 1: 3,5,7 → nén lần 2: 8,12 → nén lần 3: 20. Kết quả là 20.

Dữ liệu: Một số nguyên dương N.

Kết quả: Một số nguyên là giá trị nén dãy số (mod 10⁹).

Ví dụ:

N	Kết quả
4	20
6	112
10	2816
24	104857600

Bài 2. Huấn luyện Pokemon (30 điểm)

Công ty X sản xuất những con robot thông minh gọi là pokemon, các con pokemon ban đầu giống hệt nhau, mỗi con có n kỹ năng đánh số từ 1 tới n và tất cả các kỹ năng đều ở cấp độ 0 khi xuất xưởng. Các con pokemon sau đó sẽ được huấn luyện bằng một chương trình đặc biệt nhằm gia tăng cấp độ các kỹ năng, để tăng cấp độ kỹ năng thứ i lên 1 đơn vị cần thời gian huấn luyện đúng i giây (∀i = 1,2,…,n). Ngoài ra do vấn đề kỹ thuật, không kỹ năng nào được huấn luyện vượt quá cấp độ m.

Công ty X nhận được đơn đặt hàng k con pokemon hoàn toàn phân biệt, tức là hai con pokemon bất kỳ phải có ít nhất một kỹ năng ở cấp độ khác nhau. Hãy cho biết tổng số giây ít nhất cần để huấn luyện k con pokemon thỏa mãn yêu cầu trên.

Ví dụ: với số kỹ năng n=3, giới hạn cấp độ kỹ năng m=4, số con pokemon đặt hàng k=10. Công ty có thể huấn luyện 10 con pokemon với các kỹ năng sao cho tổng thời gian huấn luyện là 26 (nhỏ nhất có thể).

Em cần tạo file văn bản POKEMON.TXT gồm 10 dòng, mỗi dòng ghi một số nguyên duy nhất là tổng thời gian ít nhất cần để huấn luyện đủ k con pokemon theo đơn đặt hàng ứng với các bộ dữ liệu cho trong bảng sau:

Dòng	n	m	k	POKEMON.TXT
1	3	4	9	22
2	4	2	20
3	5	6	30
4	6	6	100
5	10	1	1000
6	12	4	1000
7	5	67	10000
8	1000	1000	100000
9	100	10000	100000
10	100000	10	100000

Bài 3. Trò chơi: Giải toán lấy quà (40 điểm: 30 + 10)

Chính giữa màn hình là một cây thông nô-en lớn. Trên cây thông có rất nhiều loại quà khác nhau được gắn ngẫu nhiên trên các vị trí dọc theo cây. Nhiệm vụ của em là, trong thời gian 1 phút, điều khiển nhân vật chính (HS) lấy được nhiều phần quà nhất có thể từ cây thông này. Nhấn phím Space để bắt đầu trò chơi.

Khi bắt đầu chơi, em sẽ điều khiển nhân vật chính bằng các phím lên, xuống, phải, trái, nhân vật chính sẽ di chuyển lên, xuống, phải, trái 5 bước tương ứng (Hình 1).

Khi va chạm vào một món quà đầu tiên, người chơi sẽ ôm quà này và phải đi đến vị trí có vòng tròn bên phải để bỏ đồ chơi vào bên trong vòng tròn mới được tính là nhận được món quà đó (Hình 2).

Nhưng mỗi khi đến vị trí vòng tròn, trước khi đưa được món quà này vào bên trong vòng tròn, Giáo viên và Bảng sẽ xuất hiện yêu cầu em làm một bài toán (Hình 3). Làm xong bài toán này thì món quà đó mới vào được bên trong vòng tròn và em được quyền đi lấy tiếp món quà khác.

Câu hỏi toán có thể là một trong 2 loại sau:

Tính số các ước số thực sự của một số tự nhiên cho trước (tính cả 1).
Trả lời yes/no cho câu hỏi: số tự nhiên sau có phải là nguyên tố hay không.

Với mỗi câu hỏi em cần trả lời liên tục cho đến khi đúng. Nếu làm đúng, giáo viên nói “đúng rồi” và sau 1 giây giáo viên, bảng biến mất, quà được đưa vào vòng tròn và em sẽ tiếp tục công việc tìm quà của mình.

Sau đúng 60 giây, chương trình dừng lại, giáo viên xuất hiện và thông báo em đã nhận được bao nhiêu phần quà.

Em hãy viết chương trình mô tả trò chơi trên. Ghi tệp chương trình B3.sb2.

Yêu cầu bắt buộc:

Số lượng các món quà phải lớn hơn hoặc bằng 10. Các hình ảnh quà lấy từ thư viện của Scratch.
Các món quà cần gắn và xếp ngẫu nhiên dọc theo thân cây thông. Hình ảnh minh hoạ trên chỉ là ví dụ.

MỞ RỘNG: Trò chơi trên có thể mở rộng theo nhiều cách khác nhau để trở nên hay hơn, đa dạng hơn và hấp dẫn hơn. Gợi ý một số hướng mở rộng:

Tăng số lượng các quà sinh nhật lên cho thêm phần hấp dẫn.
Mở rộng thêm các dạng toán khác cho phong phú hơn. Ví dụ các dạng toán sau có thể đưa thêm vào chương trình: tính giá trị của một biểu thức toán học, ví dụ dạng (m+n)×d; tìm phần tử tiếp theo của một dãy số có qui luật cho trước, ví dụ dãy các số chẵn liên tiếp.
Bổ sung thêm chức năng: nhân vật chính có thể thay thế quà. Khi đã nhận một món quà trên cây, có thể bỏ lại quà đó và chọn quà khác.
Mỗi món quà có một âm thanh tương ứng. Khi nhận một món quà thì âm thanh tương ứng sẽ vang lên.

Phần mở rộng, sáng tạo sẽ đặt tên B3m.sb2.

Th.S Trần Huy Phúc

Kỹ sư phần mềm @Adnovum & Bumbii Academy

Học Tiếng Anh với Bumbii English