Tìm Phần Thưởng (THUONG) (HSG9 TP Đà Nẵng 2018-2019 – Bài 3)

Nguồn: HSG lớp 9 TP Đà Nẵng 2018-2019 – Bài 3 Độ khó: Trung bình Tìm quy luật Ước số Toán học

Đề bài

Câu 3. Tìm phần thưởng (4 điểm) – Đề thi HSG Tin học lớp 9 TP Đà Nẵng năm học 2018-2019

Trong Học kỳ I vừa qua, Tý đạt được danh hiệu học sinh giỏi nên được bố thưởng. Biết Tý là học sinh rất đam mê Toán và Tin học nên bố muốn thử thách Tý bằng một trò chơi có thưởng như sau:

Bố có rất nhiều hộp hình khối lập phương giống nhau xếp thành một hàng thẳng và được đánh số ký hiệu bằng các số tự nhiên lẻ bắt đầu từ $1; 3; 5; \ldots$ Trong các hộp đó có duy nhất 1 hộp đựng phần thưởng, các hộp khác là hộp rỗng. Bố cho Tý biết hộp đựng phần thưởng là hộp chính giữa của một đoạn dài nhất (ít nhất là 3 hộp liên tiếp) có tổng các số ký hiệu ghi trên các hộp bằng số $m$.

Yêu cầu: Với số $m$ cho trước, hãy tìm số ký hiệu của hộp có chứa phần thưởng.

Dữ liệu vào: Đọc ở file văn bản THUONG.INP số nguyên dương $m$ $(m \le 10^{16})$.

Dữ liệu ra: Ghi ra file văn bản THUONG.OUT một số $k$ là số ký hiệu của hộp có chứa phần thưởng.

Trên hệ thống chấm online thì đọc dữ liệu từ bàn phím và in ra màn hình (stdin/stdout) như bình thường nhé. Giới hạn thời gian: 1 giây.

THUONG.INP

45

THUONG.OUT

9

Giải thích: Các hộp được đánh số ký hiệu là $1; 3; 5; 7; 9; 11; 13; 15; 17; 19; 21; 23; 25; \ldots$ Đoạn dài nhất có tổng các số ký hiệu ghi trên hộp bằng $45$ là các hộp có số ký hiệu $5; 7; 9; 11; 13$. Do đó hộp cần tìm có số ký hiệu là $9$.

Lời mở đầu

Các bạn cố gắng giúp Tý nào, kẻo chọn sai là Tý chỉ "còn cái nịt" nhé các bạn 😆. Bài này nằm trong đề thi học sinh giỏi Tin học lớp 9 TP Đà Nẵng, mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.

Trước khi đi vào vấn đề chính, các bạn nhớ giúp mình điều này: với giới hạn 1 giây, muốn không bị TLE thì toàn bài chỉ nên lặp khoảng $(3 \div 5) \cdot 10^7$ lần là an toàn, tệ nhất là $10^8$ (lúc này thì hên xui nhé). Ngưỡng này là cho C/C++, còn Python, Java, C#... chạy chậm hơn thì ngưỡng phải thấp hơn.

Đề hơi "văn vở" một chút nên mình nói lại cho gọn: có dãy số lẻ $1, 3, 5, 7, \ldots$, tìm một đoạn liên tiếp dài nhất (ít nhất 3 số) có tổng bằng $m$, rồi in ra số ở chính giữa của đoạn đó. Với $m = 45$ thì có 2 đoạn có tổng bằng 45 với độ dài $\ge 3$:

• $13 + 15 + 17 = 45$ (3 số, chính giữa là 15);
• $5 + 7 + 9 + 11 + 13 = 45$ (5 số, chính giữa là 9) ⇒ dài nhất, đáp án $9$.

Nếu bạn nào làm theo đúng cách đề "dắt" đi, tức là tạo hẳn dãy $1, 3, 5, 7, \ldots$ rồi cố tìm đoạn con liên tiếp dài nhất có tổng bằng $m$, thì xin chia buồn là các bạn đã bị đề bài đánh lừa 😅: làm theo hướng này rất phức tạp, mà $m$ lên tới $10^{16}$ thì dãy có quá nhiều phần tử, làm được cũng sẽ bị TLE.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Quy luậtTổng = số lượng × số giữaCách 1Duyệt ước lẻ từ nhỏ đến lớn · O(M)Cách 2Từ √M đi lùi về 1 · O(√M) · AC

Nhìn ra quy luật của dãy số lẻ

Những dạng bài kiểu dãy số có quy luật thì trong đầu các bạn hãy luôn nhủ rằng chắc chắn nó có quy luật, và nhìn ra đúng quy luật đó là mấu chốt để giải được bài. Bạn nào muốn tự thử thách thì đọc gợi ý dưới đây xong dừng lại tự làm tiếp nhé, khi nào bí quá hãy đọc tiếp.

Gợi ý

Lấy một số $X$ trong dãy làm trung tâm, lấy $Y$ số ngay trước $X$ và $Y$ số ngay sau $X$, thì tổng của $2Y$ số đó luôn bằng $2Y$ lần số $X$.

Ví dụ lấy 3 làm trung tâm: trước nó là 1, sau nó là 5, ta thấy $1 + 5 = 6 = 2 \cdot 3$. Lấy 5 làm trung tâm: trước là 1, 3, sau là 7, 9, ta thấy $1 + 3 + 7 + 9 = 20 = 4 \cdot 5$. Lý do rất đơn giản: các số cách đều $X$ đi theo từng cặp, số bên trái nhỏ hơn $X$ bao nhiêu thì số bên phải lớn hơn $X$ bấy nhiêu, nên mỗi cặp cộng lại đúng bằng $2X$:

13579

$1 + 9 = 10 = 2 \cdot 5$ và $3 + 7 = 10 = 2 \cdot 5$ ⇒ cả đoạn $1 + 3 + 5 + 7 + 9 = 5 \cdot 5 = 25$.

Giờ áp dụng vào bài. Đề nói lấy hộp chính giữa nên đoạn kết quả phải có số lượng phần tử lẻ thì mới có phần tử chính giữa (đề không nói gì với trường hợp số lượng chẵn, nên có thể yên tâm đoạn kết quả luôn có số phần tử lẻ). Đề cũng không nói nếu không có đáp án thì in gì, nên bộ test chắc chắn luôn có đáp án.

Cho đơn giản, giả sử đoạn kết quả có 3 phần tử: $L$ bên trái, $X$ chính giữa, $R$ bên phải. Theo đề ta có $L + X + R = M$, theo quy luật ở trên ta có $L + R = 2X$. Chuyển vế phương trình đầu thành $L + R = M - X$, hai vế trái bằng nhau nên $M - X = 2X$ ⇔ $3X = M$ ⇔ $X = \dfrac{M}{3}$.

Số 3 ở mẫu là vì $2 + 1 = 3$: 1 là $X$ chuyển vế qua, 2 là vì bên trái và bên phải mỗi bên có 1 phần tử. Tức là chia 3 vì đoạn có 3 phần tử. Đoạn có 5 phần tử thì chia 5, có 7 phần tử thì chia 7, cứ thế...

Công thức tổng quát

Đoạn có $S$ số lẻ liên tiếp (S lẻ) với số chính giữa là $X$ thì tổng $= S \cdot X$, nên $X = \dfrac{M}{S}$.
$X$ phải là số nguyên ⇒ $S$ phải là ước lẻ của $M$. Đề muốn đoạn dài nhất ⇒ $S$ phải lớn nhất có thể.

Thử với $M = 45$, các ước (đều lẻ) là $1, 3, 5, 9, 15, 45$:

Ước $S$	$X = 45 / S$	Cần $\frac{S-1}{2}$ số trước $X$	Trước $X$ có $\lfloor X/2 \rfloor$ số	Đoạn
1	45	0	22	45 ✔
3	15	1	7	13, 15, 17 ✔
5	9	2	4	5, 7, 9, 11, 13 ✔
9	5	4	2 (là 1, 3)	không đủ số ✘
15	3	7	1 (là 1)	không đủ số ✘
45	1	22	0	không đủ số ✘

Các bạn chú ý kỹ: với ước 9 thì $X = 5$, cần 4 số trước 5 nhưng trước 5 chỉ có 1, 3 thôi, đào đâu ra 4 số? Ước 15, 45 cũng vậy. Nên chỉ nhận các ước hợp lệ $1, 3, 5$, ước hợp lệ lớn nhất là 5 ⇒ đáp án $45 / 5 = 9$.

Điều kiện hợp lệ

Trước số lẻ $X$ có đúng $\lfloor X/2 \rfloor$ số lẻ (ví dụ trước 5 có $5/2 = 2$ số là 1, 3; trước 15 có $15/2 = 7$ số). Đoạn cần $\lfloor S/2 \rfloor$ số ở mỗi bên, nên ước $S$ hợp lệ khi $\lfloor S/2 \rfloor \le \lfloor X/2 \rfloor$, tức là $S \le X = \dfrac{M}{S}$.

Vì sao M luôn là số lẻ?

Đoạn kết quả có một số lẻ phần tử, mỗi phần tử đều lẻ, mà tổng của một số lẻ các số lẻ thì luôn lẻ. Nên test hợp lệ luôn có $M$ lẻ, và khi đó mọi ước của $M$ đều lẻ, $X = M / S$ cũng tự động lẻ. Code bên dưới dựa vào đúng đảm bảo "test luôn có đáp án" này của đề.

Minh hoạ: thử từng ước lẻ của M

Em nhập $M$ rồi bấm Tiếp để xem với mỗi ước lẻ $S$, đoạn $S$ số có số giữa $X = M / S$ trông như thế nào, và khi nào thì "hụt" số (ô viền đỏ đứt là những số không tồn tại vì nhỏ hơn 1):

M

Ví dụ nhanh:

Cách 1Duyệt các ước lẻ từ nhỏ đến lớn – O(M)

Từ phân tích trên, cách làm đầu tiên rất tự nhiên: cho $Y$ chạy qua các số lẻ $1, 3, 5, \ldots$, gặp $Y$ là ước của $M$ thì tính $X = M / Y$. Muốn biết trước $X$ có bao nhiêu số thì lấy phép chia nguyên $X / 2$. Nếu $Y / 2 \le X / 2$ thì $Y$ hợp lệ, ta ghi nhận đáp án là $X$; còn nếu $Y / 2 \gt X / 2$ thì loại.

Ví dụ $M = 45$: $Y = 1$ ⇒ $X = 45$, $X/2 = 22$, $Y/2 = 0$ ⇒ nhận. $Y = 3$ ⇒ $X = 15$, $X/2 = 7$, $Y/2 = 1$ ⇒ nhận. $Y = 5$ ⇒ $X = 9$, $X/2 = 4$, $Y/2 = 2$ ⇒ nhận. $Y = 9$ ⇒ $X = 5$, $X/2 = 2$, $Y/2 = 4 \gt 2$ ⇒ loại.

Dừng sớm được

Ước $Y$ càng lớn thì $X$ càng nhỏ, nên một khi đã gặp ước không hợp lệ đầu tiên thì mọi ước lớn hơn cũng không hợp lệ ⇒ dừng luôn. Đáp án là $X$ của ước hợp lệ cuối cùng.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long m;
    cin >> m;
    long long ans = 0;
    for(long long y = 1; y <= m; y += 2){
        if(m % y == 0){
            long long x = m / y;
            if(y / 2 > x / 2){
                break;
            }
            ans = x;
        }
    }
    cout << ans;
    return 0;
}

m = int(input())
ans = 0
y = 1
while y <= m:
    if m % y == 0:
        x = m // y
        if y // 2 > x // 2:
            break
        ans = x
    y += 2
print(ans)

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(1)$.
• Thời gian: vòng lặp chạy qua mọi số lẻ cho tới ước không hợp lệ đầu tiên, tức là ước nhỏ nhất lớn hơn $\sqrt{M}$. Nếu $M = 3 \cdot p$ với $p$ là số nguyên tố lớn thì ước đó chính là $p$, vòng lặp chạy cỡ $p / 2 \approx M / 6$ lần ⇒ $O(M)$.

Không gian$O(1)$

Thời gian$O(M)$

TLE với M lớn

Với $M$ cỡ $10^{16}$ thì có thể phải lặp tới cỡ $10^{15}$ lần, chắc chắn TLE. Cách này đúng nhưng chỉ dùng được khi $M$ nhỏ.

Cách 2Đi lùi từ √M về 1, gặp ước lẻ đầu tiên là xong – O(√M)

Nếu cố gắng nhìn thêm chút nữa thì sẽ thấy hướng tối ưu hơn. Nhắc lại bài toán liệt kê tất cả ước số của một số nguyên mà mình đã từng hướng dẫn: ta chỉ cần chạy từ 1 đến $\sqrt{M}$, mỗi khi tìm được ước $i$ thì ước còn lại chính là $M / i$ (vì $M$ chia hết cho $i$ thì kết quả phép chia cũng là một ước). Bài này chỉ cần ước lẻ nên chỉ xét các giá trị lẻ.

Ví dụ $M = 45$: $\sqrt{45} \approx 6{,}708$, lấy phần nguyên là 6, chỉ xét các số lẻ $1, 3, 5$ (bỏ qua $2, 4, 6$):

• $i = 1$: 45 chia hết cho 1 ⇒ có 2 ước là $1$ và $45/1 = 45$;
• $i = 3$: 45 chia hết cho 3 ⇒ có 2 ước là $3$ và $45/3 = 15$;
• $i = 5$: 45 chia hết cho 5 ⇒ có 2 ước là $5$ và $45/5 = 9$.

Mà ở trên ta thấy chỉ $1, 3, 5$ hợp lệ, còn $9, 15, 45$ thì không. Quy luật là: các ước lẻ $\le \sqrt{M}$ đều hợp lệ, còn các ước $\gt \sqrt{M}$ đều không hợp lệ. Điều này khớp với điều kiện $S \le X = M / S$ ⇔ $S^2 \le M$ ⇔ $S \le \sqrt{M}$.

Quy về bài toán

Tìm ước lẻ lớn nhất của $M$ mà $\le \sqrt{M}$, gọi là $S$. Đáp án là $M / S$.
Cách tìm: cho $i$ chạy từ $\lfloor \sqrt{M} \rfloor$ (nếu chẵn thì giảm đi 1 cho thành lẻ) lùi về 1, mỗi bước giảm 2. Giá trị đầu tiên mà $M$ chia hết chính là $S$ (vì đang xét từ lớn về bé nên nó lớn nhất ⇒ đoạn dài nhất). In $M / i$ rồi kết thúc luôn.

Như $M = 45$: $\lfloor \sqrt{45} \rfloor = 6$ chẵn nên giảm còn 5, mà 45 chia hết cho 5 ⇒ in $45 / 5 = 9$ luôn, chỉ 1 lần lặp.

Source code để các bạn tham khảo với tất cả những gì mình phân tích ở trên:

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long m;
    cin >> m;
    int sqr = (int)sqrt(m);
    if(sqr % 2 == 0){
        sqr--;
    }
    for(int i = sqr; i >= 1; i -= 2){
        if(m % i == 0){
            cout << m / i;
            return 0;
        }
    }
    return 0;
}

import math

m = int(input())
sqr = math.isqrt(m)
if sqr % 2 == 0:
    sqr -= 1
for i in range(sqr, 0, -2):
    if m % i == 0:
        print(m // i)
        break

Python: dùng math.isqrt

Ở bản Python mình dùng math.isqrt(m) để lấy phần nguyên căn bậc 2 chính xác tuyệt đối với số nguyên lớn, thay vì int(math.sqrt(m)) có thể bị sai số khi $m$ gần $10^{16}$.

Bấm Tiếp để chạy tay từng dòng code C++ ở trên:

C++▶ Chạy tay từng dòng codeCách 2: sqr = phần nguyên √m (chẵn thì giảm 1), i chạy lùi từng bước 2, gặp i là ước của m thì in m / i.

Dữ liệu vào (stdin) – sửa thoải mái45

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int main() {

5 long long m;

6 cin >> m;

7 int sqr = (int)sqrt(m);

8 if(sqr % 2 == 0){

9 sqr--;

10 }

11 for(int i = sqr; i >= 1; i -= 2){

12 if(m % i == 0){

13 cout << m / i;

14 return 0;

15 }

16 }

17 return 0;

18}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(1)$.
• Thời gian: trường hợp xấu nhất vòng lặp chạy đủ $\sqrt{M} / 2$ lần (chia 2 vì mỗi bước nhảy 2 đơn vị). $\sqrt{M}/2 = 0{,}5 \cdot \sqrt{M}$, theo quy tắc Big O thì nhân hằng số được bỏ qua ⇒ $O(\sqrt{M})$.

Không gian$O(1)$

Thời gian$O(\sqrt{M})$

Trường hợp xấu nhất là khi nào? Là khi ước lẻ hợp lệ lớn nhất tìm được rất nhỏ, ví dụ $M$ là số nguyên tố thì chỉ có ước 1, vòng lặp phải đi hết từ $\sqrt{M}$ về 1. Với $M$ lớn nhất là $10^{16}$ thì $\sqrt{10^{16}} = 10^8$, số lần lặp tối đa là $10^8 / 2 = 5 \cdot 10^7$, vẫn nằm trong ngưỡng nên yên tâm không bị TLE. Còn bình thường thì vòng lặp sẽ kết thúc sớm hơn nhiều.

Bạn nào code Python để ý

Với $M = 9\,999\,999\,999\,999\,903 = 3 \cdot 3\,333\,333\,333\,333\,301$ (thừa số thứ 2 là số nguyên tố, nên phải lùi gần hết từ $10^8$ về 3), bản C++ chạy khoảng 0,3 giây nhưng bản Python mất gần 10 giây ⇒ chắc chắn TLE. Bài này các bạn nên nộp C++ nha.

Ghi chú của mình: code C++ và Python của cả 2 cách đều cho đúng output ví dụ của đề, và đã được so với một chương trình vét cạn độc lập (thử mọi đoạn số lẻ liên tiếp) trên 400 giá trị $M$ hợp lệ ngẫu nhiên (số lẻ là hợp số, $M \le 3000$) – khớp hết. Với $M = 9\,999\,999\,999\,999\,903$: bản C++ cách 2 chạy khoảng 0,3 giây, còn cách 1 chạy quá 20 giây chưa xong (mình dừng lại), đúng như phân tích $O(M)$.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇