CPE-49
針對我比較不熟的題目做的筆記
這樣下次考試前就不用翻程式碼進入回憶錄了
公式題
UVA 10021 Satellites
題意
計算兩個在相同軌道的衛星的距離
a：衛星到地球的距離
b：與地球形成的夾角
s：角度的單位
輸出：兩個衛星之間的弧長、弦長
思路
1 deg = 60 min
所以如果角度單位是 min，先幫將其換成 deg
如果角度大於 180 度的話，使用補角
衛星的軌道半徑為
將度轉換成弧度
弧長公式：
弦長公式：
程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;
int main() {
double a, b, r;
string s;
while (cin >> a >> b >> s) {
r = 6440 + a;
if (s == "min") b /= 60;
if (b > 180) b = 360 - b;
b = b * acos(-1) / 180;
cout << fixed << setprecision(6) << r*b << ' ' << 2*r*sin(b/2) << endl;
}
}UVA 10056 What is the Probability?
題意
總共有 n 個人，輪流擲骰子直到有人獲勝，獲勝條件隨機
給你達成獲勝條件的機率，計算第 r 個人獲勝的機率
思路
總人數：n
獲勝機率：p
計算勝率的目標：r
單次失敗的機率：q = 1 - p
如果獲勝機率
p為 0，則所有人都不可能獲勝
因此做一個特判，直接輸出 0
直接帶入公式後輸出：
程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
for (cin >> t; t; t--) {
double n, p, r, q;
cin >> n >> p >> r;
q = 1-p;
if (!p) cout << p;
else cout << fixed << setprecision(4) << pow(q, (r-1)) * p / (1 - pow(q, n));
cout << endl;
}
}UVA 10642 Can You Solve It?
題意
依照題目的附圖中提供的 x , y 軸和移動路線
從座標 (st, sy) 到 (ex, ey) 需要移動多少次
思路
對於 (x, y) 點在圖上的斜線可以給予一個代號稱呼為 k = x + y
例如 (0, 1) 在 k = 1 這條線上，(1, 0) 也在 K = 1 這條線上，(0, 2) 則在 k = 2 這條線上
那要計算從 (0, 0) 走到 (x, y) 需要幾條路，可以用此公式來計算：走到 k 線要幾條路 + 偏移量 x
走到 k 有幾條路的公式：
最後 K = x + y 可以推導出從 (0, 0) 走到 (x, y) 經過幾條路的函數：
題目會給予起點 (sx, sy) 跟終點 (ex, ey)
程式碼只需要讀取資料後並輸出 S(ex, ey) - S(sx, sy) 即可
程式碼
1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
using namespace std;
int main() {
int n, i = 1;
for (cin >> n; i <= n; i++) {
int sx, sy, ex, ey;
cin >> sx >> sy >> ex >> ey;
cout << "Case " << i << ": " << ((ex+ey)*(ex+ey+1)/2 + ex) - ((sx+sy)*(sx+sy+1)/2 + sx) << endl;
}
}UVA 10268 498-bis
題意
給你一個數字 x 跟一串數字 a
a 代表一個一元多次方程式，每一項數字由左到右的常數
例如：1 2 1 代表
目的為輸出將 a 方程式微分後代入 x 的結果
思路
因為方程式的常數微分後為 0，所以先將其移除
計算方式為：第 i 個常數 乘上 當前次方 乘上 x 的 當前次方減 1 的次方
當前次方 = n 常數總數（陣列長度） - i 第幾個數字（陣列索引）
轉換成程式碼為：v[i]*(n-i)*pow(x, n-i-1)
不過使用 pow 計算 x 的次方會有精確度的問題
所以使用每次迴圈將總和乘以 x 一次代替
程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
signed main() {
string s; int x, n;
while (cin >> x) {
cin.ignore();
getline(cin, s);
stringstream ss(s);
vector<int> v;
while (ss >> n) v.pb(n);
v.pop_back();
double sum = 0; n = v.size();
for (int i = 0; i < n; i++) {
sum *= x;
sum += v[i]*(n-i);
}
cout << (int)sum << '\n';
}
}UVA 10242 Fourth Point!!
題意
題目給予平行四邊形中兩鄰邊的端點
因為其中一點會重複兩次，目的是找出沒提到的第四點座標
思路
平行四邊形中對角座標相加後會相等（不知道原理的人自己去 Google）
可以用其特性來計算第四點
公式為：
程式碼只需要判斷哪一點是重複的，然後帶入公式即可
不會發生同一邊的端點座標相等，所以只需要判斷 4 次
程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;
int main() {
double x1, x2, x3, x4, y1, y2, y3, y4;
while (cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4) {
double x, y;
if (x1 == x3 && y1 == y3) {
x = x2 + x4 - x1;
y = y2 + y4 - y1;
}
else if (x1 == x4 && y1 == y4) {
x = x2 + x3 - x1;
y = y2 + y3 - y1;
}
else if (x2 == x4 && y2 == y4) {
x = x1 + x3 - x2;
y = y1 + y3 - y2;
}
else {
x = x1 + x4 - x2;
y = y1 + y4 - y2;
}
cout << fixed << setprecision(3) << x << ' ' << y << endl;
}
}先背下來題意就不用花時間看英文文章題
UVA 10057 A mid-summer night’s dream
題意
每筆測資給你 n 和 n 個數字
將數字放進公式後
輸出：
- 使算式能得到最小值的 A 的多種可能中，最小的 A
- 輸入的數字有多少個能得到算式的最小值
- A 有幾種可能
思路
能使算式的得到最小值的 A，其實就是整個數列的中位數
當 n 是奇數的時候，中位數為第 n/2 個數字
當 n 是偶數的時候，中位數為第 n/2-1 跟第 n/2 個數字相加除二
輸出 1 要判斷 n 是否為奇數或偶數，則輸出第 n/2 或 n/2-1 個數
輸出 2 要判斷 n 是否為奇數或偶數，則輸出第 n/2 或 n/2 + n/2-1 個數出現的次數
當
n為偶數時，第n/2和n/2-1個數值相等時，次數不用重複累加
輸出 3 要判斷 n 是否為奇數或偶數，則輸出第 1 （中位數只有一種可能） 或 n/2 個數減去 n/2-1 個數加 1 （A ~ B 的有幾個數字為 B - A + 1）
程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
while (cin >> n) {
vector<int> v(n);
map<int, int> mp;
for (auto &i : v) {
cin >> i;
mp[i]++;
}
sort(v.begin(), v.end());
if (n&1) cout << v[n/2] << ' ' << mp[v[n/2]] << " 1\n";
else cout << v[n/2-1] << ' ' << (v[n/2-1] == v[n/2] ? mp[v[n/2]] : mp[v[n/2]] + mp[v[n/2-1]]) << ' ' << v[n/2]-v[n/2-1]+1 << endl;
}
}UVA 10415 Eb Alto Saxophone Player
題意
根據題目給予的薩克斯風音階與按鍵
判斷輸入的音階順序，計算每個按鍵被按下的次數
按下的次數 會統計：之前原本沒按下的按鍵被按下
所以如果當前按下的按鍵，是上一個音階已經按下的按鍵，並不會計入次數
思路
使用 map 紀錄 mp[按鍵] = pair<按鍵, vector<範圍>>，範圍 = pair<起點, 終點>
接著從頭開始讀取音階
然後檢查所有按鍵有無在該音階的範圍
如果有先標註為按下，再檢查當前是否已經被按下，有的話計數器++
如果沒有在範圍內，則將按鍵標註為放開
最後輸出計數器的值
程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
for (cin >> n; n; n--) {
int cnt[10] = {}, n[10] = {};
map<char, vector<pair<int, int>>> mp = {
{'c', {{1, 3}, {6, 9}}},
{'d', {{1, 3}, {6, 8}}},
{'e', {{1, 3}, {6, 7}}},
{'f', {{1, 3}, {6, 6}}},
{'g', {{1, 3}}},
{'a', {{1, 2}}},
{'b', {{1, 1}}},
{'C', {{2, 2}}},
{'D', {{0, 3}, {6, 8}}},
{'E', {{0, 3}, {6, 7}}},
{'F', {{0, 3}, {6, 6}}},
{'G', {{0, 3}}},
{'A', {{0, 2}}},
{'B', {{0, 1}}}
};
string s;
cin >> s;
for (auto c : s) {
for (int i = 0; i < 10; i++) {
bool f = false;
for (auto j : mp[c]) if(i >= j.first && i <= j.second) f = true;
if (f) {
if (!n[i]) cnt[i]++;
n[i] = 1;
}
else n[i] = 0;
}
}
for (auto &i : cnt) cout << i << " \n"[&i == cnt+9];
}
}UVA 118 Mutant Flatworld Explorers
題意
模擬一個機器人按照指令在平台上移動
單純的按照指令移動會使機器人走出平台
所以機器人會記取上一次的教訓，不會在同一個地方失足第二次
請輸出每次指令執行完畢後，輸出機器人的位置及面向方位
如果掉出平台則輸出之前的位置且標記 LOST
思路
指令包含左轉跟右轉和前進
轉方向可以用方向 0 1 2 3 代表 上 右 下 左
左轉可以用 d = (d+3)%4 計算
右轉可以用 d = (d+1)%4 計算
前進只需要邊界判斷，然後用一個二維陣列做失足的紀錄
程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m, nx, ny, d, dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
string dir = "NESW", s;
char cd;
cin >> n >> m;
vector<vector<int>> v(m+1, vector<int>(n+1, 0));
while (cin >> nx >> ny >> cd) {
bool f = false;
cin >> s;
d = dir.find(cd);
for (auto c : s) {
if (c == 'L') d = (d+3)%4;
if (c == 'R') d = (d+1)%4;
if (c == 'F') {
nx += dx[d]; ny += dy[d];
if (nx < 0 || nx > n || ny < 0 || ny > m) {
nx -= dx[d]; ny -= dy[d];
if (!v[ny][nx]) {
v[ny][nx] = 1;
f = true;
break;
}
}
}
}
cout << nx << ' ' << ny << ' ' << dir[d] << (f ? " LOST" : "") << endl;
}
}UVA 11005 Cheapest Base
題意
給你 0 ~ 35 的成本跟整數 n
計算 n 是 2 ~ 36 進位的情況下，每一個位數的成本加總
找出成本總和最小的進位（輸出所有可能）
思路
在 i 進位時，n 對 i 取餘數來取得每一位數，取完後將 n 除 i 以刪除位數
可以使用 while 迴圈來取位數至數字歸零
接著透過成本表計算出成本總和後記錄並標註最小值
最後輸出成本總和最小的進位數
程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, t;
for (cin >> n, t = 0; n; n--) {
if (t) cout << endl;
cout << "Case " << ++t << ":\n";
vector<int> v(36);
for (auto &i : v) cin >> i;
int k;
for (cin >> k; k; k--) {
int input, tmp, mn = 1e9;
vector<int> ans(38, 0);
cin >> input;
for (int i = 2; i <= 36; i++) {
int cost = 0;
tmp = input;
while (tmp) {
cost += v[tmp % i];
tmp /= i;
}
mn = min(mn, cost);
ans[i] = cost;
}
cout << "Cheapest base(s) for number " << input << ":";
for (int i = 2; i <= 36; i++) if (ans[i] == mn) cout << ' ' << i;
cout << endl;
}
}
}UVA 10093 An Easy Problem!
題意
給你一個 N 進位的數字 X（要用字串存）
且 X 可以被 N - 1 整除
請判斷最小的 N 為何並輸出
思路
如果這個數字 X 是 11，N 有可能是 2、3、4、5
但是可以透過兩個限制來找出 N
N - 1要可以整除X- 如果
X是N進位，X的每一個位數必須小於N
所以先遍歷一次 X，找出最大的位數
從 N = 最大的位數 + 1 開始到 62 進行大數除法，如果可以整除就輸出
程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
int main() {
string s, f = "0123456789ABCDEFGHIJKMNOLPQRSTUVWXYZabcdefghijkmnolpqrstuvwxyz";
while (cin >> s) {
int sum = 0, mx = 2;
for (auto &c : s) if (isalnum(c)) mx = max(mx, (int)f.find(c)+1);
string ans = "such number is impossible!";
for (int i = mx; i <= 62; i++) {
int sum = 0;
for (auto &c : s) if (isalnum(c)) sum = (sum*i+f.find(c))%(i-1);
if (!sum) {
ans = to_string(i);
break;
}
}
cout << ans << endl;
}
}UVA 11321 Sort! Sort!! And Sort!!!
題意
按照特地條件進行排序
若此項條件兩者相同，則使用下一項條件
- 兩數除以 m 的餘數大小
- 奇數在前偶數在後
- 若原為奇數較大者在前，較小者在後。若原為偶數則較小者在前，較大者在後。
思路
如果兩者除以 m 的餘數可以比出大小（不相同），就回傳餘數比大小
如果兩者都是奇數，就回傳原數值 大在前
如果兩者都是偶數，就回傳原數值 小在前
若上述條件都不符合，代表兩者一奇一偶，回傳 a 是否為奇數（不成立代表 b 是奇數）
程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
int n, m;
bool cmp(int a, int b) {
if (a%m != b%m) return a%m < b%m;
if (a&1 && b&1) return a > b;
if (!(a&1) && !(b&1)) return a < b;
return a&1;
}
int main() {
while (cin >> n >> m, cout << n << ' ' << m << endl, n+m) {
vector<int> v(n);
for (auto &i : v) cin >> i;
sort(v.begin(), v.end(), cmp);
for (auto i : v) cout << i << endl;
}
}UVA 10101 Bangla Numbers
題意
將輸入的數字依照孟加拉的單位輸出
思路
因為題目的測資範圍限制，kuti 只有機會出現一次
可以寫一個遞迴函式，該函式可以換算小於 kuti 的數字
如果數字大於 kuti，就把前後分兩部分拿去換算
程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<pair<int, string>> v = {
{100000, " lakh"},
{1000, " hajar"},
{100, " shata"},
};
int bn(int x) {
if (x >= 10000000) {
bn(x / 10000000);
cout << " kuti";
x %= 10000000;
}
for (auto i : v) {
if (x >= i.first) {
cout << ' ' << x/i.first << i.second;
x %= i.first;
}
}
if (x > 0) cout << ' ' << x;
}
signed main() {
int n, j = 0;
while (cin >> n) {
cout << setw(4) << ++j << '.';
if (!n) cout << " 0";
else bn(n);
cout << endl;
}
}UVA 10050 Hartals
題意
給你每個罷工團體罷工的頻率，代表從第一天開始數，每隔幾天後會罷工
計算 N 天中（從 1 開始數），有多少天有罷工事件發生
星期五、六為每週假日，假日罷工不計入統計
思路
用一個陣列儲存罷工頻率
用迴圈模擬 1 ~ N 天，判斷天數能不能被頻率整除，可以的話計數器++
如果天數對 7 取餘數為 6、0，代表當天為週五和週六，則跳過
輸出計數器
程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <vector>
using namespace std;
int main() {
int t;
for (cin >> t; t; t--) {
int n, p, cnt = 0;
cin >> n >> p;
vector<int> v(p);
for (auto &i : v) cin >> i;
for (int i = 1; i <= n; i++) {
if (i%7 == 6 || i%7 == 0) continue;
for (auto d : v) if (!(i%d)) {
cnt++;
break;
}
}
cout << cnt << endl;
}
}