CSES - Removing Digits | Loại bỏ chữ số
Xem PDF
Điểm:
1300
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Bạn được cho một số nguyên \(n\). Ở mỗi bước, bạn có thể trừ \(n\) đi một lượng bằng một trong các chữ số của nó.
Cần bao nhiêu bước để làm cho \(n\) bằng \(0\)?
Input
- Gồm một dòng duy nhất chứa số nguyên \(n\).
Output
- In ra một số nguyên duy nhất là số bước tối thiểu cần dùng.
Constraints
- \(1 \leq n \leq 10 ^ 6\)
Example
Sample input
27
Sample output
5
Note
Một giải pháp tối ưu là \(27 \to 20 \to 18 \to 10 \to 9 \to 0\).
Bình luận
ý tường vấn là tìm chữ số lớn nhất trong n rồi lấy n trừ đi chữ số đó là được.
int main(){
string s;
cin>>s;
int cnt=1;
while(s.size()>1 &&s[0]!='0'){
char i=0;
for(auto x:s){
i=max(i,x);
}
s=to_string(stoi(s)-(i-'0'));
cnt++;
}
cout<<cnt<<endl;
return 0;
}
12 bình luận nữa