HP CodeWars 2007 參考解答
************ 1. Powers of Two ************
//1. Powers of Two (HP CodeWars 2007) by Snail
#include <iostream>
using namespace std;
int main () {
int n, i;
cin >> n;
for (i=0; i<=n; i++)
cout << "2^" << i << " = " << (1 << i) << endl;
}
************ 2. Vertical Printing ************
//2. Vertical Printing (HP CodeWars 2007) by Snail
#include <iostream>
#include <string>
using namespace std;
int main () {
string s[17];
int n=0, i, j, mxl=0;
while (getline(cin,s[n]), s[n]!="END")
mxl = max ((int)s[n++].size(), mxl); //mxl--字串最大長度
for (i=0; i<n; i++)
s[i] += string (mxl-s[i].size(), ' '); //補空白
for (j=0; j<mxl; j++) {
for (i=0; i<n; i++)
cout << s[i][j] << " ";
cout << endl;
}
}
************ 3. Combination ************
//3. Combination (HP CodeWars 2007) by Snail
#include <iostream>
using namespace std;
int main () {
int n, m, c, i; //c(ombination)--組合
while (cin >> n >> m) {
m = min (m, n-m); //c(n,m) == c(n,n-m)
c = 1;
for (i=1; i<=m; i++)
c = c * (n-i+1) / i;
cout << c << endl;
}
}
************ 4. Password Analyzer ************
//4. Password Analyzer (HP CodeWars 2007) by Snail
#include <iostream>
#include <string>
using namespace std;
int main () {
string s, strength[] = {"WEAK", "ACCEPTABLE", "GOOD", "STRONG"};
while (cin >> s) {
int uc=0, lc=0, ds=0, i;
for (i=0; i!=s.size(); i++) {
uc = uc || isupper(s[i]); //u(pper) c(ase)--大寫
lc = lc || islower(s[i]); //l(ower) c(ase)--小寫
ds = ds || isdigit(s[i]) //d(igit) or s(ymbol)
|| ispunct(s[i]); //--數字或符號
}
i = (s.size()>=8) + (uc && lc) + ((uc || lc) && ds);
cout << "This password is " << strength[i] << endl;
}
}
************ 5. Overhanging Cards ************
//5. Overhanging Cards (HP CodeWars 2007) by Snail
#include <iostream>
using namespace std;
int main () {
float c, s, n; //有處理浮點數誤差的話，float 也能 AC
while (cin >> c) {
s = 0;
for (n=2; s+1e-6<c; n++) //1e-6 : 浮點數誤差
s += 1 / n;
cout << n-2 << " card(s)\n";
}
}
************ 6. Prime Directive ************
//6. Prime Directive (HP CodeWars 2007 (by Snail)
#include <iostream>
#include <iomanip>
using namespace std;
int main () {
int n, i, k=2, np=0, p[1010]={};
while (k < 1000) {
while (p[k]) //找下一個質數 k
k++;
p[np++] = k; //記錄質數
for (i=k; i<=1009; i+=k) //篩掉 k 的倍數
p[i] = 1;
}
while (cin >> n) {
for (i=0; p[i] <= n; i++) { //列出 <= n 的質數
if (i && i%5 == 0) //已輸出 5 個質數
cout << endl; // 換行
cout << setw(10) << p[i];
}
cout << endl;
}
}
************ 7. RAID Sizer ************
//7. RAID Sizer (HP CodeWars 2007) by Snail
#include <iostream>
using namespace std;
int main () {
int r, i, c, q, t, ac, mini, mint, minq, minc;
int dc[4] = {250,400,500,750}, dp[4] = {75,110,140,250};
while (cin >> c >> r) { //c(apacity)--容量
mint = 2001;
for (i=0; i<4; i++) {
q = (c-1) / dc[i] + 1; //硬碟數量無條件進位
ac = dc[i] * q; //陣列實際容量
if (r == 1)
q *= 2; //RAID 1 需要 2 倍硬碟
else if (r)
q += 1; //RAID 5 需要多 1 顆硬碟
if (q <= 8) { //最多 8 顆硬碟
t = q * dp[i]; //總金額
if (t < mint)
mint = t, minq = q, mini = i, minc = ac;
}
}
cout << "Qty: " << minq << " Disk: " << dc[mini] << "GB Price: $" << dp[mini] << endl;
cout << "Total price of this " << minc << "GB array: $" << mint << endl;
}
}
************ 8. Number Spiral ************
//8. Number Spiral (HP CodeWars 2007) by Snail
#include <iostream>
#include <iomanip>
using namespace std;
int main () {
int n, m[19][19], sn=0, x, y, k;
x = 8, y = 9;
for (k=0; k<=9; k++) {
x++, y++; //向右移出
while (y > 9-k) //向上
m[--y][x] = sn++;
while (x > 9-k) //向左
m[y][--x] = sn++;
while (y < 9+k) //向下
m[++y][x] = sn++;
while (x < 9+k) //向右
m[y][++x] = sn++;
}
while (cin >> n) {
n /= 2;
for (y=9-n; y<=9+n; y++){ //輸出陣列
for (x=9-n; x<=9+n; x++)
cout << setw(4) << m[y][x];
cout << endl;
}
cout << endl;
}
}
************ 9. Musical Intervals ************
//9. Musical Intervals (HP CodeWars 2007) by Snail
#include <iostream>
#include <string>
using namespace std;
int main () { //n(ote) n(name)--音名
string nn[12] = {"C","C#","D","D#","E","F","F#","G","G#","A","A#","B"};
int n, i, k, sc[7] = {0,2,4,5,7,9,11}; //sc(ale)--大調音階
char ch;
while (cin >> ch) {
k = sc[(ch-'A'+5)%7]; //k(ey)--調名
if (cin.peek() == '#') //升半音
k++, cin.ignore();
cout << nn[k]; //輸出起始主音
n = 0;
while (cin.peek() != '\n') {
cin >> i; //輸入音程
i += (i<0) - (i>0); //扣掉起始音本身
n = (n + i + 49) % 7; //計算下一個音符
cout << ' ' << nn[(k+sc[n])%12]; //輸出音名
}
cout << endl;
}
}
************ 10. New Math ************
//10. New Math (HP CodeWars 2007) by Snail
#include <iostream>
#include <string>
#include <cstdlib>
using namespace std;
int main () {
long long s, t;
int a, b;
string n, d = "0123456789abcdefghij";
char ch;
while (cin >> ws, !cin.eof()) {
getline (cin, n, '^');
cin >> b; //b(ase)--底
t = strtol (n.c_str(), NULL, b); //將字串 n 轉成 int
s = 0, ch = ' ';
while (ch != '=') { //處理 = 後跳出
cin >> ch; //運算子
getline (cin, n, '^'); //運算元
cin >> b; //底
a = strtol (n.c_str(), NULL, b);
if (ch == '*')
t *= a; //t(erm)--乘積
else {
s += t, t = a; //s(um)--和
if (ch == '-')
t = -t;
}
}
if (s < 0)
cout << '-', s = -s; //去掉負號
while (s) { //轉成 b 進位
n = d[s%b] + n;
s /= b;
}
cout << n << '^' << b << endl;
}
}
************ 11. LED Decoder ************
//11. LED Decoder (HP CodeWars 2007) by Snail
#include <iostream>
#include <string>
using namespace std;
int main () {
string s, a = "BAROWQMESGHKUZFYVPDJNLTCIX ";
string c[27] = {"1234567","123457","123459","123567","135790","12347","12357","12456","12467","12569","13457","13459",
"13567","23456","1249","1347","1379","1458","1580","3567","3579","156","278","456","37","90","0"};
int i, p;
while (getline(cin,s)) {
for (i=0; i<27; i++) {
p = -1;
while ((p=s.find(c[i],p+1)) != -1) //把 s 中所有的 c[i]
s.replace(p,c[i].size(),1,a[i]);//換成 a[i];
}
cout << s << endl;
}
}
************ 12. Domino Rally ************
//12. Domino Rally (HP CodeWars 2007) by Snail
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
int main () {
int n, i, f;
int d[29][2] = {{},{0,0},{0,1},{0,2},{0,3},{0,4},{0,5},{0,6},{1,1},{1,2},
{1,3},{1,4},{1,5},{1,6},{2,2},{2,3},{2,4},{2,5},{2,6},{3,3},
{3,4},{3,5},{3,6},{4,4},{4,5},{4,6},{5,5},{5,6},{6,6}};
char o; //o(rietation)--方向
while (cin >> n >> o) {
vector <int> r; //r(ally)
do {
if (o == 'B') n = -n; //若反向則加負號
r.push_back(n); //將點數加入陣列 r
} while (cin >> n >> o, n); //輸入下一張骨牌
do {
f = false; //f(ound)--找到相同點數
for (i=0; i+1<(int)r.size(); i++)
if (d[abs(r[ i ])][r[ i ]>0] == //這張骨牌右側點數
d[abs(r[i+1])][r[i+1]<0]) { //與下一張左側點數相同
r.erase (r.begin()+i, r.begin()+i+2);
f = true; //移除兩張骨牌
break;
}
} while (f); //若有相同點數重頭開始
if (r.size()) {
for (i=0; i!=r.size(); i++)
cout << abs(r[i]) << ' '; //輸出 n
cout << endl;
} else
cout << "DATASET CLEARED\n";
}
}
************ 13. Not Quite OCR ************
//13. Not Quite OCR (HP CodeWars 2007) by Snail
#include <iostream>
#include <string>
using namespace std;
int main () {
string dm[10] = {" _ | ||_|"," | |"," _ _||_ "," _ _| _|"," |_| |",
" _ |_ _|"," _ |_ |_|"," _ | |"," _ |_||_|"," _ |_| _|"};
char ch;
int n, i, j, cs, g, d[10];
cin >> n;
while (n--) {
string m[10]; //m[i]--第i位掃瞄影像
for (i=0; i<3; i++) {
cin.ignore(99,'\n'); //跳過換行
for (j=0; j<27; j++) {
cin.get(ch); //輸入影像
m[9-j/3] += ch; //接到適當的位數
}
}
cs = g = 0;
for (i=1; i<=9; i++) {
for (j=0; j<=9 && m[i]!=dm[j]; j++);//比對數字影像
if (j > 9) //若比對失敗
g = i; //g(arble)--模糊
else
d[i] = j, cs += i * j; //計算檢查碼
}
if (g)
for (d[g]=0; d[g]<=9; d[g]++) //還原模糊的數字
if ((cs + d[g]*g) % 11 == 0)
break;
if (g && d[g]>9 || !g && cs%11!=0) //無法還原或檢查碼錯誤
cout << "failure\n";
else {
for (i=9; i; i--)
cout << d[i];
cout << endl;
}
}
}
************ 14. Knights Path ************
//14. Knights Path (HP CodeWars 2007) by Snail
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector <string> nxt[8][8]; //下一步的位置
void trace (int x, int y, string s) {
if (nxt[x][y].size()) { //若有下一步
sort (nxt[x][y].begin(), nxt[x][y].end());//依字典順序排序
for (int i=0; i!=nxt[x][y].size(); i++) {
string p = nxt[x][y][i];
trace (p[0]-'a',p[1]-'1',s+" "+p); //遞迴到下一步
}
} else //到達終點時
cout << "Solution: " << s << endl; //輸出解答
}
int main () {
int qf, qb, x, y, x1, y1, i, j, bd[8][8]; //bd (board)--棋盤
int dx[8] = {-2,-2,-1,-1, 1, 1, 2, 2}; //d(elta) x--X 座標差
int dy[8] = {-1, 1,-2, 2,-2, 2,-1, 1}; //d(elta) y--Y 座標差
string s, e, b, p, q[64];
while (cin >> s >> e) { //s(tart)--起點, e(nd)--終點
for (i=0; i<8; i++)
for (j=0; j<8; j++) //9999--未到過
bd[i][j] = 9999, nxt[i][j].clear();
while (cin >> b, b != "xx") //b(locker)--路障
bd[b[0]-'a'][b[1]-'1'] = -1; //記錄路障
bd[e[0]-'a'][e[1]-'1'] = 0; //從終點往回找
qf = qb = 0; //q(ueue) f(ront)--頭, b(ack)--尾
q[qb++] = e; //將終點推入佇列
while (q[qf] != s) { //尚末找到起點時
p = q[qf++]; //從佇列取出一點
x = p[0]-'a', y = p[1]-'1';
for (i=0; i<8; i++) { //能走的 8 個方向
x1 = x + dx[i];
y1 = y + dy[i];
if (x1<0 || x1>7 || y1<0 || y1>7//超出範圍
|| bd[x1][y1] < bd[x][y] + 1)//或已有更小步數
continue; //跳過
if (bd[x1][y1] == 9999) { //若未拜訪過
bd[x1][y1] = bd[x][y] + 1; //步數 +1
q[qb ] = char(x1+'a'); //推入佇列
q[qb++] += char(y1+'1');
}
nxt[x1][y1].push_back(p); //記錄下一步位置
}
}
cout << "The shortest solution is " << bd[s[0]-'a'][s[1]-'1'] << " move(s).\n";
trace (s[0]-'a',s[1]-'1',s); //從起點往下遞迴
}
}