|
|
1 /* Accepted 2488K 688MS G++ 3131B */
2 #include <queue>
3 #include <iostream>
4
5 using namespace std;
6
7 struct point { int x, y; } ;
8
9 point dir[8] = {
10 {-2, +1}, {-1, +2}, {+1, +2}, {+2, +1},
11 {+2, -1}, {+1, -2}, {-1, -2}, {-2, -1}
12 };
13
14 int n, a[300][300], b[300][300];
15
16 inline bool inside(const int x, const int y)
17 {
18 if(x >= 0 && x < n && y >= 0 && y < n)
19 return true;
20 return false;
21 }
22
23 int bfs(int sx, int sy, int tx, int ty)
24 {
25 for(int i = 0; i < n; i++)
26 for(int j = 0; j < n; j++)
27 a[i][j] = b[i][j] = -1;
28
29 a[sx][sy] = b[tx][ty] = 0;
30
31 queue <point> l, r;
32 point sp = { sx, sy };
33 point tp = { tx, ty };
34 l.push(sp); r.push(tp);
35
36 point cp;
37 while(l.empty() == false || r.empty() == false)
38 {
39 if(l.empty() == false)
40 {
41 cp = l.front(); l.pop();
42 for(int i = 0; i < 8; i++)
43 {
44 int x = cp.x + dir[i].x;
45 int y = cp.y + dir[i].y;
46 if(inside(x, y))
47 {
48 if(a[x][y] == -1)
49 {
50 a[x][y] = a[cp.x][cp.y] + 1;
51 point np = { x, y };
52 l.push(np);
53 }
54 if(b[x][y] != -1)
55 return a[x][y] + b[x][y];
56 }
57 }
58 }
59 if(r.empty() == false)
60 {
61 cp = r.front(); r.pop();
62 for(int i = 0; i < 8; i++)
63 {
64 int x = cp.x + dir[i].x;
65 int y = cp.y + dir[i].y;
66 if(inside(x, y))
67 {
68 if(b[x][y] == -1)
69 {
70 b[x][y] = b[cp.x][cp.y] + 1;
71 point np = { x, y };
72 r.push(np);
73 }
74 if(a[x][y] != -1)
75 return a[x][y] + b[x][y];
76 }
77 }
78 }
79 }
80 }
81
82 int main()
83 {
84 cin >> n;
85 while(cin >> n)
86 {
87 int sx, sy, tx, ty;
88 cin >> sx >> sy >> tx >> ty;
89
90 if(sx == tx && sy == ty)
91 cout << 0 << endl;
92 else
93 cout << bfs(sx, sy, tx, ty) << endl;
94 }
95
96 return 0;
97 }
98
摘要: 1 #include <queue> 2 #include <iostream> 3 4 using namespace std; 5 6 ... 阅读全文
1 /* Accepted 2207 C++ 00:00.00 844K */
2 #include <string>
3 #include <iostream>
4
5 using namespace std;
6
7 int n;
8 bool x[100][5][5];
9
10 int BestRanking;
11 int CurOrder[5], BestOrder[5]; bool choosed[5];
12
13 void search(int k, int CurRanking)
14 {
15 if(k == 5)
16 {
17 BestRanking = CurRanking;
18 memcpy(BestOrder, CurOrder, sizeof(CurOrder));
19
20 return;
21 }
22
23 for(int i = 0; i < 5; i++)
24 if(choosed[i] == false)
25 {
26 if(k == 0)
27 {
28 CurOrder[k] = i;
29
30 choosed[i] = true;
31 search(k + 1, 0);
32 choosed[i] = false;
33
34 continue;
35 }
36
37 int p, cnt = CurRanking;
38 for(p = 0; p < n; p++)
39 {
40 int t = i;
41 for(int s = 0; s < k; s++)
42 if(x[p][t][CurOrder[s]])
43 cnt++;
44 if(cnt >= BestRanking)
45 break;
46 }
47
48 if(p == n)
49 {
50 CurOrder[k] = i;
51
52 choosed[i] = true;
53 search(k + 1, cnt);
54 choosed[i] = false;
55 }
56 }
57 }
58
59 int main()
60 {
61 while(scanf("%d", &n) && n)
62 {
63 BestRanking = INT_MAX;
64 memset(x, false, sizeof(x));
65 memset(choosed, false, sizeof(choosed));
66
67 string s;
68 for(int k = 0; k < n; k++)
69 {
70 cin >> s;
71 for(int i = 0; i < 5; i++)
72 s[i] -= 'A';
73 for(int i = 0; i < 5; i++)
74 for(int j = i + 1; j < 5; j++)
75 x[k][s[i]][s[j]] = true;
76 }
77
78 search(0, 0);
79
80
81 for(int k = 0; k < 5; k++)
82 cout << char(BestOrder[k] + 'A');
83 cout << " is the median ranking with value "
84 << BestRanking << '.' << endl;
85 }
86
87 return 0;
88 }
89
1 /* Accepted 1331 C++ 00:00.23 836K */
2 #include <iostream>
3
4 using namespace std;
5
6 int cmp(const void * a, const void * b)
7 {
8 return *(int*)a - *(int*)b;
9 }
10
11 int main()
12 {
13 cout << "Cube = 6, Triple = (3,4,5)" << endl;
14 cout << "Cube = 12, Triple = (6,8,10)" << endl;
15 cout << "Cube = 18, Triple = (2,12,16)" << endl;
16 cout << "Cube = 18, Triple = (9,12,15)" << endl;
17 cout << "Cube = 19, Triple = (3,10,18)" << endl;
18 cout << "Cube = 20, Triple = (7,14,17)" << endl;
19
20 int x[202];
21 for(int i = 2; i <= 200; i++)
22 x[i] = i * i * i;
23
24 for(int n = 24; n <= 200; n++)
25 for(int a = 2; a < n; a++)
26 for(int b = 2; b < n; b++)
27 if(a < b)
28 {
29 int c = x[n] - x[a] - x[b];
30 if(c <= 0)
31 continue;
32 int *p = (int*)bsearch(&c, x, n, sizeof(int), cmp);
33 if(p && p - x > b)
34 printf("Cube = %d, Triple = (%d,%d,%d)\n", n, a, b, p - x);
35 }
36
37 return 0;
38 }
39
1 /* Accepted 340K 204MS G++ 1571B */
2 #include <iostream>
3
4 using namespace std;
5
6 enum { A, B, C, D, E, F, G, H, I };
7
8 int clocks[9];
9 int control[9][6] = {
10 {4, A, B, D, E},
11 {3, A, B, C},
12 {4, B, C, E, F},
13 {3, A, D, G},
14 {5, B, D, E, F, H},
15 {3, C, F, I},
16 {4, D, E, G, H},
17 {3, G, H, I},
18 {4, E, F, H, I}
19 };
20
21 int x[9];
22 int bestx[9], best = INT_MAX;
23 void search(int k)
24 {
25 if(k == 9)
26 {
27 for(int i = 0; i < 9; i++)
28 if(clocks[i])
29 return;
30
31 int cnt = 0;
32 for(int i = 0; i < 9; i++)
33 cnt += x[i];
34
35 if(cnt < best)
36 {
37 best = cnt;
38 for(int i = 0; i < 9; i++)
39 bestx[i] = x[i];
40 }
41 return;
42 }
43
44 x[k] = 0;
45 search(k + 1);
46
47 for(int i = 1; i <= 3; i++)
48 {
49 for(int j = 1; j <= control[k][0]; j++)
50 {
51 clocks[control[k][j]]++;
52 clocks[control[k][j]] %= 4;
53 }
54
55 x[k] = i;
56
57 search(k + 1);
58 }
59
60 for(int i = 1; i <= 3; i++)
61 for(int j = 1; j <= control[k][0]; j++)
62 if(clocks[control[k][j]] == 0)
63 clocks[control[k][j]] = 3;
64 else
65 clocks[control[k][j]]--;
66 }
67
68 int main()
69 {
70 for(int i = 0; i < 9; i++)
71 cin >> clocks[i];
72
73 search(0);
74
75 for(int i = 0; i < 9; i++)
76 for(int j = 0; j < bestx[i]; j++)
77 cout << i + 1 << ' ';
78 cout << endl;
79
80 return 0;
81 }
82
1 /* Accepted 1083 C++ 00:00.01 840K */
2 #include <iostream>
3
4 using namespace std;
5
6 int n, m;
7 char pic[30][30];
8
9 int in[26];
10 bool map[30][30];
11
12 struct { int ax, ay, bx, by; } frame[26];
13 int FrameCnt;
14
15 bool choosed[26];
16 char ans[26];
17
18 void TopSort(int k)
19 {
20 if(k == FrameCnt)
21 {
22 for(int i = 0; i < FrameCnt; i++)
23 cout << char(ans[i] + 'A');
24 cout << endl;
25 return;
26 }
27
28 for(int i = 0; i < FrameCnt; i++)
29 if(in[i] == 0 && choosed[i] == false)
30 {
31 ans[k] = i;
32
33 for(int j = 0; j < FrameCnt; j++)
34 if(map[i][j])
35 in[j]--;
36
37 choosed[i] = true;
38 TopSort(k + 1);
39 choosed[i] = false;
40
41 for(int j = 0; j < FrameCnt; j++)
42 if(map[i][j])
43 in[j]++;
44 }
45 }
46
47 int main()
48 {
49 while(cin >> n >> m)
50 {
51 memset(in, 0, sizeof(in));
52 memset(pic, false, sizeof(pic));
53 memset(map, false, sizeof(map));
54 memset(choosed, false, sizeof(choosed));
55
56 bool appear[26] = { false };
57
58 for(int i = 0; i < n; i++)
59 for(int j = 0; j < m; j++)
60 {
61 cin >> pic[i][j];
62 if(pic[i][j] == '.')
63 pic[i][j] = -1;
64 else
65 {
66 pic[i][j] -= 'A';
67 appear[pic[i][j]] = true;
68 }
69 }
70
71 FrameCnt = 0;
72 for(int i = 0; i < 26; i++)
73 FrameCnt += appear[i];
74
75 for(int k = 0; k < FrameCnt; k++)
76 {
77 bool x;
78
79 x = false;
80 for(int i = 0; i < n; i++) {
81 for(int j = 0; j < m; j++)
82 if(pic[i][j] == k) {
83 frame[k].ax = i; x = true; break;
84 }
85 if(x) break;
86 }
87
88 x = false;
89 for(int j = 0; j < m; j++) {
90 for(int i = 0; i < n; i++)
91 if(pic[i][j] == k) {
92 frame[k].ay = j; x = true; break;
93 }
94 if(x) break;
95 }
96
97 x = false;
98 for(int i = n - 1; i >= 0; i--) {
99 for(int j = m - 1; j >= 0; j--)
100 if(pic[i][j] == k) {
101 frame[k].bx = i; x = true; break;
102 }
103 if(x) break;
104 }
105
106 x = false;
107 for(int j = m - 1; j >= 0; j--) {
108 for(int i = n - 1; i >= 0; i--)
109 if(pic[i][j] == k) {
110 frame[k].by = j; x = true; break;
111 }
112 if(x) break;
113 }
114 }
115
116 for(int k = 0; k < FrameCnt; k++)
117 {
118 int i, j;
119
120 i = frame[k].ax;
121 for(j = frame[k].ay; j <= frame[k].by; j++)
122 if(pic[i][j] != k)
123 map[k][pic[i][j]] = true;
124
125 i = frame[k].bx;
126 for(j = frame[k].ay; j <= frame[k].by; j++)
127 if(pic[i][j] != k)
128 map[k][pic[i][j]] = true;
129
130 j = frame[k].ay;
131 for(i = frame[k].ax; i <= frame[k].bx; i++)
132 if(pic[i][j] != k)
133 map[k][pic[i][j]] = true;
134
135 j = frame[k].by;
136 for(i = frame[k].ax; i <= frame[k].bx; i++)
137 if(pic[i][j] != k)
138 map[k][pic[i][j]] = true;
139 }
140
141 for(int i = 0; i < FrameCnt; i++)
142 for(int j = 0; j < FrameCnt; j++)
143 if(map[i][j])
144 in[j]++;
145
146 TopSort(0);
147 }
148
149 return 0;
150 }
151
1 /* Accepted 280K 16MS G++ 1675B */
2 #include <iostream>
3
4 using namespace std;
5
6 int n, m, cnt, N;
7 bool visited[26][26], found;
8
9
10 struct { int x, y; } dir[8] = {
11 {-2, -1}, {-2, +1}, {-1, -2}, {-1, +2},
12 {+1, -2}, {+1, +2}, {+2, -1}, {+2, +1}
13 };
14
15 struct {int x, y; } path[26];
16
17 inline bool inside(const int x, const int y)
18 {
19 if(x >= 0 && x < n && y >= 0 && y < m)
20 return true;
21 return false;
22 }
23
24 void search(int x, int y)
25 {
26 if(found)
27 return;
28
29 visited[x][y] = true;
30 path[cnt].x = x, path[cnt].y = y;
31
32 if(cnt == n * m - 1)
33 {
34 found = true;
35 return;
36 }
37
38 for(int i = 0; i < 8; i++)
39 {
40 int xx = x + dir[i].x;
41 int yy = y + dir[i].y;
42 if(inside(xx, yy) && visited[xx][yy] == false)
43 {
44 cnt++;
45 search(xx, yy);
46 cnt--;
47 }
48 }
49
50 visited[x][y] = false;
51 }
52
53 int main()
54 {
55 scanf("%d", &N);
56 for(int i = 1; i <= N; i++)
57 {
58 found = false;
59 memset(visited, false, sizeof(visited));
60
61 scanf("%d %d", &m, &n);
62
63 printf("Scenario #%d:\n", i);
64
65 search(0, 0);
66
67 if(found)
68 for(int i = 0; i < n * m; i++)
69 printf("%c%d", path[i].x + 'A', path[i].y + 1);
70 else
71 printf("impossible");
72
73 printf("\n");
74
75 if(i < N)
76 printf("\n");
77 }
78
79 return 0;
80 }
81
1 /* Accepted 1225 C++ 00:00.00 848K */
2 #include <cctype>
3 #include <iostream>
4
5 using namespace std;
6
7 bool cmp(const string & a, const string & b)
8 {
9 if(isdigit(a[0]) && isdigit(b[0]))
10 {
11 if(a.size() < b.size())
12 return true;
13 if(a.size() > b.size())
14 return false;
15 return a < b;
16 }
17 if(a[0] == '-' && b[0] == '-')
18 {
19 if(a.size() < b.size())
20 return false;
21 if(a.size() > b.size())
22 return true;
23 return a > b;
24 }
25 if(a[0] == '-' && isdigit(b[0]))
26 return true;
27 if(isdigit(a[0]) && b[0] == '-')
28 return false;
29
30 string ta, tb;
31 for(int i = 0; i < a.size(); i++)
32 ta += tolower(a[i]);
33 for(int i = 0; i < b.size(); i++)
34 tb += tolower(b[i]);
35
36 return ta < tb;
37 }
38
39 int main()
40 {
41 int n;
42 bool word[100];
43 string s[100];
44
45 while(true)
46 {
47 cin >> s[0];
48 if(s[0] == ".")
49 break;
50
51 if(isdigit(s[0][0]) || s[0][0] == '-')
52 word[0] = false;
53 else
54 word[0] = true;
55 s[0] = s[0].substr(0, s[0].size() - 1);
56
57 n = 1;
58 while(true)
59 {
60 if(getchar() == '\n')
61 break;
62
63 cin >> s[n];
64
65 if(isdigit(s[n][0]) || s[n][0] == '-')
66 word[n] = false;
67 else
68 word[n] = true;
69
70 s[n] = s[n].substr(0, s[n].size() - 1);
71
72 n++;
73 }
74
75 sort(s, s + n, cmp);
76
77 bool x[100] = { false };
78 for(int i = 0; i < n; i++)
79 {
80 if(word[i])
81 for(int j = 0; j < n; j++)
82 {
83 if(x[j] == false && isalpha(s[j][0]))
84 {
85 cout << s[j]; x[j] = true; break;
86 }
87 }
88 else
89 for(int j = 0; j < n; j++)
90 if(x[j] == false && (s[j][0] == '-' || isdigit(s[j][0])))
91 {
92 cout << s[j]; x[j] = true; break;
93 }
94 if(i == n - 1)
95 cout << '.' << endl;
96 else
97 cout << ',' << ' ';
98 }
99 }
100
101 return 0;
102 }
103
1 /* Accepted 1298 C++ 00:00.01 1824K */
2 #include <queue>
3 #include <iostream>
4
5 using namespace std;
6
7 int n, m;
8 int map[500][500];
9
10 void spfa(int s, int d[])
11 {
12 for(int i = 1; i <= n; i++)
13 d[i] = INT_MAX;
14 d[1] = 0;
15
16 queue <int> q;
17 q.push(1);
18
19 while(q.empty() == false)
20 {
21 int cur = q.front(); q.pop();
22 for(int i = 1; i <= n; i++)
23 if(cur != i && map[cur][i] != INT_MAX && d[cur] + map[cur][i] < d[i])
24 {
25 d[i] = d[cur] + map[cur][i];
26 q.push(i);
27 }
28 }
29 }
30
31 int main()
32 {
33 cout.setf(ios_base::showpoint);
34 cout.setf(ios_base::fixed);
35 cout.precision(1);
36
37 int cnt = 1;
38 while(cin >> n >> m)
39 {
40 if(n == 0 && m == 0)
41 break;
42
43 for(int i = 1; i <= n; i++)
44 for(int j = 1; j <= n; j++)
45 map[i][j] = INT_MAX;
46
47 int s, t, l;
48 for(int i = 0; i < m; i++)
49 {
50 cin >> s >> t >> l;
51 map[s][t] = map[t][s] = l;
52 }
53
54 int d[500];
55 spfa(1, d);
56
57 double ans = 0; int idx = 1;
58 for(int i = 2; i <= n; i++)
59 if(d[i] > ans)
60 {
61 ans = d[i];
62 idx = i;
63 }
64 int x = 0, y = 0;
65 for(int i = 1; i <= n; i++)
66 for(int j = i + 1; j <= n; j++)
67 if(map[i][j] != INT_MAX)
68 {
69 double k = (map[i][j] - abs(d[i] - d[j])) * 0.5 + max(d[i], d[j]);
70 if(ans < k)
71 {
72 ans = k;
73 x = i, y = j;
74 }
75 }
76
77 cout << "System #" << cnt++ << endl
78 << "The last domino falls after " << ans << " seconds, ";
79 if(x == 0 && y == 0)
80 cout << "at key domino " << idx << '.' << endl;
81 else
82 cout << "between key dominoes " << x << " and " << y << '.' << endl;
83 cout << endl;
84 }
85
86 return 0;
87 }
88
1 /* Accepted 1563 C++ 00:00.01 920K */
2 #include <iostream>
3
4 using namespace std;
5
6 int main()
7 {
8 int c, n;
9 struct { int need, price; } pearl[101];
10
11 cin >> c;
12 while(c--)
13 {
14 cin >> n;
15 for(int i = 1; i <= n; i++)
16 cin >> pearl[i].need >> pearl[i].price;
17
18 int sum[101][101] = { 0 };
19 for(int i = 1; i <= n; i++)
20 for(int j = i; j <= n; j++)
21 sum[i][j] = sum[i][j - 1] + pearl[j].need;
22
23 int opt[101][101] = { 0 };
24
25 for(int i = 1; i <= n; i++)
26 opt[1][i] = (sum[1][i] + 10) * pearl[i].price;
27
28 for(int i = 2; i <= n; i++)
29 for(int j = 1; j <= n; j++)
30 {
31 opt[i][j] = INT_MAX;
32 for(int k = 1; k <= j; k++)
33 opt[i][j] <?= opt[i - 1][k - 1] + (sum[k][j] + 10) * pearl[j].price;
34 }
35 cout << opt[n][n] << endl;
36 }
37
38 return 0;
39 }
40
|