# APCS實作題2020年7月第1題：購物車

> 日期：2023年9月13日
> 作者：王一哲
> 題目來源：109年7月實作題第1題
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=f579)

<br />

## 題目

### 問題描述

給兩個整數 $a$、$b$，代表你要觀察的商品編號。

商場在每一位客人的購物車都放置了一個感應器，能夠得知每位客人將商品放入購物車或拿出購物車。感應器存放的紀錄是一連串的整數，一個正整數 $x$ 表示這位客人將一個編號是 $x$ 的商品放入他的購物車，一個負數 $-x$ 表示這位客人將一個編號是 $x$ 的商品從他的購物車移除。

現在有 $n$ 位客人的購物車紀錄，你想要統計有幾位客人最後有購買商品 $a$ 與 $b$ 商品，一個客人有購買商品 $x$ 表示商品 $x$ 在他的購物車中放入的次數比拿出還多。
<br />

### 輸入格式

第一行有兩個正整數 $a$、$b$（$1 \leq a, b \leq 100$）。

第二行有一個正整數 $n$（$1 \leq n \leq 100$），表示客人的數量。

接下來有 $n$ 行，第 $i$ 行表示第 $i$ 位客人的購物車紀錄。對於每個購物車紀錄包含一連串的整數，最後一個數字必定為 0，表示購物紀錄結尾，其他數字必定為非 0 的整數且絕對值不超過 100，定義同題目敘述。

配分
- 50分：每一行購物車紀錄只有 2 個正整數與一個結尾 0 (不會有取出的動作)。
- 50分：同原題目限制。
<br />

### 輸出格式

輸出一個整數，表示有幾位客人同時有購買商品 $a$ 與商品 $b$。
<br />

### 範例一：輸入

1 8
5
1 8 0
5 6 0
2 7 0
8 1 0
33 22 0

### 範例一：正確輸出

2

<br />

### 範例二：輸入

3 9
2
3 9 -3 3 9 0
3 3 -3 -3 9 0

### 範例二：正確輸出

1

<br />

## Python 程式碼

於 ZeroJudge 測試結果，最長運算時間約為 28 ms，使用記憶體最多約為 3.3 MB，通過測試。

a, b = map(int, input().split())   # 讀取要觀察的商品編號
n = int(input())   # 讀取顧客人數
ans = 0            # 答案預設為0
for _ in range(n): # 讀取n行資料
    na, nb = 0, 0  # 這個顧客購買商品a、b的數量，預設為0
    data = list(map(int, input().split()))  # 讀取購物車紀錄存入串列 data
    for d in data: # 由 data 依序讀取紀錄，計算購買商品a、b的數量
        if d == a: na += 1
        elif d == -a: na -= 1
        elif d == b: nb += 1
        elif d == -b: nb -= 1
    if na >= 1 and nb >= 1: ans += 1  # 如果 na、nb 皆大於等於1，ans 加1

print(ans)  # 印出答案

<br /><br />

## C++ 程式碼

於 ZeroJudge 測試結果，最長運算時間約為 5 ms，使用記憶體最多約為 332 kB，通過測試。

#include <iostream>
using namespace std;

int main() {
    int a, b, n, ans = 0;  // 答案預設為0
    cin >> a >> b;   // 讀取要觀察的商品編號
    cin >> n;        // 讀取顧客人數
    
    for(int i=0; i<n; i++) {  // 讀取n行資料
        int na = 0, nb = 0, d;// 這個顧客購買商品a、b的數量，預設為0；購物車紀錄d
        while(cin >> d) {
            if (d == a) {
                na++;
            } else if (d == -a) {
                na--;
            } else if (d == b) {
                nb++;
            } else if (d == -b) {
                nb--;
            } else if (d == 0) {
                break;
            }
        }
        if (na >= 1 && nb >= 1) ans++;  // 如果 na、nb 皆大於等於1，ans 加1
    }
    cout << ans << endl;  // 印出答案
    return 0;
}

<br /><br />

---

###### tags:`APCS`、`Python`、`C++`