HSG lớp 9 Tuyên Quang 2022-2023

ĐỀ THI CHỌN HỌC SINH GIỎI LỚP 9 TỈNH TUYÊN QUANG 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. Khai căn

Trong toán học, khi học về căn bậc hai ta có: √20 = 2√5; √36 = 6.

Tổng quát: √n = x√y (với x²·y = n và x lớn nhất có thể).

Yêu cầu: Viết chương trình tìm x và y khi biết giá trị của n.

Dữ liệu vào: Từ bàn phím một số nguyên dương duy nhất n (n ≤ 10⁹).

Kết quả: Ghi ra màn hình theo một trong ba trường hợp sau:

Giá trị của x và y nếu x ≠ 1 và y ≠ 1 (giữa hai số cách nhau một khoảng trắng).
Giá trị của x nếu y = 1 hoặc giá trị của y nếu x = 1.
Ghi số 1 nếu x = 1 và y = 1.

Ví dụ:

KHAICAN.INP	KHAICAN.OUT
`20`	`2 5`
`25`	`5`
`7`	`7`

Ràng buộc:

Có 80% số test tương ứng với 80% số điểm của bài thỏa mãn n ≤ 10³;
Có 20% số test tương ứng với 20% số điểm của bài thỏa mãn 10³ < n ≤ 10⁹.

Bài 2. Cặp số chẵn

Sau khi học về tính chẵn lẻ của số tự nhiên, thầy giáo đã giao cho các bạn trong lớp về nhà làm bài tập như sau:

Cho một số nguyên dương N. Hãy đếm xem có bao nhiêu cặp số (A, B) thỏa mãn điều kiện sau:

1 ≤ A ≤ B ≤ N;
A × B là số chẵn.

Yêu cầu: Viết chương trình đếm số bộ (A, B) giúp cho các bạn.

Dữ liệu vào: Từ bàn phím một số nguyên dương N (N ≤ 10⁹).

Kết quả: Ghi ra màn hình một số nguyên duy nhất là số cặp số thỏa mãn.

Ví dụ:

CAPSOCHAN.INP	CAPSOCHAN.OUT
`5`	`9`

Giải thích: Các bộ số thỏa mãn: (1,2), (1,4), (2,2), (2,3), (2,4), (2,5), (3,4), (4,4), (4,5).

Ràng buộc:

Có 60% số test tương ứng với 60% số điểm của bài thỏa mãn N ≤ 10³.
Có 40% số test tương ứng với 40% số điểm của bài thỏa mãn N ≤ 10⁹.

Bài 3. Đoạn tăng

Cho một dãy số nguyên a gồm N phần tử a₁, a₂, …, a_N. Một đoạn con của dãy số gồm các phần tử liên tiếp nhau trong dãy, độ dài đoạn con là số lượng phần tử trong đoạn con đó.

Yêu cầu: Hãy tìm đoạn con dài nhất trong dãy a thỏa mãn tính chất sau:

Đoạn con đó chỉ gồm các phần tử có giá trị chẵn hoặc chỉ gồm các phần tử có giá trị lẻ.
Các phần tử có giá trị tăng dần.

Dữ liệu vào: Từ bàn phím gồm:

Dòng thứ nhất: Số nguyên N (1 ≤ N ≤ 10⁶) là số lượng phần tử của dãy a.
Dòng thứ hai: N số nguyên a₁, a₂, …, a_N (|aᵢ| ≤ 10⁹ với 1 ≤ i ≤ N). Các số cách nhau một khoảng trắng.

Kết quả: Ghi ra màn hình một số nguyên duy nhất là độ dài của đoạn con tìm được.

Ví dụ:

DOANTANG.INP	DOANTANG.OUT
`9` `2 1 3 5 5 6 3 7 6`	`3`

Ràng buộc:

Có 80% số test tương ứng với 80% số điểm của bài thỏa mãn N ≤ 5000;
Có 20% số test tương ứng với 20% số điểm của bài thỏa mãn 5000 < N ≤ 10⁶.

Bài 4. Cái túi

Lại nói về câu truyện Cây khế năm ấy, sau khi ăn một quả khế, Đại bàng nói với cậu chủ “Ăn một quả trả một cục vàng, may túi ba gang mang đi mà đựng”. Đại bàng hứa sẽ chở cậu chủ K chuyến đến hòn đảo nhỏ xa xôi, trên hòn đảo có N đồ vật được đánh số từ 1 đến N từ ngoài cửa hang vào trong, đồ vật thứ i có khối lượng aᵢ. Cậu chủ phải lấy lần lượt các đồ vật từ ngoài vào trong. Công việc của cậu chủ là phải may một chiếc túi đựng được tổng khối lượng M càng nhỏ càng tốt sao cho sau K chuyến có thể lấy được hết N đồ vật trên đảo.

Yêu cầu: Hãy tìm giá trị M nhỏ nhất.

Dữ liệu vào: Từ bàn phím gồm hai dòng:

Dòng thứ nhất: Hai số nguyên dương N, K, giữa hai số cách nhau một khoảng trắng (1 ≤ N ≤ 10⁵; K ≤ N).
Dòng thứ hai: N số nguyên dương a₁, a₂, …, a_N (aᵢ ≤ 10⁹ với 1 ≤ i ≤ N), các số cách nhau một khoảng trắng.

Kết quả: Ghi ra màn hình một số nguyên duy nhất là giá trị M nhỏ nhất tìm được.

Ví dụ:

CAITUI.INP	CAITUI.OUT
`6 3` `5 2 3 1 4 2`	`6`

Ràng buộc:

Có 60% số test tương ứng với 60% số điểm của bài thỏa mãn N ≤ 5000; aᵢ ≤ 1000;
Có 40% số test tương ứng với 40% số điểm của bài không có thêm ràng buộc gì.

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