Codeforces A. IQ Test 題解：找出唯一奇偶性不同的數

問題重述

給定 n（3 ≤ n ≤ 100）個不超過 100 的自然數，保證其中 恰好一個 數的奇偶性與其他數不同。請輸出該數在輸入序列中的位置（1-based）。

核心觀察

只需檢查前三個數的奇偶性，即可決定「主流奇偶性」是奇數還是偶數：

• 若前三個數中有 ≥2 個為偶數 → 主流為偶數，目標是奇數。
• 反之主流為奇數，目標是偶數。

確定目標奇偶性後，再掃描一次找出第一個符合條件的數即可。

簡潔實作（C++）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; 
    cin >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;

    // 統計前三個數的偶數個數
    int evenCnt = 0;
    for (int i = 0; i < 3; ++i) if (a[i] % 2 == 0) ++evenCnt;

    // 目標奇偶性：true=找奇數, false=找偶數
    bool targetOdd = (evenCnt >= 2); 

    for (int i = 0; i < n; ++i) {
        if ((a[i] % 2 != 0) == targetOdd) {
            cout << i + 1 << '\n';
            break;
        }
    }
    return 0;
}

進階：單次掃描、無陣列版本

若想挑戰不使用陣列、單次讀取即解題，需維護狀態機：記錄前兩個數的奇偶性、可能的答案位置等。但實際競賽中不推薦，因為極易出錯且難以維護。上述「兩次掃描 + 陣列」寫法清晰、O(n) 時間、O(n) 空間（n ≤ 100 完全可接受），是最佳工程實踐。

複雜度分析

• 時間：O(n)，兩次線性掃描。
• 空間：O(n)，儲存輸入陣列（可優化為 O(1) 但無必要）。

測試樣例

輸入：
5
2 4 7 8 10

輸出：
3

解析：前三數 {2,4,7} 有兩個偶數 → 主流為偶數 → 找奇數 → 第 3 個數 7 是唯一奇數。