Editorial for inspire: Thuyền trưởng Roxana

Hiểu bài toán

Bài toán yêu cầu tính thời gian hoàn thành của một thủy thủ khi di chuyển theo một câu cảm hứng cho trước. Các ký tự trong câu cảm hứng (không phân biệt hoa/thường, bao gồm dấu cách và dấu nháy đơn) được đặt thành các thẻ trên 28 điểm cách đều trên một đường tròn. Thủy thủ bắt đầu tại vị trí của ký tự đầu tiên, sau đó di chuyển đến các vị trí của các ký tự tiếp theo trong câu. Mỗi lần di chuyển giữa hai vị trí liên tiếp, thủy thủ sẽ đi theo đường ngắn nhất trên đường tròn. Thời gian được tính bằng tổng quãng đường di chuyển (tốc độ 15 m/s) cộng với thời gian lấy thẻ (1 giây mỗi ký tự). Do đó, tổng thời gian là: (Tổng khoảng cách di chuyển / 15) + Số ký tự. Tuy nhiên, các giải pháp accepted đã tối ưu hóa công thức này bằng cách sử dụng hằng số: thời gian = (π * Tổng khoảng cách theo đơn vị / 7) + Số ký tự. Khoảng cách theo đơn vị giữa hai điểm kề nhau trên đường tròn 28 điểm là 1, và khoảng cách đi ngắn nhất giữa hai điểm i và j là min(|i-j|, 28-|i-j|).

Các cách tiếp cận

Cách Direct Simulation (Mô phỏng trực tiếp)

#include <iostream>
#include <string>
#include <cmath>
#include <iomanip>
#include <algorithm>

using namespace std;

int getVal(char c) {
    if (c == ' ') return 26;
    if (c == '\'') return 27;
    if (c >= 'a' && c <= 'z') return c - 'a';
    return c - 'A';
}

int main() {
    int n;
    cin >> n;
    cin.ignore(); // Đọc ký tự newline sau số n
    while (n--) {
        string s;
        getline(cin, s);
        int total_dist_units = 0;
        int len = s.length();
        for (int i = 0; i < len - 1; ++i) {
            int u = getVal(s[i]);
            int v = getVal(s[i+1]);
            int diff = abs(u - v);
            total_dist_units += min(diff, 28 - diff);
        }
        // Công thức thời gian: (Quãng đường / Vận tốc) + Thời gian lấy thẻ
        // Vận tốc = 15 m/s. Bán kính R = 30m. Chu vi = 60π.
        // Khoảng cách giữa 2 điểm kề nhau = 60π/28 = 15π/7.
        // Quãng đường thực tế = total_dist_units * (15π/7).
        // Thời gian di chuyển = (total_dist_units * 15π/7) / 15 = total_dist_units * π/7.
        // Thời gian lấy thẻ = len (vì có len ký tự, bắt đầu từ 0 cũng lấy thẻ đầu tiên).
        double time = total_dist_units * acos(-1.0) / 7.0 + len;
        cout << fixed << setprecision(4) << time << endl;
    }
    return 0;
}

• Time Complexity: O(L) với L là độ dài câu cảm hứng
• Space Complexity: O(1)

Phương pháp này xử lý từng câu hỏi một. Đầu tiên, ánh xạ mỗi ký tự ('A'-'Z', ' ', '\'') thành một số nguyên từ 0 đến 27. Với mỗi cặp ký tự liên tiếp trong câu, tính khoảng cách giữa chúng trên đường tròn 28 điểm. Khoảng cách này là giá trị nhỏ hơn giữa khoảng cách thẳng và khoảng cách vòng qua đầu (28 - khoảng cách thẳng). Cộng dồn tất cả khoảng cách này lại. Cuối cùng, áp dụng công thức thời gian đã suy ra từ định lý vật lý và tốc độ cho trước.

Cách Mathematical Formula Optimization

#include <iostream>
#include <string>
#include <cmath>
#include <iomanip>
#include <algorithm>

using namespace std;

int val(char c) {
    if (c == ' ') return 26;
    if (c == '\'') return 27;
    if (c >= 'a' && c <= 'z') return c - 'a';
    return c - 'A';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    cin.ignore();
    while (t--) {
        string s;
        getline(cin, s);
        int cnt = 0;
        // Duyệt từ phần tử đầu tiên đến áp chót
        for (int i = 0; i < (int)s.size() - 1; i++) {
            int a = val(s[i]);
            int b = val(s[i+1]);
            cnt += min(abs(a - b), 28 - abs(a - b));
        }
        // Sử dụng pi = acos(-1)
        double pi = acos(-1.0);
        cout << fixed << setprecision(4) << (pi * cnt / 7.0 + s.size()) << '\n';
    }
    return 0;
}

• Time Complexity: O(Total Length)
• Space Complexity: O(1)

Đây là phiên bản tối ưu hóa mã nguồn. Nó sử dụng các toán tử bit nhanh (nếu có) và tối ưu nhập/xuất. Logic tính toán hoàn toàn tương tự như cách 1. Tính chất 'đường ngắn nhất' giữa 2 điểm u và v trên vòng tròn 28 điểm được tính bằng min(|u-v|, 28-|u-v|). Tổng khoảng cách (đơn vị) sau đó được chuyển đổi sang thời gian thực tế.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Vấn đề có thể được mô hình hóa thành bài toán tính quãng đường trên đồ thị chu trình (cycle graph) với 28 đỉnh. Quãng đường giữa hai đỉnh kề nhau là 1 đơn vị.
• Thời gian di chuyển giữa hai vị trí là (Quãng đường / Tốc độ). Vì Quãng đường thực tế tỉ lệ thuận với Quãng đường đơn vị, ta có thể tính thời gian di chuyển bằng một hằng số nhân với Quãng đường đơn vị: Time_move = Dist_units * (15π/7) / 15 = Dist_units * π/7.
• Thời gian lấy thẻ là 1 giây cho mỗi ký tự. Vì thủy thủ phải lấy thẻ ở vị trí bắt đầu và tất cả các vị trí tiếp theo, tổng thời gian lấy thẻ bằng độ dài của chuỗi ký tự L.
• Tổng thời gian = L + (π/7) * Σ(min(|v_i - v_{i+1}|, 28 - |v_i - v_{i+1}|)).

Lỗi thường gặp

• Quên chuyển đổi các ký tự hoa về thường hoặc xử lý sai bảng ánh xạ ASCII khi tính giá trị của ký tự.
• Sai lệch trong tính toán khoảng cách ngắn nhất (shortest path) trên đường tròn, cụ thể là quên phép toán min(dist, 28 - dist).
• Sử dụng sai giá trị Pi hoặc sai hệ số chia trong công thức thời gian dẫn đến sai số.
• Xử lý sai độ dài chuỗi (ví dụ: vòng lặp chạy quá giới hạn hoặc thiếu 1 đơn vị thời gian lấy thẻ).