Help tui câu này với mn ơi gấp c++ nhé

Ý tưởng

Giả sử số `X` có chữ số cuối cùng là `t` `(t in {0;1;2;3;4;5;6;7;8;9})`

Khi đó, ta có thể viết lại `X=10k_0+t \ (k in NN)`

Khi đó: `X+1=10k_0+t+1 \ (k in NN)`

Gọi $sc(n)$ là tổng các chữ số của số tự nhiên `n`

Khi này với mọi `t < 9` hay `t + 1 < 10`, ta có:

$sc(X)=sc(10k_0)+sc(t)$

$sc(X+1)=sc(10k_0)+sc(t+1)$

Dễ thấy `t < t + 1 < 10` `=>` $sc(t) < sc(t+1)$

`=>` $sc(X) < sc(X+1)$ với mọi `X` không có chữ số tận cùng là `9`

`=>` Ta chỉ cần xét với các số `X` có chữ số tận cùng là `9`

Khi đó: `X=10k_0+9` và `X+1=10k_0+10=10(k_0+1)`

Khi này:

$sc(X)=sc(10k_0)+9=sc(k_0)+9$

$sc(X+1)=sc(k_0+1)$

Nếu như `k_0` có chữ số tận cùng khác `9` thì:

$sc(k_0)-sc(k_0+1)=-1$

`=>` $sc(X)-sc(X+1)=8 > 0$

`=>` $sc(X)>sc(X+1)$

Nếu như `k_0` tiếp tục có chữ số tận cùng bằng `9` thì ta lại viết `k_0=10k_1+9`

`=>` $sc(X)=sc(k_1)+18$

Đồng thời `k_0+1=10(k_1+1)`

`=>` $sc(X+1)=sc(k_1+1)$

Giả cứ tiếp tục như vậy đến `k_n` `(k_n in NN, k_n <= 9)` sao cho tất cả `k_i` `(i in NN, 0 <= i < n)` đều có chữ số cuối cùng bằng `9`

(Vì nếu có bất kỳ một `k_i` nào có chữ số cuối cùng khác `9` thì sẽ như trường hợp trên dẫn đến $sc(X) > sc(X+1)$)

Khi này: $sc(X)=k_n+9(n+1)$ và $sc(X+1)=sc(k_n+1)$

TH1: `k_n` khác `9` `=>` $sc(k_n+1)=k_n+1$ `=>` $sc(X+1)=k_n+1$

Khi đó: $sc(X)-sc(X+1)=k_n+9n+9-k_n-1=9n+8 > 0$

`=>` $sc(X)>sc(X+1)$

TH2: `k_n=9` `=>` `k_n+1=10`

Khi này: $sc(X)=9n+18 > 1$ và $sc(X+1)=1$

`=>` $sc(X) > sc(X+1)$

Từ các điều trên, ta kết luận rằng $sc(X) > sc(X+1)$ khi và chỉ khi `X` có chữ số tận cùng là `9`

Từ đó, bài toán trên sẽ được quy về bài toán: Đếm các số tự nhiên có chữ số tận cùng là `9` trong đoạn từ `1` đến `N`

*** Mình giải thích hơi khó hiểu nha, bạn thông cảm :>> ***

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    freopen("BAI1.INP", "r", stdin);
    freopen("BAI1.OUT", "w", stdout);
    int n, start, end;
    cin >> n;
    if (n < 9) {
        cout << 0;
        return 0;
    }
    start = 9;
    end = n;
    while (end % 10 != 9) end--;
    cout << (end - start) / 10 + 1;
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

ifstream fi("BAI1.inp");

ofstream fo("BAI1.out");

int main(){

long long dem=0;

long long X,X2;

fi>>X;

for(long long i=1;i<=X;i++){

X2=X+i

while(X>0){

X+=(X%10);

X/=10;

X2+=(X2%10);

X2/=10;

}

if(X>X2){

dem++;

}

}

fo<<dem;

}