CSES - Removing Digits II | Loại bỏ chữ số II

Tác giả:

Dạng bài

Ngôn ngữ cho phép

~~Assembly~~, Awk, C, C++, Clang, Clang++, Cobol, D, ~~Groovy~~, Haskell, Java, JS, Kotlin, Lua, Node JS, ObjectiveC, Output, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Scala, Scratch

Điểm: 2500 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một số nguyên \(n\). Mỗi bước, bạn có thể trừ bất kỳ số có một chữ số nào xuất hiện trong đó.

Cần thực hiện mấy bước để số đó bằng \(0\)?

Input

Một dòng duy nhất chứa số nguyên \(n\).

Output

Một dòng duy nhất chứa số bước thực hiện ít nhất.

Constraints

\(1\leq n \leq 10^{18}\)

Example

Sample input

Sample output

Note

Giải thích: Cách làm tối ưu là \(27 \rightarrow 20 \rightarrow 18 \rightarrow 10 \rightarrow 9 \rightarrow 0\).

Bình luận

TheBloxdPlayer • 6:23 p.m. 20 Tháng 1, 2025 •

tố cáo quocbao2710 xài chatgpt

1
Phản hồi Chia sẻ

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;

    int sobuoc = 0;
    while (n > 0) {
        string s = to_string(n);
        int maz = 0;
        for (char c : s) {
            maz = max(maz, c - '0');
        }

        n -= maz;
        sobuoc++;
    }
    cout << sobuoc << endl;
    return 0;
}

cái này đc 5 test thôi 🙂

Phản hồi

iMafool • 8:20 p.m. 31 Tháng 10, 2024 •
code c++03:
//cop code

pragma GCC optimize("Ofast")

include <bits/stdc++.h>

define hutao_my_wife ios_base::sync_with_stdio(0);

define forcalors_so_cute cin.tie(0);

define ll long long

define int ll //這個int單純是因為debug時懶得找溢位的程式碼

define pii pair<int,int>

define ff first

define ss second

define pb push_back

define eb emplace_back

define bug(A) cout<<A<<" hi\n";

using namespace std;

const int M = 200005;
ll dp[20][10][10];
ll to[20][10][10];
int maxdigital(ll x){
ll ans = 0;
while(x){
ans = max(ans,x%10);
x/=10;
}
return ans;
}
int numi(ll x){
x/=10;
int ans = 0;
while(x%10 == 9){
ans++;
x/=10;
}
return ans;
}
void solve(){
ll n;
cin>>n;
ll ans = 0;
while(n>0){
int i = numi(n);
int k = maxdigital(n - n%(ll)pow(10,i+1));
int j = n%10;
ans += dp[i][j][k];
n -= (ll)pow(10,i+1);
n = n - n%10 + to[i][j][k];
}
cout<<ans<<'\n';

}
signed main()
{
hutao_my_wife forcalors_so_cute

int t = 1; memset(dp,0,sizeof(dp)); for(int i = 0; i <= 18; i++){ for(int k = 0; k < 10; k++){ for(int j = 0; j < 10; j++){ if(i+j+k == 0){ to[i][j][k] = 0; continue; } if(i+k == 0){ dp[i][j][k]=1,to[i][j][k]=0;continue; } if(i == 0){ if(j < k)dp[i][j][k] = 1,to[i][j][k]=(10+j-k)%10; else dp[i][j][k] = 2,to[i][j][k] = (10-k)%10; continue; } int last = j; for(int l = 9; l >= 0; l--){ dp[i][j][k] += dp[i-1][last][max(k,l)]; last = to[i-1][last][max(k,l)]; } to[i][j][k] = last; } } } while(t--){ solve(); }

}
-3
Phản hồi Chia sẻ

rock • 8:16 a.m. 25 Tháng 10, 2024 •

Uses math;

const
MAXN = 1000005;

var
dp: array[1..19, 0..9, 0..9] of Int64;
trace: array[1..19, 0..9, 0..9] of Int64;
pw: array[0..19] of Int64;
i:Longint;
result:Int64;
procedure CreateDP;
var
i, j, k, l: Longint;
res, trc: Int64;
begin
pw[0] := 1;
for i := 1 to 18 do
pw[i] := pw[i-1] * 10;

for i := 1 to 18 do
begin
if (i = 1) then
begin
for j := 0 to 9 do
begin
for k := 9 downto 0 do
begin
if ((9 - k) - Max(j, 9 - k) < 0) then
begin
dp[i][j][k] := 1;
trace[i][j][k] := -((9 - k) - Max(j, 9 - k));
end
else
begin
dp[i][j][k] := dp[i][j][9 - ((9 - k) - Max(j, 9 - k))] + 1;
trace[i][j][k] := trace[i][j][9 - ((9 - k) - Max(j, 9 - k))];
end;
end;
end;
end
else
begin
for j := 0 to 9 do
begin
for k := 0 to 9 do
begin
trc := k + 1;
res := 0;
for l := 9 downto 0 do
begin
res := res + dp[i-1][Max(j, l)][trc-1];
trc := trace[i-1][Max(j, l)][trc-1];
end;
dp[i][j][k] := res;
trace[i][j][k] := trc;
end;
end;
end;
end;
end;

function GetTCS(n: Int64): Int64;
var
ans: Int64;
begin
ans := 0;
while (n > 0) do
begin
ans := Max(ans, n mod 10);
n := n div 10;
end;
Result := ans;
Exit(result);
end;

function GetAns(n: Int64): Int64;
var
k: Integer;
ans, x, z: Int64;
begin
k := 1;
ans := 0;
while (n > 0) do
begin
x := n mod pw[k+1] div pw[k];
for i := 0 to x do
begin
z := GetTCS(n div pw[k]);
ans := ans + dp[k][z][pw[k] - n mod pw[k] - 1];
n := n - n mod pw[k] - trace[k][z][pw[k] - n mod pw[k] - 1];
end;
k := k + 1;
end;
Result := ans - 1;
Exit(result);
end;

var
n: Int64;
begin
CreateDP();
ReadLn(n);
WriteLn(GetAns(n));
end.(pascal)

0
Phản hồi Chia sẻ

happydkiwi • 2:53 p.m. 19 Tháng 9, 2024 •

CSES - Removing Digits II | Loại bỏ chữ số II với CSES - Removing Digits II | Loại bỏ chữ số thấy đề giống í

0
Phản hồi Chia sẻ

1 phản hồi

happydkiwi • 2:48 p.m. 19 Tháng 9, 2024 •

TLE hoài vậy

0
Phản hồi Chia sẻ

pa_ldk • 4:58 p.m. 1 Tháng 8, 2024 • ← chỉnh sửa 13 →

admin

-3
Phản hồi Chia sẻ

kingofgame • 12:15 a.m. 29 Tháng 5, 2024 •

https://ideone.com/P2OBvf

2
Phản hồi Chia sẻ

Vodangngoclam • 6:43 p.m. 22 Tháng 5, 2024 •

mình cho code cho:))

Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

-7
Phản hồi Chia sẻ

1 phản hồi