|
|
1 /* Accepted 1913 C++ 00:00.00 836K */
2 #include <string>
3 #include <iostream>
4
5 using namespace std;
6
7 void swap(int & a, int & b)
8 {
9 a = a ^ b;
10 b = a ^ b;
11 a = a ^ b;
12 }
13
14 int main()
15 {
16 int a, b;
17 string player[2] = {"Stan", "Ollie"};
18 while(cin >> a >> b)
19 {
20 if(a == 0 && b == 0)
21 break;
22
23 int curPlayer = 0;
24 while(1)
25 {
26 if(a < b)
27 swap(a, b);
28
29 if(a - b >= b)
30 break;
31
32 a = a % b;
33 if(a == 0 || b == 0)
34 break;
35
36 curPlayer = (++curPlayer) % 2;
37 }
38 cout << player[curPlayer] << ' ' << "wins" << endl;
39 }
40
41 return 0;
42 }
43
1 /* Accepted 1558 C++ 00:00.01 904K */
2 #include <limits.h>
3 #include <string.h>
4 #include <iostream>
5
6 using namespace std;
7
8 int N, x[10], opt[2008];
9
10 int search(int n)
11 {
12 if(n == 0) return 0;
13 if(opt[n]) return opt[n];
14
15 opt[n] = INT_MAX;
16 for(int i = 1; i <= 6; i++)
17 if(n - x[i] >= 0)
18 opt[n] <?= search(n - x[i]) + 1;
19 for(int i = 1; i <= 6; i++)
20 if(n + x[i] <= 2000)
21 opt[n] <?= search(n + x[i]) + 1;
22 return opt[n];
23 }
24
25 int main()
26 {
27 cout.setf(ios_base::showpoint);
28 cout.setf(ios_base::fixed);
29 cout.precision(2);
30
31 cin >> N;
32 while(N--)
33 {
34 memset(x, 0, sizeof(x));
35 memset(opt, 0, sizeof(opt));
36
37 for(int i = 1; i <= 6; i++)
38 cin >> x[i];
39
40 int sum = 0, max = 0;
41 for(int i = 1; i <= 100; i++)
42 {
43 sum += search(i);
44 max >?= search(i);
45 }
46
47 cout << double(sum) / 100 << ' ' << max << endl;
48 }
49
50 return 0;
51 }
52
1 /* Accepted 1027 C++ 00:00.01 892K */
2 #include <cstdio>
3 #include <cstring>
4 #include <iostream>
5
6 using namespace std;
7
8 int score(char a, char b)
9 {
10 if(a == b) return 5;
11 if(a == 'A')
12 {
13 if(b == 'C' || b == 'T')
14 return -1;
15 if(b == 'G') return -2;
16 if(b == ' ') return -3;
17 }
18 if(a == 'C')
19 {
20 if(b == 'A') return -1;
21 if(b == 'G') return -3;
22 if(b == 'T') return -2;
23 if(b == ' ') return -4;
24 }
25 if(a == 'G')
26 {
27 if(b == 'A' || b == 'T' || b == ' ')
28 return -2;
29 if(b == 'C') return -3;
30 }
31 if(a == 'T')
32 {
33 if(b == 'A' || b == ' ')
34 return -1;
35 if(b == 'C' || b == 'G')
36 return -2;
37 }
38 if(a == ' ')
39 {
40 if(b == 'A') return -3;
41 if(b == 'C') return -4;
42 if(b == 'G') return -2;
43 if(b == 'T') return -1;
44 }
45 }
46
47 int main()
48 {
49 int n, la, lb, opt[120][120];
50 char sa[120], sb[120];
51
52 scanf("%d", &n);
53 while(n--)
54 {
55 scanf("%d %s", &la, sa + 1);
56 scanf("%d %s", &lb, sb + 1);
57
58 opt[0][0] = 0;
59 for(int i = 1; i <= la; i++)
60 opt[i][0] = opt[i - 1][0] + score(sa[i], ' ');
61 for(int j = 1; j <= lb; j++)
62 opt[0][j] = opt[0][j - 1] + score(' ', sb[j]);
63
64 for(int i = 1; i <= la; i++)
65 for(int j = 1; j <= lb; j++)
66 {
67 opt[i][j] = opt[i - 1][j - 1] + score(sa[i], sb[j]);
68 opt[i][j] >?= opt[i][j - 1] + score(' ', sb[j]);
69 opt[i][j] >?= opt[i - 1][j] + score(sa[i], ' ');
70 }
71
72 printf("%d\n", opt[la][lb]);
73 }
74
75 return 0;
76 }
77
1 /* Accepted 1666 C++ 00:00.00 872K */
2 #include <iostream>
3
4 using namespace std;
5
6 int main()
7 {
8 int count[20][500] = {0};
9
10 for(int i = 0; i <= 17; i++)
11 count[i][0] = 1;
12
13 for(int i = 1; i <= 17; i++)
14 for(int j = 1; j <= 300; j++)
15 for(int k = 0; k * i * i <= j; k++)
16 if(count[i - 1][j - k * i * i])
17 count[i][j] += count[i - 1][j - k * i * i];
18 int n;
19 while((cin >> n) && n)
20 cout << count[17][n] << endl;
21
22 return 0;
23 }
24
1 /* Accepted 1101 C++ 00:00.22 848K */
2 #include <stdlib.h>
3 #include <iostream>
4
5 using namespace std;
6
7 int cmp(const void * a, const void * b)
8 {
9 return *(int*)a - *(int*)b;
10 }
11
12 int n;
13 int x[1000];
14
15 void solve()
16 {
17 for(int k = n - 1; k >= 0; k--)
18 for(int i = 0; i < n; i++)
19 for(int j = i + 1; j < n; j++)
20 if(i != k && j != k)
21 {
22 int left = x[k] - (x[i] + x[j]);
23
24 if(left == x[i] || left == x[j] || left == x[k])
25 continue;
26
27 if(bsearch(&left, x, n, sizeof(int), cmp))
28 {
29 cout << x[k] << endl;
30 return;
31 }
32 }
33 cout << "no solution" << endl;
34 }
35
36 int main()
37 {
38 while((cin >> n) && n)
39 {
40 for(int i = 0; i < n; i++)
41 cin >> x[i];
42
43 qsort(x, n, sizeof(int), cmp);
44
45 solve();
46 }
47
48 return 0;
49 }
50
1 /* Accepted 2807 C++ 00:00.00 832K */
2 #include <iostream>
3
4 using namespace std;
5
6 int main()
7 {
8 int n, m, sum, t;
9 cin >> n;
10 while(n--)
11 {
12 sum = 0;
13 cin >> m;
14 for(int i = 0; i < m; i++)
15 {
16 cin >> t;
17 sum = sum + t;
18 }
19 cout << (sum - m + 1) << endl;
20 }
21
22 return 0;
23 }
24
1 /* Accepted 1128 C++ 00:00.02 848K */
2 #include <stdio.h>
3 #include <iostream>
4
5 using namespace std;
6
7 template <typename T>
8 class queue
9 {
10 private:
11 int len;
12 struct node
13 {
14 T item;
15 node *next;
16 }*front, *rear;
17 public:
18 queue()
19 {
20 len = 0;
21 front = rear = NULL;
22 }
23 int size()
24 {
25 return len;
26 }
27 bool empty()
28 {
29 return len == 0;
30 }
31 void push(const T & item)
32 {
33 node *p = new node;
34 p -> item = item;
35 p -> next = NULL;
36 if(empty())
37 front = rear = p;
38 else
39 {
40 rear -> next = p;
41 rear = p;
42 }
43 len++;
44 }
45 void pop(T & item)
46 {
47 node *p = front;
48 if(len == 1)
49 front = rear = NULL;
50 else
51 front = front -> next;
52 item = p -> item;
53 delete p;
54 len--;
55 }
56 };
57
58 struct Rect
59 {
60 double x1, y1, x2, y2;
61 };
62
63 queue<Rect> rects;
64
65 inline void addRect(double x1, double y1, double x2, double y2)
66 {
67 Rect tmp = {x1, y1, x2, y2};
68 rects.push(tmp);
69 }
70
71 int main()
72 {
73 //freopen("p1128.in", "r", stdin);
74
75 cout.setf(ios_base::showpoint);
76 cout.setf(ios_base::fixed);
77 cout.precision(2);
78
79 int n, m = 1;
80 double x1, y1, x2, y2;
81 while((cin >> n) && n)
82 {
83 cin >> x1 >> y1 >> x2 >> y2;
84
85 addRect(x1, y1, x2, y2);
86
87 Rect tmp;
88 for(int i = 2; i <= n; i++)
89 {
90 cin >> x1 >> y1 >> x2 >> y2;
91
92 int k = rects.size();
93 while(k--)
94 {
95 rects.pop(tmp);
96
97 if(x1 > tmp.x2 || x2 < tmp.x1 || y1 > tmp.y2 || y2 < tmp.y1)
98 {
99 rects.push(tmp);
100 continue;
101 }
102
103 if(x1 >= tmp.x1 && x2 <= tmp.x2 && y1 >= tmp.y1 && y2 <= tmp.y2)
104 continue;
105
106 if(x1 > tmp.x1)
107 {
108 addRect(tmp.x1, tmp.y1 , x1, tmp.y2);
109 tmp.x1 = x1;
110 }
111 if(x2 < tmp.x2)
112 {
113 addRect(x2, tmp.y1, tmp.x2, tmp.y2);
114 tmp.x2 = x2;
115 }
116 if(y1 > tmp.y1)
117 addRect(tmp.x1, tmp.y1, tmp.x2, y1);
118 if(y2 < tmp.y2)
119 addRect(tmp.x1, y2, tmp.x2, tmp.y2);
120 }
121 addRect(x1, y1, x2, y2);
122 }
123 double ans = 0.00000000;
124 while(rects.empty() == false)
125 {
126 rects.pop(tmp);
127 ans += (tmp.x2 - tmp.x1) * (tmp.y2 - tmp.y1);
128 }
129 cout << "Test case #" << m++ << endl;
130 cout << "Total explored area: ";
131 cout << ans << endl;
132 cout << endl;
133 }
134
135 return 0;
136 }
137
1 /* Accepted 1006 C++ 00:00.01 836K */
2 #include <stdio.h>
3 #include <string.h>
4 #include <iostream>
5
6 using namespace std;
7
8 int mod(int a, int b)
9 {
10 while(a < 0)
11 a += b;
12 return a % b;
13 }
14
15 int main()
16 {
17 //freopen("p1006.in", "r", stdin);
18
19 int k;
20 char s[100], c[100];
21 while(scanf("%d %s", &k, s) == 2)
22 {
23 int n = strlen(s);
24 for(int i = 0; i < n; i++)
25 {
26 switch(s[i])
27 {
28 case '_' : s[i] = 0; break;
29 case '.' : s[i] = 27; break;
30 default : s[i] = s[i] - 'a' + 1;
31 }
32 c[k * i % n] = (s[i] + i) % 28;
33 }
34
35 for(int i = 0; i < n; i++)
36 switch(c[i])
37 {
38 case 0 : c[i] = '_'; break;
39 case 27 : c[i] = '.'; break;
40 default : c[i] = 'a' + c[i] - 1;
41 }
42
43 for(int i = 0; i < n; i++)
44 cout << c[i];
45 cout << endl;
46 }
47
48 return 0;
49 }
50
1 /* Accepted 1005 C++ 00:00.01 2836K */
2 #include <stdio.h>
3 #include <string.h>
4 #include <iostream>
5
6 using namespace std;
7
8 int min(int a, int b)
9 {
10 return a < b ? a : b;
11 }
12
13 struct
14 {
15 int a, b, last, operation;
16 }queue[65535];
17 int front, rear;
18 bool isRepeat[1001][1001];
19
20 void outPut(int i)
21 {
22 if(i == 0)
23 return;
24 outPut(queue[i].last);
25 switch(queue[i].operation)
26 {
27 case 1 : cout << "fill A" << endl; break;
28 case 2 : cout << "fill B" << endl; break;
29 case 3 : cout << "empty A" << endl; break;
30 case 4 : cout << "empty B" << endl; break;
31 case 5 : cout << "pour A B" << endl; break;
32 case 6 : cout << "pour B A" << endl; break;
33 }
34 }
35
36 int main()
37 {
38 //freopen("p1005.in", "r", stdin);
39
40 int A, B, N;
41
42 while(cin >> A >> B >> N)
43 {
44 memset(isRepeat, 0, sizeof(isRepeat));
45 front = -1, rear = 0;
46 queue[0].a = queue[0].b = 0;
47 queue[0].last = queue[0].operation = 0;
48 while(front < rear)
49 {
50 front++;
51 int a = queue[front].a;
52 int b = queue[front].b;
53
54 if(b == N)
55 {
56 outPut(front);
57 cout << "success" << endl;
58 break;
59 }
60
61 //fill A
62 if(a != A)
63 {
64 rear++;
65 queue[rear].a = A;
66 queue[rear].b = b;
67 queue[rear].last = front;
68 queue[rear].operation = 1;
69 if(isRepeat[queue[rear].a][queue[rear].b])
70 rear--;
71 else
72 isRepeat[queue[rear].a][queue[rear].b] = true;
73 }
74
75 //fill B
76 if(b != B)
77 {
78 rear++;
79 queue[rear].a = a;
80 queue[rear].b = B;
81 queue[rear].last = front;
82 queue[rear].operation = 2;
83 if(isRepeat[queue[rear].a][queue[rear].b])
84 rear--;
85 else
86 isRepeat[queue[rear].a][queue[rear].b] = true;
87 }
88
89 //empty A
90 if(a != 0)
91 {
92 rear++;
93 queue[rear].a = 0;
94 queue[rear].b = b;
95 queue[rear].last = front;
96 queue[rear].operation = 3;
97 if(isRepeat[queue[rear].a][queue[rear].b])
98 rear--;
99 else
100 isRepeat[queue[rear].a][queue[rear].b] = true;
101 }
102
103 //empty B
104 if(b != 0)
105 {
106 rear++;
107 queue[rear].a = a;
108 queue[rear].b = 0;
109 queue[rear].last = front;
110 queue[rear].operation = 4;
111 if(isRepeat[queue[rear].a][queue[rear].b])
112 rear--;
113 else
114 isRepeat[queue[rear].a][queue[rear].b] = true;
115 }
116
117 //pour A to B
118 rear++;
119 queue[rear].a = a - min(a, B - b);
120 queue[rear].b = b + min(a, B - b);
121 queue[rear].last = front;
122 queue[rear].operation = 5;
123 if(isRepeat[queue[rear].a][queue[rear].b])
124 rear--;
125 else
126 isRepeat[queue[rear].a][queue[rear].b] = true;
127
128 //pour B to A
129 rear++;
130 queue[rear].a = a + min(b, A - a);
131 queue[rear].b = b - min(b, A - a);
132 queue[rear].last = front;
133 queue[rear].operation = 6;
134 if(isRepeat[queue[rear].a][queue[rear].b])
135 rear--;
136 else
137 isRepeat[queue[rear].a][queue[rear].b] = true;
138 }
139 }
140
141 return 0;
142 }
143
144
1 /* Accepted 1002 C++ 00:00.01 840K */
2 #include <iostream>
3
4 using namespace std;
5
6 int n, best;
7 char map[5][5];
8
9 bool canPut(int x, int y)
10 {
11 if(map[x][y] != '.')
12 return false;
13 for(int i = x - 1; i >= 0; i--)
14 {
15 if(map[i][y] == 'X') break;
16 if(map[i][y] == 'O') return false;
17 }
18 for(int i = x + 1; i < n; i++)
19 {
20 if(map[i][y] == 'X') break;
21 if(map[i][y] == 'O') return false;
22 }
23 for(int j = y - 1; j >= 0; j--)
24 {
25 if(map[x][j] == 'X') break;
26 if(map[x][j] == 'O') return false;
27 }
28 for(int j = y + 1; j < n; j++)
29 {
30 if(map[x][y] == 'X') break;
31 if(map[x][j] == 'O') return false;
32 }
33 return true;
34 }
35
36 bool donePut()
37 {
38 for(int i = 0; i < n; i++)
39 for(int j = 0; j < n; j++)
40 if(canPut(i, j))
41 return false;
42 return true;
43 }
44
45 void search(int m)
46 {
47 if(donePut())
48 {
49 best >?= m;
50 return;
51 }
52 for(int i = 0; i < n; i++)
53 for(int j = 0; j < n; j++)
54 if(canPut(i, j))
55 {
56 map[i][j] = 'O';
57 search(m + 1);
58 map[i][j] = '.';
59 }
60 }
61
62 int main()
63 {
64 while((cin >> n) && n)
65 {
66 for(int i = 0; i < n; i++)
67 for(int j = 0; j < n; j++)
68 switch(cin.get())
69 {
70 case '.' : map[i][j] = '.'; break;
71 case 'X' : map[i][j] = 'X'; break;
72 default : j--;
73 }
74 best = 0;
75 search(0);
76 cout << best << endl;
77 }
78
79 return 0;
80 }
81
|