|
|
1 /* Accepted 1088 C++ 00:03.46 836K */
2 #include <iostream>
3
4 using namespace std;
5
6 int main()
7 {
8 int n;
9 while((cin >> n) && n)
10 {
11 int k = 2;
12 while(1)
13 {
14 int now = 0, left = n - 2;
15 bool x[200] = {1}, flag = 0;
16 while(1)
17 {
18 int i = 0;
19 while(i < k)
20 {
21 if(x[(now + 1) % n] == 0)
22 i++;
23 now = (now + 1) % n;
24 }
25 left--;
26 x[now] = 1;
27 if(now == 1)
28 break;
29 if(left == 0)
30 {
31 cout << k << endl;
32 flag = 1;
33 break;
34 }
35 }
36 if(flag)
37 break;
38 k++;
39 }
40 }
41
42 return 0;
43 }
44
1 /* Accepted 1108 C++ 00:00.02 876K */
2 #include <stdlib.h>
3 #include <iostream>
4
5 using namespace std;
6
7 struct Mice { int w, s, num; } mice[1001];
8
9 void output(int path[], int pos)
10 {
11 if(pos == 0)
12 return;
13 output(path, path[pos]);
14 cout << mice[pos].num << endl;
15 }
16
17 int cmp(const void * a, const void * b)
18 {
19 Mice* c = (Mice*) a;
20 Mice* d = (Mice*) b;
21 if(c -> w == d -> w)
22 return d -> s - c -> s;
23 return c -> w - d -> w;
24 }
25
26 int main()
27 {
28 int n = 1;
29 while(cin >> mice[n].w >> mice[n].s)
30 {
31 mice[n].num = n;
32 n++;
33 }
34 qsort(mice + 1, n, sizeof(Mice), cmp);
35
36 int opt[1001] = {0, 1}, path[1001] = {0};
37
38 for(int i = 2; i <= n; i++)
39 {
40 for(int j = 1; j < i; j++)
41 if(mice[i].w > mice[j].w && mice[i].s < mice[j].s)
42 if(opt[i] < opt[j])
43 {
44 opt[i] = opt[j];
45 path[i] = j;
46 }
47 opt[i]++;
48 }
49
50 int max = 0, pos;
51 for(int i = 1; i <= n; i++)
52 if(opt[i] > max)
53 {
54 max = opt[i];
55 pos = i;
56 }
57 cout << max << endl;
58 output(path, pos);
59
60 return 0;
61 }
62
1 /* Accepted 1074 C++ 00:00.07 876K */
2 #include <iostream>
3
4 using namespace std;
5
6 int n;
7 int A[101][101];
8
9 int maxSubList(int b[], int n)
10 {
11 int f[101] = {0}, max = 0;
12 for(int i = 1; i <= n; i++)
13 {
14 f[i] = b[i];
15 f[i] >?= f[i - 1] + b[i];
16 max >?= f[i];
17 }
18 return max;
19 }
20
21 int maxSubMatrix()
22 {
23 int max = 0;
24 for(int i = 1; i <= n; i++)
25 {
26 int b[101] = {0};
27 for(int j = i; j <= n; j++)
28 {
29 for(int k = 1; k <= n; k++)
30 b[k] += A[j][k];
31 max >?= maxSubList(b, n);
32 }
33 }
34 return max;
35 }
36
37 int main()
38 {
39 cin >> n;
40 for(int i = 1; i <= n; i++)
41 for(int j = 1; j <= n; j++)
42 cin >> A[i][j];
43 cout << maxSubMatrix() << endl;
44
45 return 0;
46 }
47
1 /* Accepted 1051 C++ 00:00.01 840K */
2 #include <iostream>
3
4 using namespace std;
5
6 int main()
7 {
8 int n, m, d[16], f[20][20];
9 cin >> n;
10 while(n--)
11 {
12 cin >> m;
13 for(int i = 0; i <= 15; i++)
14 cin >> d[i];
15 for(int i = 0; i < 20; i++)
16 for(int j = 0; j < 20; j++)
17 cin >> f[i][j];
18
19 while(m--)
20 {
21 int g[20][20];
22
23 for(int i = 0; i < 20; i++)
24 for(int j = 0; j < 20; j++)
25 {
26 int k = f[i][j];
27 if(i - 1 >= 0) k += f[i - 1][j];
28 if(i + 1 < 20) k += f[i + 1][j];
29 if(j - 1 >= 0) k += f[i][j - 1];
30 if(j + 1 < 20) k += f[i][j + 1];
31
32 g[i][j] = f[i][j] + d[k];
33 if(g[i][j] < 0) g[i][j] = 0;
34 if(g[i][j] > 3) g[i][j] = 3;
35 }
36
37 for(int i = 0; i < 20; i++)
38 for(int j = 0; j < 20; j++)
39 f[i][j] = g[i][j];
40 }
41 for(int i = 0; i < 20; i++)
42 {
43 for(int j = 0; j < 20; j++)
44 switch(f[i][j])
45 {
46 case 0 : cout << '.'; break;
47 case 1 : cout << '!'; break;
48 case 2 : cout << 'X'; break;
49 case 3 : cout << '#'; break;
50 }
51 cout << endl;
52 }
53 if(n)
54 cout << endl;
55 }
56
57 return 0;
58 }
59
1 /* Accepted 1094 C++ 00:00.00 844K */
2 #include <map>
3 #include <stack>
4 #include <string>
5 #include <iostream>
6
7 using namespace std;
8
9 struct Matrix { int r, c; };
10
11 int main()
12 {
13 int n;
14 char name;
15 map<char, Matrix> matrix;
16
17 cin >> n;
18 for(int i = 0; i < n; i++)
19 {
20 cin >> name;
21 cin >> matrix[name].r >> matrix[name].c;
22 }
23
24 string exp;
25 while(cin >> exp)
26 {
27 if(exp.size() == 1)
28 {
29 cout << 0 << endl;
30 continue;
31 }
32
33 int i, count = 0;
34 stack<Matrix> mst;
35 for(i = 0; i < exp.size(); i++)
36 {
37 if(exp[i] == '(')
38 continue;
39 if(exp[i] == ')')
40 {
41 Matrix b = mst.top(); mst.pop();
42 Matrix a = mst.top(); mst.pop();
43 if(a.c != b.r)
44 {
45 cout << "error" << endl;
46 break;
47 }
48 count += a.r * b.r * b.c;
49 Matrix tmp = {a.r, b.c};
50 mst.push(tmp);
51 }
52 else
53 mst.push(matrix[exp[i]]);
54 }
55 if(i == exp.size())
56 cout << count << endl;
57 }
58
59 return 0;
60 }
61
1 /* Accepted 1093 C++ 00:00.01 848K */
2 #include <stdlib.h>
3 #include <iostream>
4
5 using namespace std;
6
7 struct Rect { int a, b, height; } rect[100];
8
9 int cmp(const void * a, const void * b)
10 {
11 Rect * c = (Rect*)(a);
12 Rect * d = (Rect*)(b);
13 if(c -> a == d -> a)
14 return c -> b - d -> b;
15 return c -> a - d -> a;
16 }
17
18 void swap(int & a, int & b)
19 {
20 a = a ^ b;
21 b = a ^ b;
22 a = a ^ b;
23 }
24
25 int main()
26 {
27 int Case = 0, n;
28 while((cin >> n) && n)
29 {
30 int x, y, z, count = 0;
31 for(int i = 0; i < n; i++)
32 {
33 cin >> x >> y >> z;
34 count++; rect[count].a = x; rect[count].b = y; rect[count].height = z;
35 count++; rect[count].a = x; rect[count].b = z; rect[count].height = y;
36 count++; rect[count].a = y; rect[count].b = z; rect[count].height = x;
37 }
38
39 for(int i = 1; i <= count; i++)
40 if(rect[i].a > rect[i].b)
41 swap(rect[i].a, rect[i].b);
42
43 qsort(rect + 1, count, sizeof(Rect), cmp);
44
45 int opt[100] = {0};
46 opt[1] = rect[1].height;
47 for(int i = 2; i <= count; i++)
48 {
49 for(int j = 1; j < i; j++)
50 if(rect[i].a > rect[j].a && rect[i].b > rect[j].b)
51 opt[i] >?= opt[j];
52 opt[i] += rect[i].height;
53 }
54
55 int max = 0;
56 for(int i = 1; i <= count; i++)
57 max >?= opt[i];
58 cout << "Case " << ++Case << ": maximum height = " << max << endl;
59 }
60
61 return 0;
62 }
63
1 /* Accepted 1092 C++ 00:00.34 852K */
2 #include <string>
3 #include <iostream>
4
5 using namespace std;
6
7 int main()
8 {
9 int n, m, cases = 0;
10 string currency[30];
11 while((cin >> n) && n) {
12 for(int i = 0; i < n; i++)
13 cin >> currency[i];
14 cin >> m;
15
16 double f[30][30] = {0};
17 for(int i = 0; i < n; i++)
18 f[i][i] = 1.00;
19
20 string s, t;
21 double exchangeRate;
22 for(int k = 0; k < m; k++) {
23 cin >> s >> exchangeRate >> t;
24 int i, j;
25 for(i = 0; i < n; i++)
26 if(currency[i] == s)
27 break;
28 for(j = 0; j < n; j++)
29 if(currency[j] == t)
30 break;
31 f[i][j] = exchangeRate;
32 }
33
34 for(int k = 0; k < n; k++)
35 for(int i = 0; i < n; i++)
36 for(int j = 0; j < n; j++)
37 f[i][j] >?= f[i][k] * f[k][j];
38
39 bool Yes = 0;
40 for(int i = 0; i < n; i++)
41 if(f[i][i] > 1.00) {
42 Yes = 1;
43 break;
44 }
45 cases++;
46 cout << "Case " << cases << ": ";
47 if(Yes)
48 cout << "Yes" << endl;
49 else
50 cout << "No" << endl;
51 }
52 return 0;
53 }
54
1 /* Accepted 1037 C++ 00:00.48 848K */
2 #include <math.h>
3 #include <iostream>
4
5 using namespace std;
6
7 int main()
8 {
9 cout.setf(ios_base::showpoint);
10 cout.setf(ios_base::fixed);
11 cout.precision(2);
12
13 int n, m, k;
14
15 cin >> k;
16 for(int i = 1; i <= k; i++)
17 {
18 cin >> n >> m;
19 cout << "Scenario #" << i << ':' << endl;
20 if(n % 2 && m % 2)
21 cout << (n * m - 1 + pow(2, 0.5)) << endl;
22 else
23 cout << double(n * m) << endl;
24 cout << endl;
25 }
26
27 return 0;
28 }
29
1 /* Accepted 1013 C++ 00:03.25 2804K */
2 #include <stdio.h>
3 #include <string.h>
4 #include <iostream>
5
6 using namespace std;
7
8 int n;
9 int w1, s1, d1;
10 int w2, s2, d2;
11 int w3, s3, d3;
12 int c1, c2, c3, d4;
13 int opt[2][501][501];
14 struct { int w, s; } caravan[101];
15
16 int put(int k, int i, int j)
17 {
18 int w = (caravan[k].w - i * w1 - j * w2) / w3;
19 int s = (caravan[k].s - i * s1 - j * s2) / s3;
20 if(w <= 0 || s <= 0) return 0;
21 return (w < s ? w : s);
22 }
23
24 int main()
25 {
26 int cs = 0;
27 while(cin >> n)
28 {
29 if(n == 0)
30 break;
31 cin >> w1 >> s1 >> d1;
32 cin >> w2 >> s2 >> d2;
33 cin >> w3 >> s3 >> d3;
34 cin >> c1 >> c2 >> c3 >> d4;
35 for(int i = 1; i <= n; i++)
36 cin >> caravan[i].w >> caravan[i].s;
37
38 memset(opt, 0, sizeof(opt));
39
40 opt[0][0][0] = 0;
41 int mx = 0, my = 0;
42 for(int k = 1; k <= n; k++)
43 {
44 memset(opt[1], 0XFF, sizeof(opt[1]));
45 int mmx = mx, mmy = my;
46 for(int i = 0; i <= mx; i++)
47 for(int j = 0; j <= my; j++)
48 {
49 if(opt[0][i][j] == -1)
50 continue;
51 for(int p = 0; p * w1 <= caravan[k].w && p * s1 <= caravan[k].s; p++)
52 for(int q = 0; p * w1 + q * w2 <= caravan[k].w && p * s1 + q * s2 <= caravan[k].s; q++)
53 {
54 opt[1][i + p][j + q] >?= (opt[0][i][j] + put(k, p, q));
55 mmx >?= i + p;
56 mmy >?= j + q;
57 }
58 }
59 mx = mmx;
60 my = mmy;
61 memcpy(opt[0], opt[1], sizeof(opt[1]));
62 }
63 int max = 0;
64 for(int i = 0; i <= mx; i++)
65 for(int j = 0; j <= my; j++)
66 if(opt[0][i][j] >= 0)
67 {
68 if(d4 > c1 * d1 + c2 * d2 + c3 * d3)
69 {
70 int t1 = i, t2 = j, t3 = opt[0][i][j], cur = 0;
71 while(t1 - c1 >= 0 && t2 - c2 >= 0 && t3 - c3 >= 0)
72 {
73 t1 -= c1;
74 t2 -= c2;
75 t3 -= c3;
76 cur += d4;
77 }
78 cur += (t1 * d1 + t2 * d2 + t3 * d3);
79 max >?= cur;
80 }
81 else
82 max >?= (i * d1 + j * d2 + opt[0][i][j] * d3);
83 }
84 if(cs++)
85 cout << endl;
86 cout << "Case " << cs << ':' << ' ' << max << endl;
87 }
88 return 0;
89 }
90
1 /* Accepted 1019 C++ 00:00.04 852K */
2 #include <iostream>
3
4 using namespace std;
5
6 int n, m, p;
7 bool map[101][101];
8
9 struct
10 {
11 int s, t;
12 char direction;
13 }trip[100];
14
15 bool finish;
16
17 void swap(int & a, int & b)
18 {
19 a = a ^ b;
20 b = a ^ b;
21 a = a ^ b;
22 }
23
24 inline bool canGo(int sx, int sy, int tx, int ty)
25 {
26 if(tx >= 1 && tx <= n && ty >= 1 && ty <= m);
27 else
28 return 0;
29 if(sx > tx)
30 swap(sx, tx);
31 if(sy > ty)
32 swap(sy, ty);
33 for(int i = sx; i <= tx; i++)
34 for(int j = sy; j <= ty; j++)
35 if(map[i][j])
36 return 0;
37 return 1;
38 }
39
40 void search(int x, int y, int k)
41 {
42 if(finish)
43 return;
44 if(k > p)
45 {
46 finish = 1;
47 return;
48 }
49 if(trip[k].direction == 'U')
50 {
51 for(int i = trip[k].s; i <= trip[k].t; i++)
52 if(canGo(x - 1, y, x - i, y))
53 search(x - i, y, k + 1);
54 return;
55 }
56 if(trip[k].direction == 'D')
57 {
58 for(int i = trip[k].s; i <= trip[k].t; i++)
59 if(canGo(x + 1, y, x + i, y))
60 search(x + i, y, k + 1);
61 return;
62 }
63 if(trip[k].direction == 'L')
64 {
65 for(int j = trip[k].s; j <= trip[k].t; j++)
66 if(canGo(x, y - 1, x, y - j))
67 search(x, y - j, k + 1);
68 return;
69 }
70 if(trip[k].direction == 'R')
71 {
72 for(int j = trip[k].s; j <= trip[k].t; j++)
73 if(canGo(x, y + 1, x, y + j))
74 search(x, y + j, k + 1);
75 return;
76 }
77 }
78
79 int main()
80 {
81 int N;
82 int s, t;
83 char direction;
84
85 cin >> N;
86 while(N--)
87 {
88 cin >> n >> m;
89 for(int i = 1; i <= n; i++)
90 for(int j = 1; j <= m; j++)
91 cin >> map[i][j];
92 p = 0;
93 while(1)
94 {
95 cin >> s >> t;
96 if(s == 0 && t == 0)
97 break;
98 p++;
99 trip[p].s = s;
100 trip[p].t = t;
101 cin >> trip[p].direction;
102 }
103 int ans = 0;
104 for(int i = 1; i <= n; i++)
105 for(int j = 1; j <= m; j++)
106 if(map[i][j] == 0)
107 {
108 finish = 0;
109 search(i, j, 1);
110 ans += finish;
111 }
112 cout << ans << endl;
113 }
114
115 return 0;
116 }
117
|