HSG THCS Phú Yên 2022-2023

SỞ GIÁO DỤC VÀ ĐÀO TẠO TỈNH PHÚ YÊN ĐỀ CHÍNH THỨC
(Đề thi có 04 trang)

KỲ THI CHỌN HỌC SINH GIỎI THCS CẤP TỈNH Năm học 2022 - 2023
Môn: Tin học - Ngày thi: 07/3/2023
Thời gian: 150 phút (không kể thời gian phát đề)

---

Tổng quan bài thi

Tên bài	File chương trình	File dữ liệu	File kết quả	Điểm
Bài 1	BAI1.*	BAI1.INP	BAI1.OUT	5,0
Bài 2	BAI2.*	BAI2.INP	BAI2.OUT	5,0
Bài 3	BAI3.*	BAI3.INP	BAI3.OUT	4,0
Bài 4	BAI4.*	BAI4.INP	BAI4.OUT	6,0

Dấu * tương ứng là PAS đối với Pascal hoặc CPP đối với C++ hoặc PY đối với Python. Học sinh phải đặt đúng tên tệp chương trình, tệp dữ liệu, tệp kết quả như đã quy định ở phần tổng quan bài thi.

Bài 1. Đổi sang hệ La Mã (5,0 điểm)

Trong thời cổ đại và trung đại người ta sử dụng số La Mã. Hiện nay các bạn có thể thấy số La Mã vẫn được sử dụng rất phổ biến trong những bản kê được đánh số, mặt đồng hồ, đánh số thứ tự trong các văn bản …

• Có 7 chữ số La Mã cơ bản đó là:

Ký tự hệ La Mã	I	V	X	L	C	D	M
Giá trị	1	5	10	50	100	500	1000

Nhiều ký tự chữ số La Mã cơ bản có thể được kết hợp lại với nhau để chỉ các số với các giá trị các chúng. Thông thường được quy định các chữ số I, X, C, M không được lặp lại quá ba lần liên tiếp (được xuất hiện 2 hoặc 3 lần trong số). Chữ số I, X, C, M được lặp lại 2 hoặc 3 lần biểu thị giá trị gấp 2 hoặc gấp 3.

Ví dụ:

• Chữ số I: I = 1; II = 2; III = 3
• Chữ số X: X = 10; XX = 20; XXX = 30
• Chữ số C: C = 100; CC = 200; CCC = 300
• Chữ số M: M = 1000; MM = 2000; MMM = 3000

Các chữ số V, L, D không được lặp lại quá một lần liên tiếp (chỉ được xuất hiện 1 lần duy nhất trong số).

• Có 6 nhóm chữ số đặc biệt:

Ký tự hệ La Mã	IV	IX	XL	XC	CD	CM
Giá trị	4	9	40	90	400	900

Như vậy sử dụng các chữ số cơ bản I, V, X, L, C, D, M và nhóm chữ số đặc biệt IV, IX, XL, XC, CM để viết số La Mã. Tính từ trái sang phải giá trị của các chữ số và nhóm chữ số giảm dần.

Ví dụ: III = 3; VIII = 8; XXXII = 32; XLV = 45; MMMDCCCLXXXVIII = 3888; MMMCMXCIX = 3999.

Lưu ý: I chỉ có thể đứng trước V hoặc X, X chỉ có thể đứng trước L hoặc C, C chỉ có thể đứng trước D hoặc M.

• Quy tắc viết chữ số La Mã
  • Chữ số thêm vào bên phải là cộng thêm vào số gốc (chữ số thêm nhỏ hơn hoặc bằng chữ số gốc) và không được thêm quá 3 lần số. Nghĩa là lấy chữ số đầu tiên cộng với các chữ số được thêm phía sau ra chữ số đó.
  • Chữ số thêm vào bên trái chữ số gốc là trừ đi (chữ số thêm phía bên trái phải nhỏ hơn chữ số gốc) hay còn hiểu là lấy số gốc (là số phía bên phải) trừ đi những số đứng bên trái nó sẽ ra chữ số.

Ví dụ:

• I = 1; V = 5; IV = 5 − 1 = 4; VI = 5 + 1 = 6

• X = 10; XI = 10 + 1 = 11; XII = 10 + 2

• L = 50; LI = 50 + 1 = 51; LX = 50 + 10 = 60;

• C = 100; CI = 101; CX = 110; CV = 105

• X = 10; L = 50 ⇒ XL = 50 − 10 = 40; LX = 50 + 10 = 60

• C = 100; M = 1000 ⇒ CM = 1000 − 100 = 900; MC = 1000 + 100 = 1100

• Còn với những số lớn thì sẽ đọc tính từ trái sang phải giá trị của các chữ số và nhóm chữ số giảm dần. Các bạn cần xác định các chữ số hàng ngàn, hàng trăm, hàng chục và hàng đơn vị giống như đọc số tự nhiên.

Yêu cầu: Cho một số tự nhiên N (số hệ thập phân), N < 4000 hãy chuyển số N từ hệ Ả rập sang dạng biểu diễn bằng hệ La Mã.

Dữ liệu vào: cho từ tệp văn bản BAI1.INP, gồm nhiều dòng, mỗi dòng là một số tự nhiên trong hệ đếm thập phân. Dữ liệu cho đảm bảo hợp lệ.

Dữ liệu ra: ghi vào tệp văn bản BAI1.OUT, gồm nhiều dòng, mỗi dòng là số của hệ La Mã tương ứng số tự nhiên đã cho.

Ví dụ:

BAI1.INP	BAI1.OUT
3 19 3999	III XIX MMMCMXCIX

Bài 2. Đồng điệu với dãy mẫu (5,0 điểm)

Hai dãy số A_N = a₁, a₂, …, aₙ và B_N = b₁, b₂, …, bₙ. Dãy B_N được gọi là đồng điệu với dãy A_N khi và chỉ khi b₁ = k + a₁, b₂ = k + a₂, …, bₙ = k + aₙ với k là số nguyên. Chẳng hạn, dãy B₆ = 5, 4, 8, 7, 10, 9 là đồng điệu của dãy A₆ = 2, 1, 5, 4, 7, 6.

Yêu cầu: Cho dãy A_N gồm N (với 3 ≤ N ≤ 100) số nguyên có giá trị trong khoảng từ 1 đến 100 gọi là dãy mẫu. Dãy B_M gồm M (với N < M ≤ 500) số nguyên có giá trị trong khoảng từ 1 đến 10⁶.

Hãy tìm số lượng dãy con của dãy B_M đồng điệu với dãy A_N. Lưu ý dãy con là một đoạn gồm N phần tử liên tục nhau. Các dãy đồng điệu với dãy mẫu là rời nhau.

Dữ liệu vào: cho từ tệp văn bản BAI2.INP, gồm 02 dòng:

• Dòng đầu là số N và N số nguyên của dãy A.
• Dòng thứ hai là M số nguyên của dãy B.

Dữ liệu ra: ghi vào tệp văn bản BAI2.OUT, gồm một số chỉ số lượng dãy con trong dãy B đồng điệu với dãy A.

Ví dụ:

Test	BAI2.INP	BAI2.OUT
01	3 1 2 3 7 4 5 3 4 3 6 1 2	0
02	3 1 2 3 67 6 7 5 4 1 2 3 4 5 23 4 5 3 5 6 12 56 57 58 59 13 14 13 14	2
03	6 2 1 5 4 7 6 67 6 7 5 4 8 7 10 9 4 5 23 4 5 3 5 6 12 56 57 58 59 13 14 13 14	1

(Trong đề gốc, các dãy con đồng điệu được gạch chân: ở test 02 là “1 2 3” và “56 57 58”; ở test 03 là “5 4 8 7 10 9”.)

Bài 3. Cụm biểu thức (4,0 điểm)

Một cụm trong một biểu thức toán học là đoạn nằm giữa hai dấu đóng và mở ngoặc đơn (). Với mỗi biểu thức cho trước hãy tách các cụm của biểu thức đó.

Dữ liệu vào: cho từ tệp văn bản BAI3.INP chứa một dòng kiểu xâu kí tự là biểu thức cần xử lí. Dữ liệu cho đảm bảo hợp lệ.

Dữ liệu ra: ghi vào tệp văn bản BAI3.OUT dòng đầu tiên ghi d là số lượng cụm. Tiếp đến là d dòng, mỗi dòng ghi một cụm được tách từ biểu thức.

Ví dụ:

Test	BAI3.INP	BAI3.OUT
01	x*(a+4)*(b-3)/(c+2)	3 (a+4) (b-3) (c+2)
02	x*(a+4)*((b-3)/(c+2))	4 (a+4) (b-3) (c+2) ((b-3)/(c+2))

Bài 4. Tìm đội thi (6,0 điểm)

Nhân kỷ niệm ngày thành lập Đoàn Thanh niên Cộng sản Hồ Chí Minh, Đoàn trường tổ chức cuộc thi tìm hiểu về Đoàn bằng hình thức trả lời các câu hỏi trắc nghiệm trực tuyến trên hệ thống website của nhà trường. Biết rằng có N bạn đoàn viên được đánh số báo danh theo thứ tự từ 1 đến N cùng tham gia cuộc thi, mỗi bạn trả lời được số câu trả lời đúng khác nhau trong khoảng 0 đến 100. Ban tổ chức muốn tìm ra một đội gồm K (K < N) bạn đoàn viên có số báo danh liên tiếp nhau có thành tích tốt nhất (với tổng số câu trả lời đúng của cả đội là nhiều nhất) để trao thưởng và cử tham gia cuộc thi cấp tỉnh. Bạn hãy giúp ban tổ chức chọn ra đội đó. Nếu có nhiều đội cùng thành tích thì chọn đội có người có số báo danh sau cùng là lớn nhất.

Dữ liệu vào: từ tệp văn bản BAI4.INP gồm 02 dòng:

• Dòng 1: chứa 2 số nguyên dương N và K (1 ≤ N ≤ 500, 1 ≤ K ≤ 255).
• Dòng 2: chứa N số tự nhiên trong khoảng từ 0 đến 100, tương ứng là số câu trả lời đúng của từng bạn đoàn viên.

Dữ liệu ra: ghi vào tệp văn bản BAI4.OUT gồm 02 dòng như sau:

• Dòng 1: số S là tổng số câu trả lời đúng nhiều nhất của đội gồm K bạn đoàn viên tìm được.
• Dòng 2: là số báo danh tương ứng K bạn liên tiếp được chọn.

Ví dụ:

BAI4.INP	BAI4.OUT	Giải thích
10 3 2 5 2 7 9 3 6 4 8 7	19 8 9 10	K = 3; tìm đội gồm 3 bạn đoàn viên liên tiếp có thành tích tốt nhất. + Đội gồm các bạn có số báo danh là: 4, 5, 6, có số câu trả lời đúng là 19. + Đội gồm các bạn có số báo danh là: 8, 9, 10 có số câu trả lời đúng là 19. Vậy: Đội được chọn là các bạn có số báo danh là: 8, 9, 10

Các số trên cùng một dòng cách nhau một khoảng trống.

---

Thí sinh không được sử dụng tài liệu. Giám thị coi thi không giải thích gì thêm.