Đề số 28 - Ôn thi Tin học trẻ Scratch

ĐỀ ÔN THI TIN HỌC TRẺ LẬP TRÌNH SCRATCH Bumbii Academy

BẢNG B – THCS ĐỀ SỐ 28 Thời gian làm bài: 100 phút

Tổng quan đề thi

Bài	Tên bài	Mã bài	Giới hạn thời gian	Điểm
1	Giải đấu vòng tròn	`VONGTRON`	1 giây	100
2	Tháp Hà Nội	`HANOI`	1 giây	100
3	Trung vị	`TRUNGVI`	1 giây	100
4	Cặp chia hết	`CAPCHIA`	1 giây	100
5	Đếm đảo	`DEMDAO`	1 giây	100

Dữ liệu nhập vào từ bàn phím, kết quả ghi ra màn hình. Bài làm lưu thành file MÃBÀI.sb3 (ví dụ VONGTRON.sb3).

Bài 1. Giải đấu vòng tròn (VONGTRON)

Giải bóng đá có N đội thi đấu vòng tròn: mỗi cặp đội gặp nhau đúng một trận. Thắng được 3 điểm, hòa được 1 điểm, thua được 0 điểm.

Yêu cầu: Tính số trận đấu; tổng điểm của tất cả các đội nhỏ nhất và lớn nhất có thể; số điểm nhiều nhất một đội có thể đạt.

Dữ liệu nhập vào từ bàn phím: Một dòng chứa N (2 ≤ N ≤ 10⁷).

Kết quả ghi ra màn hình: Gồm 4 dòng lần lượt là bốn số trên.

Ví dụ:

Input	Output	Giải thích
`4`	`6` `12` `18` `9`	6 trận; nếu mọi trận hòa thì tổng 12 điểm, nếu không trận nào hòa thì 18 điểm.
`2`	`1` `2` `3` `3`

Bài 2. Tháp Hà Nội (HANOI)

Trò chơi Tháp Hà Nội có N đĩa. Người ta đã chứng minh số bước di chuyển ít nhất để chuyển hết N đĩa sang cọc khác là 2ᴺ − 1.

Yêu cầu: Tính số dư khi chia 2ᴺ − 1 cho M.

Dữ liệu nhập vào từ bàn phím: Gồm 2 dòng: N (1 ≤ N ≤ 10¹⁵) và M (1 ≤ M ≤ 10⁶).

Kết quả ghi ra màn hình: Một số tự nhiên là số dư.

Ví dụ:

Input	Output	Giải thích
`3` `100`	`7`	2³ − 1 = 7.
`10` `1000`	`23`	2¹⁰ − 1 = 1023.

Ràng buộc:

Có 40% số test với N ≤ 10⁶;
60% số test còn lại có N ≤ 10¹⁵.

Bài 3. Trung vị (TRUNGVI)

Trung vị của k số là số đứng ở vị trí thứ (k + 1) : 2 (làm tròn xuống) khi xếp k số theo thứ tự tăng dần. Ví dụ trung vị của 5, 2, 8 là 5; của 5, 2, 8, 1 là 2.

Yêu cầu: Cho dãy N số. Sau khi đọc mỗi số, in trung vị của các số đã đọc.

Dữ liệu nhập vào từ bàn phím:

Dòng 1: N;
Dòng 2: N số tự nhiên (mỗi số từ 1 đến 10⁹), cách nhau một dấu cách.

Kết quả ghi ra màn hình: N dòng, dòng thứ i là trung vị của i số đầu tiên.

Ví dụ:

Input	Output	Giải thích
`5` `5 2 8 1 9`	`5` `2` `5` `2` `5`	Sau 4 số: 1 2 5 8, trung vị là số thứ 2.
`3` `4 4 4`	`4` `4` `4`

Ràng buộc:

Có 40% số test với 1 ≤ N ≤ 100;
60% số test còn lại có 1 ≤ N ≤ 3 × 10⁴.

Bài 4. Cặp chia hết (CAPCHIA)

Yêu cầu: Đếm số cặp (X, Y) với A ≤ X ≤ B, C ≤ Y ≤ D và Y chia hết cho X.

Dữ liệu nhập vào từ bàn phím: Gồm 4 dòng: A, B, C, D (1 ≤ A ≤ B; 1 ≤ C ≤ D).

Kết quả ghi ra màn hình: Một số tự nhiên là số cặp.

Ví dụ:

Input	Output	Giải thích
`2` `3` `5` `10`	`5`	(2, 6), (2, 8), (2, 10), (3, 6), (3, 9).
`7` `7` `1` `6`	`0`

Ràng buộc:

Có 40% số test với B, D ≤ 1000;
60% số test còn lại có B ≤ 10⁶, D ≤ 10¹².

Bài 5. Đếm đảo (DEMDAO)

Bản đồ một vùng biển là lưới M hàng, N cột; ô ghi 1 là đất, ô ghi 0 là nước. Hai ô đất chung cạnh thuộc cùng một đảo.

Yêu cầu: Đếm số đảo.

Dữ liệu nhập vào từ bàn phím:

Dòng 1: M; dòng 2: N;
M dòng tiếp theo, mỗi dòng là xâu N kí tự 0 hoặc 1.

Kết quả ghi ra màn hình: Một số tự nhiên là số đảo.

Ví dụ:

Input	Output	Giải thích
`4` `5` `11000` `10011` `00010` `11000`	`3`
`2` `2` `00` `00`	`0`

Ràng buộc:

Có 40% số test với 1 ≤ M, N ≤ 30;
60% số test còn lại có 1 ≤ M, N ≤ 300.

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