UVA-11005: Cheapest Base

CPE 一顆星選集 49 道必考題

題目連結:https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1946

內容

數字可以被表示成不同的進位制，當我們把數字表示成n進位時（2 <= n <= 36），我們需要用到字串’0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ’的前 n 項。

每個字元有自己的價錢，以一個1~128的整數表示，計算用哪些進位來表示最省錢。

輸入第一列 T (T <= 25) 代表測資數，每筆測資前四列代表各個字元的價錢(一列9個)，接著有一整數 Q 代表數字數量，隨後為數字。

範例輸入

2
10 8 12 13 15 13 13 16 9
11 18 24 21 23 23 23 13 15
17 33 21 23 27 26 27 19 4
22 18 30 30 24 16 26 21 21
5
98329921
12345
800348
14
873645
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
4
0
1
10
100

範例輸出

Case 1:
Cheapest base(s) for number 98329921: 24
Cheapest base(s) for number 12345: 13 31
Cheapest base(s) for number 800348: 31
Cheapest base(s) for number 14: 13
Cheapest base(s) for number 873645: 22

Case 2:
Cheapest base(s) for number 0: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
Cheapest base(s) for number 1: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
Cheapest base(s) for number 10: 11 12 13 14 15 16 17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32 33 34 35 36
Cheapest base(s) for number 100: 11 12 13 14 15 16 17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32 33 34 35 36

想法

對於每個數字，枚舉出各個進位表示的花費，並存到陣列，找出最小值，最後遍歷一次陣列，若等於最小值就輸出。

最後一筆測資後面不要有換行。

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false), cin.tie(nullptr)
using namespace std;

int main(){
    fastio;
    int T, mp[36], Q, n, value[37];
    cin >> T;
    for(int c = 1; c <= T; ++c){
        for(int i = 0; i < 36; ++i) cin >> mp[i];
        cin >> Q;
        cout << "Case " << c << ":\n";
        while(Q--){
            cin >> n;
            int mi = INT_MAX;
            for(int base = 2; base <= 36; ++base){
                int temp = n, sum = 0;
                while(temp > 0){
                    sum += mp[temp%base];
                    temp /= base;
                }
                mi = min(mi, sum);
                value[base] = sum;
            }
            cout << "Cheapest base(s) for number " << n << ":";
            for(int i = 2; i <= 36; ++i){
                if(value[i] == mi){
                    cout << " " << i;
                }
            }
            cout << "\n";
        }
        if(c != T) cout << "\n";
    }
    return 0;
}