# 299 Train Swapping

## Code

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    cin >> N;
    while (N--)
    {
        int L;
        cin >> L;
        vector<int> train(L);  
        
        for (int i = 0; i < L; i++)
        	cin >> train[i];
        
        // Bubble sort
        int cnt = 0;
        for (int i = L - 1; i > 0; i--)
            for (int j = 0; j < i; j++)
                if (train[j] > train[j + 1])
                {
                    swap(train[j], train[j + 1]);
                    cnt++;                   
                }
        
        cout << "Optimal train swapping takes " << cnt << " swaps.\n";
    }
    
    return 0;
}

Bubble sort 與 inversion number 是有某種方面關聯，可替代程式碼如下

        // Inversion Number
        int cnt = 0;
        for (int i = 0; i < L - 1; i++)
            for (int j = i + 1; j < L; j++)
                if (train[i] > train[j])
                    cnt++;

---

# 10062 Tell me the frequencies!

## Code

#include <bits/stdc++.h>
using namespace std;

int main()
{    
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string line;
    bool is_first = true;
    
    while (getline(cin, line))
    {   
        if (!is_first)
            cout << '\n';
        is_first = false;
        
        // count the ASCII frequency
        vector<int> cnt(129, 0); 
        for (char c : line)  
            cnt[c]++;
        
        // Output
        for (int freq = 1; freq <= 1000; freq++)
            for (int ascii = 128; ascii > 31; ascii--)  
                if (cnt[ascii] == freq)
                    cout << ascii << ' ' << freq << '\n';
    }
    
    return 0;
}

# 10057 A mid-summer night’s dream

## Code

#include <bits/stdc++.h>
using namespace std;

int main() 
{
	ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    while(cin >> n) 
    {
        vector<int> vec(n);
        
        for(int i = 0; i < n; i++)
            cin >> vec[i];
        
        sort(vec.begin(), vec.end());
       
        // 找中位數
        int left_middle = vec[(n - 1) / 2]; 
        int right_middle = vec[n / 2];        
        
        // 計算陣列中，有多少個的數字在 [左中, 右中] 範圍內
        int cnt = 0;
        for(int i = 0; i < n; i++)
            if(vec[i] >= left_middle && vec[i] <= right_middle)
                cnt++;

        // 左中 <= x <= 右中
        int x = right_middle - left_middle + 1;
        
        cout << left_middle << " " << cnt << " " << x << "\n";
    }
    
    return 0;
}

# 10226 Hardwood Species

## Code

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    cin.ignore(2);
    bool first = true;
    
    while (T--)
    {
        if (!first)
            cout << '\n';
        first = false;
        
        map<string, int> tree_cnt;
        string tree_name;
        int total = 0;
        
        while (getline(cin, tree_name))
        {
            if (tree_name.empty())
                break;
            
            tree_cnt[tree_name]++;
            total++;
        }
        
        cout << fixed << setprecision(4);
        
        for (auto& p : tree_cnt)
            cout << p.first << " " << (double)p.second * 100 / total << '\n';
    }
    
    return 0;
}