HSG lớp 9 Lâm Đồng 2022-2023

ĐỀ THI HỌC SINH GIỎI LỚP 9 TỈNH LÂM ĐỒNG Năm học 2022 - 2023

MÔN TIN HỌC Ngày thi: 03/03/2023
Thời gian: 150 phút

---

Tổng quan đề thi

Bài	Tên bài	File CT	File input	File output	Điểm
1	Tính tổng	CAU1.*	CAU1.INP	CAU1.OUT	5
2	Giả thuyết Goldbach	CAU2.*	CAU2.INP	CAU2.OUT	5
3	Dãy số	CAU3.*	CAU3.INP	CAU3.OUT	5
4	Chương trình nghệ thuật	CAU4.*	CAU4.INP	CAU4.OUT	5

Dấu * được thay thế bởi PAS, CPP hoặc PY của ngôn ngữ lập trình được sử dụng tương ứng là Pascal, C++ hoặc Python.

Bài 1. Tính tổng (5 điểm)

Yêu cầu: cho số tự nhiên n. Viết chương trình tính tổng:

1·2·3 + 2·3·4 + 3·4·5 + … + (n − 1)·n·(n + 1)

Input: ghi số tự nhiên n (2 ≤ n ≤ 10²⁰).

Output: ghi số nguyên duy nhất là kết quả cần tìm.

CAU1.INP	CAU1.OUT	Giải thích
3	30	1·2·3 + 2·3·4 = 30
5	210	1·2·3 + 2·3·4 + 3·4·5 + 4·5·6 = 210

Bài 2. Giả thuyết Goldbach (5 điểm)

Giả thuyết Goldbach do nhà toán học người Đức Christian Goldbach (1690 - 1764) nêu ra vào năm 1742 trong một lá thư gửi tới Leonhard Euler, là một trong những bài toán lâu đời và nổi tiếng còn chưa giải được trong lý thuyết số nói riêng và toán học nói chung.

Giả thuyết phỏng đoán rằng: “Mỗi số tự nhiên chẵn lớn hơn 2 có thể biểu diễn bằng tổng của hai số nguyên tố”.

Yêu cầu: viết chương trình để kiểm tra kết quả phỏng đoán của Goldbach.

Input:

• Dòng đầu tiên ghi số tự nhiên n (n ≤ 200) là số test cần kiểm tra.
• n dòng tiếp theo, mỗi dòng ghi một số tự nhiên chẵn k (2 ≤ k ≤ 10¹²).

Output: gồm n dòng, mỗi dòng ứng với một test. Trên mỗi dòng, ghi hai số nguyên tố có tổng bằng số đã cho tương ứng, hai số ghi theo thứ tự tăng dần và cách nhau một khoảng trắng, nếu có nhiều kết quả thì ghi hai số có giá trị tuyệt đối của hiệu lớn nhất hoặc ghi “NO” nếu không tìm được.

Ví dụ:

CAU2.INP	CAU2.OUT	Giải thích
2 14 24	3 11 5 19	14 = 3 + 11 = 7 + 7 24 = 5 + 19 = 7 + 17 = 11 + 13

Bài 3. Dãy số (5 điểm)

Cho dãy số A gồm N phần tử là các số nguyên dương a₁, a₂, …, a_N. Thực hiện lần lượt Q thao tác trên dãy số đó, thao tác thứ i sẽ có một trong hai loại như sau:

• Loại 1: 1 pᵢ mᵢ xᵢ tăng giá trị phần tử tại vị trí pᵢ tới vị trí mᵢ của dãy số A thêm xᵢ đơn vị.
• Loại 2: 2 uᵢ vᵢ, tính tổng các phần tử của dãy số A từ vị trí uᵢ tới vị trí vᵢ.

Yêu cầu: Viết chương trình thực hiện Q thao tác và ghi ra kết quả của các thao tác Loại 2.

Input:

• Dòng đầu tiên ghi hai số nguyên dương N, Q (0 < N, Q ≤ 10⁵).
• Dòng thứ hai là một dãy số gồm N số nguyên dương aᵢ (0 < aᵢ ≤ 10¹²), các số nằm trên một dòng và cách nhau một khoảng trắng.
• Q dòng tiếp theo (từ dòng thứ 3 trở đi): với dòng thứ i số đầu tiên là 1 hoặc 2.
  • Nếu số 1 thì theo sau là 3 số nguyên dương pᵢ mᵢ và xᵢ (1 ≤ pᵢ ≤ mᵢ ≤ N; 1 ≤ xᵢ ≤ 10⁹). Các số nằm trên một dòng và cách nhau một khoảng trắng.
  • Nếu số 2 thì theo sau là 2 số nguyên dương uᵢ vᵢ (1 ≤ uᵢ ≤ vᵢ ≤ N). Các số nằm trên một dòng và cách nhau một khoảng trắng.

Output: gồm nhiều dòng, mỗi dòng ghi kết quả tương ứng với thao tác loại 2.

Ví dụ:

CAU3.INP	CAU3.OUT
8 4 5 6 9 1 2 1 10 15 1 4 7 15 2 3 8 1 2 5 17 2 1 6	98 137

Bài 4. Chương trình nghệ thuật (5 điểm)

Trong một chương trình nghệ thuật diễn ra liên tục trong n giờ. Công ty X có danh sách của m nghệ sĩ khác nhau có thể thuê để biểu diễn. Thời điểm bắt đầu biểu diễn được tính bằng 0.

Để đơn giản trong quản lí và sắp xếp, các nghệ sĩ được đánh số theo thứ tự từ 1 tới m, nghệ sĩ thứ i (với i = 1, 2, …, m) biểu diễn trong thời điểm sᵢ đến thời điểm tᵢ (0 ≤ sᵢ < tᵢ ≤ n) với tiền công là cᵢ (0 ≤ cᵢ ≤ 10⁶).

Yêu cầu: viết chương trình thuê các nghệ sĩ để bất cứ thời điểm nào cũng luôn có ít nhất một nghệ sĩ biểu diễn đồng thời chi phí thuê là nhỏ nhất.

Input:

• Dòng đầu tiên chứa 2 số nguyên n và m (1 ≤ n, m ≤ 400).
• m dòng tiếp theo, mỗi dòng chứa ba số nguyên không âm sᵢ, tᵢ và cᵢ.

Output: một số nguyên là chi phí thuê nhỏ nhất (dữ liệu được cho đảm bảo luôn có kết quả).

Ví dụ:

CAU4.INP	CAU4.OUT
9 5 0 5 25 1 3 18 3 7 21 4 6 38 7 9 20	66