CSES - Removing Digits II | Loại bỏ chữ số II
Xem PDF
Đ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
27
Sample output
5
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
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
}
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)
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 í
TLE hoài vậy
admin
https://ideone.com/P2OBvf
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
Khó nhưng cũng đc 1k điểm mà dễ
tăng memory ik ad
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
3 bình luận nữa