HSG lớp 9 Phú Thọ 2022-2023

ĐỀ THI CHỌN HỌC SINH GIỎI LỚP 9 TỈNH PHÚ THỌ Năm học 2022 - 2023

MÔN TIN HỌC 4 bài
Nhập từ bàn phím, in ra màn hình

Bài 1. Tính tổng

Cho số nguyên dương n. Hãy tính tổng S = −1 + 2 − 3 + … + n·(−1)ⁿ.

Dữ liệu vào: nhập từ bàn phím số nguyên n (1 ≤ n ≤ 10¹²).

Kết quả: in ra màn hình kết quả tìm được.

Ví dụ:

Dữ liệu vào	Dữ liệu ra
`4`	`2`

Ràng buộc:

Có 75% số test tương ứng với 75% số điểm của câu có n ≤ 10⁶;
Có 25% số test tương ứng với 25% số điểm của câu có n ≤ 10¹².

Bài 2. Đếm ước

Số tự nhiên a chia hết cho tự nhiên x thì x được gọi là ước của a. Nếu x < a thì x được gọi là ước thực sự của a.

Cho số tự nhiên n (1 ≤ n ≤ 10⁶). Tìm số tự nhiên nhỏ hơn n có nhiều ước thực sự nhất.

Dữ liệu vào: nhập vào từ bàn phím số nguyên n (1 ≤ n ≤ 10⁶).

Kết quả: in ra màn hình kết quả của bài toán. Nếu có nhiều số thỏa mãn bài toán thì in ra số bé nhất trong số chúng.

Ví dụ:

Dữ liệu vào	Dữ liệu ra
`7`	`6`

Ràng buộc:

Có 50% số test tương ứng với 50% số điểm của câu có n ≤ 10⁴;
Có 50% số test tương ứng với 50% số điểm của câu có n ≤ 10⁶.

Bài 3. Số chính phương

Số chính phương là số tự nhiên mà có thể viết dưới dạng bình phương của một số tự nhiên khác. Ví dụ: 0, 1, 4, 9, 16, 25, … là các số chính phương, còn các số 2, 3, 5, … không là số chính phương.

Cho dãy gồm n số nguyên a₁, a₂, …, aₙ. Tìm số chính phương nhỏ nhất không xuất hiện trong dãy số đã cho.

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

Dòng đầu tiên chứa số nguyên n (1 ≤ n ≤ 10⁶);
Dòng thứ hai chứa n số nguyên a₁, a₂, …, aₙ (0 ≤ aᵢ ≤ 10¹², i = 1, 2, …, n), các số cách nhau một dấu cách.

Kết quả: in ra màn hình kết quả tìm được.

Ví dụ:

Dữ liệu vào	Dữ liệu ra
`8` `0 3 4 2 1 4 16 25`	`9`

Ràng buộc:

Có 50% số test tương ứng với 50% số điểm của câu có 1 ≤ n ≤ 10³, 0 ≤ aᵢ ≤ 10⁴;
Có 30% số test tương ứng với 30% số điểm của câu có 10³ < n ≤ 10⁶, 0 ≤ aᵢ ≤ 10⁶;
Có 20% số test tương ứng với 20% số điểm của câu có 0 ≤ aᵢ ≤ 10¹².

Bài 4. Khách hàng may mắn

Nhân dịp năm mới, để thu hút khách hàng đến mua sắm, siêu thị Hùng Vương tổ chức chương trình khách hàng may mắn: mỗi khách hàng đến siêu thị đều nhận được một số may mắn, khách hàng thứ i nhận số may mắn là số nguyên aᵢ được tạo tự động bằng máy tính. Kết thúc chương trình có n khách hàng nhận được số may mắn. Ban tổ chức tiến hành quay số trúng thưởng, những khách hàng may mắn sẽ nhận được phần thưởng của siêu thị. Để đảm bảo tính khách quan Ban tổ chức nhờ một khách hàng bắt thăm ngẫu nhiên hai số nguyên x, y (1 ≤ x, y ≤ n) sau đó sử dụng một chương trình máy tính để tìm ra hai số u, v (0 < u ≤ v ≤ 10⁶) thỏa các điều kiện sau:

Số lượng người có số may mắn aᵢ thỏa mãn u ≤ aᵢ ≤ v tối thiểu là x.
Số lượng người có số may mắn aⱼ thỏa mãn u ≤ −aⱼ ≤ v tối thiểu là y.
Hiệu v − u là nhỏ nhất.

Sau khi tìm được hai số u, v thỏa mãn các điều kiện trên khách hàng có số may mắn aᵢ thỏa mãn u ≤ |aᵢ| ≤ v sẽ được nhận phần thưởng của siêu thị.

Yêu cầu: hãy giúp Ban tổ chức tìm hai số u, v thỏa mãn các điều kiện trên.

Dữ liệu vào: nhập từ bàn phím (các số cách nhau một dấu cách):

Dòng đầu tiên chứa ba số nguyên dương n, x, y (1 ≤ n ≤ 2×10⁵; x, y ≤ n).
Dòng thứ hai chứa n số nguyên a₁, a₂, …, aₙ (0 < |a₁| < |a₂| < … < |aₙ| < 10⁶).

Kết quả: in ra màn hình một dòng duy nhất là hai số u, v tìm được (các số cách nhau một dấu cách). Nếu có nhiều cặp số (u, v) thỏa mãn bài toán thì in ra cặp số (u, v) có u nhỏ nhất; nếu không tìm được u, v thỏa mãn yêu cầu thì in ra −1.

Ví dụ:

Dữ liệu vào	Dữ liệu ra	Giải thích
`4 1 2` `1 -2 -3 4`	`1 3`	Có 3 cặp số u, v thỏa mãn các điều kiện: Cặp (u = 1, v = 4) có v − u = 3 Cặp (u = 1, v = 3) có v − u = 2 Cặp (u = 2, v = 4) có v − u = 2 Cặp (u = 1, v = 3) có v − u = 2 nhỏ nhất và (u, v) có u nhỏ nhất.

Ràng buộc:

Có 50% số test tương ứng 50% số điểm của bài có n ≤ 2×10², |aᵢ| ≤ 10²;
Có 30% số test tương ứng 30% số điểm của bài có 2×10² < n ≤ 2×10³, |aᵢ| ≤ 10⁴;
Có 20% số test tương ứng 20% số điểm của bài có 2×10³ < n ≤ 2×10⁵, |aᵢ| ≤ 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