要解決這個問題,我們需要模擬一個簡單的遊戲過程,其中偶數會殺掉下一個數字並移到數列的末尾,奇數則會直接移到數列的末尾。這個過程將重複進行,直到數列中只剩下一個數字。
可以使用雙端隊列 (deque) 來有效地模擬這個過程。雙端隊列允許我們在O(1)時間內從頭部和尾部插入和刪除元素,這對於本問題中的操作非常適合。
以下是解決這個問題的具體步驟:
1. 讀取輸入的數據。
2. 使用雙端隊列初始化數列。
3. 持續進行操作,直到數列中只剩下一個數字:
- 如果當前數字是偶數,移除下一個數字,並將當前數字移到數列的末尾。
- 如果當前數字是奇數,直接將當前數字移到數列的末尾。
4. 最後輸出剩下的那一個數字。
以下是實現上述邏輯的Python程式碼:
from collections import deque
def odd_killer(n, numbers):
queue = deque(numbers)
while len(queue) > 1:
current = queue.popleft()
if current % 2 == 0:
# It's an even number, so we kill the next number
queue.popleft()
queue.append(current)
return queue[0]
# 讀取輸入
n = int(input().strip())
numbers = list(map(int, input().strip().split()))
# 獲取最後存活的數字並輸出
result = odd_killer(n, numbers)
print(result)
```
### 說明
1. **初始化雙端隊列**:
- `queue = deque(numbers)`:將輸入的數字列表初始化為雙端隊列。
2. **模擬遊戲過程**:
- 使用 `while len(queue) > 1:` 保證數列中只剩下一個數字時停止操作。
- `current = queue.popleft()`:取出數列的第一個數字。
- 如果 `current` 是偶數,則使用 `queue.popleft()` 殺掉下一個數字。
- 無論 `current` 是奇數還是偶數,都將其放到數列的末尾 `queue.append(current)`。
3. **輸出結果**:
- 最後剩下的那一個數字位於隊列的開頭 `queue[0]`。
這個程式碼可以在短時間內處理最多 40,000 個數字的數列,並且能夠正確地模擬出遊戲的過程,從而得出正確的結果。