#40670: 解答 python


n0970616056@gmail.com (CIOU-HE-CHEN)

學校 : 不指定學校
編號 : 273811
來源 : [111.253.1.171]
最後登入時間 :
2024-06-14 11:55:43
n763. 我愛偶數 (之偶數殺手) -- 板橋高中教學題 | From: [27.247.62.29] | 發表日期 : 2024-06-04 22:18

要解決這個問題,我們需要模擬一個簡單的遊戲過程,其中偶數會殺掉下一個數字並移到數列的末尾,奇數則會直接移到數列的末尾。這個過程將重複進行,直到數列中只剩下一個數字。

可以使用雙端隊列 (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 個數字的數列,並且能夠正確地模擬出遊戲的過程,從而得出正確的結果。

 
ZeroJudge Forum