HO&#803;C CHUYÊN TIN ONLINE A - Z!

Tài liệu hướng dẫn giải chi tiết, code mẫu, chấm online Đề thi HSG9, tin học trẻ, tuyển sinh 10 chuyên tin các năm

Đề thi Olympic Tin học cấp THCS trường THPT chuyên Hạ Long năm học 2024-2025

Mời các bạn tham khảo

Đề thi Olympic Tin học cấp THCS trường THPT chuyên Hạ Long năm học 2024-2025

Xem thêm

https://www.chuyentin.pro/2024/07/goi-luyen-giai-e-tin-hoc-tre-toan-quoc.html

Chủ Nhật, 30 tháng 3, 2025

Giải bài Tổng dãy số, Đề thi tin học trẻ toàn quốc bảng A năm 2024-2025, vòng sơ khảo tự do lần 1

Hướng dẫn giải, code mẫu của đề đã được cập nhật trong tài liệu “Bộ đề ôn thi tin học trẻ bảng A quốc gia”

Đề bài

Cho dãy số có quy luật sau:

1, 2, 3, 6, 5, 4, 7, 8, 9, 12, 11, 10, 13, 14, 15, 18, 17, 16, ...

Yêu cầu: Cho hai số nguyên dương l, r. Hãy tính tổng các số từ vị trí l đến vị trí r của dãy số trên.

Dữ liệu: Gồm hai số tự nhiên l và r (1 ≤ l ≤ r ≤ 10⁸). Mỗi số trên một dòng.

Kết quả:Gồm một số tự nhiên là kết quả của bài toán.

LỜI GIẢI

1. Nhận xét quy luật của dãy số

Dãy số được chia thành các nhóm 6 phần tử có quy luật:

Mỗi nhóm gồm 6 số và có thứ tự như sau:

Nhóm 1: 1, 2, 3, 6, 5, 4
Nhóm 2: 7, 8, 9, 12, 11, 10
Nhóm 3: 13, 14, 15, 18, 17, 16

Mỗi nhóm bắt đầu bằng một số mới tăng thêm 6 đơn vị so với nhóm trước.

2. Xây dựng công thức tính tổng dãy số

Muốn tính tổng từ 1 đến n, ta thực hiện các bước sau:

1. Tìm số x lớn nhất chia hết cho 6 và nhỏ hơn hoặc bằng n:

o x = (n // 6) * 6

2. Tính tổng các số từ 1 đến x bằng công thức:

o S = x * (x + 1) / 2

3. Xử lý các số dư còn lại, dựa vào phần dư của n khi chia 6:

o Nếu n chia 6 dư 1, cộng thêm n

o Nếu n chia 6 dư 2, cộng thêm (n - 1) + n

o Nếu n chia 6 dư 3, cộng thêm (n - 2) + (n - 1) + n

o Nếu n chia 6 dư 4, cộng thêm (n - 3) + (n - 2) + (n-1) + (n + 2)

o Nếu n chia 6 dư 5, cộng thêm (n - 4) + (n - 3) + (n - 2) + n + (n + 1)

3. Tính tổng từ l đến r

Tính tổng từ 1 đến r: tong(r)
Tính tổng từ 1 đến l - 1: tong(l - 1)
Kết quả cần tìm: tong(r) - tong(l - 1)

Độ phức tạp thuật toán

Thuật toán chỉ sử dụng phép chia, nhân và một số phép toán điều kiện.
Thời gian thực hiện là O(1), tức là chạy nhanh ngay cả khi r lên đến 10^8.

CODE PYTHON

def tong(n):

x = (n // 6) * 6

s = x * (x + 1) // 2

#print(x,s)

if n % 6 == 1:

s += n

elif n % 6 == 2:

s += n - 1 + n

elif n % 6 == 3:

s += n - 2 + n - 1 + n

elif n % 6 == 4:

s += n - 3 + n - 2 + n-1 + n + 2

elif n % 6 == 5:

s += n - 4 + n - 3 + n - 2 + n + n + 1

return s

l = int(input())

r = int(input())

print(tong(r) - tong(l - 1))

CODE SCRATCH

Định nghĩa KHOI(N)

Đặt X thành (N / 6) * 6

Đặt S thành X * (X + 1) / 2

Nếu N chia lấy dư 6 = 1 thì

Đặt S thành S + N

Nếu N chia lấy dư 6 = 2 thì

Đặt S thành S + (N - 1 + N)

Nếu N chia lấy dư 6 = 3 thì

Đặt S thành S + (N - 2 + N - 1 + N)

Nếu N chia lấy dư 6 = 4 thì

Đặt S thành S + (N - 3 + N - 2 + N - 1 + N + 2)

Nếu N chia lấy dư 6 = 5 thì

Đặt S thành S + (N - 4 + N - 3 + N - 2 + N + N + 1)

Đặt KQ thành S

Khi bấm vào cờ xanh

Hỏi L = ? và đợi

Đặt L thành trả lời

Hỏi R = ? và đợi

Đặt R thành trả lời

KHOI R

Đặt S1 thành KQ

KHOI L - 1

Đặt S2 thành KQ

Đặt K thành S1 - S2

Nói K

Thứ Năm, 27 tháng 3, 2025

Đề thi Học sinh giỏi cấp THPT tỉnh Phú Yên năm học 2024-2025

Mời các bạn tham khảo

Đề thi Học sinh giỏi cấp THPT tỉnh Phú Yên năm học 2024-2025

Xem thêm

Tài liệu hướng dẫn giải chi tiết, code mẫu, chấm online Đề thi HSG9, tin học trẻ, tuyển sinh 10 chuyên tin các năm

Tài liệu hướng dẫn giải chi tiết, code mẫu, chấm online Đề thi HSG9, tin học trẻ, tuyển sinh 10 chuyên tin các năm

Đề thi Học sinh giỏi cấp tỉnh lớp 10 tỉnh Thái Nguyên năm học 2024-2025

Mời các bạn tham khảo

Đề thi Học sinh giỏi cấp tỉnh lớp 10 tỉnh Thái Nguyên năm học 2024-2025

Xem thêm

Tài liệu hướng dẫn giải chi tiết, code mẫu, chấm online Đề thi HSG9, tin học trẻ, tuyển sinh 10 chuyên tin các năm

Đề thi Huế-ICT bảng THPT không chuyên, vòng chung kết năm học 2024 - 2025

Mời các bạn tham khảo

Đề thi Huế-ICT bảng THPT không chuyên, vòng chung kết năm học 2024 - 2025

Xem thêm

Tài liệu hướng dẫn giải chi tiết, code mẫu, chấm online Đề thi HSG9, tin học trẻ, tuyển sinh 10 chuyên tin các năm

Thứ Hai, 24 tháng 3, 2025

Đề thi Tin học trẻ Bảng A thành phố Tân An năm học 2024-2025

Mời các bạn tham khảo

Đề thi Tin học trẻ Bảng A thành phố Tân An năm học 2024-2025

Xem thêm

Tài liệu hướng dẫn giải chi tiết, code mẫu, chấm online Đề thi HSG9, tin học trẻ, tuyển sinh 10 chuyên tin các năm

Đề thi Tin học trẻ Bảng A huyện Hòa Vang năm học 2024-2025

Mời các bạn tham khảo

Đề thi Tin học trẻ Bảng A huyện Hòa Vang năm học 2024-2025

Xem thêm

Tài liệu hướng dẫn giải chi tiết, code mẫu, chấm online Đề thi HSG9, tin học trẻ, tuyển sinh 10 chuyên tin các năm

Đề thi Huế ICT vòng chung kết bảng THCS năm 2024-2025

Mời các bạn tham khảo

Đề thi Huế ICT vòng chung kết bảng THCS năm 2024-2025

Xem thêm

Tài liệu hướng dẫn giải chi tiết, code mẫu, chấm online Đề thi HSG9, tin học trẻ, tuyển sinh 10 chuyên tin các năm

Thứ Bảy, 22 tháng 3, 2025

Đề thi Tin học trẻ Bảng A thành phố Đông Triều năm học 2024-2025

Mời các bạn tham khảo

Đề thi Tin học trẻ Bảng A thành phố Đông Triều năm học 2024-2025

Xem thêm