Tìm số nguyên dương x nhỏ nhất sao cho f(x) + f(x+1) + ... + f(x+k) = n với f là hàm tính tổng chữ số

GC_Loc_GC · July 8, 2020, 7:24am

Mình ngồi nghĩ bài này cả tiếng đồng hồ mà k thể tìm ra được hướng giải quyết cho bài này.

Hiện tại mình mới chỉ có 1 hướng là sẽ cố gắng giới hạn range của x tới nhỏ nhất có thể, tới range nhỏ nhất mà k tìm đc chính xác x thì sẽ loop từng thằng một để tìm, k tìm đc thì return 0.
Nhưng vấn đề là mình k tìm thấy quy luật gì của f(x)+…+f(x+k) để có thể xác định đc range của x. VD f(8)+f(9) = 17, f(9)+f(10)=10. Cứ đến đoạn biên chỗ 9 là tổng f lại bị giảm, và mình k tìm đc cái quy luật giảm này.

Ai có thể nhìn đc quy luật của tổng f thì bày mình với, hoặc ai có solution thì hướng dẫn mình tại sao lại có thể suy nghĩ và tìm ra đc solution đó. Many thanks

rogp10 · July 7, 2020, 6:28pm

Tổng các chữ số hàng đơn vị khả dĩ (có 0).
Số 0 không đóng góp gì vào tổng chữ số nên xem như hàng cao hơn không có 0.

Với n = 27, k = 1 thì x = 58

tntxtnt · July 8, 2020, 4:28pm

Đặt f(x) = y

TH1:
Giả sử f(x+i) = y+i với mọi i < k
Ta có:\displaystyle\sum_{i=0}^{k-1}{f(x+i)} = \sum_{i=0}^{k-1}{(y+i)} = ky + \dfrac{k(k-1)}{2} = n
Hay ky = n - r, với r = \dfrac{k(k-1)}{2}
Nếu n-r chia hết cho k, nghĩa là ta tìm được giá trị y = \dfrac{n-r}{k} = f(x) từ đó suy ra giá trị x = g(y), với g(y) là hàm ngược của f(x)

TH2:
Giả sử f(x+i) = y+i với mọi 0 \leq i < j < k Với i \geq j, vì giá trị hàng đơn vị giảm từ 9 xuống 0 nên f(x+i) = y + i - 9 với i \geq j
Vậy ta có: \displaystyle\sum_{i=0}^{k-1}{f(x+i)} = \sum_{i=0}^{j-1}{(y+i)} + \sum_{i=j}^{k-1}{(y+i-9)} = \sum_{i=0}^{k-1}{(y+i)} - \sum_{i=j}^{k-1}{9} = ky + \dfrac{k(k-1)}{2} - 9(k-j) = n
Hay ky = n - r + 9(k-j). Tương tự bài toán có nghiệm khi n - r + 9(k-j) chia hết cho k, với j \in \{1,2,3,...,k-1\}

TH N:
Khi ko chỉ có hàng đơn vị giảm từ 9 xuống 0 mà hàng trăm hàng ngàn v.v… giảm từ 9 xuống 0 nữa, khi đó điều kiện có nghiệm là n - r + 9h(k-j) chia hết cho k với h \geq 2. Vì 1 \leq k \leq 9 nên có thể :V :V trường hợp này ko bao giờ xảy ra vì 9h chia hết cho 9, nếu h=1 vô nghiệm thì h > 1 cũng vô nghiệm :V Ko chắc lắm :V

Cuối cùng ta cần tìm hàm g() sao cho y = f(x) thì x = g(y) :V Gộp với TH2 nữa thì g phải nhận 2 input mới đủ :V x = g(y, u) với u = k-j

Hình như sai, độc giả tự mò vậy =)

u cho ta biết có bao nhiêu số vòng ngược lại sau số 9. Ví dụ n=10=f(9)+f(10)=9+1 thì u=1, nghĩa là có 1 số sau số 9 hàng đơn vị.

Nếu u = 0 thì để x nhỏ nhất, hàng đơn vị của nó phải là 9 cho giảm bớt số lượng chữ số và số 9 ở hàng đơn vị sẽ tạo ra số nhỏ hơn số ko có số 9 ở hàng đơn vị. vd 3,9 thì 39 nhỏ hơn 93. Tương tự cho hàng chục trăm ngàn cũng phải là số 9 hết. Trừ y tới khi nào y < 9 thì đó là chữ số cuối cùng. Vd y=39=9+9+9+9+3 thì ta có x = 39999.
Nếu u > 0, ta có thể suy ra hàng đơn vị của x phải là 10 - (k-u) để có đúng u số sau số 9 hàng đơn vị. Vd u=6, k=7 thì chữ số cuối cùng của x phải là 9 để có đúng 6 số bị trừ 9. Vd: n=51, k=7 thì y=12, u=6. Chữ số cuối cùng của x là 9, để có f(x)=y=12 thì x = 39. (12+4+5+6+7+8+9=51).
Sau khi tìm ra số hàng đơn vị, ta có thể áp dụng cách trừ 9 dần như trường hợp u=0, chỉ có 1 điểm khác là hàng chục phải là số khác 9 lớn nhất, hay hàng chục phải là số 8 :V, vì nếu hàng chục cũng là 9 thì x có dạng ...9\#, f(x+j) sẽ bị giảm 18 đơn vị chứ ko phải giảm 9 như giả thuyết :V

edit: đọc lộn đề, tổng f(x) tới f(x+k) luôn chứ ko phải chỉ tới f(x+k-1), sửa đơn giản là k ở đây = k_{input} + 1 vậy :V

tntxtnt · July 8, 2020, 4:29pm

thật ra với k \geq 3 duyệt trâu dễ hơn :V k=1 thì trừ 999... là ra, chỉ có k=2 mới khó :V

duyệt trâu khi k\geq3 theo kiểu cho x chạy từ 0 tới 10^6 rồi tính tổng f(x) + ... + f(x+k-1). Nếu quá 10^6 ko ra thì vô nghiệm.

với k=2 thì n=150 có thể có x = 899999989, lười viết code C++ duyệt trâu kiểm chứng quá :V

edit: đọc lộn đề, tổng f(x) tới f(x+k) luôn chứ ko phải chỉ tới f(x+k-1), sửa đơn giản là k ở đây = k_{input} + 1 vậy :V

Stanley00 · July 8, 2020, 2:49am

“ Premature optimization is the root of all evil ”
Mất cả tiếng để lo tìm solution “xịn” làm gì khi vẫn còn chưa có chưa có solution.
Kinh nghiệm của mình là máy tính không ngại làm việc “nhiều” đâu bạn.
Hãy viết code 1 cách “trâu bò” nhất cho bài này rồi chạy với đầu vào n<20, k<10 thì biết đâu lại thấy được quy luật.

Còn một cách tiếp cận khác là hãy làm nhiều bài tập vào, tự nhiên bạn sẽ phân loại được “dạng” và có từng solution tương ứng, chỉ phải chỉnh sửa một chút cho hợp với điều kiện của đề thôi.

Còn solution thì chắc cũng giống giống với @tntxtnt bên trên

nguyen2812 · July 8, 2020, 5:41am

Duyệt trâu kiểu đấy liệu có đủ thời gian trong vòng 2s không anh nhỉ🤔

rogp10 · July 8, 2020, 6:22am

Bạn có đến 1000 test vậy mỗi test nhắm 2m ops. Bỏ qua k=0 và k=1 thì bạn chỉ có thể kéo lên mức x ~ 400k là may rồi, 6 chữ số thì sum ~ 45-50, vậy k = 2 là sát ván, k >= 3 là ổn.

Tức là k = 0, 1, 2 bạn cần tìm cách giải vì ko brute được

Stanley00 · July 8, 2020, 6:19am

Mình không nói giải bằng code “trâu bò”, mình nói là dùng code trâu bò để tìm/test code optimized

noname00 · July 8, 2020, 8:39am

Em đang nghĩ đến 1 giải pháp cắt số đi một tí.

Đặt getX(n, k) là số nguyên dương nhỏ nhất sao cho n = f(x) + f(x+1) + ... + f(x+k).

Giả sử x, x + 1,…, x + k có cùng độ dài (với điều kiện nếu x có ít chữ số hơn x + k thì trước x có chữ số 0).

Mỗi số x + i sẽ có dạng \overline{cA_i} (c là 1 chữ số, A_i là 1 hoặc 1 số các chữ số)

Định nghĩa c\ ||\ A = \overline{cA} với c là 1 chữ số, A là 1 số tự nhiên.

TH1. x, x + 1,…, x + k có cùng chữ số hàng cao nhất (chữ số này khác 0).

\displaystyle\Rightarrow f(x) + f(x+1) + ... + f(x+k) = c(k+1) + f(A_0) + f(A_1) + ... + f(A_k). Tất nhiên là dãy A_0, A_1,..., A_k là dãy các số tự nhiên liên tiếp.

\displaystyle \Rightarrow getX(n, k) = \min_{1 \le c \le 9} \left\{c\ ||\ getX(n - c(k+1),\ k)\right\}

TH2. x,… x + j - 1 có cùng chữ số hàng cao nhất và x + j,… x + k có cùng chữ số hàng cao nhất (0 < j \le k).

\Rightarrow x + j - 1 = \overline{c9...9}, x + j = \overline{(c+1)0...0} hay A_{j-1} = 9...9, A_j = 0...0.

\Rightarrow f(x) + f(x+1) + ... + f(x+k)\\ = f(x) + ... + f(x+j-1) + f(x+j) + ... + f(x+k)\\ = cj + f(A_0) + ... + f(A_{j-1}) + (c+1)(k-j+1) + f(A_j) + ... + f(A_k)\\ = cj - j(c+1) + (c+1)(k+1) + f(A_0) + ... + f(A_{j-1}) + f(0) + ... + f(k - j)\\ = -j + (c+1)(k+1) + f(A_0) + ... + f(A_{j-1}) + 0 + ... + (k - j)
(do k \le 9,\ j > 0 \Rightarrow k - j < 9 \Rightarrow f(t) = t\ \forall 0 \le t \le k - j)

\displaystyle = \frac{(k-j+1)(k-j)}{2} - j + (c+1)(k+1) + f(A_0) + ... + f(A_{j-1})

\displaystyle \Rightarrow getX(n, k) = \min_{0 \le c \le 9,\ 0 < j \le k} \left\{c\ ||\ A'\right\}

với

\left\{\begin{matrix} A' := getX\left(n - \frac{(k-j+1)(k-j)}{2} + j - (c+1)(k+1),\ j-1\right)\\ A' + j = 10...0 \end{matrix}\right.

Tính nốt điều kiện dừng:

getX(n, k) = \left\{\begin{matrix} 0 & if\ n = \frac{k(k+1)}{2}\\ -1 & if\ n < \frac{k(k+1)}{2}\\ \overline{(n \mod 9)9...9} & k = 0,\ n \mod 9 > 0\\ 9...9 & k = 0,\ n \mod 9 = 0\\ \text{đệ quy như trên} & if\ n > \frac{k(k+1)}{2} \end{matrix}\right.

Tuy nhiên, với n đủ nhỏ (n \le 9k) thì hoàn toàn có thể tính được x qua brute force (độ phức tạp O(n k \log n).

Độ phức tạp tổng O(9k \log n + 9k * k\log (9k)) = O(9k \log n + k^2 \log k).

noname00 · July 8, 2020, 8:47am

Sửa mãi còm trên rồi, còm này là để post về code :>

Code Python test 1 150 2 (chỉ 1 test duy nhất) ra 899995 trong 0.02s. Thêm cache chắc 1000 test vẫn ăn trong 2s.

VannyTraanf · July 8, 2020, 5:04pm

Mình ngồi soạn ý tưởng và gõ ra file excel nên mình chụp hình dán vào đây.
Ý tưởng là dùng quy hoạch động
P/s: Hình khá dài, Nên click vào hình 1 lần sẽ hiện ra cửa sổ View Picture, lại click vào thêm 1 lần nữa thì hình sẽ to ra, scroll được.
★Edit 1): Sửa lại công thức S2 của TH2. (Thanks @tntxtnt đã detect)

tntxtnt · July 8, 2020, 4:30pm

ngồi tính đpt luôn ghê vậy =] input nhỏ tính chậm thì tính trước 1 cái table 150x10 chứa kết quả rồi copy paste vào chạy tức thì O(1) =]]

tntxtnt · July 8, 2020, 4:38pm

ehehe TH2 đọc chắc loạn não mất =] từ f(x+k_1+1) tới f(x+k_1+k_2) chỉ có k_2 số thôi chứ, ở dưới tính ra k_2 + 1 lần là dư rồi :V

noname00 · July 8, 2020, 4:45pm

Như vậy thì xấu tính quá :v cũng phải tính toán một tí chứ anh :v

VannyTraanf · July 8, 2020, 4:48pm

@tntxtnt ờ hớ hớ. Uh nhỉ ^^.
Quên mất.
Mới vừa làm việc xong, khuya lắc cmnr (h là 1:50AM). online thấy bài này cái bay vào mần ^^.
Sai sót cmnr. Cảm ơn bạn đã xem và tìm ra lỗi sai giúp ^^ <3

VannyTraanf · July 8, 2020, 5:04pm

Ai lại chơi “ăn gian” thế ^^
Mấy cái này để luyện skill chứ chơi vậy ai chơi ^^

tntxtnt · July 8, 2020, 5:41pm

https://oeis.org/A007953 dãy số digit sum
https://oeis.org/A037123 dãy số sum of digit sum Muốn tính f(x) + f(x+1) + ... + f(x+k) nhanh có thể lấy A037123(x+k) - A037123(x-1), nhưng ko biết tìm x nhỏ nhất thế nào Mà dãy số này ko biết có công thức ko nữa =]
nhìn phần link/references thấy cũng có nhiều người nghiên cứu digit sum nhỉ

nguyen2812 · July 9, 2020, 1:51am

em có thắc mắc 1 chút ạ
Theo quy luật em tìm thì khi chuyển hàng(em cũng không biết gọi là gì) kiểu thế này:

9 lên 10 thì hàng chục tăng 1; 
19 lên 20 thì hàng chục tăng 1; 
99 lên 100 thì hàng trăm tăng 1;

thì khi đó f(x) sẽ giảm đi 1 lượng bằng 9 * i - 1 với i tương ứng với vị trí của hàng bị thay đổi là đơn vị, hàng chục hay hàng trăm
Ví dụ :

9 -> 10 : giảm 8 ( i == 1)
99 -> 100 : giảm 17 (i == 2) //Hàng đơn vị bằng 9 nhưng lại giảm 17
109 -> 110 : giảm 8 (i == 1)
199 -> 200 : giảm 17 ( i == 2)
999 -> 1000 : giảm 28 (i == 3)

Vì thế nên em nghĩ công thức tính S2 của anh cần sửa đổi 1 chút và trong phương pháp nen xét duyệt thêm biến i rồi lấy miền giá trị của x theo i và f(x)
Ví dụ:

i == 1 : 0 <= x <= 100;
i == 2 : 10 <= x <= 1000;
9 < f(x) < 18 : 10 <= x <= 100;

Trên đây là suy nghĩ của em. Nếu em có chỗ nào hiểu sai bài làm của anh ấy hay suy luận sai chỗ nào mong các anh chỉ giúp ạ. Em cảm ơn.

rogp10 · July 9, 2020, 1:49am

A037123 thì có tổng sigma chạy theo từng chữ số đó mà

VannyTraanf · July 9, 2020, 3:29pm

Uhm. ^^ Cảm ơn em.
Đúng là xét bị thiếu sót mất rồi.
Quy luật tăng từ 9 lên thì đúng là như em chỉ ra:
Nếu có l chữ số 9 liên tiếp kể từ hàng đơn vị thì
f(x + 1) = f(x) - (9*l - 1).
Vậy thì sẽ cần phải sửa c thức truy hồi lại, sẽ rắc rối hơn đây ^^.