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”

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

Đề 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