AOJ 0072 Carden Lantern

灯篭 | Aizu Online Judge


最小全域木問題、114514810は何の関係もない

#include <iostream>
#include <numeric>
#include <algorithm>
using namespace std;

int ma[100][100];

int main() {
	int n, m, a, b, d;
	char t;
	while (cin >> n) {
		if (n == 0) break;
		cin >> m;

		fill(ma[0], ma[100], 114514810);
		for (int i = 0; i < m; i++) {
			cin >> a >> t >> b >> t >> d;
			ma[a][b] = ma[b][a] = (d - 100) / 100;
		}

		bool v[100] = {false};
		v[0] = true;
		d = 0;
		for (int i = 0; i < n - 1; i++) {
			m = 114514810;
			for (int j = 0; j < n; j++) {
				if (ma[0][j] < m && !v[j]) {
					m = ma[0][j];
					b = j;
				}
			}
			v[b] = true;
			d += ma[0][b];
			for (int j = 0; j < n; j++) {
				ma[0][j] = min(ma[0][j], ma[b][j]);
			}
		}
		cout << d << endl;
	}
	return 0;
}

AOJ 0071 Bombs Chain

爆弾の連鎖 | Aizu Online Judge


(´・ω・`)

#include <iostream>
#include <string>
using namespace std;

bool map[8][8] = { 0 };
int siz[3] = { 1,2,3 }, dir[2][4] = { {1,0, -1,0},{0,1,0,-1} };
void bomb(int x, int y) {
	if (x < 0 || y < 0 || x >= 8 || y >= 8 || !map[y][x]) return;

	map[y][x] = false;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 3; j++) {
			bomb(x + dir[0][i] * siz[j], y + dir[1][i] * siz[j]);
		}
	}
}

int main() {
	int n, x, y;
	string str;
	cin >> n;
	for (int l = 1; l <= n; l++) {
		for (int i = 0; i < 8; i++) {
			cin >> str;

			for (int j = 0; j < 8; j++) {
				if (str[j] == '1') map[i][j] = true;
				else map[i][j] = false;
			}
		}
		cin >> x >> y;
		bomb(x - 1, y - 1);

		cout << "Data " << l << ":" << endl;
		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 8; j++) {
				cout << map[i][j];
			}
			cout << endl;
		}
	}

	return 0;
}

AOJ 0070 Combination of Number Sequences

組み合わせの個数 | Aizu Online Judge


先に計算をしておく、s > 330 の場合はないので0個にしてしまう
(最大の数1*0+2*1+3*2+4*3+5*4+6*5+7*6+8*7+9*8*10*9=330であるため)

#include <iostream>
using namespace std;

int n, s, res[10][330] = { 0 };
bool num[10] = { 0 };
void combinations(int c, int sum) {
	if (c == 11) return ;
	for (int i = 0; i < 10; i++) {
		if (num[i]) continue;
		num[i] = 1;
		++res[c + 1][sum + i * (c + 1)];
		combinations(c + 1, sum + i * (c + 1));
		num[i] = 0;
	}
}

int main() {
	combinations(0, 0);
	while (cin >> n) {
		cin >> s;
		if (s > 330) {
			n = 0;
			s = 0;
		}
		cout << res[n][s] << endl;
	}
	return 0;
}

AOJ 0069 Drawing Lots II

あみだくじ | Aizu Online Judge


各階層の両側に線がない('1000'の3つ目4つ目みたいな)とこに線があった場合のあみだくじを一番上の一番左から順に解いていった

#include <iostream>
#include <string>
#include <numeric>
#include <vector>
using namespace std;

#define PAIR pair<int, int>

int lot[30][10];
int n, m, a, d;
int solve(int n) {
	for (int i = 0; i < d; i++) {
		if (lot[i][n] == -1) continue;
		n = lot[i][n];
	}
	return n;
}

int main() {
	string s;
	while (cin >> n) {
		if (n == 0) break;
		cin >> m >> a >> d;

		vector<PAIR> v[30];
		for (int i = 0; i < 30; i++) {
			fill(lot[i], lot[i] + 10, -1);
		}

		for (int i = 0; i < d; i++) {
			cin >> s;
			for (int j = 0; j < n - 1; j++) {
				if (s[j] == '1') {
					lot[i][j] = j + 1;
					lot[i][j + 1] = j;
				}

				if (s[j] == '1') continue;

				if ((j - 1 < 0 || s[j - 1] == '0') && (j + 1 >= n - 1 || s[j + 1] == '0'))
					v[i].push_back(make_pair(j, j + 1));
			}
		}

		m--; a--;
		if (solve(m) == a) {
			cout << 0 << endl;
			continue;
		}

		bool judge = false;
		for (int i = 0; i < d; i++) {
			if (v[i].empty()) continue;
			for (int j = 0; j < v[i].size(); j++) {
				lot[i][v[i][j].first] = v[i][j].second;
				lot[i][v[i][j].second] = v[i][j].first;

				if (solve(m) == a) {
					cout << i + 1 << " " << v[i][j].second << endl;
					judge = true;
					break;
				}

				lot[i][v[i][j].first] = -1;
				lot[i][v[i][j].second] = -1;
			}
			if (judge) break;
		} 
	
		if (!judge) cout << 1 << endl;
	}
	return 0;
}

AOJ 0065 Trading

取引 | Aizu Online Judge


無駄に長いと思う

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

int a, b;
void split(string s) {
	int tmp = 0, n = 0;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] != ',') {
			tmp *= 10;
			tmp += s[i] - '0';
		} else {
			a = tmp;
			tmp = 0;
		}
		b = tmp;
	}
}

bool find(vector<int> v, int n) {
	for (int i = 0; i < v.size(); i++) {
		if (v[i] == n) return true;
	}
	return false;
}

int main() {
	string s;
	map<int, int> m1;
	map<int, int> m2;
	vector<int> v;
	while (getline(cin, s)) {
		if (s.size() == 0) break;
		split(s);
		m1[a]++;

		if (find(v, a)) continue;
		v.push_back(a);
	}

	while (getline(cin, s)) {
		split(s);
		m2[a]++;
	}
	sort(v.begin(), v.end());
	for (int i = 0; i < v.size(); i++) {
		if (m2[v[i]] == 0) continue;
		cout << v[i] << " " << m1[v[i]] + m2[v[i]] << endl;
	}
	return 0;
}

AOJ 0064 Secret Number

暗証番号 | Aizu Online Judge

#include <iostream>
#include <string>
using namespace std;

int findNumber(string s) {
	int tmp = 0, res = 0;
	for (int i = 0; i < s.size(); i++) {
		if (0 <= s[i] - '0' && s[i] - '0' < 10) {
			tmp *= 10;
			tmp += s[i] - '0';
		} else {
			res += tmp;
			tmp = 0;
		}
	}
	return res + tmp;
}

int main() {
	string s;
	int sum = 0;
	while (cin >> s) {
		sum += findNumber(s);
	}
	cout << sum << endl;
	return 0;
}

AOJ 0063 Palindrome

回文 | Aizu Online Judge


#include <iostream>
#include <string>
using namespace std;

bool findPalindrome(string s) {
	for (int i = 0; i < s.size() / 2; i++) {
		if (s[i] != s[s.size() - i - 1]) return false;
	}
	return true;
}

int main() {
	string s;
	int c = 0;
	while (cin >> s) {
		if (findPalindrome(s)) {
			c++;
		}
	}
	cout << c << endl;
	return 0;
}