|
|
1 /* Accepted 1091 C++ 00:00.08 844K */
2 #include <queue>
3 #include <iostream>
4
5 using namespace std;
6
7 struct rec { int x, y, cnt; };
8 struct { int x, y; } dir[8] = {
9 {-2, +1}, {-1, +2}, {+1, +2}, {+2, +1},
10 {+2, -1}, {+1, -2}, {-1, -2}, {-2, -1}
11 };
12
13 inline bool inside(const int x, const int y)
14 {
15 if(x >= 0 && x < 8 && y >= 0 && y < 8)
16 return true;
17 return false;
18 }
19
20 int BFS(int sx, int sy, int tx, int ty)
21 {
22 bool visited[8][8] = {false};
23
24 visited[sx][sy] = true;
25 rec cur = {sx, sy, 0};
26 queue <rec> q;
27 q.push(cur);
28
29 while(q.empty() == false)
30 {
31 cur = q.front(); q.pop();
32
33 if(cur.x == tx && cur.y == ty)
34 return cur.cnt;
35
36 for(int i = 0; i < 8; i++)
37 {
38 int x = cur.x + dir[i].x;
39 int y = cur.y + dir[i].y;
40
41 if(inside(x, y) && visited[x][y] == false)
42 {
43 visited[x][y] = true;
44 rec tmp = {x, y, cur.cnt + 1};
45 q.push(tmp);
46 }
47 }
48 }
49 }
50
51 int main()
52 {
53 char sx, sy, tx, ty;
54 while(cin >> sx >> sy >> tx >> ty)
55 {
56 sx -= 'a', sy = sy - '0' - 1;
57 tx -= 'a', ty = ty - '0' - 1;
58 printf("To get from %c%d to %c%d takes %d knight moves.\n",
59 sx + 'a', sy + 1, tx + 'a', ty + 1, BFS(sx, sy, tx, ty));
60 }
61
62 return 0;
63 }
64
1 /* Accepted 1136 C++ 00:00.41 992K */
2 #include <queue>
3 #include <string>
4 #include <iostream>
5
6 using namespace std;
7
8 struct rec { int num; string strDigit; };
9
10 int main()
11 {
12 int n, m;
13 while(cin >> n)
14 {
15 cin >> m;
16 int * digit = new int[m];
17 for(int i = 0; i < m; i++)
18 cin >> digit[i];
19
20 if(n == 0)
21 {
22 cout << 0 << endl;
23 delete [] digit;
24 continue;
25 }
26
27 sort(digit, digit + m);
28
29 queue <rec> q;
30
31 rec cur;
32 cur.num = 0;
33 cur.strDigit = "";
34
35 q.push(cur);
36
37 bool r[5000] = {false};
38
39 while(q.empty() == false)
40 {
41 cur = q.front(); q.pop();
42
43 for(int i = 0; i < m; i++)
44 {
45 int x = cur.num * 10 + digit[i];
46
47 if(x == 0)
48 continue;
49
50 rec tmp;
51 if(r[x % n] == false)
52 {
53 r[x % n] = true;
54 tmp.num = x % n;
55 tmp.strDigit = cur.strDigit;
56 tmp.strDigit += char(digit[i] + '0');
57 q.push(tmp);
58 }
59 if(r[0])
60 {
61 cout << tmp.strDigit << endl; goto over;
62 }
63 }
64 }
65 cout << 0 << endl;
66
67 over:
68 delete [] digit;
69 }
70
71 return 0;
72 }
73
74
1 /* Accepted 1196 C++ 00:00.04 1020K */
2 #include <iostream>
3
4 using namespace std;
5
6 int main()
7 {
8 int n, m, chain = 0;
9 while(cin >> n >> m)
10 {
11 if(n == 0 && m == 0)
12 break;
13
14 int p[201];
15 for(int i = 1; i <= n; i++)
16 cin >> p[i];
17
18 int w[201][201] = {0};
19 for(int i = 1; i <= n; i++)
20 for(int j = 1; j <= n; j++)
21 for(int k = i; k <= j; k++)
22 w[i][j] += abs(p[k] - p[(i + j) / 2]);
23
24 int opt[31][201];
25
26 for(int i = 1; i <= n; i++)
27 opt[1][i] = w[1][i];
28
29 for(int i = 2; i <= m; i++)
30 for(int j = i; j <= n; j++)
31 {
32 opt[i][j] = INT_MAX;
33 for(int k = i - 1; k < j; k++)
34 opt[i][j] <?= (opt[i - 1][k] + w[k + 1][j]);
35 }
36 chain++;
37 cout << "Chain " << chain << endl
38 << "Total distance sum = " << opt[m][n] << endl << endl;
39 }
40
41 return 0;
42 }
43
1 /* Accepted 1148 C++ 00:00.01 872K */
2 #include <queue>
3 #include <iostream>
4
5 using namespace std;
6
7 struct rec { int x, y, cnt, dir; };
8 struct { int x, y; } dir[4] = { {-1, 0}, {+1, 0}, {0, -1}, {0, 1} };
9
10 int main()
11 {
12 int w, h, board = 0;
13 bool map[77][77];
14
15 while(cin >> h >> w)
16 {
17 if(w == 0 && h == 0)
18 break;
19
20 board++;
21 cout << "Board #" << board << ':' << endl;
22
23 memset(map, false, sizeof(map));
24
25 for(int i = 1; i <= w; i++)
26 for(int j = 1; j <= h; j++)
27 switch(cin.get())
28 {
29 case 'X' : map[i][j] = 1; break;
30 case ' ' : map[i][j] = 0; break;
31 default : j--;
32 }
33
34 int sx, sy, tx, ty, pair = 0;
35 while(cin >> sy >> sx >> ty >> tx)
36 {
37 if(sx == 0 && sy == 0 && tx == 0 && ty == 0)
38 break;
39
40 pair++;
41 cout << "Pair " << pair << ": ";
42
43 bool repeat[77][77][4] = {false};
44
45 rec start = { sx, sy , 0, -1};
46 queue <rec> q; q.push(start);
47
48 rec cur;
49 int min = INT_MAX;
50 while(q.empty() == false)
51 {
52 cur = q.front(); q.pop();
53
54 for(int i = 0; i < 4; i++)
55 {
56 int x = cur.x + dir[i].x;
57 int y = cur.y + dir[i].y;
58
59 if(x == tx && y == ty)
60 min <?= (cur.cnt + (cur.dir != i));
61
62 if(x >= 0 && x <= w + 1 && y >= 0 && y <= h + 1)
63 if(map[x][y] == false && repeat[cur.x][cur.y][i] == false)
64 {
65 repeat[cur.x][cur.y][i] = true;
66 rec tmp = {x, y, cur.cnt + (cur.dir != i), i};
67 q.push(tmp);
68 }
69 }
70 }
71
72 if(min != INT_MAX)
73 cout << min << " segments." << endl;
74 else
75 cout << "impossible." << endl;
76 }
77 cout << endl;
78 }
79
80 return 0;
81 }
82
1 /* Accepted 1164 C++ 00:00.00 856K */
2 #include <string>
3 #include <iostream>
4
5 using namespace std;
6
7 int main()
8 {
9 string s;
10 while(true)
11 {
12 getline(cin, s);
13
14 if(s == "#")
15 break;
16
17 int n = 0;
18 for(int i = 0; i < s.size(); i++)
19 n = (n * 256 + int(s[i])) % 34943;
20
21 n = n * 256 % 34943;
22 n = n * 256 % 34943;
23 n = (34943 - n) % 34943;
24
25 int left = n >> 8;
26 int right = n & 255;
27
28 char c1, c2, c3, c4, m[] = "0123456789ABCDEF";
29
30 c2 = m[left % 16]; left /= 16;
31 c1 = m[left % 16]; left /= 16;
32 c4 = m[right % 16]; right /= 16;
33 c3 = m[right % 16]; right /= 16;
34
35 cout << c1 << c2 << ' ' << c3 << c4 << endl;
36 }
37
38 return 0;
39 }
40
1 /* Accepted 0.001 292 KB */
2 #include <iostream>
3
4 using namespace std;
5
6 int n, m, map[101][101], opt[101][101];
7
8 struct BinaryTree
9 {
10 int num, apple;
11 BinaryTree * left, * right;
12
13 BinaryTree()
14 {
15 left = right = NULL;
16 }
17 void PostOrder()
18 {
19 if(left == NULL && right == NULL)
20 {
21 opt[num][1] = apple;
22 return;
23 }
24 if(left)
25 left -> PostOrder();
26 if(right)
27 right -> PostOrder();
28
29 for(int i = 1; i <= m; i++)
30 {
31 int max = 0;
32 for(int j = 0; j < i; j++)
33 if(max < opt[left -> num][j] + opt[right -> num][i - j - 1])
34 max = opt[left -> num][j] + opt[right -> num][i - j - 1];
35 opt[num][i] = max + apple;
36 }
37 }
38 }Tree[101];
39
40 bool visited[101];
41 void dfs(int p)
42 {
43 visited[p] = true;
44 for(int i = 1; i <= n; i++)
45 if(map[p][i] && visited[i] == false)
46 {
47 Tree[i].num = i;
48 Tree[i].apple = map[p][i];
49
50 if(Tree[p].left == NULL)
51 Tree[p].left = &Tree[i];
52 else
53 Tree[p].right = &Tree[i];
54 dfs(i);
55 }
56 }
57
58 int main()
59 {
60 cin >> n >> m; m++;
61
62 int s, t, l;
63 while(cin >> s >> t >> l)
64 map[s][t] = map[t][s] = l;
65
66 dfs(1);
67
68 Tree[1].num = 1;
69 Tree[1].apple = 0;
70 Tree[1].PostOrder();
71
72 cout << opt[1][m] << endl;
73
74 return 0;
75 }
76
1 /* Accepted 1170 C++ 00:00.01 840K */
2 #include <string>
3 #include <iostream>
4
5 using namespace std;
6
7 int gcd(int a, int b)
8 {
9 if(b == 0)
10 return a;
11 return gcd(b, a % b);
12 }
13
14 int main()
15 {
16 string s1, s2;
17 while(cin >> s1 >> s2)
18 {
19 cout << "appx" << '(' << s1 << ',' << s2 << ')' << " = ";
20
21 if(s1 == s2)
22 {
23 cout << 1 << endl;
24 continue;
25 }
26
27 int max = 0;
28 for(int i = 0; i < s1.size(); i++)
29 {
30 int sum = 0;
31 for(int j = 0; j < s2.size(); j++)
32 if(i + j >= s1.size())
33 break;
34 else
35 sum += (s1[i + j] == s2[j]);
36 max >?= sum;
37 }
38 for(int i = 0; i < s2.size(); i++)
39 {
40 int sum = 0;
41 for(int j = 0; j < s1.size(); j++)
42 if(i + j >= s2.size())
43 break;
44 else
45 sum += (s2[i + j] == s1[j]);
46 max >?= sum;
47 }
48
49 max *= 2;
50 int len = s1.size() + s2.size();
51
52 while(true)
53 {
54 int x = gcd(max, len);
55 if(x == 1)
56 break;
57 max /= x, len /= x;
58 }
59
60 if(max == 0)
61 cout << 0 << endl;
62 else
63 cout << max << '/' << len << endl;
64 }
65
66 return 0;
67 }
68
1 /* Accepted 1184 C++ 00:00.00 832K */
2 #include <string>
3 #include <iostream>
4
5 using namespace std;
6
7 int main()
8 {
9 int n;
10 cin >> n;
11 while(n--)
12 {
13 string left, right, status;
14
15 int weight[12] = {0};
16 bool real[12] = {false};
17
18 for(int i = 0; i < 3; i++)
19 {
20 cin >> left >> right >> status;
21 if(status == "even")
22 {
23 for(int j = 0; j < left.size(); j++)
24 real[left[j] - 'A'] = true, real[right[j] - 'A'] = true;
25 continue;
26 }
27 if(status == "up")
28 {
29 for(int j = 0; j < left.size(); j++)
30 weight[left[j] - 'A']++, weight[right[j] - 'A']--;
31 continue;
32 }
33 //status == "down"
34 for(int j = 0; j < left.size(); j++)
35 weight[left[j] - 'A']--, weight[right[j] - 'A']++;
36 }
37
38 int max = 0, counterfeit; bool light;
39 for(int i = 0; i < 12; i++)
40 if(real[i] == false)
41 if(max < abs(weight[i]))
42 {
43 max = abs(weight[i]);
44 counterfeit = i;
45 if(weight[i] < 0)
46 light = true;
47 else
48 light = false;
49 }
50 cout << char(counterfeit + 'A') << " is the counterfeit coin and it is "
51 << (light ? "light." : "heavy.") << endl;
52 }
53
54 return 0;
55 }
56
1 /* Accepted 1137 C++ 00:07.49 1820K */
2 #include <iostream>
3
4 using namespace std;
5
6 int n, match[1000];
7 bool map[1000][1000], visited[1000];
8
9 bool dfs(int p)
10 {
11 for(int i = 0; i < n; i++)
12 if(map[p][i] && visited[i] == false)
13 {
14 visited[i] = true;
15 if(match[i] == -1 || dfs(match[i]))
16 {
17 match[i] = p;
18 return true;
19 }
20 }
21 return false;
22 }
23
24 int main()
25 {
26 while(cin >> n)
27 {
28 memset(map, false, sizeof(map));
29 memset(match, 255, sizeof(match));
30
31 int s, t, m;
32 for(int i = 0; i < n; i++)
33 {
34 scanf("%d: (%d)", &s, &m);
35 while(m--)
36 {
37 cin >> t;
38 map[s][t] = true;
39 }
40 }
41
42 int cnt = 0;
43 for(int i = 0; i < n; i++)
44 {
45 memset(visited, false, sizeof(visited));
46 cnt += dfs(i);
47 }
48 cout << n - cnt / 2 << endl;
49 }
50
51 return 0;
52 }
53
1 /* Accepted 1139 C++ 00:04.99 900K */
2 #include <iostream>
3
4 using namespace std;
5
6 struct Rectangle
7 {
8 int x1, y1, x2, y2;
9 };
10
11 int main()
12 {
13 int n;
14 while(cin >> n)
15 {
16 Rectangle * rect = new Rectangle[n];
17
18 for(int i = 0; i < n; i++)
19 cin >> rect[i].x1 >> rect[i].x2 >> rect[i].y1 >> rect[i].y2;
20
21 int cnt = 0;
22 for(int i = 0; i < n; i++)
23 for(int j = 0; j < n; j++)
24 if(i != j)
25 if(rect[i].x1 >= rect[j].x1 && rect[i].y1 >= rect[j].y1)
26 if(rect[i].x2 <= rect[j].x2 && rect[i].y2 <= rect[j].y2)
27 {
28 cnt++;
29 break;
30 }
31 cout << cnt << endl;
32
33 delete [] rect;
34 }
35
36 return 0;
37 }
38
|