UVa 712 S-Trees

題意：
    第一個數字為樹的深度N，然後有N個xi表示從root到(N-1)每一層的變數xi(例如x3 x1 x2表示root層的變數為x3，第1層變數為x1，第二層變數為x2)，接下來一串0和1的序列代表樹的最底層從左到右的値，然後有M個VVL，每個VVL依序表示變數xi的値(例如011表示x1=0，x2=1，x3=1)，因此知道xi代表的値後，就能從root走到底層(每層有自己的變數xi，遇到0向左走，1向右走)，一直走到底層看最底層是什麼數字。

想法：
    從root開始往下走，先將root編號n為0，往左下走就乘以2，往右下走就乘以2加1，直到最底層，看編號n是多少就輸出底層序列的第n個數字。
        0              root
    0       1          第1層
  0   1   2   3        第2層
 0 1 2 3 4 5 6 7       最底層

	#include <iostream>
	#include <cstdio>
	#include <string>
	#include <vector>
	using namespace std;
	int main()
	{
	// freopen("input.txt","rt",stdin);
	ios::sync_with_stdio(false);
	int N, M, Case = 1;
	while (cin >> N && N) {
	cout << "S-Tree #" << Case++ << ':' << endl;
	string tmp;
	vector<int> order;
	string terminal_node;
	for (int i = 0; i < N; ++i) {
	cin >> tmp;
	order.push_back(tmp[1]-'0');
	}
	cin >> terminal_node >> M;
	string VVA;
	while (M--) {
	cin >> VVA;
	int node_num = 0;
	for (int i = 0; i < N; ++i) {
	int direction = VVA[order[i]-1] - '0';
	node_num = node_num * 2 + direction;
	}
	cout << terminal_node[node_num];
	}
	cout << endl << endl;
	}
	return 0;
	}

view raw [UVa] 712 S-Trees.cpp hosted with ❤ by GitHub

UVa 501 Black Box

想法：
    原本是用multiset來存每個數字，因為multiset為紅黑樹，想說從第一個元素iterate i次來GET第i個數字，但一個一個iterate效率太慢就TLE了。
    後來改用vector來存數字，每新增一個數字，就用binary search找到它該放的位置，然後用vector的insert來插入該數字，要GET第i個元素因為是vector就可以直接存取了，效率還不錯，UVa花了0.495秒。

	#include <cstdio>
	#include <vector>
	#include <algorithm>
	using namespace std;
	int A[30010];
	int main()
	{
	// freopen("input.txt","rt",stdin);
	int Case, M, N, tmp;
	scanf("%d", &Case);
	while (Case--) {
	scanf("%d %d", &M, &N);
	for (int i = 0; i < M; ++i)
	scanf("%d", &A[i]);
	vector<int> Box;
	int U, a = 0, i = 0; // a is index of A
	while (N--) {
	scanf("%d", &U);
	while (a < U) { // lower_bound回傳一個iterator指向Box裡面第一個>=A[a]的元素
	auto iter = lower_bound(Box.begin(), Box.end(), A[a]);
	Box.insert(iter, A[a++]);
	}
	printf("%d\n", Box[i++]);
	}
	if (Case) printf("\n");
	}
	return 0;
	}

view raw [UVa] 501-2 Black Box.cpp hosted with ❤ by GitHub

這是用set的版本：

	#include <cstdio>
	#include <set>
	using namespace std;
	int Case, M, N;
	int A[30010], U[30010];
	int main()
	{
	freopen("input.txt","rt",stdin);
	scanf("%d", &Case);
	while (Case--) {
	scanf("%d %d", &M, &N);
	for (int i = 0; i < M; ++i)
	scanf("%d", &A[i]);
	for (int i = 0; i < N; ++i)
	scanf("%d", &U[i]);
	multiset<int> Box;
	for (int i = 0, u = 0, a = 0; u < N; ++u, ++i)
	{
	while (a < U[u] && a < N)
	Box.insert(A[a++]);
	auto iter = Box.cbegin();
	for (int j = 0; j < i; ++j)
	++iter;
	printf("%d\n", *iter);
	}
	if (Case) printf("\n");
	}
	return 0;
	}

view raw [UVa] 501-1 Black Box.cpp hosted with ❤ by GitHub

UVa 902 Password Search

題意：
  N為一個substring的長度，找出題目string裡面哪個substring重複最多次數。

想法：
  用map[substring] = 次數 來記錄每個substring出現的次數，然後再找出最大的次數並輸出該substring。

	#include <iostream>
	#include <string>
	#include <map>
	using namespace std;
	int main()
	{
	ios::sync_with_stdio(false);
	int N;
	string str;
	while (cin >> N) {
	cin.get();
	getline(cin, str);
	map<string, int> Map;
	for (int i = 0; i <= str.size()-N; ++i) {
	string tmp = str.substr(i, N); // 從第i個位置擷取str N個字元
	if (!Map[tmp]) Map[tmp] = 1;
	else Map[tmp]++;
	}
	int Max = 0;
	for (auto &m : Map) { // m為pair structure
	if (m.second > Max) {
	Max = m.second;
	str = m.first;
	}
	}
	cout << str << endl;
	}
	return 0;
	}

view raw [UVa] 902 Password Search.cpp hosted with ❤ by GitHub

POJ 3481 Double Queue

想法：
　　用STL_map可以完成這題，map<int, int>Map，然後對應方式為Map[優先權] = 人員編號，因為Map為自動平衡的tree，所以優先權最大的會在tree的最右下方，也就是Map這個container的最後一個，而優先權最小的反之，在Map的第一個位置。另外map這container是用pair來存資料，因此要輸出人員編號要用->second。

	#include <cstdio>
	#include <map>
	using namespace std;
	int main()
	{
	map<int,int> Map;
	int instruction, priority, number;
	while (scanf("%d", &instruction)) {
	switch (instruction) {
	case 1:
	scanf("%d%d", &number, &priority);
	Map[priority] = number;
	break;
	case 2:
	if (Map.empty()) puts("0");
	else {
	printf("%d\n", (--Map.end())->second);
	Map.erase(--Map.end());
	}
	break;
	case 3:
	if (Map.empty()) puts("0");
	else {
	printf("%d\n", Map.begin()->second);
	Map.erase(Map.begin());
	}
	break;
	case 0:
	return 0;
	}
	}
	}

view raw [POJ] 3481 Double Queue.cpp hosted with ❤ by GitHub

UVa 10308 Roads in the North

題意：
　　計算該graph最遠的距離。
想法：
　　DFS function 定義為"回傳該點能走的最遠深度"，例如DFS(p點)，則在DFS裡面我們對p點能前往的那些點做DFS，記下該路徑(route)的長度，並一直刷新route_max的大小，最後回傳route_max。
　　在刷新route_max"之前"，我們先把(route+route_max)與ans比較，刷新ans，(route+route_max)表示p點往兩個不同方向的路徑的和，不斷刷新ans，就能產生最遠的距離。

	#include <cstdio>
	#include <vector>
	using namespace std;
	struct point_type{
	int nxt;
	int len;
	};
	vector<point_type> toPoint[10005];
	int ans;
	int DFS(int point, int prev_point) // DFS回傳該點能走的最深路徑的距離
	{
	int route_max = 0;
	for (auto &p : toPoint[point]) {
	if (p.nxt == prev_point) continue;
	int route = DFS(p.nxt, point) + p.len;
	if (route + route_max > ans) // 現在走的路徑+已經儲存的最大路徑如果大於ans就更新ans
	ans = route + route_max;
	if (route > route_max)
	route_max = route;
	}
	return route_max;
	}
	void input(char line[])
	{
	int p1, p2, L;
	sscanf(line, "%d%d%d", &p1, &p2, &L);
	toPoint[p1].push_back({p2,L});
	toPoint[p2].push_back({p1,L});
	}
	int main()
	{
	freopen("input.txt","rt",stdin);
	char line[100];
	while (gets(line)) {
	if (line[0] == '\0') {
	puts("0");
	continue;
	}
	for (auto &v : toPoint) v.clear();
	input(line);
	while (gets(line)) {
	if (line[0] == '\0') break;
	input(line);
	}
	ans = 0;
	DFS(1,-1);
	printf("%d\n", ans);
	}
	return 0;
	}

view raw [UVa] 10308 Roads in the North.cpp hosted with ❤ by GitHub

UVa 11624 Fire

題意：

　　J在一個迷宮裡，迷宮有"不只一個"起火點F，J一分鐘移動一步，而火焰一分鐘也會向上下左右蔓延一步，J只要碰到迷宮的邊緣即可逃走，確認J是否能逃走，如果可以，輸出要走的最短步數。

想法：

　　將每個起火點用vector(或array)存下來，然後同時用兩個BFS，先讓所有起火點先動一步，再讓J動一步，確認J是否能碰到迷宮的邊緣。

　　用int Maze[1001][1001]來描述該迷宮的情況，我用-2代表起火點，-1代表牆壁('#')，0代表可以走的路，用BFS時，每次為了確認火焰都只動一步，因此勢必要記錄火焰走的步數，每次火焰走下一步時Maze[nxt_i][nxt_j] = Maze[cur_i][cur_j] - 1，用負數記錄火焰步數，而正數用來記錄Joe的步數。

	#include <cstdio>
	#include <vector>
	#include <queue>
	using namespace std;
	int R, C;
	int Maze[1001][1001]; // -2:'F', 0:'.', -1:'#'
	struct point_type{
	int x;
	int y;
	};
	vector<queue<point_type>> QF; // 存每個起火點
	const int direction[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
	int BFS(point_type J)
	{
	queue<point_type> QJ; QJ.push(J); // 存Joe
	point_type cur, nxt;
	int minute;
	while(!QJ.empty()) {
	for (int i = 0; i < QF.size(); ++i) { // 多個火焰都要各動一步
	if (!QF[i].empty()){
	cur = QF[i].front();
	minute = Maze[cur.x][cur.y]; // 讓該火焰只動完目前這一分鐘後
	}
	while (!QF[i].empty()){
	cur = QF[i].front();
	if (Maze[cur.x][cur.y] != minute) break; // 就跳出queue 換成 J 移動
	QF[i].pop();
	for (int x = 0; x < 4; ++x) {
	nxt.x = cur.x + direction[x][0];
	nxt.y = cur.y + direction[x][1];
	if (nxt.x < 0 || nxt.x >= R || nxt.y < 0 || nxt.y >= C) continue;
	if (Maze[nxt.x][nxt.y] == 0) {
	Maze[nxt.x][nxt.y] = Maze[cur.x][cur.y] - 1;
	QF[i].push(nxt);
	}
	}
	}
	}
	cur = QJ.front();
	minute = Maze[cur.x][cur.y];
	while (!QJ.empty()) {
	cur = QJ.front();
	if (Maze[cur.x][cur.y] != minute) break; //只動完一步後 就換火焰移動
	QJ.pop();
	for (int x = 0; x < 4; ++x) {
	nxt.x = cur.x + direction[x][0];
	nxt.y = cur.y + direction[x][1];
	if (nxt.x < 0 || nxt.x >= R || nxt.y < 0 || nxt.y >= C)
	return Maze[cur.x][cur.y];
	if (Maze[nxt.x][nxt.y] == 0) {
	Maze[nxt.x][nxt.y] = Maze[cur.x][cur.y] + 1;
	QJ.push(nxt);
	}
	}
	}
	}
	return -1;
	}
	int main()
	{
	// freopen("input.txt","rt",stdin);
	int Case;
	char line[1005];
	scanf("%d", &Case);
	while (Case--) {
	scanf("%d %d", &R, &C);
	point_type J;
	QF.clear();
	for (int i = 0; i < R; ++i) {
	scanf("%s", line);
	for (int j = 0; j < C; ++j) {
	if (line[j] == '.')
	Maze[i][j] = 0;
	else if (line[j] == '#')
	Maze[i][j] = -1;
	else if (line[j] == 'J') {
	J = {i,j};
	Maze[i][j] = 1;
	}
	else if (line[j] == 'F') {
	queue<point_type> tmp;
	tmp.push({i,j});
	QF.push_back(tmp);
	Maze[i][j] = -2;
	}
	}
	}
	int minute = BFS(J);
	if (minute == -1) puts("IMPOSSIBLE");
	else printf("%d\n", minute);
	}
	return 0;
	}

view raw [UVa] 11624 Fire!.cpp hosted with ❤ by GitHub

UVa 10946 You want what filled

題意：
　　計算給定的區域不同種類的坑洞的面積，輸出時依照坑洞面積的大小排序，如果一樣則按照字母順序。

想法：
　　碰到不是'.'的字元就用BFS去算該坑洞的面積，最後再sort輸出即可。

	#include <cstdio>
	#include <queue>
	#include <algorithm>
	using namespace std;
	int X, Y;
	char grid[55][55];
	struct hole_type {
	char ch;
	int num;
	}hole[2550];
	struct point_type {
	int i;
	int j;
	};
	hole_type BFS(char c, int i, int j);
	bool cmp(hole_type a, hole_type b);
	int main()
	{
	// freopen("input.txt","rt",stdin);
	int Case = 1;
	while (scanf("%d%d", &X, &Y) && (X || Y)) {
	for (int i = 0; i < X; ++i)
	scanf("%s", grid[i]);
	int numOfhole = 0;
	for (int i = 0; i < X; ++i)
	for (int j = 0; j < Y; ++j)
	if (grid[i][j] != '.')
	hole[numOfhole++] = BFS(grid[i][j], i, j);
	sort(hole, hole + numOfhole, cmp);
	printf("Problem %d:\n", Case++);
	for (int i = 0; i < numOfhole; ++i)
	printf("%c %d\n", hole[i].ch, hole[i].num);
	}
	}
	const int direction[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
	hole_type BFS(char c, int i, int j)
	{
	queue<point_type> Q;
	Q.push({i,j});
	grid[i][j] = '.';
	int num = 1;
	point_type cur, nxt;
	while (!Q.empty()) {
	cur = Q.front();
	Q.pop();
	for (int k = 0; k < 4; ++k) {
	nxt.i = cur.i + direction[k][0];
	nxt.j = cur.j + direction[k][1];
	if (nxt.i < 0 || nxt.i >= X || nxt.j < 0 || nxt.j >= Y) continue;
	if (grid[nxt.i][nxt.j] == c) {
	grid[nxt.i][nxt.j] = '.';
	Q.push(nxt);
	++num;
	}
	}
	}
	return {c, num};
	}
	bool cmp(hole_type a, hole_type b)
	{
	return (a.num == b.num) ? (a.ch < b.ch) : (a.num > b.num);
	}

view raw [UVa] 10946 You want what filled.cpp hosted with ❤ by GitHub

UVa 10592 Freedom FIghter

題意：

　　'B'為fighter，'P'為enemy，'*'圍起來的範圍內為一個sector，sector的編號由左至右由上至下，要計算每個sector裡面有幾組fighter和幾組enemy，如果fighter和enemy面對面的話，表示有2個group在fighting position。

面對面的情況只會各有一組，

BBB

PP

不會有底下這種情況

BBB

PP

BBB

想法：

　　用DFS_1來走遍該sector，如果碰到'B'或'P'則用DFS_2走遍該group，並確認有沒有碰到另一個group。

	#include <cstdio>
	using namespace std;
	int n;
	int fighter, enemy, fighting_group;
	char grid[51][51];
	const int direction[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
	bool DFS_2(char, int ,int);
	void DFS_1(int i, int j, int &fighter, int &enemy) // DFS_1用來走遍'*',如果遇到'B'或'P'則進入DFS_2
	{
	grid[i][j] = '.';
	for (int x = 0; x < 4; ++x) {
	int nxt_i = i + direction[x][0];
	int nxt_j = j + direction[x][1];
	if (nxt_i < 0 || nxt_i >= n || nxt_j < 0 || nxt_j >= n) continue;
	if (grid[nxt_i][nxt_j] == 'B') {
	++fighter;
	if (DFS_2('B', nxt_i, nxt_j)) fighting_group += 2;
	}
	if (grid[nxt_i][nxt_j] == 'P') {
	++enemy;
	if (DFS_2('P', nxt_i, nxt_j)) fighting_group += 2;
	}
	if (grid[nxt_i][nxt_j] == '*')
	DFS_1(nxt_i, nxt_j, fighter, enemy);
	}
	}
	bool DFS_2(char C, int i, int j) //用來走遍'B'或'P'並確認是否有碰到另一個group(面對面)
	{
	grid[i][j] = '*';
	bool another_group = 0;
	bool touch_another = 0;
	for (int x = 0; x < 4; ++x) {
	int nxt_i = i + direction[x][0];
	int nxt_j = j + direction[x][1];
	if (nxt_i < 0 || nxt_i >= n || nxt_j < 0 || nxt_j >= n) continue;
	if (C == 'B' && grid[nxt_i][nxt_j] == 'P' ||
	C == 'P' && grid[nxt_i][nxt_j] == 'B') another_group = 1;
	if (grid[nxt_i][nxt_j] == C)
	another_group = DFS_2(C, nxt_i, nxt_j);
	if (another_group == 1) touch_another = 1;
	}
	return touch_another;
	}
	int main()
	{
	// freopen("input.txt","rt",stdin);
	while (scanf("%d", &n) && n) {
	for (int i = 0; i < n; ++i)
	scanf("%s", grid[i]);
	int sector = 1;
	fighting_group = 0;
	for (int i = 0; i < n; ++i) {
	for (int j = 0; j < n; ++j) {
	if (grid[i][j] != '.') {
	fighter = 0;
	enemy = 0;
	if (grid[i][j] == 'B') {++fighter; if (DFS_2('B', i, j)) fighting_group += 2;}
	if (grid[i][j] == 'P') {++enemy; if (DFS_2('P', i, j)) fighting_group += 2;}
	DFS_1(i, j, fighter, enemy);
	printf("Sector #%d: contain %d freedom fighter group(s) & %d enemy group(s)\n",
	sector++, fighter, enemy);
	}
	}
	}
	printf("Total %d group(s) are in fighting position.\n\n", fighting_group);
	}
	return 0;
	}

view raw [UVa] 10592 Freedom Fighter.cpp hosted with ❤ by GitHub

UVa 705 Slash Maze

想法：
　　把長和寬延伸3倍，使得迷宮地圖大9倍，並將'/'和'\'變成底下的形式：
001  100
010  010
100  001
　　延伸3倍的目的是為了讓我們在使用BFS的時候，能夠直接上下左右的走，不需要斜著走，所以只要依照'/'將地圖先做出來，再使用BFS走遍，並要判斷走遍的時候會不會走出界，如果會走出界代表它不是一個Cycle，而因為延伸3倍的關係，走的路徑長度最後要除以3。

	#include <cstdio>
	#include <cstring>
	#include <queue>
	using namespace std;
	int W, H;
	int Maze[300][300];
	struct point_type{
	int i;
	int j;
	};
	void Write_Maze(char line[], int i)
	{
	for (int j = 0; line[j]; ++j) {
	int ii = i * 3, jj = j * 3;
	for (int x = 0; x < 3; ++x)
	for (int y = 0; y < 3; ++y)
	Maze[ii+x][jj+y] = 0;
	if (line[j] == '\\') {
	Maze[ii][jj] = 1;
	Maze[ii+1][jj+1] = 1;
	Maze[ii+2][jj+2] = 1;
	}
	else {
	Maze[ii][jj+2] = 1;
	Maze[ii+1][jj+1] = 1;
	Maze[ii+2][jj] = 1;
	}
	}
	}
	const int direction[][2] = {{-1,0},{1,0},{0,-1},{0,1}};
	bool Run_Maze(int i, int j, int &longest)
	{
	queue<point_type> Q;
	Q.push({i,j});
	int length = 1;
	bool isCycle = 1;
	point_type cur, nxt;
	while (!Q.empty()) {
	length++;
	cur = Q.front();
	Q.pop();
	for (int x = 0; x < 4; ++x) {
	nxt.i = cur.i + direction[x][0];
	nxt.j = cur.j + direction[x][1];
	if (nxt.i < 0 || nxt.j < 0 || nxt.i >= H || nxt.j >= W) {
	isCycle = 0;
	continue;
	}
	if (Maze[nxt.i][nxt.j] == 0) {
	Maze[nxt.i][nxt.j] = 1;
	Q.push(nxt);
	}
	}
	}
	if (isCycle == 0) return 0;
	length /= 3;
	if (longest < length) longest = length;
	return 1;
	}
	int main()
	{
	// freopen("input.txt","rt",stdin);
	int Case = 1;
	char line[100];
	while (scanf("%d %d", &W, &H) && (W || H)) {
	for (int i = 0; i < H; ++i){
	scanf("%s", line);
	Write_Maze(line, i);
	}
	H *= 3;
	W *= 3;
	int numOfCycles = 0;
	int longest = 0;
	for (int i = 0; i < H; ++i)
	for (int j = 0; j < W; ++j)
	if (Maze[i][j] == 0)
	if (Run_Maze(i, j, longest))
	numOfCycles++;
	printf("Maze #%d:\n", Case++);
	if (numOfCycles)
	printf("%d Cycles; the longest has length %d.\n\n", numOfCycles, longest);
	else printf("There are no cycles.\n\n");
	}
	}

view raw [UVa] 705 Slash Maze.cpp hosted with ❤ by GitHub

UVa 10009 All Roads Lead Where?

想法：
       將讀進來的字串用map轉成數字，並建立兩個點的連線。
       用BFS演算法來搜索目的地，並在過程中用visit[]記錄每次的步數，最後抵達終點時BFS演算法結束，然後我們再利用visit從終點逆向走回起點，記下這條路徑走過的點，最後輸出結果。

	#include <cstdio>
	#include <iostream>
	#include <queue>
	#include <vector>
	#include <map>
	using namespace std;
	map<string, int> Map;
	vector<string> toPoint[10001];
	void BFS (string Start, string End)
	{
	queue<string> Q;
	Q.push(Start);
	int visit[10001] = {0};
	visit[Map[Start]] = 1;
	// 標準BFS演算法
	string cur;
	bool FindedEnd = 0;
	while (!Q.empty() && !FindedEnd) {
	cur = Q.front();
	Q.pop();
	for (const auto &nxt : toPoint[Map[cur]]) {
	if (visit[Map[nxt]] == 0) {
	// 將走過的步數存下來，等等逆向的時候會用到
	visit[Map[nxt]] = visit[Map[cur]] + 1;
	if (nxt == End) {
	FindedEnd = 1;
	break;
	}
	Q.push(nxt);
	}
	}
	}
	// 逆向走回起點並將該路徑存在Ans
	int step_count = visit[Map[End]];
	vector<char> Ans = {End[0]};
	cur = End;
	while (step_count != 1) {
	for (const auto &nxt : toPoint[Map[cur]]) {
	if (visit[Map[nxt]] == step_count - 1) {
	Ans.push_back(nxt[0]);
	--step_count;
	cur = nxt;
	break;
	}
	}
	}
	for (auto i = Ans.end() - 1; i != Ans.begin(); --i)
	cout << *i;
	cout << Ans[0] << endl;
	}
	int main()
	{
	// freopen("input.txt","rt",stdin);
	ios::sync_with_stdio(false);
	int Case, M, N;
	cin >> Case;
	while (Case--) {
	Map.clear();
	for (auto &v : toPoint) v.clear();
	string s1, s2;
	cin >> M >> N;
	for (int i = 0, j = 1; i < M; ++i) {
	cin >> s1 >> s2;
	if (!Map[s1]) Map[s1] = j++;
	if (!Map[s2]) Map[s2] = j++;
	toPoint[Map[s1]].push_back(s2);
	toPoint[Map[s2]].push_back(s1);
	}
	for (int i = 0; i < N; ++i) {
	cin >> s1 >> s2;
	BFS (s1, s2);
	}
	if (Case) cout << endl;
	}
	return 0;
	}

view raw [UVa] 10009 All Roads Lead Where?.cpp hosted with ❤ by GitHub

UVa 10004 Bicoloring

題意：
       只有兩種顏色，兩個相鄰的點必須顏色不同，給定一個graph，判斷該graph是否能符合上述條件。

想法：
       用BFS走遍所有的點，走過的點將它編號為1或2，如果下一個點還沒走過，將它標上和現在這個點不一樣的編號，如果下一個已經走過，而編號和現在這個點一樣，回傳false，否則當BFS搜索完，回傳true。

	#include <cstdio>
	#include <queue>
	#include <vector>
	using namespace std;
	int N,I;
	vector<int> toPoint[205];
	bool BFS(int Start)
	{
	queue<int> Q;
	Q.push(Start);
	int visit[205] = {0};
	while (!Q.empty()) {
	int cur = Q.front();
	Q.pop();
	for (int &nxt : toPoint[cur]) {
	if (visit[nxt] == 0) {
	Q.push(nxt);
	if (visit[cur] == 1) visit[nxt] = 2;
	else visit[nxt] = 1;
	}
	else if (visit[nxt] == visit[cur])
	return false;
	}
	}
	return true;
	}
	int main()
	{
	// freopen ("input.txt","rt",stdin);
	while (scanf("%d", &N)) {
	if (!N) break;
	for (auto &v : toPoint) v.clear();
	scanf("%d", &I);
	int p1, p2;
	for (int i=0; i<I; ++i) {
	scanf("%d %d", &p1, &p2);
	toPoint[p1].push_back(p2);
	toPoint[p2].push_back(p1);
	}
	printf("%s\n", BFS(p1) ? "BICOLORABLE." : "NOT BICOLORABLE.");
	}
	}

view raw [UVa] 10004 Bicoloring.cpp hosted with ❤ by GitHub

UVa 762 We Ship Cheap

想法：
        用BFS從起點搜尋終點，並用visit[]儲存步數，然後再從終點依據visit走回起點，並將過程走過的點儲存起來，最後輸出。

	#include <bits/stdc++.h>
	using namespace std;
	map<string, int> Map; //將每個點從字串換成編號
	vector<string> toPoint[10001]; // 用來存每個點能連到哪些點
	void BFS(string Start, string End)
	{
	queue<string> Q;
	Q.push(Start);
	int visit[10001] = {0};
	visit[Map[Start]] = 1;
	string cur;
	bool findedEnd = 0;
	while (!Q.empty() && !findedEnd) { // BFS演算法
	cur = Q.front();
	Q.pop();
	for (string &nxt : toPoint[Map[cur]]) {
	if (visit[Map[nxt]] == 0) {
	visit[Map[nxt]] = visit[Map[cur]] + 1;
	if (nxt == End){
	findedEnd = 1;
	break;
	}
	Q.push(nxt);
	}
	}
	}
	// 從終點逆向走回起點，並將過程存在ans裡
	int step_count = visit[Map[End]];
	cur = End;
	vector<string> ans;
	ans.push_back(End);
	bool stop = 0;
	while (!stop) {
	bool finded_nxt_point = 0;
	for (string &nxt : toPoint[Map[cur]]) {
	if (nxt == Start) {
	ans.push_back(Start);
	stop = 1;
	break;
	}
	if (visit[Map[nxt]] == step_count - 1) {
	--step_count;
	ans.push_back(nxt);
	cur = nxt;
	finded_nxt_point = 1;
	break;
	}
	}
	if (!finded_nxt_point) stop = 1;
	}
	if (visit[Map[End]] == 0) cout << "No route" << endl;
	else {
	for (int i = ans.size() - 1; i > 0; --i)
	cout << ans[i] << ' ' << ans[i-1] << endl;
	}
	}
	int main()
	{
	// freopen("input.txt","rt",stdin);
	ios::sync_with_stdio(false);
	int N, blank_line = 0;
	while (cin >> N) {
	if (blank_line) cout << endl;
	blank_line = 1;
	Map.clear();
	for (auto &v : toPoint) v.clear();
	string p1, p2;
	for (int i = 0, j = 1; i < N; ++i) {
	cin >> p1 >> p2;
	if (!Map[p1]) Map[p1] = j++;
	if (!Map[p2]) Map[p2] = j++;
	toPoint[Map[p1]].push_back(p2);
	toPoint[Map[p2]].push_back(p1);
	}
	cin >> p1 >> p2;
	//p1,p2不管是否為前面儲存的點，如果p1==p2就輸出p1 p2
	if (p1 == p2) cout << p1 << ' ' << p2 << endl;
	else if (!Map[p1] || !Map[p2]) cout << "No route" << endl;
	else BFS (p1, p2);
	}
	}

view raw [UVa] 762 We Ship Cheap.cpp hosted with ❤ by GitHub

UVa 567 Risk

題意:
　　1~19行，每行第一個數字表示後面會輸入幾個數字，而第i行表示第i個點能連到哪些點，第20行只有一個數字表示之後有幾個測試資料，每個測試資料有兩個數字：起點和終點，求出最短距離。

想法：
　　BFS題目，將每個點依序建立連結後，使用BFS並依題目要求輸出即可。

	#include <cstdio>
	#include <vector>
	#include <queue>
	using namespace std;
	int BFS(int Start, int End, vector<int> toPoint[])
	{
	int visit[21] = {0};
	queue<int> Q;
	Q.push(Start);
	while (!Q.empty()) {
	int cur = Q.front();
	Q.pop();
	for (int nxt : toPoint[cur]) {
	if (visit[nxt] == 0) {
	visit[nxt] = visit[cur] + 1;
	if (nxt == End) return visit[nxt];
	Q.push(nxt);
	}
	}
	}
	return -1;
	}
	int main()
	{
	// freopen("input.txt","rt",stdin);
	int N, i, j, point, Case = 1;
	while (scanf("%d", &N) != EOF) {
	vector<int> toPoint[21];
	for (j=0; j<N; ++j){ // 輸入第1個點
	scanf("%d", &point);
	toPoint[1].push_back(point);
	toPoint[point].push_back(1);
	}
	for (i=2; i<=19; ++i) { // 輸入第2~19個點
	scanf("%d", &N);
	for (j=0; j<N; ++j) {
	scanf("%d", &point);
	toPoint[i].push_back(point);
	toPoint[point].push_back(i);
	}
	}
	scanf("%d", &N);
	printf("Test Set #%d\n", Case++);
	while (N--) {
	int start_point, end_point;
	scanf("%d%d", &start_point, &end_point);
	printf("%2d to %2d: %d\n", start_point, end_point,
	BFS(start_point, end_point, toPoint));
	}
	printf("\n");
	}
	return 0;
	}

view raw [UVa] 567 Risk.cpp hosted with ❤ by GitHub

UVa 539 The Settlers of Catan

題目連結
想法：
　　將每個點能連到哪些點存起來，然後對每個點使用DFS看該點最遠能走多深。

	#include <cstdio>
	#include <vector>
	using namespace std;
	int DFS (int node, vector<int> toNode[30], int dis, bool visit[][30])
	{
	int longest_length = 0; // 當前node能走的最遠距離
	for (int nxt_node : toNode[node]){
	if (!visit[node][nxt_node]) { // 該條線還沒走過
	visit[node][nxt_node] = 1;
	visit[nxt_node][node] = 1; // 雙向關閉
	int length = DFS (nxt_node, toNode, dis+1, visit);
	if (length > longest_length) longest_length = length;
	visit[node][nxt_node] = 0;
	visit[nxt_node][node] = 0; // 雙向開啟
	}
	}
	if (longest_length == 0) return dis; //如果走到底 回傳當前距離
	else return longest_length; //否則回傳該點能走的最長距離
	}
	int main()
	{
	// freopen("input.txt","rt",stdin);
	int n, m;
	while (scanf("%d%d", &n, &m)) {
	if (!n && !m) break;
	vector<int> toNode[30]; // toNode[i]儲存i_node能走向哪幾個點
	for (int i=0, n1, n2; i<m; ++i) {
	scanf("%d%d", &n1, &n2);
	toNode[n1].push_back(n2);
	toNode[n2].push_back(n1);
	}
	bool visit[30][30] = {0}; //visit[i][j]=1 表示i_j這條線已經走過
	int longest = 0;
	for (int i=0; i<n; ++i){
	int length = DFS(i, toNode, 0, visit);
	if (length > longest)
	longest = length;
	}
	printf("%d\n", longest);
	}
	}

view raw [UAa] 539 The Settlers of Catan.cpp hosted with ❤ by GitHub

UVa 439 Knight Moves

想法：
　　西洋棋Knight的走法與中國象棋'馬'的走法一樣，所以在8x8方格中用BFS即可。注意index轉換的問題。

	#include <cstdio>
	#include <queue>
	using namespace std;
	struct point_type{
	int i;
	int j;
	};
	const int direction[][2] = {{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1}};
	int BFS(point_type Start, point_type End)
	{
	int step[9][9] = {0};
	queue<point_type> Q;
	Q.push(Start);
	point_type cur, nxt;
	while (!Q.empty()) {
	cur = Q.front();
	Q.pop();
	if (cur.i == End.i && cur.j == End.j)
	return step[cur.i][cur.j];
	for (int i = 0; i < 8; ++i) {
	nxt.i = cur.i + direction[i][0];
	nxt.j = cur.j + direction[i][1];
	if (nxt.i < 1 || nxt.i > 8 || nxt.j < 1 || nxt.j > 8) continue;
	if (step[nxt.i][nxt.j] == 0) {
	step[nxt.i][nxt.j] = step[cur.i][cur.j] + 1;
	Q.push(nxt);
	}
	}
	}
	return step[cur.i][cur.j];
	}
	int main()
	{
	// freopen("input.txt","rt",stdin);
	char s1[3], s2[3];
	while (scanf("%s%s", s1, s2) != EOF) {
	point_type Start, End;
	Start.i = s1[0] - 'a' + 1;
	Start.j = s1[1] - '0';
	End.i = s2[0] - 'a' + 1;
	End.j = s2[1] - '0';
	int moves = BFS(Start, End);
	printf("To get from %s to %s takes %d knight moves.\n", s1, s2, moves);
	}
	return 0;
	}

view raw [UVa] 439 Knight Moves.cpp hosted with ❤ by GitHub

UVa 571 Jugs

想法：
　　題目沒說要最少步數(先輸出10次fill A empty A也可)，所以直接用DFS求解即可。

	#include <cstdio>
	#include <vector>
	#include <string>
	using namespace std;
	int A, B, N;
	vector<string> process;
	int visit[1005][1005];
	bool DFS(int a, int b)
	{
	visit[a][b] = 1;
	if (b == N) return 1;
	if (visit[A][b] == 0) {process.push_back("fill A"); if (DFS(A,b)) return 1; process.pop_back();}
	if (visit[a][B] == 0) {process.push_back("fill B"); if (DFS(a,B)) return 1; process.pop_back();}
	if (visit[0][b] == 0) {process.push_back("empty A"); if (DFS(0,b)) return 1; process.pop_back();}
	if (visit[a][0] == 0) {process.push_back("empty B"); if (DFS(a,0)) return 1; process.pop_back();}
	int pour_A, pour_B;
	if (b > (A-a)) {pour_A = A; pour_B = B - (A-a);}
	else {pour_A = a + b; pour_B = 0;}
	if (visit[pour_A][pour_B] == 0) {
	process.push_back("pour B A");
	if (DFS(pour_A,pour_B)) return 1;
	process.pop_back();
	}
	if (a > (B-b)) {pour_A = A - (B-b); pour_B = B;}
	else {pour_A = 0; pour_B = b + a;}
	if (visit[pour_A][pour_B] == 0) {
	process.push_back("pour A B");
	if (DFS(pour_A,pour_B)) return 1;
	process.pop_back();
	}
	return 0;
	}
	int main()
	{
	while (scanf("%d%d%d", &A, &B, &N) != EOF) {
	process.clear();
	for (int i = 0; i<1005; ++i)
	for (int j = 0; j<1005; ++j)
	visit[i][j] = 0;
	DFS(0,0);
	for (string &a : process)
	printf("%s\n", a.c_str());
	printf("success\n");
	}
	return 0;
	}

view raw [UVa] 571 Jugs.cpp hosted with ❤ by GitHub

UVa 336 A Node Too Far

想法：
　　先記錄某個點與哪些點有相連，然後對起點和TTL用BFS即可。

	#include <cstdio>
	#include <queue>
	#include <map>
	#include <vector>
	using namespace std;
	map<int, int> mapping;
	struct node_type{
	vector<int> connceted_node;
	};
	int NC;
	int numOfnode;
	int BFS(int start_node, int TTL, node_type node[]);
	int main()
	{
	//freopen("input.txt","rt",stdin);
	int Case = 1;
	while (scanf("%d", &NC)) {
	if (!NC) break;
	node_type node[100];
	mapping.clear();
	int node1, node2, i, j;
	for (i=0, j=0; i<NC; ++i) {
	scanf("%d%d", &node1, &node2);
	if (mapping.find(node1) == mapping.end())
	mapping[node1] = j++;
	if (mapping.find(node2) == mapping.end())
	mapping[node2] = j++;
	node[mapping[node1]].connceted_node.push_back(mapping[node2]);
	node[mapping[node2]].connceted_node.push_back(mapping[node1]);
	}
	numOfnode = j;
	int TTL;
	while (scanf("%d%d", &node1, &TTL)) {
	if (!node1 && !TTL) break;
	int numOfNotReach = BFS(node1, TTL, node);
	printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",
	Case++, numOfNotReach, node1, TTL);
	}
	}
	return 0;
	}
	int BFS(int start_node, int TTL, node_type node[])
	{
	queue<int> Q;
	Q.push(mapping[start_node]);
	int visit[100] = {0};
	visit[mapping[start_node]] = 1;
	int nOfReach = 1;
	while (!Q.empty()) {
	int cur = Q.front();
	if (visit[cur] > TTL) return numOfnode - nOfReach;
	Q.pop();
	for (int nxt : node[cur].connceted_node) {
	if(visit[nxt] == 0){
	visit[nxt] = visit[cur] + 1;
	Q.push(nxt);
	++nOfReach;
	}
	}
	}
	return numOfnode - nOfReach;
	}

view raw [UVa] 336 A Node Too Far.cpp hosted with ❤ by GitHub

UVa 383 Shipping Routes

想法：
　　用BFS來做，前M個先將輸入的字串用map對應成整數，然後接下來N行每行讀兩個字串，將彼此加入可到達的路徑裡，最後P行每行用BFS搜尋路徑。

注意輸出DATA SET"  "1  有兩個空格

	#include <iostream>
	#include <string>
	#include <map>
	#include <vector>
	#include <queue>
	#include <cstdio>
	using namespace std;
	struct route_type{
	vector<string> route;
	};
	int BFS(string Start, string End, map<string,int> &mapping, route_type A[])
	{
	int step[1001] = {0};
	queue<string> Q;
	Q.push(Start);
	while (!Q.empty()) {
	string cur = Q.front();
	Q.pop();
	for (string nxt : A[mapping[cur]].route){
	if (step[mapping[nxt]] == 0) {
	step[mapping[nxt]] = step[mapping[cur]] + 1;
	if (nxt == End) return step[mapping[nxt]];
	Q.push(nxt);
	}
	}
	}
	return 0;
	}
	int main()
	{
	//freopen("input","rt",stdin);
	ios::sync_with_stdio(false);
	int T,Case = 1;
	int M, N, P;
	cin >> T;
	cout << "SHIPPING ROUTES OUTPUT" << endl << endl;
	while (T--) {
	cin >> M >> N >> P;
	map<string,int> mapping;
	string s1,s2;
	for (int i=0; i<M; ++i){
	cin >> s1;
	mapping[s1] = i;
	}
	route_type A[1000];
	for (int i=0; i<N; ++i){
	cin >> s1 >> s2;
	A[mapping[s1]].route.push_back(s2);
	A[mapping[s2]].route.push_back(s1);
	}
	cout << "DATA SET " << Case++ << endl << endl;
	int Size;
	for (int i=0; i<P; ++i){
	cin >> Size >> s1 >> s2;
	int legs = BFS(s1,s2,mapping,A);
	if (!legs) cout << "NO SHIPMENT POSSIBLE" << endl;
	else cout << '$' << Size * legs * 100 << endl;
	}
	cout << endl;
	}
	cout << "END OF OUTPUT" << endl;
	return 0;
	}

view raw [UV] 383 Shipping Routes.cpp hosted with ❤ by GitHub

UVa 260 Il Gioco dell'X

想法：
　　因為題目說一定有人獲勝，獲勝條件為黑色是由上走到下，白色是要由左走到右，因此就用DFS確認即可。

	#include <cstdio>
	using namespace std;
	int N;
	char board[201][201];
	const int direction[][2] = {{-1,-1},{-1,0},{0,-1},{0,1},{1,0},{1,1}};
	void DFS(int i, int j, char c,int &win)
	{
	board[i][j] = '.';
	if (c == 'b' && i == N-1) win = 1;
	if (c == 'w' && j == N-1) win = 2;
	for (int x=0; x<6; ++x){
	int i_next = i+direction[x][0];
	int j_next = j+direction[x][1];
	if (i_next<0 || i_next>=N || j_next<0 || j_next>=N) continue;
	if (board[i_next][j_next] == c)
	DFS(i_next, j_next, c, win);
	}
	}
	int main()
	{
	//reopen("input.txt","rt",stdin);
	int Case = 1;
	while (scanf("%d",&N)){
	if (!N) break;
	for (int i=0; i<N; ++i)
	scanf("%s",board[i]);
	int win = 0; // win=1:Black win=2:White
	for (int i=0; i<N; ++i)
	if (board[i][0] == 'w')
	DFS(i, 0, 'w', win);
	for (int j=0; j<N; ++j)
	if (board[0][j] == 'b')
	DFS(0, j, 'b', win);
	if (win == 1) printf("%d B\n",Case++);
	else printf("%d W\n",Case++);
	}
	return 0;
	}

view raw UVa 260 Il Gioco dell'X.cpp hosted with ❤ by GitHub

UVa 113 Power of Cryptography

想法：
　　在題目條件下，k^n與(k+1)^n的差異double的精度可以分辨的出來，因此直接對p開根號在四捨五入即可。

	#include <cstdio>
	#include <cmath>
	using namespace std;
	int main()
	{
	double n,p;
	while (scanf("%lf %lf", &n, &p) != EOF)
	printf("%.0f\n",pow(p,1.0/n));
	return 0;
	}

view raw [UVa] 113 Power of Cryptography.cpp hosted with ❤ by GitHub

UVa 11538 Chess Queen

題意：
　　兩個Chess Queen在同一欄，或同一行，或同一對角線上表示為attacking position，給定a*b棋盤，問為attacking position的情況有幾種?

想法：
　　分成位在同一欄(直)，同一行(橫)，和同一對角線三種情況分開算，假設a為寬(橫的)，b為長(直的)，a必須<=b：

• 兩個棋子位在同一直線共有 a*C(b,2)*2!
• 位在同一橫線共有 b*C(a,2)*2!
• 位在對角線上可以自己畫圖觀察得到，對角線最長為a，且最長的共有(b-a+1)條，其他比a還短的對角線(長度2~a-1)都各有2條，記得對角線有左斜和右斜兩個方向。
  ....
  ....   4x5的棋盤 對角線最長為4，共2條
  ....
  ....
  ....
  因此可得 2(左斜右斜)*[(b-a+1)*C(a,2) + 2*(C(2,2)+C(3,2)+C(4,2)+...+C(a-1,2))]
  = 2*[(b-a+1)*C(a,2) + 2*C(a,3)]
• 把以上三式加起來即是答案

	#include <cstdio>
	#include <iostream>
	using namespace std;
	int main()
	{
	long long a,b;
	while (scanf("%lld%lld",&a,&b)){
	if (!a && !b) break;
	if (a > b) swap(a,b); // a:寬 b:長
	long long ans = a*b*(a-1) + a*b*(b-1); //寬 + 長
	ans += 4* (2*(a*(a-1)*(a-2)/6) + (b-a+1)*a*(a-1)/2); // 對角線
	printf("%lld\n",ans);
	}
	return 0;
	}

view raw [UVa] 11538 Chess Queen..cpp hosted with ❤ by GitHub

UVa 10763 Foreign Exchange

想法：
　　先對出發地排序一次，再對目的地排序一次，兩兩比較是否一樣即可。

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	int N;
	int origin[500001], target[500001];
	int main()
	{
	while (scanf("%d",&N)){
	if (!N) break;
	for (int i=0; i<N; i++)
	scanf("%d %d",&origin[i],&target[i]);
	if (N % 2) {
	printf("NO\n");
	continue;
	}
	sort(origin, origin+N, cmp);
	sort(target, target+N, cmp);
	bool yes = 1;
	for (int i=0; i<N; i++)
	if (origin[i] != target[i])
	yes = 0;
	printf("%s\n", yes ? "YES" : "NO");
	}
	return 0;
	}

view raw [UVa] 10763 Foreign Exchange.cpp hosted with ❤ by GitHub

UVa 10222 Decode the Mad man

想法：
　　先建立一個鍵盤keyboard，然後輸入一個字元c之後就找在keyboard裡的index，並輸出keyboard[i-2]。

	#include <cstdio>
	#include <cctype>
	using namespace std;
	const char keyboard[] = "`1234567890-=qwertyuiop[]\\asdfghjkl;'zxcvbnm,./";
	int main()
	{
	char c;
	while (scanf("%c",&c) != EOF){
	c = tolower(c); //換成小寫字母
	if (isspace(c)) printf("%c",c); //如果為' '或'\n'直接輸出
	else{
	for (int i=0; keyboard[i]; ++i)
	if (c == keyboard[i]){
	printf("%c",keyboard[i-2]);
	break;
	}
	}
	}
	return 0;
	}

view raw [UVa] 10222 Decode the Mad man.cpp hosted with ❤ by GitHub

UVa 579 ClockHands

想法：
　　題目很長但只是時針和分針夾角幾度，先將時針指的地方換成分鐘表示，然後時針分針相減後換成角度表示即可。

	#include <cstdio>
	using namespace std;
	double Abs(double a) { return a<0 ? -a : a; }
	int main()
	{
	int H,M;
	while (scanf("%d:%d",&H,&M) != EOF){
	if (!H && !M) break;
	double H_minute = (double(H) + double(M)/60) * 5; // 將時針換成分鐘表示
	double M_minute = double(M);
	double diff = Abs(H_minute - M_minute);
	while (diff >= 60) diff -= 60;
	if (diff > 30) diff = 60 - diff;
	printf("%.3f\n", diff * 6); // 一分鐘6度
	}
	return 0;
	}

view raw [UVa] 579 ClockHands.cpp hosted with ❤ by GitHub

UVa 10905 Children's Game

想法：
　　對每個數字做排序，排序用STL_sort，cmp函數裡面就比較a和b兩個數字是(ab)比較大還是(ba)比較大決定排序方式，最後依序輸出即可。

	#include <iostream>
	#include <vector>
	#include <algorithm>
	#include <string>
	using namespace std;
	bool cmp(string a, string b)
	{
	return (a+b) > (b+a);
	}
	int main()
	{
	ios::sync_with_stdio(false);
	int n;
	while (cin >> n){
	if (!n) break;
	vector<string> num;
	string temp;
	for (int i=0; i<n; ++i){
	cin >> temp;
	num.push_back(temp);
	}
	sort(num.begin(),num.end(),cmp);
	for (int i=0; i<n; ++i)
	cout << num[i];
	cout << endl;
	}
	return 0;
	}

view raw [UVa] 10905 Children's Game.cpp hosted with ❤ by GitHub

UVa 12079 Pie

題意：
　　有N塊半徑Ri的pie要分給F+1(包含作者)個人，要把N塊pie平分成F+1片，每片大小需一樣，而且須完整，表示不能從兩塊pie切下來合併成一片，問一片最大的面積為多少。

想法：
　　使用binary search搜出答案。

	#include <cstdio>
	#include <cmath>
	using namespace std;
	int main()
	{
	const double pi = 2 * asin(1);
	int Case,N, F;
	int R[10001];
	scanf("%d",&Case);
	while (Case--){
	scanf("%d%d", &N, &F);
	F++;
	int UP = 0; // BS上界
	for (int i=0; i<N; i++){
	scanf("%d",&R[i]);
	R[i] *= R[i];
	if (R[i] > UP) UP = R[i];
	}
	double left = 0, right = UP;
	while (right-left > 0.00000001){
	double mid = (left+right)/2;
	int piece = 0;
	for (int i=0; i<N; i++)
	piece += R[i]/mid;
	if (piece >= F) left = mid; //片數大於人數 因此往上逼近
	else right = mid;
	}
	printf("%.3f\n",pi * left);
	}
	return 0;
	}

view raw [UVa] 12079 Pie.cpp hosted with ❤ by GitHub

UVa 352 The Seasonal War

題意：
　　要確認畫面中有幾隻Eagles，每個pixel如果是'1'代表為一隻Eagles，但上下左右(包含斜角共8個方向)相連的'1'只能算是同一隻。

想法：
　　使用DFS找'1'有幾個區域。

	#include <cstdio>
	using namespace std;
	char image[30][30];
	void DFS(int &n, int i, int j)
	{
	image[i][j] = '0';
	if (i-1 >= 0 && image[i-1][j] == '1') DFS(n, i-1, j);
	if (i+1 < n && image[i+1][j] == '1') DFS(n, i+1, j);
	if (j-1 >= 0 && image[i][j-1] == '1') DFS(n, i, j-1);
	if (j+1 < n && image[i][j+1] == '1') DFS(n, i, j+1);
	if (i-1 >= 0 && j-1 >= 0 && image[i-1][j-1] == '1') DFS(n, i-1, j-1);
	if (i-1 >= 0 && j+1 < n && image[i-1][j+1] == '1') DFS(n, i-1, j+1);
	if (i+1 < n && j-1 >= 0 && image[i+1][j-1] == '1') DFS(n, i+1, j-1);
	if (i+1 < n && j+1 < n && image[i+1][j+1] == '1') DFS(n, i+1, j+1);
	}
	int main()
	{
	// freopen ("input.txt","rt",stdin);
	int n,Case = 1;
	while (scanf("%d", &n) != EOF){
	getchar();
	for (int i = 0; i < n; ++i)
	gets(image[i]);
	int num = 0;
	for (int i = 0; i < n; ++i)
	for (int j = 0; j < n; ++j)
	if (image[i][j] == '1'){
	DFS(n, i, j);
	++num;
	}
	printf("Image number %d contains %d war eagles.\n", Case++, num);
	}
	return 0;
	}

view raw [UVa] 352 The Seasonal War.cpp hosted with ❤ by GitHub

UVa 532 Dungeon Master

想法：
　　走迷宮使用BFS演算法，使用BFS時要注意把該位置排入queue時就要同時把該位置關閉，避免該位置被排入queue裡面很多次，導致TLE。

	#include <cstdio>
	#include <queue>
	using namespace std;
	char dungeon[32][32][32];
	int Distance[32][32][32];
	int L, R, C;
	const int direction[6][3] = {{-1,0,0},{1,0,0},{0,-1,0},{0,1,0},{0,0,-1},{0,0,1}};
	struct point_type{
	int x;
	int y;
	int z;
	};
	int BFS(int i, int j, int k)
	{
	Distance[i][j][k] = 0;
	queue<point_type> q;
	q.push(point_type{i,j,k});
	dungeon[i][j][k] = '#';
	point_type cur, nxt;
	while (!q.empty()){
	cur = q.front();
	q.pop();
	for (int i = 0; i < 6; ++i){
	nxt.x = cur.x + direction[i][0];
	nxt.y = cur.y + direction[i][1];
	nxt.z = cur.z + direction[i][2];
	if (nxt.x<0 || nxt.x >= L || nxt.y<0 || nxt.y >= R || nxt.z<0 || nxt.z>=C) continue;
	if (dungeon[nxt.x][nxt.y][nxt.z] != '#'){
	Distance[nxt.x][nxt.y][nxt.z] = Distance[cur.x][cur.y][cur.z] + 1;
	if (dungeon[nxt.x][nxt.y][nxt.z] == 'E')
	return Distance[nxt.x][nxt.y][nxt.z];
	dungeon[nxt.x][nxt.y][nxt.z] = '#';
	q.push(nxt);
	}
	}
	}
	return -1;
	}
	int main()
	{
	// freopen ("input.txt","rt",stdin);
	while (scanf("%d%d%d", &L, &R, &C)){
	if (!L && !R && !C) break;
	int start_i, start_j, start_k;
	for (int i = 0; i < L; ++i){
	for (int j = 0; j < R; ++j){
	scanf("%s",dungeon[i][j]);
	for (int k = 0; k < C; ++k)
	if (dungeon[i][j][k] == 'S'){
	start_i = i;
	start_j = j;
	start_k = k;
	}
	}
	}
	int minute = BFS(start_i, start_j, start_k);
	if (minute != -1) printf("Escaped in %d minute(s).\n", minute);
	else printf("Trapped!\n");
	}
	return 0;
	}

view raw [UVa] 532 Dungeon Master.cpp hosted with ❤ by GitHub

UVa 10776 Determine The Combination

想法：

直接舉例子來講，假設字串aaabbc(編號012345)，取3個(n==3)，我們先假設ans這個容器來存放所選的字元。

首先進入第一層遞迴後，表示要選一個字元放到ans[0]，能選的字元為0~5，for loop 0~5，先放0('a')到ans。然後進入第二層遞迴，能選的字元變成1~5，for loop 1~5，放入1('a')到ans。再進入第三層遞迴，能選的字為2~5，for loop 2~5，放入2('a')到ans。進入第四層遞迴後發現ans.size()==n，因此輸出答案。

接下來退出第四層回到第三層，跳出ans的字(ans.pop_back())，找下一個字元，因為避免重複，所以用while loop找到下一個不一樣的字，放入3('b')到ans，以此類推...

把第三層for loop跑完後，回到第二層，一樣跳出第二層的字，找下一個字不一樣的字元，然後繼續進入第三層。....剩下以此類推。

	#include <iostream>
	//#include <cstdio>
	#include <vector>
	#include <algorithm>
	using namespace std;
	string str;
	int n;
	void choose_ch (vector<char> &ans,int start)
	{
	if (ans.size() == n) {
	for (char &c : ans)
	cout << c;
	cout << endl;
	return;
	}
	for (int i = start; i < str.size(); ){
	char c = str[i];
	ans.push_back(c);
	choose_ch (ans, i+1);
	ans.pop_back();
	while (str[i] == c) i++;
	}
	}
	int main()
	{
	ios::sync_with_stdio(false);
	// freopen ("input.txt","rt",stdin);
	while (cin >> str >> n){
	sort(str.begin(), str.end());
	vector<char> ans;
	choose_ch(ans, 0);
	}
	return 0;
	}

view raw [UVa] 10776 Determine The Combination.cpp hosted with ❤ by GitHub

UVa 12337 Bob's Beautiful Balls

題目連結
想法：
　　枚舉各種方式，每次都依照題意依順時針方向填入，再檢查是否符合每個colum都是同種顏色，把長+寬最小的値儲存起來，最後輸出。

	#include <iostream>
	#include <string>
	//#include <cstdio>
	using namespace std;
	void Fill(int w, int h, string &str, char grid[][51])
	{
	int i = 0, j = 0;
	int move_i = 0, move_j = 1;
	int L = -1, U = -1, R = w, D = h;
	for (int n = 0; n < str.size(); n++){
	grid[i][j] = str[n];
	if (j + move_j == R) {
	move_i = 1;
	move_j = 0;
	U++;
	}
	else if (i + move_i == D){
	move_i = 0;
	move_j = -1;
	R--;
	}
	else if (j + move_j == L) {
	move_i = -1;
	move_j = 0;
	D--;
	}
	else if (i + move_i == U) {
	move_i = 0;
	move_j = 1;
	L++;
	}
	i += move_i;
	j += move_j;
	}
	}
	bool analysis (int w, int h, char grid[][51])
	{
	bool ok = 1;
	for (int i = 0; i < w && ok; i++){
	char c = grid[0][i];
	for (int j = 1; j < h; j++){
	if (grid[j][i] != c)
	ok = 0;
	}
	}
	return ok;
	}
	int main()
	{
	ios::sync_with_stdio(false);
	// freopen("input.txt","rt",stdin);
	int T, Case = 1;
	string str;
	cin >> T;
	while (T--){
	cin >> str;
	int ans = 1000001;
	char grid[51][51];
	for (int i = 2; i < str.size(); i++){
	if (str.size() % i != 0) continue;
	int w = i, h = str.size()/i;
	Fill(w, h, str, grid);
	if (analysis(w, h, grid)){
	if (w+h < ans)
	ans = w+h;
	}
	}
	cout << "Case " << Case++ << ": ";
	if (ans == 1000001) cout << -1 <<endl;
	else cout << ans <<endl;
	}
	return 0;
	}

view raw [UVa] 12337 Bob's Beautiful Balls.cpp hosted with ❤ by GitHub

UVa 12667 Last Blood

想法：

1. 輸入
2. 如果WA->回到1.
3. 如果已經AC->回到1.
4. 更新problem[]資料

	#include <iostream>
	#include <string>
	//#include <cstdio>
	using namespace std;
	struct team_type{
	bool problem_AC[13] = {0};
	}team[101];
	struct problem_type{
	int time;
	int team_ID = 0;
	}problem[15];
	int main()
	{
	ios::sync_with_stdio(false);
	// freopen ("input.txt","rt",stdin);
	int n, t, m;
	cin >> n >> t >> m;
	int time, ID;
	string problem_name, state;
	for (int i = 0; i < m; i++){
	cin >> time >> ID >> problem_name >> state;
	if (state != "Yes") continue;
	int index = problem_name[0]-'A';
	if (team[ID].problem_AC[index] == false){
	team[ID].problem_AC[index] = true;
	problem[index].time = time;
	problem[index].team_ID = ID;
	}
	}
	for (int i = 0; i < n; i++){
	if (problem[i].team_ID != 0)
	cout << char(i+'A') << ' ' << problem[i].time << ' '
	<< problem[i].team_ID << endl;
	else
	cout << char(i+'A') << " - -" << endl;
	}
	return 0;
	}

view raw [UVa] 12667 Last Blood.cpp hosted with ❤ by GitHub

UVa 657 The die is cast

題意：
　　定義上下左右如果有一樣的符號，這些符號為connected。
　　分辨骰子某一面的點數，以'*'圍起來的面積代表那是骰子的某一面，在那裡面要計算有幾個點數，而且如果有多個'X'是connected，只能算作一個點數，例如sample input裡面左上為2，右上為1(因為'X'是connected)，左下為2，右下為4。

想法：
　　當碰到'*'的時候，代表有一塊區域，進入DFS_pixel走遍該區域，每走到一個點就將'*'變成'.'避免重複走過，如果碰到'X'，一樣代表有一塊X區域，計數器+1，並進入DFS_X走遍該區域，並將走到的點從'X'轉為'*'。

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	char pic[51][51];
	int w, h;
	void DFS_X(int, int);
	void DFS_pixel (int i, int j, int &dots)
	{
	if (pic[i][j] == 'X') {
	dots++;
	DFS_X(i, j);
	}
	pic[i][j] = '.';
	if (i+1 < h && pic[i+1][j] != '.') DFS_pixel(i+1, j, dots);
	if (i-1 >=0 && pic[i-1][j] != '.') DFS_pixel(i-1, j, dots);
	if (j+1 < w && pic[i][j+1] != '.') DFS_pixel(i, j+1, dots);
	if (j-1 >=0 && pic[i][j-1] != '.') DFS_pixel(i, j-1, dots);
	}
	void DFS_X (int i, int j)
	{
	pic[i][j] = '*';
	if (i+1 < h && pic[i+1][j] == 'X') DFS_X(i+1, j);
	if (i-1 >=0 && pic[i-1][j] == 'X') DFS_X(i-1, j);
	if (j+1 < w && pic[i][j+1] == 'X') DFS_X(i, j+1);
	if (j-1 >=0 && pic[i][j-1] == 'X') DFS_X(i, j-1);
	}
	int main()
	{
	// freopen("input.txt","rt",stdin);
	int Case = 1;
	while (scanf("%d%d", &w, &h)){
	if (!w && !h) break;
	getchar();
	for (int i = 0; i < h; i++)
	gets(pic[i]);
	int ans[100] = {0}, nOfans = 0;
	for (int i = 0; i < h; i++)
	for (int j = 0; j < w; j++)
	if (pic[i][j] == '*'){
	DFS_pixel(i, j, ans[nOfans]);
	nOfans++;
	}
	sort(ans, ans + nOfans);
	printf("Throw %d\n", Case++);
	for (int i = 0; i < nOfans; i++){
	if (i) printf(" ");
	printf("%d", ans[i]);
	}
	printf("\n\n");
	}
	return 0;
	}

view raw [UVa] 657 The die is cast.cpp hosted with ❤ by GitHub

UVa 375 Inscribed Circles and Isosceles Triangles

題意：
　　求內切圓的圓周長總合，由於內切圓有無限多個，只要求到半徑0.000001為止。

                         

想法：
　　先求斜邊T，在透過三角型面積 T*R*2 + B*R = B*H 算得內切圓半徑R。一開始我Pi値直接使用3.14159265359，想說已經夠了，沒想到還不夠精確@_@，因此pi要使用2*arcsin(1)。

	#include <cstdio>
	#include <cmath>
	using namespace std;
	int main()
	{
	double B, H;
	const double pi = 2 * asin(1);
	int Case;
	scanf("%d", &Case);
	while (Case--){
	scanf("%lf %lf", &B, &H);
	double C = 0;
	while (1){
	double T = hypot(B/2, H);
	double R = (B*H)/(2*T+B); // 2TR+BR = BH
	if (R < 0.000001) break;
	C += (2 * pi * R);
	double H_tmp = H - 2*R;
	B = B * (H_tmp / H);
	H = H_tmp;
	}
	printf("%13.6f\n", C);
	if (Case) printf("\n");
	}
	return 0;
	}

view raw [UVa] 375 Inscribed Circles and Isosceles Triangles.cpp hosted with ❤ by GitHub

UVa 10014 Simple calculations

題目連結
想法：
a[i] = (a[i-1]+a[i+1])/2-c[i]，代入i値，左右兩式從1加到n，消除多餘項目後可得到：

• a[1]+a[n] = a[0]+a[n+1] - 2*(c[1]+...+c[n])

再從這個等式代入n値，左右兩式從1加到n，可得到

• (n+1)*a[1] = n*a[0] + a[n+1] - 2*[n*c[1] + (n-1)*c[2] + ... + 1*c[n]]

此時只剩下a[1]為未知數。

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	double a0,an1,c[3010];
	int Case, N;
	double sum_c()
	{
	double sum = 0;
	for (int i = 1, j = N; i <= N; i++, j--)
	sum += (c[i] * j);
	return sum;
	}
	int main()
	{
	scanf("%d", &Case);
	while (Case--){
	scanf("%d", &N);
	scanf("%lf %lf", &a0, &an1);
	for (int i = 1; i <= N; i++)
	scanf("%lf",&c[i]);
	printf("%.2f\n", (N * a0 + an1 - 2 * sum_c()) / (N+1));
	if (Case) printf("\n");
	}
	return 0;
	}

view raw UVa 10014 Simple calculations.cpp hosted with ❤ by GitHub

UVa 107 The Cat in the Hat

題目連結
題意：
　　一隻高度H的貓可以呼叫N個小貓幫手(N是我們要算的)，其每個小貓高度為 H*(1/(N+1))，每隻小貓可以在呼叫它的幫手N隻，身高為H*(1/(N+1))^2，一直下去，直到呼叫的小貓高度為1後，就不能再呼叫幫手了，因此這些高度為1的最矮的貓(worker cats)要把工作作完。
　　
　　現在題目給定兩個數：

• 第一個數為最高的貓(一開始只有一隻最高的貓)的高度H
• 第二個數為高度為1的貓(worker cats)的數量W，
• 求出沒有工作的貓的數量(全部-W)以及這些貓的身高總合。

想法：
　　首先最高的貓呼叫幫手後，產生N隻，高度為H*(1/(N+1))，我們假設呼叫k次直到身高為1後停止，可得出兩個等式：

• H * (1/(N+1))^k = 1
• N^k = W

因此解出N以及k後即可知道每次呼叫多少貓以及身高變為多少，將等式移項取log：

• k * log(N+1) = log(H)
• k * log(N) = log(W)

我們將第一式除以第二式消除k，然後使用binary search找出N値，接下來就能求出答案了。

	#include <cstdio>
	#include <cmath>
	using namespace std;
	typedef long long int llt;
	int main()
	{
	// freopen ("input.txt","rt",stdin);
	int H,W;
	while (scanf("%d%d",&H,&W) != EOF){
	if (!H && !W) break;
	// klog(N+1) = logH
	// klogN = logW
	// 第一式除以第二式
	double C = log(H) / log(W);
	int L = 1, R = 2147483645, mid = (L + R)/2;
	while (L != R){
	if (log(mid+1) / log(mid) - C > 0.000000000001) L = mid+1;
	else if (log(mid+1) / log(mid) - C < -0.000000000001) R = mid;
	else break;
	mid = (L + R) / 2;
	}
	int N = mid;
	int k = round (log(H) / log(N+1));
	// 不要用logW/logN避免N=1的情況，使用round四捨五入
	// N和k已經有了，剩下只是統計數量和高度
	llt notWorking = 0;
	llt totalHeight = 0;
	W = 1;
	for (int i = 0; i < k; i++){
	notWorking += W;
	totalHeight += (H * W);
	W *= N;
	H /= (N+1);
	}
	printf("%lld %lld\n",notWorking, totalHeight+(H * W));
	}
	return 0;
	}

view raw [UVa] 107 The Cat in the Hat.cpp hosted with ❤ by GitHub

UVa 10025 The ? 1 ? 2 ?....? n = k problem

想法：
　　可以先將k取絕對值，只考慮正數k，然後假設?都是+，也就是sum = +1+2+3+....+n，然後當sum > k時，將某些'+'變成'-'湊成k，可以發現把'+'變成'-'時，sum都是減掉偶數，例如Example，sum = +1+2+..+5 = 15，要湊成12，這時候把任一個數變號都是減掉偶數，因此奇數(15)減掉偶數不可能變成偶數(12)，所以要把sum往上加，直到sum為偶數為止(因為偶數-偶數=偶數)。
　　總結：sum = 1+2+3+..+n，如果k為偶數，sum為>=k的最小偶數(偶=偶-偶)；如果k為奇數，sum為>=k的最小奇數(奇=奇-偶)。

	#include <cstdio>
	#include <cmath>
	using namespace std;
	int main()
	{
	int Case, k;
	scanf("%d",&Case);
	while (Case--){
	scanf("%d",&k);
	k = abs(k);
	int n = 0;
	int sum = 0;
	while (sum < k) sum += (++n);
	if (k % 2)
	while (sum % 2 != 1) sum += (++n);
	else
	while (sum % 2 != 0) sum += (++n);
	if (k == 0) printf("3\n");
	else printf("%d\n",n);
	if (Case) printf("\n");
	}
	return 0;
	}

view raw [UVa] 10025 The ?1?2?...?n=k problem.cpp hosted with ❤ by GitHub

UVa 550 Mutiplying by Rotation

題意：
　　給定3個數(假設B,A,S)，B表示B進位，A表示被乘數的最低位數字，S表示乘數，也就是現在是xxxxxA * S，問符合 xxxxxA * S = Axxxxx則Axxxxx是幾位數?

想法：
　　可以解出xxxxx是多少，以題目example(179487)為例，B=10, A=7, S=4，可以從等式
abcde7 * 4 =
7abcde
發現，7*4=28，所以e=8，進位2，然後知道e以後，8*4+2=34，d=4，進位3，4*4+3=19，c=9，進位1，依此類推...。因此我們可以將每個位數算出來，迴圈終止條件為該位數==A且進位為0。

	#include <cstdio>
	using namespace std;
	int main()
	{
	int B, A, S;
	while (scanf("%d%d%d", &B, &A, &S) != EOF){
	int carry = 0, len = 0, x = A;
	while (1){
	int tmp = x * S + carry;
	carry = tmp / B;
	x = tmp % B;
	len++;
	if (carry == 0 && x == A) break;
	}
	printf("%d\n", len);
	}
	return 0;
	}

view raw [UVa] 550 Mutiplying by Rotation.cpp hosted with ❤ by GitHub

UVa 10392 Factoring Large Number

題意：質因數分解

想法：
　　因為題目說1000000以上的質因數最多只有1個，因此我們質數表只要建到1000000即可，建表時可以跳過2和3的倍數比較快速。

	#include <cstdio>
	#include <cmath>
	using namespace std;
	int main()
	{
	int prime[80000];
	int nOfprime = 2;
	prime[0] = 2;
	prime[1] = 3;
	for (int i = 5, gap = 2; i <= 1000000; i += gap, gap = 6-gap){
	int sqrt_i = sqrt(i);
	bool isPrime = 1;
	for (int j = 1; prime[j] < sqrt_i; j++){
	if (i % prime[j] == 0){
	isPrime = 0;
	break;
	}
	}
	if (isPrime)
	prime[nOfprime++] = i;
	}
	long long int N;
	while (scanf("%lld",&N)){
	if (N < 0) break;
	for (int i = 0; i < nOfprime; i++){
	while (N % prime[i] == 0){
	printf(" %d\n",prime[i]);
	N /= prime[i];
	}
	if (N == 1) break;
	}
	if (N != 1) printf(" %lld\n",N);
	printf("\n");
	}
	return 0;
	}

view raw [UVa] 10392 Factoring Large Numbers.cpp hosted with ❤ by GitHub

UVa 10061 How many zero's and how many digits

題意：
　　以B進位計算N!尾數有幾個0以及有幾個位數。

想法：

1. 位數部分比較簡單，如果要知道n有幾位數，直接log(10,n)+1，那如果n要換成B進位的話就取log(B,n)+1，而log的計算規則，log(B,N!) = log(B,1)+log(B,2)+......+log(B,N)。
2. 計算尾數有幾個0，對(N!)質因數分解，計算每個因數的數量，然後再看這些因數能夠湊成幾個B，例如B=20，那麼有2和5這兩個質因數能組成20，計算能夠湊成幾個，本題時間限制夠長，因此算因數的時候直接2~B枚舉即可。

	#include <cstdio>
	#include <cmath>
	using namespace std;
	int main()
	{
	int N,B;
	while (scanf("%d%d",&N,&B) != EOF){
	double digit = 0;
	int factor[801] = {0};
	double log10_B = log10(B);
	// N!
	for (int i = 2; i <= N; i++){
	//計算位數
	digit += (log10(i) / log10_B); // 換底公式log(B,i)
	//計算i的質因數
	for (int temp = i, j = 2; j <= B; j++){
	while (temp % j == 0){
	factor[j]++;
	temp /= j;
	}
	}
	}
	// 計算有幾個0
	int nOf0 = 0;
	while (1){
	int temp = B;
	// 將因數從2~B跑過 看能不能使temp==1
	for (int i = 2; i <= B; i++){
	while (factor[i] && temp % i == 0){
	factor[i]--;
	temp /= i;
	}
	}
	if (temp == 1) nOf0++;
	else break;
	}
	printf("%d %d\n",nOf0,(int)digit+1);
	}
	return 0;
	}

view raw [UVa] 10061 How many zero's and how many digits.cpp hosted with ❤ by GitHub

UVa 408 Uniform Generator

想法：
　　本題要確定Step與Mod的最大公因數是否為1，如果不是互質，那麼一定會存在空隙，比如(10,12)，其產生為10,8,6,4,2,0,..，空隙為gcd(10,12)=2。

	#include <cstdio>
	using namespace std;
	int gcd(int a, int b)
	{
	while (b){
	int temp = a % b;
	a = b;
	b = temp;
	}
	return a;
	}
	int main()
	{
	int step, mod;
	while (scanf("%d%d",&step,&mod) != EOF){
	printf("%10d%10d %s\n\n",step,mod,
	gcd(step,mod) == 1 ? "Good Choice":"Bad Choice");
	}
	return 0;
	}

view raw [UVa] 408 Uniform Generator.cpp hosted with ❤ by GitHub

UVa 10110 Light, more light

本題連結
題意：
　　有個人管理一條走廊的燈泡，當走廊有'n'個燈泡，編號1~n，預設是關閉的，他會來回走n趟，第i趟他把編號能被i整除的燈泡開關切換，本題問編號n的燈泡最後是亮還是暗。

想法：
　　n只有在其因數的時候被切換，因此如果因數個數為偶數，那麼最後是暗的，反之如果為基數則為亮的，而只有能被開平方根的時候因數個數才會為奇數。

	#include <cstdio>
	#include <cmath>
	using namespace std;
	typedef unsigned int uint;
	int main()
	{
	uint n;
	while (scanf("%u",&n)){
	if (!n) break;
	uint a = sqrt(n);
	if (a * a == n) printf("yes\n");
	else printf("no\n");
	}
	return 0;
	}

view raw [UVa] 10110 Light, more light.cpp hosted with ❤ by GitHub

UVa 668 Parliament

本題連結
題意：
　　議會中有N位代表，依照規定須分成好幾個group，每個group的人數不能一樣，然後每個group每天要派出1個人出席會議，每次的會議人員組成必須與以前不同，否則會議無法開始(意即每次組合不能與以前重複)，求如何分配group人數使得能開會議的天數最久。
　　本題簡而言之，即為給定整數N，把N分成a,b,c....不同數字，求乘積最大的方式。

想法：
　　把數字分配的越小(試想如果每個group人數能一樣，那每組分成2或3乘積為最大)和越鄰近越好(如2,3,4,5..)。因此就從2開始，2,3,4,5,.....k，直到剩下的數left(=N-(1+2+3+...+k)) < (k+1)為止，那麼將left從k,k-1....往下分配，把每個數+1，如果分配到2如果left還有剩，再從k+1開始分配，使得每個數盡量靠近。

	#include <cstdio>
	using namespace std;
	int main()
	{
	int M,N;
	scanf("%d", &M);
	while (M--) {
	scanf("%d", &N);
	int ans[1001],nOfans = 0, sum = 0;
	for (int i = 2; sum + i <= N; i++){
	sum += i;
	ans[nOfans++] = i;
	}
	int left = N - sum;
	for (int i = nOfans-1; left > 0; i--, left--){
	if (i < 0) i = nOfans-1;
	ans[i]++;
	}
	printf("%d", ans[0]);
	for (int i = 1; i < nOfans; i++)
	printf(" %d", ans[i]);
	printf("\n");
	if (M) printf("\n");
	}
	return 0;
	}

view raw [UVa] 668 Parliament.cpp hosted with ❤ by GitHub

UVa 424 Integer Inquiry

本題連結
想法：
　　先不考慮進位與不夠減的情況，把每個位數都加起來，最後再處理進位或借位。

	#include <cstdio>
	#include <cstring>
	using namespace std;
	int main()
	{
	char num[101][1001];
	int ans[1001]={0};
	for (int i = 0; scanf("%s",num[i]); i++){
	if (num[i][0] == '0') break;
	if (num[i][0] != '-'){ // 正數輸入
	for (int j = strlen(num[i])-1, k = 0; j >= 0; j--, k++)
	ans[k] += (num[i][j] - '0');
	}
	else { // 負數輸入
	for (int j = strlen(num[i])-1, k = 0; j >= 1; j--, k++)
	ans[k] -= (num[i][j] - '0');
	}
	}
	bool negative = 0;
	int i = 1000;
	while (ans[i] == 0) i--; // 找答案的最高位數
	if (ans[i] < 0) negative = 1;
	if (negative) // 如果答案為負數，先將每個數字變號，確保最高位數為正
	for (int j = 0; j <= i; j++) ans[j] *= (-1);
	for (int j = 0; j <= i; j++){
	int k = j;
	while (ans[k] > 9){ // 一直往高位數進位，直到不能進位為止
	ans[k+1]++;
	ans[k] -= 10;
	if (ans[k] <= 9) k++; // 確保該位數<=9
	}
	while (ans[k] < 0){ // 一直向高位數拿10，來使該位數>=0
	ans[k+1]--;
	ans[k] += 10;
	if (ans[k] >= 0) k++; // 確保該位數>=0
	}
	}
	if (negative) printf("-");
	for (i = 1000; ans[i] == 0; i--); // 因為進位的關係，重新找最高位數
	for (; i >= 0; i--)
	printf("%d", ans[i]);
	printf("\n");
	return 0;
	}

view raw [UVa] 424 Integer Inquiry.cpp hosted with ❤ by GitHub

UVa 10494 If We Were a Child Again

本題連結
想法：
　　與直式除法一樣，一邊作商數，一邊作餘數，直到被除數的個位數為止。

	#include <cstdio>
	using namespace std;
	char num[10001];
	long long int b,R;
	char oper[2];
	int main()
	{
	//freopen ("input.txt","rt",stdin);
	while (scanf("%s%s%lld",num,oper,&b) != EOF){
	int Q[10001],pos = 0;
	int i;
	for (i = 0, R = 0; num[i]; i++){
	R = R * 10 + (num[i] - '0');
	Q[pos++] = R / b; // ans前面幾個數字可能為0，等等輸出要從非0開始
	R = R % b;
	}
	if (oper[0] == '/'){
	for (i = 0; i < pos && Q[i] == 0; i++)
	;
	if (i == pos) printf("0"); // 如果被除數比除數小的情況
	else
	for (; i < pos; i++) printf ("%d",Q[i]);
	printf("\n");
	}
	else
	printf("%lld\n",R);
	}
	return 0;
	}

view raw [UVa] 10494 If We Were a Child Again.cpp hosted with ❤ by GitHub

UVa 10878 Decode the tape

本題連結
想法：
　　觀察a,b,c,d..字母後發現：

• a=|oo__.__o|
• b=|oo__._o_|
• c=|oo__._oo|
• d=|oo__.o__|
• e=|oo__.o_o|

　　可以知道它是以二進位的方式表示，在把'a'的値(2^0+2^5+2^6=97)加起來後與ASCII表比較，剛好就是表上'a'的値，因此這題把每個字元的値加起來輸出即可(換行符號它也已經在input裡囉，不用自己換行)。

	#include <cstdio>
	using namespace std;
	int main()
	{
	freopen ("input.txt","rt",stdin);
	char line[50];
	while (gets(line)){
	if (line[0] != '|') continue;
	char c = 0;
	for (int i=0; line[i]; i++){
	if (line[i]==' ' || line[i]=='o')
	c <<= 1;
	if (line[i]=='o')
	c++;
	}
	printf("%c",c);
	}
	return 0;
	}

view raw [UVa] 10878 Decode the tape.cpp hosted with ❤ by GitHub

UVa 409 Excuses, Excuses!

題意：
　　給定K個關鍵字，和E個句字，分析每個句字含有多少個關鍵字，將關鍵字最多的句字輸出，如果有多個數量相同的句字，則全部都要輸出。

想法：
　　將句子不是英文字母的字去掉，一個單字一個單字比對。本題輸出的時候包含最後一個Case都要有個空行。

	#include <cstdio>
	using namespace std;
	int K,E;
	char keyword[20][100],line[20][1000];
	int analysis (int x)
	{
	int num = 0, p = 0;
	char word[100];
	while (1){
	while (line[x][p]<'A' || line[x][p]>'Z' && line[x][p]<'a' || line[x][p]>'z') {
	if (line[x][p] == '\0') break;
	p++;
	}
	if (line[x][p] == '\0') break;
	int i;
	for (i=0; line[x][p]>='A'&&line[x][p]<='Z'||line[x][p]>='a'&&line[x][p]<='z'; i++)
	word[i] = line[x][p++];
	word[i] = '\0';
	for (int i=0; i<K; i++){
	int j=0,k=0;
	for (; word[j] && keyword[i][k]; j++){
	if (word[j]==keyword[i][k] || word[j]==keyword[i][k]-32) k++;
	}
	if (keyword[i][k]=='\0' && word[j]=='\0') num++;
	}
	}
	return num;
	}
	int main()
	{
	freopen ("input.txt","rt",stdin);
	int Case = 1;
	while (scanf("%d%d",&K,&E)!=EOF)
	{
	for (int i=0; i<K; i++) scanf("%s",keyword[i]);
	getchar();
	int num[20],Max = 0;
	for (int i=0; i<E; i++){
	gets(line[i]);
	num[i] = analysis(i);
	if (num[i] > Max) Max = num[i];
	}
	printf("Excuse Set #%d\n",Case++);
	for (int i=0; i<E; i++)
	if (num[i] == Max)
	puts(line[i]);
	printf("\n");
	}
	return 0;
	}

view raw [UVa] 409 Excuses, Excuses!.cpp hosted with ❤ by GitHub

UVa 537 Artificial Intelligence?

題意：
　　找出關鍵字U=???V或P=???W或I=???A的其中兩個，並從等式P=I*U算出另一個值。

想法：
　　函數分析時依序從整數，小數，以及指數的順序，在回傳兩個值後計算另一個即可。

	#include <cstdio>
	using namespace std;
	double num (char line[],int i)
	{
	double a = 0;
	while (line[i]>='0' && line[i]<='9'){
	a *= 10;
	a += (line[i]-'0');
	i++;
	}
	if (line[i] == '.'){
	i++;
	int j = 10;
	while (line[i]>='0' && line[i]<='9'){
	a += ((double)(line[i]-'0')/j);
	j *= 10;
	i++;
	}
	}
	if (line[i] == 'm') a /= 1000;
	else if (line[i] == 'k') a *= 1000;
	else if (line[i] == 'M') a *= 1000000;
	return a;
	}
	int main()
	{
	// freopen ("input.txt","rt",stdin);
	int Case;
	char line[1000];
	scanf("%d",&Case);
	getchar();
	for (int k=1; k<=Case; k++){
	gets(line);
	double P=0,U=0,I=0;
	for (int i=0; line[i+1]; i++){
	if (line[i]=='U' && line[i+1]=='=') U = num (line,i+2);
	if (line[i]=='P' && line[i+1]=='=') P = num (line,i+2);
	if (line[i]=='I' && line[i+1]=='=') I = num (line,i+2);
	}
	printf ("Problem #%d\n",k);
	if (U && I) printf("P=%.2fW\n",U*I);
	else if (P && U) printf ("I=%.2fA\n",P/U);
	else printf("U=%.2fV\n",P/I);
	printf("\n"); // 這題連最後一個problem都要空行
	}
	return 0;
	}

view raw [UVa] 537 Artificial Intelligence?.cpp hosted with ❤ by GitHub

UVa 10361 Automatic Poetry

題意：
　　給定n對詩句，每對詩句的第一句為s1<s2>s3<s4>s5的形式(si表示那是個字串，可包含空格)，我們所要做的就是把第一句<>去掉，然後第二句的"..."換成"s4s3s2s5"即可。

想法：
　　讀取每個si的時候一定要以'<'或'>'作為分隔點，因為測資不一定是以空格隔開。

	#include <cstdio>
	using namespace std;
	void l1 (char line[], char s[][1000])
	{
	int i,j;
	for (i=0; line[i]!='<'; i++) printf("%c",line[i]);
	for (i++,j=0; line[i]!='>'; i++,j++) s[2][j] = line[i];
	s[2][j] = '\0';
	for (i++,j=0; line[i]!='<'; i++,j++) s[3][j] = line[i];
	s[3][j] = '\0';
	for (i++,j=0; line[i]!='>'; i++,j++) s[4][j] = line[i];
	s[4][j] = '\0';
	for (i++,j=0; line[i]; i++,j++) s[5][j] = line[i];
	s[5][j] = '\0';
	printf("%s%s%s%s\n",s[2],s[3],s[4],s[5]);
	}
	void l2 (char line[], char s[][1000])
	{
	int i,j;
	for (i=0; line[i]!='.'; i++) printf("%c",line[i]);
	printf("%s%s%s%s\n",s[4],s[3],s[2],s[5]);
	}
	int main()
	{
	// freopen ("input.txt","rt",stdin);
	int N;
	char line[10000],s[6][1000];
	scanf("%d",&N);
	getchar();
	while (N--){
	gets(line);
	l1 (line, s);
	gets(line);
	l2 (line, s);
	}
	return 0;
	}

view raw [UVa[ 10361 Automatic Poetry.cpp hosted with ❤ by GitHub

UVa 10010 Where's Waldorf?

想法：
　　先把字都換成小寫，然後由左往右，由上往下，每個位置往八個方向找確認是否符合。

	#include <cstdio>
	using namespace std;
	char grid[51][51],word[51];
	int Case,m,n,k;
	void upper_to_lower (char a[])
	{
	for (int i=0; a[i]; i++)
	if (a[i]>='A' && a[i]<='Z')
	a[i] += 32;
	}
	bool Locate (int i, int j)
	{
	int x;
	for (x=1; i-x>=0 && word[x]==grid[i-x][j];) {x++; if (word[x]=='\0') return 1;}
	for (x=1; i+x<m && word[x]==grid[i+x][j];) {x++; if (word[x]=='\0') return 1;}
	for (x=1; j-x>=0 && word[x]==grid[i][j-x];) {x++; if (word[x]=='\0') return 1;}
	for (x=1; j+x<n && word[x]==grid[i][j+x];) {x++; if (word[x]=='\0') return 1;}
	for (x=1; i-x>=0 && j-x>=0 && word[x]==grid[i-x][j-x];) {x++; if (word[x]=='\0') return 1;}
	for (x=1; i+x<m && j-x>=0 && word[x]==grid[i+x][j-x];) {x++; if (word[x]=='\0') return 1;}
	for (x=1; i-x>=0 && j+x<n && word[x]==grid[i-x][j+x];) {x++; if (word[x]=='\0') return 1;}
	for (x=1; i+x<m && j+x<n && word[x]==grid[i+x][j+x];) {x++; if (word[x]=='\0') return 1;}
	return 0;
	}
	int main()
	{
	// freopen("input.txt","rt",stdin);
	scanf("%d",&Case);
	while (Case--){
	scanf("%d%d",&m,&n);
	for (int i=0; i<m; i++){
	scanf("%s",grid[i]);
	upper_to_lower(grid[i]);
	}
	scanf("%d",&k);
	while (k--){
	scanf("%s",word);
	upper_to_lower(word);
	int i,j,ok=0;
	for (i=0; i<m && !ok; i++)
	for (j=0; j<n && !ok; j++)
	if (grid[i][j] == word[0] && Locate (i,j)){
	printf("%d %d\n",i+1,j+1);
	ok = 1;
	}
	}
	if (Case) printf("\n");
	}
	return 0;
	}

view raw [UVa] 10010 Where's Waldorf.cpp hosted with ❤ by GitHub

UVa 401 Palindromes

本題連結
想法：
　　處理鏡像的部份我是把它存成陣列，Mir[]="AAE3HHIIJLLJ...."，比對兩個字元是否為鏡像，則看Mir[i]和Mir[i+1]是否符合，另外要注意本題每個輸出之間還要空一行。

	#include <cstdio>
	#include <cstring>
	using namespace std;
	char Mir[]="AAE3HHIIJLLJMMOOS2TTUUVVWWXXYYZ500112S3E5Z88";
	bool isMirrored (char a, char b){
	for (int i=0; Mir[i+1]; i++)
	if (Mir[i]==a && Mir[i+1]==b) return 1;
	return 0;
	}
	bool isPalindrome (char a,char b){
	return a == b;
	}
	int main()
	{
	// freopen("input.txt","rt",stdin);
	char c[100];
	while (gets(c)){
	bool palindrome = 1,mirrored = 1;
	for (int i = 0, j = strlen(c)-1; i <= j; i++, j--){
	if (!isMirrored(c[i],c[j])) mirrored = 0;
	if (!isPalindrome(c[i],c[j])) palindrome = 0;
	}
	if (palindrome && mirrored) printf("%s -- is a mirrored palindrome.\n\n",c);
	else if (palindrome) printf("%s -- is a regular palindrome.\n\n",c);
	else if (mirrored) printf("%s -- is a mirrored string.\n\n",c);
	else printf("%s -- is not a palindrome.\n\n",c);
	}
	return 0;
	}

view raw [UVa] 401 Palindromes.cpp hosted with ❤ by GitHub

UVa 445 Marvelous Mazes

題意：
　　遇到每個數字是"加起來"，如23X，則輸出5個X，2X12*，則輸出XX***，b表示空格，!則要換行。

	#include <cstdio>
	using namespace std;
	int main()
	{
	// freopen ("input.txt","rt",stdin);
	char c;
	int num=0;
	while (c=getchar()){
	if (c == EOF) break;
	if (c == '\n' || c == '!')
	printf("\n");
	else if (c >= '0' && c <= '9')
	num += (c - '0');
	else{
	if (c == 'b'){
	for (int i=0; i<num; i++)
	printf(" ");
	}
	else {
	for (int i=0; i<num; i++)
	printf("%c",c);
	}
	num = 0;
	}
	}
	return 0;
	}

view raw [UVa] 445 Marvelous Mazes.cpp hosted with ❤ by GitHub

UVa 490 Rotating Sentences

題意：
　　將每一行的句子轉成直的，順序由下到上。
想法：
　　將每個句字保存後，依題意順序將句子每個字輸出，如果該列句子已經結束，則輸出空格。

	#include <cstdio>
	#include <cstring>
	using namespace std;
	int main()
	{
	// freopen ("input.txt","rt",stdin);
	char sentence[101][101];
	int N=0,length[101];
	int Max_length=0;
	while (gets(sentence[N])) {
	length[N] = strlen(sentence[N]);
	if (length[N] > Max_length) Max_length = length[N];
	N++;
	}
	for (int i=0; i<Max_length; i++){
	for (int j=N-1; j>=0; j--){
	if (i < length[j])
	printf("%c",sentence[j][i]);
	else
	printf(" ");
	}
	printf("\n");
	}
	return 0;
	}

view raw [UVa] 490 Rotating Senteneces.cpp hosted with ❤ by GitHub

UVa 414 Machined Surfaces

題意：
　　固定左右兩邊形狀，合併後會有多少個空格
想法：
　　計算每一列有多少個X，並找出哪一列有最多個X，值為Max，則該列空格就是(Max-該列有幾個X)

	#include <cstdio>
	using namespace std;
	int main()
	{
	// freopen ("input.txt","rt",stdin);
	int N;
	while (scanf("%d",&N)){
	if (!N) break;
	int nOfX[20]={0},Max = 0;
	char line[30];
	gets(line);
	for (int i=0; i<N; i++){
	gets(line);
	for (int j=0; line[j]; j++)
	if (line[j]=='X') nOfX[i]++;
	if (nOfX[i]>Max)
	Max = nOfX[i];
	}
	int ans = 0;
	for (int i=0; i<N; i++)
	ans += (Max-nOfX[i]);
	printf("%d\n",ans);
	}
	return 0;
	}

view raw [UVa] 414 Machined Surfaces.cpp hosted with ❤ by GitHub

UVa 10082 WERTYU

想法：
　　用一個陣列代表鍵盤按鍵：char keyboard[]="QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./"，然後找出輸入字元的i值，再輸出keyboard[i-1]。

	#include <cstdio>
	using namespace std;
	int main()
	{
	// freopen("input.txt","rt",stdin);
	char keyboard[] = "`1234567890-=QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./";
	char line[1000];
	while (gets(line)){
	for (int i=0; line[i]; i++){
	if (line[i] == ' ') printf(" ");
	else{
	int j = 0;
	while (line[i] != keyboard[j+1]) j++;
	printf("%c",keyboard[j]);
	}
	}
	printf("\n");
	}
	return 0;
	}

view raw [UVa] 10082 WERTYU.cpp hosted with ❤ by GitHub

UVa 12537 Radiation

題意：
　　在核能廠半徑範圍內的住家可以得到protective equipments，a和c區域可以得到一組，而b區域因為在重疊範圍內，所以有2組，但在範圍外的d區域沒有equipment，但因為equipments只要1組就夠用了，因此b區域的住家可以分給d區域的住家，題目求d區域在b區域給了equipments之後還有幾戶住家沒有equipments，即為(d-b)。
　　給定一堆點座標和兩個圓心座標，每次兩個圓都有不同的半徑，題目所求為在圓外面點的數量減掉在左圓且在右圓內點的數量，為(d-b)。

想法：

• 找出在左圓範圍內點的數量(a+b)
• 找出在右圓範圍內點的數量(c+b)
• 所有點的總數N=a+b+c+d
• 所求即為N-(a+b)-(c+b) = d-b

	#include <cstdio>
	#include <algorithm>
	#include <cmath>
	using namespace std;
	int N,x[200001],y[200001];
	double a_dis[200001],b_dis[200001];
	int ax,ay,bx,by,Q,R1,R2;
	int BS (int R,double dis[])
	{
	int left = 0, right = N-1;
	while (left != right){
	int mid = (left+right+1)/2;
	if (dis[mid] > R) right = mid-1;
	else left = mid;
	}
	return left+1; //回傳為數量，因此是index+1
	}
	int main()
	{
	freopen ("input.txt","rt",stdin);
	int Case = 1;
	while (scanf("%d",&N)){
	if (!N) break;
	for (int i=0; i<N; i++) scanf("%d %d",&x[i],&y[i]);
	scanf("%d %d %d %d %d",&ax,&ay,&bx,&by,&Q);
	for (int i=0; i<N; i++) {
	a_dis[i] = sqrt (pow(x[i]-ax,2) + pow(y[i]-ay,2));
	b_dis[i] = sqrt (pow(x[i]-bx,2) + pow(y[i]-by,2));
	}
	sort (a_dis,a_dis+N);
	sort (b_dis,b_dis+N);
	printf("Case %d:\n",Case++);
	while (Q--){
	scanf("%d %d",&R1,&R2);
	int ans = N - BS(R1,a_dis) - BS(R2,b_dis);
	if (ans >= 0) printf("%d\n",ans);
	else printf("0\n");
	}
	}
	return 0;
	}

view raw UVa 12537 Radiation.cpp hosted with ❤ by GitHub