C++Generating Numbers kattis (solution)

Đề bài

Trên mặt bảng ghi số 1. Mỗi một lần biết đổi, Bờm thực hiện một trong hai phép toán sau đây đối với số viết trên bảng:

• Cộng số đó với 1
• Đổi chỗ các chữ số của nó (nhưng không bao giờ có số 0 ở vị trí thứ nhất tính từ trái sang phải). Sau đó xóa số đang có trên bảng và viết kết quả thu được lên bảng

Yêu cầu

Cho trức một số nguyên dương, hãy tính xem sau ít nhất bao nhiên lần biến đổi bắt đầu từ số 1 Bờm sẽ thu được số đã cho

Dữ liệu

Vào từ file văn bản NUMBER.INP

• Dòng đầu tiên chứ số nguyên $T$ ($1 \le T<10^4$) là số lượng test trong file
• Dòng thứ $i$ trong $T$ dòng tiếp theo chứ số nguyên $N_i$ ($2 \le N_i < 10^9, 1 \le i \le T$)

Kết quả

Ghi ra file văn bản NUMBER.OUT gồm $T$ số, mỗi số trên một dòng, trong đó số trên dòng thứ i là số lần biến đổi ít nhất cần thực hiện để thu được trên bảng số $N_i$.

Ví dụ

//NUMBER.INP
3
2
955
21

//NUMBER.OUT
1
48
12

Giới hạn test

• $25\%$ số test có $2 \le N_i \le 100$ với mọi $2 \le N_i \le 100$
• $25\%$ số test có $T=1, 100 \le N_i < 10^4$
• $15\%$ số test có $T>1, 100 \le N_i < 10^4$ với mọi $i$
• $35\%$ số test có $10^4 \le N_i < 10^9$ với mọi $i$

Cách giải

Lựa chọn tăng giá trị cần rồi tráo đổi ở từng vị trí đúng luôn là tối ưu nhất, chi tiết xem code

Code full AC

int jump(int ax){
    int res = 0;
    for(int i = 1; i<=ax; i++){
        res += 10*i - 1;
    }
    return res;
}
int log10ii(int ax){
    ll i = 1;
    int res = 0;
    while(1ll*i*10ll <= 1ll*ax){
        i*=10ll;
        res++;
    }
    return res;
}
int powii(int ax, int bx){
    int res = 1;
    for(int i = 1; i<=bx; i++){
        res*=ax;
    }
    return res;
}
void process(){
    int t = 1;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        int lg = (int)log10ii(n);
        int res = 0;
        if(n%((int)powii(10,lg)) == 0 && lg > 0){
            res++; n--;
            lg = (int)log10ii(n);
        }
        res += jump(lg);
        int oldn = n;
        bool ok1 = false, ok11 = false;
        while(n>0){
            int ax = n%10;
            if(n==oldn && n/10 != 0) res += ax;
            if(n!=oldn && n/10 != 0){
                res += ax;
                if(ax != 0) res++;
                if(ax == 1) ok1 = true;
            }
            if(n/10 == 0 && n!=oldn){
                if(ax != 1){
                    res += ax;
                    ok11 = true;
                }
            }
            if(n/10 == 0 && n==oldn) res += ax-1;
            n/=10;
        }
        if(ok1 && ok11) res--;
        cout << res << endl;
        fflush(stdout);
    }
}

Lời giải bài G: https://icpcvn.github.io/2019/regional/Editorial.pdf

Nguồn: https://open.kattis.com/problems/generatingnumbers