Số càng lớn càng dễ greedy, AC được
Tách 1 số nguyên thành các chữ số và lấy random 1 trong 2 số
chắc cũng phải đệ quy 200k lần cho 1 số 10^6 :V
vd như
f(37) = 7 --tối đa là 2*(37/10) + 1 = 6+1 = 7
f(65) = 12 --tối đa là 2*(65/10) + 1 = 12+1 = 13
f(12) = 3 --tối đa là 2*(12/10) + 1 = 2+1 = 3
f(150) = 27 --tối đa là 2*(150/10) + 1 = 30 + 1 = 31
:V
sợ đệ quy 1tr lần thì tràn stack thôi chứ 200k lần thì chắc ok =]
ủa mà làm vòng for trừ dần được mà thôi lo bò trắng răng =]
Python không optimize đệ quy đuôi được nên code oneliner kia nhìn cho vui thôi chứ số lớn lớn chút là sẽ tràn stack, phải viết lại thành vòng lặp mới được.
Viết bằng C++ thì may ra mới có tự động optimize đệ quy đuôi.
Không biết code thế này được không ?
def num_to_zero(n):
sobuoc = 0
while n > 0:
n = n - max(list(map(int, str(n))))
sobuoc = sobuoc + 1
return sobuoc
print(num_to_zero(237))
P/s: Cách clean hơn:
def num_to_zero(n):
sobuoc = 0
while n > 0:
n_str = str(n)
n_char = list(map(int, str(n)))
n = n - max(n_char)
sobuoc = sobuoc + 1
return sobuoc
print(num_to_zero(237))
cách ở dưới có clean hơn đâu :V
n - int(max(str(n)))
như Stanley là đẹp rồi đã convert int sang str tức là ko màn tốc độ rồi, map từng ký tự về int làm gì nữa ko cần thiết, so sánh chuỗi 1 ký tự luôn =] À mà map sang int rồi lại phải tạo 1 cái list có khi chậm hơn đó :V
Cứ n/=10 n%10 cho nó clear đọc ai cũng hiểu.
int maxInt(int n) {
int ans = 0;
while(n) {
ans = max(ans, n%10);
n /= 10;
}
return ans;
}
int makeDigitsZero(int n)
{
if(n == 0) return 0;
int c = 1;
while(n >= 10) n -= maxInt(n), c++;
return c;
}
pass all test nhé
Hình như là cái này dùng cách 1 mà mình nói thì phải . Mà hình như đây là code C/C++