Tuyển tập 16 Đề thi HSG môn Tin học Lớp 10 (Có đáp án chi tiết)

Tuyển tập 16 Đề thi HSG môn Tin học Lớp 10 (Có đáp án chi tiết) - DeThi.edu.vn

DeThi.edu.vn

ĐỀ SỐ 1

Tổng quan về đề thi Bài Tên bài File chương trình File dữ liệu File kết quả 1 Đường đi sắc màu CPATH.* CPATH.INP CPATH.OUT 2 Khôi phục trọng số STREE.* STREE.INP STREE.OUT 3 Hội thao học sinh FESTIVAL.* FESTIVAL.INP FESTIVAL.OUT Dấu * thay thế bởi PAS hoặc CPP tương ứng với ngôn ngữ lập trình Pascal hoặc C++.

Bài 1. Đường đi sắc màu (7,0 điểm) Alice là một cô bé rất thích các màu sắc. Một hôm cô đang lang thang trên các con phố của TP HCM thì gặp một con đường gạch dài gồm ? viên gạch liên tiếp, đánh số từ 1 đến ?, viên gạch thứ ? có màu là một số nguyên dương ??≤?. Cô muốn đi qua con đường này bằng cách: chọn một màu ?, sau đó bắt đầu đi từ viên gạch đầu tiên có màu ?, chỉ được bước sang các viên gạch có màu ? kế tiếp và kết thúc lộ trình ở viên gạch cuối cùng có màu ?. Vì các viên gạch có màu ? có thể không nằm liên tiếp nhau mà có thể nằm cách nhau một khoảng và việc đi một bước quá dài có thể khiến Alice vấp ngã, nên Alice muốn chọn một lộ trình sao cho khoảng cách giữa hai viên gạch liên tiếp mà cô đi là nhỏ nhất có thể. Nói cách khác, Alice muốn chọn một số chỉ số (?1,?2,…,??) (1 ≤?≤?) sao cho: - 1 ≤?1 < ?2 < ⋯< ??≤?. - ??1 = ??2 = ⋯= ??? - Không tồn tại 1 ≤?< ?1 mà ??= ??1. - Không tồn tại ?≥?> ?? mà ??= ???.

- Giá trị ?= max (0,?2 ― ?1,?3 ― ?2,…,??― ??―1) là nhỏ nhất có thể. Yêu cầu: Biết rằng Alice được phép chọn ra một viên gạch bất kì và thay đổi màu của nó thành một màu ? từ ý với 1 ≤?≤?. Hãy tính giá trị ? nhỏ nhất nếu như Alice có thể tùy ý thay đổi màu của tối đa một viên gạch bất kì. Dữ liệu Vào từ file văn bản CPATH.INP: - Dòng đầu tiên chứa hai số nguyên dương ?,? thể hiện số lượng viên gạch và số lượng màu (1 ≤?,?≤2 × 105).

SỞ GIÁO DỤC VÀ ĐÀO TẠO

THÀNH PHỐ HỒ CHÍ MINH

TRƯỜNG THPT CHUYÊN

LÊ HỒNG PHONG

KỲ THI OLYMPIC TRUYỀN THỐNG 30 THÁNG 4 - LẦN THỨ XXIX - NĂM 2025 MÔN: TIN HỌC - KHỐI: 10 Thời gian: 180 phút (không kể thời gian giao đề)

DeThi.edu.vn

Tuyển tập 16 Đề thi HSG môn Tin học Lớp 10 (Có đáp án chi tiết) - DeThi.edu.vn

DeThi.edu.vn

- Dòng thứ hai chứa ? số nguyên dương, số thứ ? là giá trị ?? thể hiện màu của viên gach thứ ? (1 ≤??≤?). Các số trên cùng một dòng cách nhau bởi dấu cách. Kết quả Ghi ra file văn bản CPATH.OUT: - Một số nguyên duy nhất thể hiện giá trị ? nhỏ nhất nếu Alice có thể đổi màu của tối đa một viên gạch. Ví dụ

CPATH. INP CPATH.OUT Giải thích

6 2 1 2 2 1 2 1

1 Alice đổi màu viên gạch thứ 4 thành màu 2. Sau đó chọn các chỉ số (2,3,4,5) với cùng màu 2 cho khoảng cách của bước lớn nhất là 1.

5 2 1 2 2 1 2

0 Alice đổi màu viên gạch thứ 4 thành màu 2. Sau đó chỉ cần chọn một chỉ số (1) với màu 1 và không phải bước thêm. Khoảng cách của bước lớn nhất là 0.

Chấm điểm Mỗi subtask bao gồm nhiều test đơn, điểm của thí sinh được tính theo từng test đơn. - Subtask 1 (30% số điẻm): ?≤100;?≤3. - Subtask 2 (30% số điểm): ?,?≤100. - Subtask ? (30% số điểm): ??= (? mod ?) + 1,∀?= 1,2,…,?. - Subtask 4 (10% số diểm): Không có ràng buộc nào thêm. Bài 2. Khôi phục trọng số (7,0 điểm) Bob là một thành viên tích cực của câu lạc bộ LHP-IT. Cậu có niểm đam mê nghiên cứu đối với cấu trúc dữ liệu dạng cây trong đồ thị. Lần này, cậu đang quan sát một cây thú vị gồm ? đỉnh, đánh số từ 1 đến ? và ?―1 cạnh, đánh số từ 1 đến ?―1. Cạnh thứ ?(1 ≤?≤?―1) nối đỉnh ?? với đỉnh ?? có trọng số ?? không âm (??< 220). Để đảm bảo khỏi quên, cậu đã đặt tên cây này là STREE, viết thông tin về cây này lên một mẩu giấy và cất nó trong ngăn kéo. Một hôm, Bob lấy mẩu giấy ra để xem lại cây này thì phát hiện ra trọng số đã bị nhòe do không khí ẩm mốc, còn phần còn lại về số lượng đỉnh và thông tin các cạnh thì vẫn có thể đọc được. Cậu mong muốn tìm lại được trọng số của các cạnh trên cây. Bob ngồi ngắm nghĩ

DeThi.edu.vn