Phân Tích Bất Đẳng Thức Tuyến Tính và Tạo Chuỗi Từ Liên Hoàn

1. Đánh giá Hệ Bất Đẳng Thức và Tính Hiệu Lớn Nhất

Mô tả bài toán:

Nhiệm vụ là kiểm tra một tập hợp các bất đẳng thức tuyến tính đã cho. Bạn cần xác định xem tất cả các bất đẳng thức này có được thỏa mãn đồng thời hay không. Ngoài ra, hãy tính toán và xuất ra phần nguyên của giá trị lớn nhất trong số các "hiệu" (vế trái trừ vế phải) của từng bất đẳng thức.

  • Các hệ số của bất đẳng thức (aij) là các giá trị kiểu double, được cung cấp dưới dạng ma trận hai chiều.
  • Các biến (xj) là các giá trị kiểu int, được cung cấp dưới dạng một mảng một chiều.
  • Các giá trị mục tiêu (bi, tức vế phải) là các giá trị kiểu double, được cung cấp dưới dạng một mảng một chiều.
  • Các toán tử ràng buộc giữa vế trái và vế phải chỉ có thể là các chuỗi ký tự: ">", ">=", "<", "<=", hoặc "=".

Ví dụ, xét một hệ bất đẳng thức có dạng:

a11x1 + a12x2 + ... + a15x5 <= b1;
a21x1 + a22x2 + ... + a25x5 <= b2;
a31x1 + a32x2 + ... + a35x5 <= b3;

Giá trị hiệu lớn nhất được tính bằng cách lấy phần tử lớn nhất từ tập hợp các giá trị (Vế Tráii - Vế Phảii) cho mỗi bất đẳng thức. Cụ thể:

max_diff = max { (a11x1+...+a15x5 - b1), (a21x1+...+a25x5 - b2), (a31x1+...+a35x5 - b3) }

Kết quả đầu ra của hiệu lớn nhất sẽ là phần nguyên của giá trị này (làm tròn xuống).

Định dạng đầu vào

Đầu vào là một chuỗi ký tự duy nhất chứa tất cả dữ liệu cần thiết, các phần tử được phân tách bằng dấu phẩy (,) và các nhóm dữ liệu được phân tách bằng dấu chấm phẩy (;). Chuỗi đầu vào có cấu trúc như sau:

  1. Các hệ số bất đẳng thức (double), theo thứ tự từng hàng một.
  2. Các giá trị của biến (int).
  3. Các giá trị mục tiêu (double).
  4. Các toán tử ràng buộc (string).

Ví dụ minh họa: a11,a12,a13,a14,a15,a21,a22,a23,a24,a25,a31,a32,a33,a34,a35;x1,x2,x3,x4,x5;b1,b2,b3;<=,<=,<=

Định dạng đầu ra

Đầu ra là một chuỗi gồm hai phần, cách nhau bởi một khoảng trắng:

  • Một giá trị boolean: true nếu tất cả các bất đẳng thức đều được thỏa mãn, ngược lại là false.
  • Một số nguyên: phần nguyên của hiệu lớn nhất đã tính.

Ví dụ 1

Đầu vào:

2.3,3,5.6,7,6;11,3,8.6,25,1;0.3,9,5.3,66,7.8;1,3,2,7,5;340,670,80.6;<=,<=,<=

Đầu ra:

false 458

Ví dụ 2

Đầu vào:

2.36,3,6,7.1,6;1,30,8.6,2.5,21;0.3,69,5.3,6.6,7.8;1,13,2,17,5;340,67,300.6;<=,>=,<=

Đầu ra:

false 758

Mã nguồn C++ thực hiện việc kiểm tra bất đẳng thức


#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm> // Cho std::max
#include <cmath>     // Cho std::abs
#include <limits>    // Cho std::numeric_limits

int main() {
    std::string lineInput;
    std::getline(std::cin, lineInput);

    // Thay thế dấu phẩy và chấm phẩy bằng khoảng trắng để dễ dàng phân tích
    for (char &c : lineInput) {
        if (c == ',' || c == ';') {
            c = ' ';
        }
    }

    std::stringstream dataStream(lineInput);

    // Giả định kích thước cố định theo mô tả bài toán (3 bất đẳng thức, 5 biến)
    const int NUM_INEQUALITIES = 3;
    const int NUM_VARIABLES = 5;

    std::vector<std::vector<double>> coefficients(NUM_INEQUALITIES, std::vector<double>(NUM_VARIABLES));
    std::vector<int> variables(NUM_VARIABLES);
    std::vector<double> targetValues(NUM_INEQUALITIES);
    std::vector<std::string> constraints(NUM_INEQUALITIES);

    // Đọc ma trận hệ số
    for (int i = 0; i < NUM_INEQUALITIES; ++i) {
        for (int j = 0; j < NUM_VARIABLES; ++j) {
            dataStream >> coefficients[i][j];
        }
    }

    // Đọc vector biến
    for (int i = 0; i < NUM_VARIABLES; ++i) {
        dataStream >> variables[i];
    }

    // Đọc vector giá trị mục tiêu
    for (int i = 0; i < NUM_INEQUALITIES; ++i) {
        dataStream >> targetValues[i];
    }

    // Đọc các ký hiệu ràng buộc
    for (int i = 0; i < NUM_INEQUALITIES; ++i) {
        dataStream >> constraints[i];
    }

    double maximumDifference = -std::numeric_limits<double>::infinity(); // Khởi tạo với số rất nhỏ
    bool allConditionsMet = true; // Cờ theo dõi tất cả điều kiện được thỏa mãn

    // Đánh giá từng bất đẳng thức
    for (int i = 0; i < NUM_INEQUALITIES; ++i) {
        double leftHandSideSum = 0.0;
        for (int j = 0; j < NUM_VARIABLES; ++j) {
            leftHandSideSum += coefficients[i][j] * variables[j];
        }

        double currentDifference = leftHandSideSum - targetValues[i];
        maximumDifference = std::max(maximumDifference, currentDifference);

        // Kiểm tra xem bất đẳng thức hiện tại có thỏa mãn không
        bool inequalityHolds = false;
        // Sử dụng một epsilon nhỏ để so sánh số thực, tránh lỗi làm tròn
        const double EPSILON = 1e-9; 

        if (constraints[i] == "<=") {
            inequalityHolds = (leftHandSideSum <= targetValues[i] + EPSILON); 
        } else if (constraints[i] == "<") {
            inequalityHolds = (leftHandSideSum < targetValues[i] - EPSILON);
        } else if (constraints[i] == ">=") {
            inequalityHolds = (leftHandSideSum >= targetValues[i] - EPSILON);
        } else if (constraints[i] == ">") {
            inequalityHolds = (leftHandSideSum > targetValues[i] + EPSILON);
        } else if (constraints[i] == "=") {
            inequalityHolds = (std::abs(leftHandSideSum - targetValues[i]) < EPSILON);
        }

        if (!inequalityHolds) {
            allConditionsMet = false;
        }
    }

    // Xuất kết quả
    std::cout << (allConditionsMet ? "true" : "false") << " " << static_cast<int>(maximumDifference) << std::endl;

    return 0;
}

2. Xây Dựng Chuỗi Từ Liên Hoàn

Mô tả bài toán

Bài toán "Xây Dựng Chuỗi Từ Liên Hoàn" yêu cầu bạn tạo một chuỗi từ dài nhất có thể bằng cách nối các từ lại với nhau theo một bộ quy tắc cụ thể:

  • Từ tiếp theo trong chuỗi phải bắt đầu bằng chữ cái cuối cùng của từ đứng trước nó.
  • Khi có nhiều từ có thể nối tiếp (tất cả đều bắt đầu bằng cùng một chữ cái), hãy ưu tiên chọn từ có độ dài lớn nhất.
  • Nếu vẫn có nhiều từ có cùng độ dài (và cùng chữ cái đầu), hãy chọn từ có thứ tự từ điển (lexicographical) nhỏ nhất.
  • Một từ đã được sử dụng trong chuỗi không được phép sử dụng lại.

Bạn sẽ được cung cấp một danh sách các từ (chỉ chứa chữ cái thường) và một từ khởi đầu. Kết quả cuối cùng là chuỗi từ dài nhất được tạo thành theo các quy tắc trên.

Định dạng đầu vào

  • Dòng đầu tiên chứa một số nguyên không âm startIndex, là chỉ số của từ khởi đầu trong mảng từ (0 <= startIndex < numWords).
  • Dòng thứ hai chứa một số nguyên không âm numWords, tổng số từ trong danh sách.
  • numWords dòng tiếp theo, mỗi dòng chứa một từ trong danh sách.

Ràng buộc:

  • Tổng số từ numWords nằm trong khoảng [1, 20].
  • Độ dài của mỗi từ nằm trong khoảng [1, 30].

Định dạng đầu ra

Một chuỗi ký tự duy nhất, biểu thị chuỗi từ liên hoàn cuối cùng.

Ví dụ 1

Đầu vào:

0
6
word
dd
da
dc
dword
d

Đầu ra:

worddwordda

Giải thích:

  1. Bắt đầu với từ có chỉ số 0: "word". Chữ cái cuối cùng là 'd'.
  2. Các từ chưa dùng bắt đầu bằng 'd' là: "dd" (dài 2), "da" (dài 2), "dc" (dài 2), "dword" (dài 5), "d" (dài 1). Chọn "dword" vì nó dài nhất. Chuỗi hiện tại: "worddword".
  3. Chữ cái cuối cùng của chuỗi là 'd'. Các từ chưa dùng bắt đầu bằng 'd' là: "dd" (dài 2), "da" (dài 2), "dc" (dài 2), "d" (dài 1).
    Trong số các từ dài nhất ("dd", "da", "dc"), "da" có thứ tự từ điển nhỏ nhất. Chọn "da". Chuỗi hiện tại: "worddwordda".
  4. Chữ cái cuối cùng của chuỗi là 'a'. Không còn từ nào chưa dùng bắt đầu bằng 'a'. Dừng quá trình.

Kết quả cuối cùng là "worddwordda".

Ví dụ 2

Đầu vào:

4
6
word
dd
da
dc
dword
d

Đầu ra:

dwordda

Giải thích:

  1. Bắt đầu với từ có chỉ số 4: "dword". Chữ cái cuối cùng là 'd'.
  2. Các từ chưa dùng bắt đầu bằng 'd' là: "dd" (dài 2), "da" (dài 2), "dc" (dài 2), "d" (dài 1). (Từ "word" không bắt đầu bằng 'd').
    Trong số các từ dài nhất ("dd", "da", "dc"), "da" có thứ tự từ điển nhỏ nhất. Chọn "da". Chuỗi hiện tại: "dwordda".
  3. Chữ cái cuối cùng của chuỗi là 'a'. Không còn từ nào chưa dùng bắt đầu bằng 'a'. Dừng quá trình.

Kết quả cuối cùng là "dwordda".

Mã nguồn C++ cho bài toán chuỗi từ liên hoàn


#include <iostream>
#include <vector>
#include <string>
#include <algorithm> // Cho std::max

int main() {
    int startIndex;
    std::cin >> startIndex;

    int numWords;
    std::cin >> numWords;

    std::vector<std::string> wordList(numWords);
    for (int i = 0; i < numWords; ++i) {
        std::cin >> wordList[i];
    }

    std::string currentChain = "";
    std::vector<bool> usedWords(numWords, false); // Theo dõi các từ đã sử dụng

    // Bắt đầu chuỗi với từ khởi tạo
    currentChain += wordList[startIndex];
    usedWords[startIndex] = true;

    // Xây dựng chuỗi theo cách tham lam (greedy)
    while (true) {
        char lastCharOfChain = currentChain.back(); // Chữ cái cuối cùng của chuỗi hiện tại
        std::string nextBestWord = ""; // Từ tốt nhất để nối tiếp
        int nextBestIndex = -1;       // Chỉ số của từ tốt nhất

        // Duyệt qua tất cả các từ có sẵn để tìm từ tốt nhất tiếp theo
        for (int i = 0; i < numWords; ++i) {
            // Kiểm tra nếu từ chưa được sử dụng và bắt đầu bằng chữ cái đúng
            if (!usedWords[i] && wordList[i][0] == lastCharOfChain) {
                // Áp dụng các quy tắc chọn: dài nhất, sau đó thứ tự từ điển nhỏ nhất
                if (nextBestIndex == -1 || // Chưa có ứng cử viên nào được tìm thấy
                    wordList[i].length() > nextBestWord.length() || // Từ hiện tại dài hơn
                    (wordList[i].length() == nextBestWord.length() && wordList[i] < nextBestWord)) { // Cùng độ dài, nhưng thứ tự từ điển nhỏ hơn
                    
                    nextBestWord = wordList[i];
                    nextBestIndex = i;
                }
            }
        }

        // Nếu tìm thấy một từ phù hợp để nối tiếp, thêm vào chuỗi và đánh dấu đã sử dụng
        if (nextBestIndex != -1) {
            currentChain += nextBestWord;
            usedWords[nextBestIndex] = true;
        } else {
            // Không còn từ nào có thể nối tiếp, thoát khỏi vòng lặp
            break;
        }
    }

    std::cout << currentChain << std::endl;

    return 0;
}

Thẻ: C++ Algorithms LinearInequalities StringManipulation GreedyAlgorithm

Đăng vào ngày 21 tháng 5 lúc 02:16

Thẻ Phổ Biến

©2026 Thành phố Cuồng loạn