AOJ 0042 A Thief
動的計画法の片鱗を味わった、二重for文でi番目の品物が重さjより軽ければ入れない場合と入れる場合で価値の高い方を選ぶ(dp[i-1][j-w[i]]≠0の時これまで入れた物との合計になる)
#include <iostream> #include <algorithm> using namespace std; #define MAX 1001 int dp[MAX][MAX]; int v[MAX], w[MAX]; int main() { int W, n, u = 0; char t; while (cin >> W) { if (W == 0) break; cin >> n; u++; for (int i = 0; i < n; i++) { cin >> v[i] >> t >> w[i]; } for (int i = 1; i <= n; i++) { for (int j = 0; j <= W; j++) { if (w[i - 1] <= j) { dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]); } else { dp[i][j] = dp[i - 1][j]; } } } int mv, mw; mv = mw = 0; for (int i = 0; i <= W; i++) { if (dp[n][i] > mv) { mv = dp[n][i]; mw = i; } } cout << "Case " << u << ":" << endl; cout << mv << endl; cout << mw << endl; } return 0; }
AOJ 0041 Expression
順列を作るのが一番悩んだ(低能)
#include <iostream> #include <cstdio> using namespace std; #define FOR(i, a, b) for(int i = a; i < b; i++) #define REP(a, b) FOR(a, 0, b) char opr[3] = { '+','-','*' }; int calc(int a, int b, int c) { if (c == 0) return a + b; if (c == 1) return a - b; return a * b; } void permutations(int a, int b, int c, int d) { int per[4] = {0}; REP(i, 4) { REP(j, 4) { REP(k, 4) { REP(l, 4) { if (k == i || k == j || i == j || l == i || l == j || l == k) continue; per[i] = a; per[j] = b; per[k] = c; per[l] = d; REP(f, 3) { REP(g, 3) { REP(h, 3) { if (calc(calc(per[0], per[1], f), calc(per[2], per[3], h), g) == 10) { printf("((%d %c %d) %c (%d %c %d))\n",per[0], opr[f], per[1], opr[g], per[2], opr[h], per[3]); return; } if (calc(calc(calc(per[0], per[1], f), per[2], g), per[3], h) == 10) { printf("(((%d %c %d) %c %d) %c %d)\n", per[0], opr[f], per[1], opr[g], per[2], opr[h], per[3]); return; } } } } } } } } cout << 0 << endl; } int main() { int a, b, c, d; while (cin >> a >> b >> c >> d) { if (a == 0 && b == 0 && c == 0 && d == 0) break; permutations(a, b, c, d); } return 0; }
AOJ 0040 Affine Cipher
アフィン暗号 | Aizu Online Judge
αとβの値をα,β > 0の範囲で総当たりして解いた(今のテストケースだとαもβも27ぐらいまでに絞れる)
REPマクロ初めて書いた
#include <iostream> #include <string> using namespace std; #define rep(a, b, i) for(int i = a; i < b; i++) char ch(int a, int b, int c) { return (a * (c - 'a') + b) % 26 + 'a'; } int main() { int n, a, b, c; cin >> n; cin.ignore(); string str, res = ""; for (; n > 0; n--) { getline(cin, str); rep(1, 27, a) { if (a == 2 || a == 13) continue; rep(1, 27, b) { res = str; c = 0; rep(0, str.size(), c) { if (res[c] == ' ') continue; res[c] = ch(a, b, res[c]); } if (res.find("this") != -1 || res.find("that") != -1) { cout << res << endl; a = 114514; b = 114514; } } } } return 0; }
AOJ 0039 Roman Figure
何でもいい(何でもいいとは言っていない)ある程度大きな数を適当に決めるとき114514にする癖がついた、そのうちに治そう...
#include <iostream> #include <string> #include <map> using namespace std; int main() { map<char, int> m; m['I'] = 1; m['V'] = 5; m['X'] = 10; m['L'] = 50; m['C'] = 100; m['D'] = 500; m['M'] = 1000; string str = ""; int sum, n; while (cin >> str) { sum = 0; n = 114514; for (int i = 0; i < str.size(); i++) { if (m[str[i]] <= n) { n = m[str[i]]; sum += n; } else { sum += m[str[i]]; sum -= (n * 2); n = 114514; } } cout << sum << endl; } return 0; }
AOJ 0038 Poker Hand
分岐だけ、
#include <iostream> #include <cstdio> #include <string> using namespace std; string pairs[2][3] = { {"null","one pair","two pair"}, {"three card","full house",""} }; int main() { int n[5], c, three, two; while (scanf("%d,%d,%d,%d,%d",&n[0],&n[1],&n[2],&n[3],&n[4]) != EOF) { int card[13] = { 0 }, c = 0, three = 0, two = 0; for (int i = 0; i < 5; i++) { card[n[i] - 1]++; } for (int i = 0; i < 13; i++) { if (card[i] == 4) { c = 114514; break; } else if (card[i] == 3) { three++; } else if (card[i] == 2) { two++; } else if (card[i] == 1) { c++; if (c == 5) { break; } if (c == 4 && i == 12 && card[0] == 1) { c = 5; break; } } else if(card[i] == 0 && c != 0) { c = 0; } } if (c == 5) { cout << "straight" << endl; } else if (c == 114514) { cout << "four card" << endl; } else { cout << pairs[three][two] << endl; } } return 0; }