zerojudge : HP CodeWars 2007 參考解答 (a621)************ 1. Powers of Two ************ //1. Powers of Two (HP CodeWars 2007) by Snail #include using namespace std; int main () { int n, i; cin >> n; for (i=0; i<=n; i++) cout << "2^" << i << " = " << (1 << i) << endl; } (a622)************ 2. Vertical Printing ************ //2. Vertical Printing (HP CodeWars 2007) by Snail #include #include 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 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; } } (a624)************ 4. Password Analyzer ************ //4. Password Analyzer (HP CodeWars 2007) by Snail #include #include 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; } } (a625)************ 5. Overhanging Cards ************ //5. Overhanging Cards (HP CodeWars 2007) by Snail #include using namespace std; int main () { float c, s, n; //有處理浮點數誤差的話,float 也能 AC while (cin >> c) { s = 0; for (n=2; s+1e-6 #include 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; } } (a627)************ 7. RAID Sizer ************ //7. RAID Sizer (HP CodeWars 2007) by Snail #include 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; } } (a628)************ 8. Number Spiral ************ //8. Number Spiral (HP CodeWars 2007) by Snail #include #include 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; } } (a629)************ 9. Musical Intervals ************ //9. Musical Intervals (HP CodeWars 2007) by Snail #include #include 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; } } (a630)************ 10. New Math ************ //10. New Math (HP CodeWars 2007) by Snail #include #include #include 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; } } (a631)************ 11. LED Decoder ************ //11. LED Decoder (HP CodeWars 2007) by Snail #include #include 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; } } (a632)************ 12. Domino Rally ************ //12. Domino Rally (HP CodeWars 2007) by Snail #include #include #include 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 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"; } } (a633)************ 13. Not Quite OCR ************ //13. Not Quite OCR (HP CodeWars 2007) by Snail #include #include 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; } } } (a634)************ 14. Knights Path ************ //14. Knights Path (HP CodeWars 2007) by Snail #include #include #include #include using namespace std; vector 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); //從起點往下遞迴 } }