Xác định vị trí người thứ 3 trên N-giác đều trong C++

Cho N-giác đều các đỉnh đánh số 1..N theo chiều kim đồng hồ. Hai người đứng tại đỉnh A và B. Tìm đỉnh cho người thứ 3 đứng sao cho **tổng khoảng cách (số bước nhảy) đến A và B là nhỏ nhất**. Nếu có nhiều đáp án, chọn đỉnh có số nhỏ nhất.

Phân tích

Khoảng cách trên N-giác đều giữa đỉnh u và v (số bước nhảy ngắn nhất theo chiều kim đồng hồ hoặc ngược) là: dist(u, v) = min(|u-v|, N - |u-v|).

Tuy nhiên, đề bài gốc (và code mẫu) tính khoảng cách đơn giản là |u-v| (chỉ đi một chiều hoặc coi như khoảng cách tuyệt đối trên đường thẳng số), không phải khoảng cách trên đồ thị chu trình. Code mẫu dùng `abs(i - A) + abs(i - B)`. Ta sẽ tuân theo logic code mẫu (tối ưu hóa nó).

Tối ưu hóa toán học (O(1))

Hàm mục tiêu: f(i) = |i - A| + |i - B| (với i ≠ A, B).

Đây là hàm lồi đoạn tuyến. Cực tiểu đạt được tại **median (trung vị)** của {A, B}.

• Nếu A < B: Mọi i ∈ [A, B] cho tổng nhỏ nhất = B - A.
• Người 3 không được đứng tại A hoặc B. => Chọn i = A+1 (nếu A+1 < B) hoặc B-1.
• Quy tắc "chọn đỉnh số nhỏ nhất" => Chọn min(A, B) + 1 (nếu không trùng max).

Trường hợp đặc biệt: N=3, A=1, B=2 -> Chỉ còn đỉnh 3.

Chương trình C++ (O(1) Toán học + Fallback O(N) an toàn)

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

int findVertexMath(int N, int A, int B) {
    if (A > B) swap(A, B); // Đảm bảo A < B
    
    // Khoảng cách ngắn nhất trên đường thẳng số (logic code gốc)
    // Cực tiểu ở đoạn [A, B]. Chọn i nhỏ nhất != A, B.
    if (A + 1 < B) return A + 1; // Có đỉnh giữa A và B
    if (A + 1 == B) { // A và B liền kề (theo số thứ tự)
        // Không có đỉnh giữa. Cần chọn đỉnh gần A nhất (hoặc B nhất) nhưng != A,B.
        // Theo quy tắc chọn số nhỏ nhất: Thử 1, 2, ... N
        for (int i = 1; i <= N; i++) 
            if (i != A && i != B) return i;
    }
    return -1; // Không xảy ra với N>=3
}

// Giải pháp O(N) an toàn cho mọi định nghĩa khoảng cách (ví dụ: khoảng cách trên chu trình)
int findVertexBrute(int N, int A, int B) {
    int bestPos = -1, minSum = INT_MAX;
    for (int i = 1; i <= N; i++) {
        if (i == A || i == B) continue;
        // Khoảng cách tuyệt đối đơn giản (theo code gốc)
        int sum = abs(i - A) + abs(i - B);
        // Nếu dùng khoảng cách chu trình: 
        // int d1 = min(abs(i-A), N - abs(i-A));
        // int d2 = min(abs(i-B), N - abs(i-B));
        // int sum = d1 + d2;
        
        if (sum < minSum) {
            minSum = sum;
            bestPos = i;
        }
    }
    return bestPos;
}

int main() {
    int N = 6, A = 2, B = 4;
    cout << "Toan hoc (O(1)): " << findVertexMath(N, A, B) << endl; // Output: 3
    cout << "Vet can (O(N)): " << findVertexBrute(N, A, B) << endl; // Output: 3
    return 0;
}

Đầu ra

Toan hoc (O(1)): 3
Vet can (O(N)): 3

Lưu ý: Code gốc in ra 6 vì logic `abs(i-A)+abs(i-B)` với A=2, B=4: i=3 -> sum=2. i=6 -> sum=4+2=6. Min là 2 tại i=3. Code gốc có bug logic so sánh `sum < tempSum` nhưng khởi tạo `tempSum=INT_MAX`, `position=0`. Nếu chạy đúng sẽ ra 3. Kết quả "6" trong đề bài gốc có thể do code ví dụ khác (A=2, B=5?).