HSG lớp 9 Quảng Trị 2020-2021

ĐỀ THI CHỌN HỌC SINH GIỎI LỚP 9 TỈNH QUẢNG TRỊ Năm học 2020 - 2021

MÔN TIN HỌC 4 bài: CAU1 - CAU4

Bài 1. Số may mắn

Số may mắn của số nguyên dương M là số có một chữ số được tạo ra từ số M như sau: nếu M chỉ có một chữ số thì số may mắn của nó là chính nó, nếu M có nhiều hơn một chữ số thì nó được thay bằng tổng các chữ số của nó cho đến khi còn đúng một chữ số, số đó chính là số may mắn.

Yêu cầu: Cho T số nguyên dương, hãy tìm các số may mắn tương ứng.

Dữ liệu vào: Đọc từ file văn bản CAU1.INP có cấu trúc như sau:

Dòng đầu ghi số nguyên dương T (T ≤ 10);
T dòng tiếp theo, mỗi dòng ghi một số nguyên dương M.

Kết quả: Ghi ra file văn bản CAU1.OUT gồm T dòng, mỗi dòng ghi một số may mắn tương ứng với số M đã cho.

Ví dụ:

CAU1.INP	CAU1.OUT
`2` `5` `12345`	`5` `6`

Ràng buộc:

Có 80% số test M ≤ 10⁹;
Có 20% số test 10⁹ ≤ M ≤ 10³⁰.

Bài 2. Chọn cây

Trong khuôn viên trường có N cây xanh được đánh số từ 1 đến N, cây thứ i (1 ≤ i ≤ N) có chiều cao Hᵢ và giá trị thẩm mĩ là Cᵢ (1 ≤ Hᵢ, Cᵢ ≤ 10⁹). Nhà trường giao cho mỗi lớp chọn ra 3 cây bất kì để chăm sóc. Lớp 9A muốn chọn 3 cây theo thứ tự i, j, k sao cho có tổng giá trị thẩm mĩ lớn nhất đồng thời thỏa mãn điều kiện 1 ≤ i < j < k ≤ N và Hᵢ < Hⱼ < H_k.

Yêu cầu: Xác định tổng giá trị thẩm mĩ lớn nhất mà lớp 9A có thể chọn được.

Dữ liệu vào: Đọc từ file văn bản CAU2.INP có cấu trúc như sau:

Dòng đầu ghi số N;
Dòng thứ 2 ghi N số H₁, H₂, …, H_N;
Dòng thứ 3 ghi N số C₁, C₂, …, C_N;
Các số cách nhau một dấu cách.

Kết quả: Ghi ra tệp văn bản CAU2.OUT tổng giá trị thẩm mĩ lớn nhất mà lớp 9A có thể chọn.

Ví dụ:

CAU2.INP	CAU2.OUT
`5` `2 4 5 4 10` `4 3 2 1 5`	`12`

Ràng buộc:

Có 70% số test N ≤ 500*;*
Có 30% số test 500 ≤ N ≤ 3000*.*

Bài 3. Khóa điện tử

Một khách sạn sử dụng thẻ điện tử trong việc quản lý phòng. Nhân viên An được cấp một thẻ riêng để quản lý một số phòng của khách sạn, mã số thẻ của An là một xâu kí tự T gồm các chữ cái và kí tự ‘?’.

Khách sạn có N phòng được đánh số từ 1 đến N. Tại cửa phòng thứ i (1 ≤ i ≤ N) có một đầu đọc thẻ, mã khóa Kᵢ của phòng là một xâu kí tự S chỉ gồm các chữ cái được lưu trong đầu đọc thẻ. Khi nhân viên đưa thẻ vào đầu đọc, nếu xâu mã số thẻ phù hợp với xâu mã khóa Kᵢ thì cửa phòng i sẽ được mở. Xâu mã số thẻ T phù hợp với mã khóa S khi thỏa mãn đồng thời các điều kiện:

Số kí tự của T bằng số kí tự của S;
Với mỗi vị trí j tương ứng của hai xâu thì T[j] = S[j] hoặc T[j] là kí tự ‘?’.

Yêu cầu: Cho biết mã số thẻ của An và các mã khóa của N phòng. Hãy kiểm tra xem thẻ của An có thể dùng để mở được những phòng nào trong khách sạn.

Dữ liệu vào: Đọc từ file văn bản CAU3.INP có cấu trúc như sau:

Dòng đầu ghi xâu mã số thẻ T.
Dòng thứ hai ghi số nguyên dương N (N ≤ 500),
N dòng tiếp mỗi dòng ghi một xâu mã khóa Kᵢ. Độ dài mỗi xâu không vượt quá 255 kí tự.

Kết quả: Ghi ra file văn bản CAU3.OUT gồm N dòng tương ứng với khả năng mở khóa của thẻ của An đối với từng phòng; nếu mở được ghi 1, ngược lại ghi 0.

Ví dụ:

CAU3.INP	CAU3.OUT
`a?aba` `2` `aaaba` `abacb`	`1` `0`

Ràng buộc:

Có 30% số test xâu T không chứa kí tự ‘?’;
Có 30% số test xâu T có chứa một kí tự ‘?’;
Có 40% số test xâu T chứa nhiều hơn một kí tự ‘?’.

Bài 4. Song nguyên tố

Số song nguyên tố là số có số lượng các ước của nó là một số nguyên tố.

Yêu cầu: Hãy đếm số lượng các số song nguyên tố trong đoạn [a, b].

Dữ liệu vào: Đọc từ tệp văn bản CAU4.INP có cấu trúc như sau:

Dòng đầu ghi số nguyên dương T là số lượng các đoạn cần đếm,
T dòng tiếp theo mỗi dòng ghi hai số nguyên dương a, b (a ≤ b) cách nhau một dấu cách.

Kết quả: Ghi ra tệp văn bản CAU4.OUT gồm T dòng, mỗi dòng ghi kết quả của một đoạn.

Ví dụ:

CAU4.INP	CAU4.OUT
`2` `2 5` `1 100`	`4` `32`

Ràng buộc:

Có 30% số điểm 1 ≤ a, b ≤ 200, T ≤ 100;
Có 30% số test 1 ≤ a, b ≤ 2000, T ≤ 1000;
Có 40% số test 1 ≤ a, b ≤ 10⁶, T ≤ 1000;
Có 40% số test 1 ≤ a, b ≤ 10⁶, T ≤ 10⁵.

(Tổng tỉ lệ các nhóm test trong bản đánh máy là 140%, giữ nguyên văn để đối chiếu với đề gốc.)

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