---
# System prepended metadata

title: 0-7 陣列及0-8 迴圈
tags: [演算法, C++, APCS, Python]

---

# 0-7 陣列及0-8 迴圈

講義不是我寫的，網址在此 https://emanlaicepsa.github.io/2020/10/21/0-index/
我只是將自己寫的練習題程式碼記錄下來。
最後更新日期：2024年10月6日

## [TOJ: 104 / 星星樹](https://toj.tfcis.org/oj/pro/104/)

### Python 程式碼

執行時間最久約為 27 ms，使用記憶體最多約為 4164 kB，通過測試。
```python=
n = int(input())
for i in range(n):
    for j in range(1, (n-i-1)+2*(i+1)):
        print(" " if j<n-i else "*", end="")
    print()
```

### C++ 程式碼

執行時間最久約為 2 ms，使用記憶體最多約為 308 kB，通過測試。
```cpp=
#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(0),cin.tie(0);
    int n; cin >> n;
    for(int i=0; i<n; i++) {
        for(int j=1; j<(n-i-1)+2*(i+1); j++) {
            if (j<n-i) cout << " ";
            else cout << "*";
        }
        cout << "\n";
    }
    return 0;
}
```

## [TOJ: 106 / 精靈的家在哪](https://toj.tfcis.org/oj/pro/106/)

### Python 程式碼

執行時間最久約為 20 ms，使用記憶體最多約為 4116 kB，通過測試。
```python=
n = 2
while n%71: n = n*2 + 1
if n%3 == 0: print("right")
else: print("left")
```

### C++ 程式碼

執行時間最久約為 1 ms，使用記憶體最多約為 284 kB，通過測試。
```cpp=
#include<iostream>
using namespace std;

int main() {
    int n = 2;
    while(n%71) n = n*2 + 1;
    if (n%3 == 0) cout << "right\n";
    else cout << "left\n";
    return 0;
}
```

## [TOJ: 107 / 紀念品的難題](https://toj.tfcis.org/oj/pro/107/)

### Python 程式碼

執行時間最久約為 21 ms，使用記憶體最多約為 4116 kB，通過測試。
```python=
n, tot = 30, 0
for i in range(n):
    tot += 1
    for j in range(i+1):
        tot += 1
        for k in range(j+1):
            tot += j+k+1
print(tot)
```

比較好的寫法，執行時間最久約為 23 ms，使用記憶體最多約為 3960 kB，通過測試。
```python=
n, tot = 30, 0
for i in range(1, n+1):
    son = 1
    gdau = i
    ggson = i * (i*(i+1)//2)
    tot += son + gdau + ggson
print(tot)
```

### C++ 程式碼

執行時間最久約為 1 ms，使用記憶體最多約為 284 kB，通過測試。
```cpp=
#include <iostream>
using namespace std;

int main() {
    int n = 30, tot = 0;
    for(int i=0; i<n; i++) {
        tot++;
        for(int j=0; j<i+1; j++) {
            tot++;
            for(int k=0; k<j+1; k++) {
                tot += j+k+1;
            }
        }
    }
    cout << tot << "\n";
    return 0;
}
```

比較好的寫法，執行時間最久約為 1 ms，使用記憶體最多約為 128 kB，通過測試。
```cpp=
#include <iostream>
using namespace std;

int main() {
    int n = 30, tot = 0;
    for(int i=1; i<=n; i++) {
        int son = 1;
        int gdau = i;
        int ggson = i * (i*(i+1)/2);
        tot += son + gdau + ggson;
    }
    cout << tot << "\n";
    return 0;
}
```

## [TOJ: 110 / 六芒星的咒符](https://toj.tfcis.org/oj/pro/110/)

### Python 程式碼

寫法1，先産生上半部三角形資料，複製、反轉成下半部三角形資料，最後再合併成六芒星。執行時間最久約為 30 ms，使用記憶體最多約為 4332 kB，通過測試。
```python=
n = int(input())  # 三角形個數
for _ in range(n):  # 執行 n 次
    h = int(input())  # 三角形高度
    w = 2*h - 1  # 三角形底部寬度
    up = []  # 上半部三角形每列的形狀
    for i in range(h):  # 執行 h 次
        s = " "*((w-1)//2-i)  # 左側的空格
        s += "*"*(2*i+1)  # 中間的 *
        up.append(s)  # 將組合而成的字串加入 up
    down = up.copy()  # 複製 up 的資料到 down
    down.reverse()  # 將 down 的資料反過來
    tri = up[:h-3] + [down[0]] + up[h-2:] + down[3:]  # 合併 up 及 down 成為六芒星
    for t in tri: print(t)  # 依序印出 tri 的資料
```

寫法2，只産生上半部三角形資料，用 for 迴圈控制要印出的資料範圍及順序。執行時間最久約為 23 ms，使用記憶體最多約為 4160 kB，通過測試。
```python=
n = int(input())  # 三角形個數
for _ in range(n):  # 執行 n 次
    h = int(input())  # 三角形高度
    w = 2*h - 1  # 三角形底部寬度
    tri = []  # 上半部三角形每列的形狀
    for i in range(h):  # 執行 h 次
        s = " "*((w-1)//2-i)  # 左側的空格
        s += "*"*(2*i+1)  # 中間的 *
        tri.append(s)  # 將組合而成的字串加入 tri
    for i in range(h-3): print(tri[i])  # 印出 tri[0] ~ tri[h-2]
    print(tri[-1])  # 印出 tri[-1]，也可以寫成 tri[h-1]
    for i in range(h-2, h): print(tri[i])  # 印出 tri[h-2] ~ tri[h-1]
    for i in range(h-4, -1, -1): print(tri[i])  # 印出 tri[h-4] ~ tri[0]
```

### C++ 程式碼

執行時間最久約為 1 ms，使用記憶體最多約為 284 kB，通過測試。
```cpp=
#include <iostream>
#include <string>
using namespace std;

int main() {
    int n; cin >> n;  // 三角形個數
    for(int i=0; i<n; i++) {  // 執行 n 次
        int h; cin >> h;  // 三角形高度
        int w = 2*h - 1;  // 三角形底部寬度
        string tri[h];  // 上半部三角形每列的形狀
        for(int j=0; j<h; j++) {  // 執行 h 次
            string s = "";  // 空字串
            for(int k=0; k<(w-1)/2-j; k++) s += " ";  // 左側的空格
            for(int k=0; k<2*j+1; k++) s += "*";  // 中間的 *
            tri[j] = s;  // 將組合而成的字串加入 tri
        }
        for(int j=0; j<h-3; j++) cout << tri[j] << "\n";  // 印出 tri[0] ~ tri[h-2]
        cout << tri[h-1] << "\n";  // 印出 tri[h-1]
        for(int j=h-2; j<h; j++) cout << tri[j] << "\n";  // 印出 tri[h-2] ~ tri[h-1]
        for(int j=h-4; j>=0; j--) cout << tri[j] << "\n";  // 印出 tri[h-4] ~ tri[0]
    }
    return 0;
}
```

## [TOJ: 114 / 我閉著眼](https://toj.tfcis.org/oj/pro/114/)

### Python 程式碼

執行時間最久約為 30 ms，使用記憶體最多約為 4108 kB，通過測試。
```python=
grid = [list(map(int, input().split())) for _ in range(5)]  # 讀取盤面
flag = False  # 是否有找到解
for r in range(5):  # 依序檢查第 0 ~ 4 列
    if flag: break  # 如果已找到解，中止迴圈
    for c in range(4):  # 依序檢查第 0 ~ 3 欄
        now = grid[r][c]  # 現在的格子數字
        if now == grid[r][c+1] and now == grid[r][c+2]:  # 檢查右側兩欄
            flag = True; break  # 如果數字皆等於 now，找到解，中止迴圈

for c in range(6):  # 依序檢查第 0 ~ 5 欄
    if flag: break  # 如果已找到解，中止迴圈
    for r in range(3):  # 依序檢查第 0 ~ 2 列
        now = grid[r][c]  # 現在的格子數字
        if now == grid[r+1][c] and now == grid[r+2][c]:  # 檢查下方兩列
            flag = True; break  # 如果數字皆等於 now，找到解，中止迴圈

print("Yes" if flag else "No")  # 如果找到解印出 Yes，否則印出 No
```

### C++ 程式碼

執行時間最久約為 1 ms，使用記憶體最多約為 248 kB，通過測試。
```cpp=
#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int grid[5][6];  // 盤面資料
    for(int r=0; r<5; r++)
        for(int c=0; c<6; c++)
            cin >> grid[r][c];
    
    bool flag = false;  // 是否有找到解
    for(int r=0; r<5; r++) {  // 依序檢查第 0 ~ 4 列
        if (flag) break;  // 如果已找到解，中止迴圈
        for(int c=0; c<4; c++) {  // 依序檢查第 0 ~ 3 欄
            int now = grid[r][c];  // 現在的格子數字
            if (now == grid[r][c+1] && now == grid[r][c+2]) {  // 檢查右側兩欄
                flag = true; break;  // 如果數字皆等於 now，找到解，中止迴圈
            }
        }
    }
    for(int c=0; c<6; c++) {  // 依序檢查第 0 ~ 5 欄
        if (flag) break;  // 如果已找到解，中止迴圈
        for(int r=0; r<2; r++) {  // 依序檢查第 0 ~ 2 列
            int now = grid[r][c];  // 現在的格子數字
            if (now == grid[r+1][c] && now == grid[r+2][c]) {  // 檢查下方兩列
                flag = true; break;  // 如果數字皆等於 now，找到解，中止迴圈
            }
        }
    }
    cout << (flag ? "Yes" : "No") << "\n";  // 如果找到解印出 Yes，否則印出 No
    return 0;
}
```

## [TOJ: 117 / 成績竄改](https://toj.tfcis.org/oj/pro/117/)

### Python 程式碼

執行時間最久約為 22 ms，使用記憶體最多約為 4124 kB，通過測試。
```python=
a = int(input())
imax = 0
for _ in range(a):
    b = int(input())
    if b > imax: imax = b

print(imax)
```

### C++ 程式碼

執行時間最久約為 1 ms，使用記憶體最多約為 304 kB，通過測試。
```cpp=
#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int a, b, imax = 0; cin >> a;
    for(int i=0; i<a; i++) {
        cin >> b;
        if (b > imax) imax = b;
    }
    cout << imax << "\n";
    return 0;
}
```

## [TOJ: 119 / B. Brainwash](https://toj.tfcis.org/oj/pro/119/)

### Python 程式碼

執行時間最久約為 99 ms，使用記憶體最多約為 16052 kB，通過測試。
```python=
n = int(input())
data = [0] + list(map(int, input().split()))
t = int(input())
flag = True
for _ in range(t):
    a, b = map(int, input().split())
    if abs(a-b) > 8:
        print("I QUIT!")
        print(*data[1:])
        flag = False; break
    else:
        data[a], data[b] = data[b], data[a]

if flag:
    print("SORTED!")
    print(*data[1:])
```

### C++ 程式碼

執行時間最久約為 14 ms，使用記憶體最多約為 1300 kB，通過測試。
```cpp=
#include <iostream>
#include <cmath>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    int data[n+1] = {0};
    for(int i=1; i<=n; i++) cin >> data[i];
    int t; cin >> t;
    bool flag = true;
    for(int i=0; i<t; i++) {
        int a, b; cin >> a >> b;
        if (!flag) continue;
        if (abs(a-b) > 8) {
            cout << "I QUIT!\n";
            for(int j=1; j<=n; j++) cout << data[j] << " \n"[j == n];
            flag = false;
        } else {
            int c = data[a];
            data[a] = data[b];
            data[b] = c;
        }
    }
    if (flag) {
        cout << "SORTED!\n";
        for(int j=1; j<=n; j++) cout << data[j] << " \n"[j == n];
    }
    return 0;
}
```

## [TOJ: 3 / GCD](https://toj.tfcis.org/oj/pro/3/)

### Python 程式碼

寫法1，輾轉相除法，執行時間最久約為 23 ms，使用記憶體最多約為 3992 kB，通過測試。
```python=
n = int(input())
for _ in range(n):
    a, b = map(int, input().split())
    while b: a, b = b, a%b
    print(a)
```

寫法2，使用 math.gcd，執行時間最久約為 19 ms，使用記憶體最多約為 3996 kB，通過測試。
```python=
from math import gcd

n = int(input())
for _ in range(n):
    a, b = map(int, input().split())
    print(gcd(a, b))
```

### C++ 程式碼

寫法1，輾轉相除法，執行時間最久約為 2 ms，使用記憶體最多約為 248 kB，通過測試。
```cpp=
#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    for(int i=0; i<n; i++) {
        int a, b, r; cin >> a >> b;
        while(b) {
            r = a%b;
            a = b;
            b = r;
        }
        cout << a << "\n";
    }
    return 0;
}
```

寫法2，使用 algorithm 函式庫的 gcd，執行時間最久約為 1 ms，使用記憶體最多約為 284 kB，通過測試。
```cpp=
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    for(int i=0; i<n; i++) {
        int a, b; cin >> a >> b;
        cout << __gcd(a, b) << "\n";
    }
    return 0;
}
```

## [TOJ: 8 / Scytale](https://toj.tfcis.org/oj/pro/8/)

### Python 程式碼

第3筆測資遇到 RuntimeError。
```python=
import sys

for line in sys.stdin:
    n = int(line.strip())  # 角柱數量 n
    s = input()  # 讀取一行字串
    m = len(s)//n  # 字串分成 n 等份，每一份長度為 m
    for i in range(n):  # 依序讀取 n 個角柱
        for j in range(m):  # 依序讀取每個每一份第 j 個字元
            print(s[j*n+i], end="")  # 索引值為 j*n+i
    print()  # 換行
```

### C++ 程式碼

執行時間最久約為 1 ms，使用記憶體最多約為 304 kB，通過測試。
```cpp=
#include <iostream>
#include <string>
#include <cstdio>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;  // 角柱數量 n
    while(cin >> n) {
        cin.ignore();  // 清除緩衝區內容，沒加這行底下的 getline 讀不到東西
        string s;  // 字串 s
        getline(cin, s);  // 讀取一行字串
        int m = (int)s.size()/n;  // 字串分成 n 等份，每一份長度為 m
        for(int i=0; i<n; i++)  // 依序讀取 n 個角柱
            for(int j=0; j<m; j++)  // 依序讀取每個每一份第 j 個字元
                cout << s[j*n+i];  // 索引值為 j*n+i
        cout << "\n";  // 換行
    }
    return 0;
}
```

## [TOJ: 120 / C. Counting Stars](https://toj.tfcis.org/oj/pro/120/)

### Python 程式碼

第2筆測資超時。
```python=
N = int(input())
ns = [0] + list(map(int, input().split()))
psum = [0]*(N+1)
for i in range(1, N+1): psum[i] = psum[i-1] + ns[i]
Q = int(input())
for _ in range(Q):
    le, ri = map(int, input().split())
    if le > ri: le, ri = ri, le  # 如果 le > ri，兩者交換
    print(psum[ri] - psum[le-1])
```

### C++ 程式碼

儲存加總的陣列格式要用 long long，用 int 會溢位。執行時間最久約為 73 ms，使用記憶體最多約為 3172 kB，通過測試。
```cpp=
#include <iostream>
#include <algorithm>
typedef long long LL;
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int N; cin >> N;
    LL psum[N+1] = {0};
    for(int i=1; i<=N; i++) {
        int n; cin >> n;
        psum[i] = psum[i-1] + n;
    }
    int Q; cin >> Q;
    for(int i=0; i<Q; i++) {
        int le, ri; cin >> le >> ri;
        if (le > ri) swap(le, ri);  // 如果 le > ri，兩者交換
        cout << psum[ri] - psum[le-1] << "\n";
    }
    return 0;
}
```

## [TOJ: 485 / 重組回文](https://toj.tfcis.org/oj/pro/485/)

### Python 程式碼

第3、4筆測資超時。
```python=
n = int(input())  # 字串長度
s = input()  # 字串
ans = n-1  # 答案預設為 n-1
for i in range(n-1, -1, -1):  # 依序産生 n-1 ~ 0
    flag = True  # 是否為迴文，預設為 True
    le, ri = i, n-1  # 左側索引值 le，右側索引值 ri
    while le < ri:  # 如果 le < ri，還沒有重疊，繼續執行
        if s[le] != s[ri]:  # 如果字元不同
            flag = False  # 已經不是迴文
            break  # 中止迴圈
        le += 1; ri -= 1  # le 向右1格，ri 向左1格
    # end of while loop
    if flag: ans = i  # 如果是回文，ans 為 i，答案只會越來越小
# end of for loop
print(ans)  # 印出答案
```

### C++ 程式碼

執行時間最久約為 47 ms，使用記憶體最多約為 560 kB，通過測試。
```cpp=
#include <iostream>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    string s; cin >> s;
    int ans = n-1;
    for(int i=n-1; i>=0; i--) {
        bool flag = true;
        for(int le=i, ri=n-1; le<ri; le++, ri--) {
            if (s[le] != s[ri]) {
                flag = false;
                break;
            }
        }
        if (flag) ans = i;
    }
    cout << ans << "\n";
    return 0;
}
```

## [TOJ: 501 / pD. 團ㄎㄧㄤ遊戲](https://toj.tfcis.org/oj/pro/501/)

### Python 程式碼

原來講義上的寫法，我自己想到的寫法沒這麼精簡。比較需要解釋的是以下3行

1. 第3行：為了使索引值對到人的編號，開頭放入 0。頂多是從第n個繞回來到第n-1個，t要存2次。
2. 第6行：如果 now+1 較小，代表第i個人記憶力足夠，可以繼續接下去；如果 m[i] 較小，代表第i個人記憶力不夠，相當於以他前 m[i]-1 個人為開頭才能使他記住，因此 now 改為 m[i]。
3. 第7行：每次都要更新 ans，取 ans 及 now 較大者。

執行時間最久約為 349 ms，使用記憶體最多約為 14420 kB，通過測試。
```python=
n = int(input())  # 人數
t = list(map(int, input().split()))  # 暫存每個人的記憶力
m = [0] + t + t  # 每個人的記憶力
ans, now = 0, 0  # 答案 ans、目前需要的記憶力 now，皆預設為0
for i in range(1, 2*n+1):  # 依序檢查第1個人 ~ 第2輪第n個人
    now = min(now+1, m[i])  # 目前需要的記憶力，取 now+1 及 m[i] 較小者
    ans = max(ans, now)  # 答案取 ans 及 now 較大者
# end of for loop
print(min(ans, n))  # 印出 ans 及 n 較小者，每個人都能輪到是最大的答案 n
```

### C++ 程式碼

執行時間最久約為 10 ms，使用記憶體最多約為 1172 kB，通過測試。
```cpp=
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    int m[2*n+1] = {0};
    for(int i=1; i<=n; i++) {
        cin >> m[i]; m[i+n] = m[i];
    }
    int ans = 0, now = 0;
    for(int i=1; i<=2*n; i++) {
        now = min(now+1, m[i]);
        ans = max(ans, now);
    }
    cout << min(ans, n) << "\n";
    return 0;
}
```
------

###### tags:`演算法`、`APCS`、`Python`、`C++`