Bài toán đầu tiên yêu cầu xác định tính hợp lệ của ba ký tự cuối trong chuỗi đầu vào. Cần kiểm tra xem giá trị số được tạo thành có nằm trong khoảng từ 1 đến 349 (loại trừ giá trị 316) hay không. Giải pháp thực hiện bằng cách trích xuất chuỗi con và chuyển đổi thành số nguyên để kiểm tra điều kiện.

#include <iostream>
#include <string>
using namespace std;

int main() {
    string inputStr;
    cin >> inputStr;
    int numericValue = stoi(inputStr.substr(3, 3));
    
    if (numericValue >= 1 && numericValue <= 349 
        && numericValue != 316) {
        cout << "Yes";
    } else {
        cout << "No";
    }
    return 0;
}

Bài toán thứ hai mô phỏng trạng thái răng qua các thao tác thay đổi. Sử dụng mảng boolean để theo dõi răng còn nguyên vẹn hay đã bị gãy, đồng thời cập nhật số lượng răng đang hoạt động sau mỗi thao tác.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int totalTeeth, operationCount;
    cin >> totalTeeth >> operationCount;
    vector<bool> toothState(totalTeeth + 1, false);
    int activeTeeth = 0;

    while (operationCount--) {
        int toothIndex;
        cin >> toothIndex;
        if (toothState[toothIndex]) {
            activeTeeth--;
        } else {
            activeTeeth++;
        }
        toothState[toothIndex] = !toothState[toothIndex];
    }

    cout << totalTeeth - activeTeeth;
    return 0;
}

Bài toán thứ ba giải quyết vấn đề sắp xếp hoán vị bằng phương pháp hoán đổi trực tiếp. Sử dụng mảng ánh xạ để xác định vị trí hiện tại của từng giá trị, ghi nhận các thao tác hoán đổi cần thiết để đưa mỗi phần tử về vị trí đúng.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> permutation(n + 1);
    vector<int> positionMap(n + 1);
    vector<pair<int, int>> swapOperations;

    for (int i = 1; i <= n; ++i) {
        cin >> permutation[i];
        positionMap[permutation[i]] = i;
    }

    for (int i = 1; i <= n; ++i) {
        if (permutation[i] != i) {
            int currentPos = positionMap[i];
            swapOperations.push_back({i, currentPos});
            positionMap[permutation[i]] = currentPos;
            swap(permutation[i], permutation[currentPos]);
        }
    }

    cout << swapOperations.size() << endl;
    for (auto [left, right] : swapOperations) {
        cout << left << " " << right << endl;
    }
    return 0;
}

Bài toán cuối cùng tập trung vào phân tích đồ thị vô hướng. Cần tính toán số cạnh có thể thêm vào bằng cách xác định các thành phần liên thông, sau đó áp dụng công thức n*(n-1)/2 cho mỗi thành phần và trừ đi số cạnh hiện có.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    int vertices, edges;
    cin >> vertices >> edges;
    vector<vector<int>> adjacencyList(vertices + 1);
    vector<bool> visited(vertices + 1, false);

    for (int i = 0; i < edges; ++i) {
        int u, v;
        cin >> u >> v;
        adjacencyList[u].push_back(v);
        adjacencyList[v].push_back(u);
    }

    long long maxPossibleEdges = 0;
    for (int i = 1; i <= vertices; ++i) {
        if (visited[i]) continue;
        
        queue<int> componentQueue;
        componentQueue.push(i);
        visited[i] = true;
        int componentSize = 0;

        while (!componentQueue.empty()) {
            int node = componentQueue.front();
            componentQueue.pop();
            componentSize++;
            
            for (int neighbor : adjacencyList[node]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    componentQueue.push(neighbor);
                }
            }
        }
        maxPossibleEdges += static_cast<long long>(componentSize) * (componentSize - 1) / 2;
    }

    cout << maxPossibleEdges - edges;
    return 0;
}