Đề số 06 - Ôn thi HSG Tin học THCS

BỘ ĐỀ ÔN THI HỌC SINH GIỎI TIN HỌC THCS Bumbii Academy

ĐỀ SỐ 06 Thời gian làm bài: 150 phút
3 bài, tổng 20 điểm

Tổng quan đề thi

Bài	Tên bài	File chương trình	File dữ liệu vào	File kết quả	Điểm
1	Đếm từ	`DEMTU.*`	`DEMTU.INP`	`DEMTU.OUT`	6
2	Số song tố	`SONGTO.*`	`SONGTO.INP`	`SONGTO.OUT`	7
3	Chồng thẻ bài	`TAMBIA.*`	`TAMBIA.INP`	`TAMBIA.OUT`	7

Dấu * được thay bằng py hoặc cpp tùy theo ngôn ngữ lập trình sử dụng.

Bài 1. Đếm từ (6 điểm)

Cho một dòng văn bản S. Từ là một dãy kí tự khác dấu cách đứng liền nhau; hai từ được ngăn cách bởi một hoặc nhiều dấu cách (đầu và cuối dòng cũng có thể có dấu cách).

Yêu cầu: Cho biết S có bao nhiêu từ, độ dài của từ dài nhất, và liệt kê các từ dài nhất theo thứ tự xuất hiện.

Dữ liệu vào: Từ file văn bản DEMTU.INP gồm một dòng chứa xâu S (có ít nhất một từ; S chỉ gồm chữ cái, chữ số, dấu câu và dấu cách).

Kết quả: Ghi ra file văn bản DEMTU.OUT gồm ba dòng: số lượng từ; độ dài từ dài nhất; các từ dài nhất theo thứ tự trong S, cách nhau một dấu cách.

Ví dụ:

DEMTU.INP	DEMTU.OUT
`An la hoc sinh gioi mon Tin hoc 9`	`9` `4` `sinh gioi`

Ràng buộc: Gọi L là độ dài xâu S.

Có 50% số test với L ≤ 1000.
Có 50% số test với L ≤ 10⁶.

Bài 2. Số song tố (7 điểm)

Số song tố là số nguyên tố có tổng các chữ số cũng là số nguyên tố. Ví dụ: 23 là số song tố vì 23 là số nguyên tố và 2 + 3 = 5 cũng là số nguyên tố; 13 không phải số song tố vì 1 + 3 = 4.

Yêu cầu: Cho q đoạn [L, R], với mỗi đoạn hãy đếm số lượng số song tố thuộc đoạn đó.

Dữ liệu vào: Từ file văn bản SONGTO.INP gồm:

Dòng đầu tiên chứa số nguyên dương q.
q dòng tiếp theo, mỗi dòng chứa hai số nguyên L, R (1 ≤ L ≤ R).

Kết quả: Ghi ra file văn bản SONGTO.OUT gồm q dòng, dòng thứ i là số lượng số song tố trong đoạn thứ i.

Ví dụ:

SONGTO.INP	SONGTO.OUT	Giải thích
`3` `1 30` `10 50` `24 28`	`7` `6` `0`	Đoạn [1, 30]: 2, 3, 5, 7, 11, 23, 29. Đoạn [10, 50]: 11, 23, 29, 41, 43, 47.

Ràng buộc:

Có 40% số test với q ≤ 100, R ≤ 10⁴.
Có 60% số test với q ≤ 10⁵, R ≤ 10⁶.

Bài 3. Chồng thẻ bài (7 điểm)

Có n tấm thẻ xếp chồng lên nhau, đánh số từ 1 (trên cùng) đến n (dưới cùng). Tấm thẻ thứ i ghi số nguyên dương a_i, các số đôi một khác nhau. Có n người lần lượt chơi như sau:

Người thứ 1 lấy hai thẻ trên cùng, giữ lại thẻ ghi số lớn hơn và đặt thẻ còn lại lên trên cùng của chồng.
Người thứ 2, 3, …, n − 1 lần lượt làm tương tự.
Người thứ n nhận tấm thẻ cuối cùng còn lại.

Yêu cầu: Cho biết người thứ mấy nhận được tấm thẻ thứ k (theo thứ tự ban đầu trong chồng).

Dữ liệu vào: Từ file văn bản TAMBIA.INP gồm:

Dòng đầu tiên chứa hai số nguyên dương n và k (k ≤ n).
Dòng thứ hai chứa n số nguyên dương a₁, a₂, …, a_n đôi một khác nhau (a_i ≤ 10⁹).

Kết quả: Ghi ra file văn bản TAMBIA.OUT một số nguyên là thứ tự của người nhận tấm thẻ thứ k.

Ví dụ:

TAMBIA.INP	TAMBIA.OUT	Giải thích
`6 2` `6 3 5 7 1 2`	`4`	Người 1 giữ thẻ 6, trả thẻ 3; người 2 giữ thẻ 5, trả thẻ 3; người 3 giữ thẻ 7, trả thẻ 3; người 4 lấy thẻ 3 và thẻ 1, giữ thẻ 3 (tấm thẻ thứ 2 ban đầu).

Ràng buộc:

Có 40% số test với n ≤ 1000.
Có 60% số test với n ≤ 5 × 10⁵.

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