# 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++`
Sign in with Wallet
Connect another wallet