|
|
1 #include <iostream>
2
3 using namespace std;
4
5 int main()
6 {
7 freopen("hamming.in", "r", stdin);
8 freopen("hamming.out", "w", stdout);
9
10 int N, B, D, x[64] = { 0 };
11
12 cin >> N >> B >> D;
13
14 x[0] = 0;
15 for (int k = 1; k < N; k++)
16 for (int i = x[k - 1] + 1; i <= (1 << B) - 1; i++)
17 {
18 int j;
19 for (j = 0; j < k; j++)
20 {
21 int cnt = 0, tmp = 1;
22 for (int p = 0; p < B; p++)
23 {
24 if ((i & tmp) != (x[j] & tmp))
25 cnt += 1;
26 tmp *= 2;
27 }
28
29 if (cnt < D)
30 break;
31 }
32
33 if (j == k)
34 {
35 x[k] = i;
36 break;
37 }
38 }
39
40 for (int i = 0; i < N; i++)
41 {
42 cout << x[i];
43 if ((i + 1) % 10 == 0)
44 cout << endl;
45 else
46 {
47 if (i + 1 == N)
48 cout << endl;
49 else
50 cout << ' ';
51 }
52 }
53
54 return 0;
55 }
56
1 #include <iostream>
2
3 using namespace std;
4
5 int n, m;
6 int need[25];
7 int feed[15][25];
8
9 int ans = 32767;
10 int cur_need[25], x[15], bestx[15];
11
12 void search(int i, int c)
13 {
14 if (i == m)
15 {
16 int j;
17 for (j = 0; j < n; j++)
18 if (cur_need[j] < need[j])
19 break;
20 if (j == n)
21 {
22 ans = c;
23 memcpy(bestx, x, sizeof(x));
24 }
25 return;
26 }
27
28 if (c + 1 < ans)
29 {
30 for (int j = 0; j < n; j++)
31 cur_need[j] += feed[i][j];
32 x[i] = 1;
33
34 search(i + 1, c + 1);
35
36 x[i] = 0;
37 for (int j = 0; j < n; j++)
38 cur_need[j] -= feed[i][j];
39 }
40
41 search(i + 1, c);
42 }
43
44 int main()
45 {
46 freopen("holstein.in", "r", stdin);
47 freopen("holstein.out", "w", stdout);
48
49 cin >> n;
50 for (int i = 0; i < n; i++)
51 cin >> need[i];
52 cin >> m;
53 for (int i = 0; i < m; i++)
54 for (int j = 0; j < n; j++)
55 cin >> feed[i][j];
56
57 search(0, 0);
58
59 cout << ans << ' ';
60 for (int i = 0, j = 0; j < ans; i++)
61 if (bestx[i])
62 {
63 j++;
64 cout << i + 1 << (j == ans ? '\n' : ' ');
65 }
66
67 return 0;
68 }
69
1 #include <iostream>
2
3 using namespace std;
4
5 int main()
6 {
7 freopen("sort3.in", "r", stdin);
8 freopen("sort3.out", "w", stdout);
9
10 int n, x[1000];
11 int c[10][10] = { 0 };
12 int t1 = 0, t2 = 0, t3 = 0;
13
14 cin >> n;
15 for (int i = 0; i < n; i++)
16 {
17 cin >> x[i];
18 if (x[i] == 1) t1 += 1;
19 if (x[i] == 2) t2 += 1;
20 if (x[i] == 3) t3 += 1;
21 }
22
23 for (int i = 0; i < t1; i++)
24 {
25 if (x[i] == 2) c[1][2] += 1;
26 if (x[i] == 3) c[1][3] += 1;
27 }
28 for (int i = t1; i < t1 + t2; i++)
29 {
30 if (x[i] == 1) c[2][1] += 1;
31 if (x[i] == 3) c[2][3] += 1;
32 }
33 for (int i = t1 + t2; i < n; i++)
34 {
35 if (x[i] == 1) c[3][1] += 1;
36 if (x[i] == 2) c[3][2] += 1;
37 }
38
39 int t, ans = 0;
40
41 t = min(c[1][2], c[2][1]);
42 c[1][2] -= t, c[2][1] -= t, ans += t;
43 t = min(c[1][3], c[2][1]);
44 c[1][3] -= t, c[2][1] -= t, c[2][3] += t, ans += t;
45
46 t = min(c[1][3], c[3][1]);
47 c[1][3] -= t, c[3][1] -= t, ans += t;
48 t = min(c[1][2], c[3][1]);
49 c[1][2] -= t, c[3][1] -= t, c[3][2] += t, ans += t;
50
51 t = min(c[2][3], c[3][2]);
52 c[2][3] -= t, c[3][2] -= t, ans += t;
53
54 cout << ans << endl;
55
56 return 0;
57 }
58
1 #include <iostream>
2
3 using namespace std;
4
5 int gcd(int a, int b)
6 {
7 if (b == 0)
8 return a;
9 return gcd(b, a % b);
10 }
11
12 struct Fraction
13 {
14 int a, b;
15
16 bool isReducedFraction()
17 {
18 return gcd(a, b) == 1 ? true : false;
19 }
20 bool operator < (const Fraction & x) const
21 {
22 int t = b * x.b / gcd(b, x.b);
23 return t / b * a < t / x.b * x.a;
24 }
25 } frac[12800];
26
27 int main()
28 {
29 freopen("frac1.in", "r", stdin);
30 freopen("frac1.out", "w", stdout);
31
32 int n;
33
34 int cnt = 2;
35 frac[0].a = 0, frac[0].b = 1;
36 frac[1].a = 1, frac[1].b = 1;
37
38 cin >> n;
39 for (int b = 2; b <= n; b++)
40 for (int a = 1; a < b; a++)
41 if (gcd(a, b) == 1)
42 {
43 frac[cnt].a = a;
44 frac[cnt].b = b;
45 cnt++;
46 }
47
48 sort(frac, frac + cnt);
49
50 for (int i = 0; i < cnt; i++)
51 cout << frac[i].a << '/' << frac[i].b << endl;
52
53 return 0;
54 }
55
1 #include <iostream>
2
3 using namespace std;
4
5 int n, m;
6 int castleStructure[50][50];
7 int castleRegion[50][50];
8
9 int regionCnt;
10 int areaOfRegions[2500];
11
12 void getRegion(int i, int j)
13 {
14 if (castleRegion[i][j] != -1)
15 return;
16 castleRegion[i][j] = regionCnt;
17 if ((castleStructure[i][j] & 1) == 0) //W
18 getRegion(i, j - 1);
19 if ((castleStructure[i][j] & 2) == 0) //N
20 getRegion(i - 1, j);
21 if ((castleStructure[i][j] & 4) == 0) //E
22 getRegion(i, j + 1);
23 if ((castleStructure[i][j] & 8) == 0) //S
24 getRegion(i + 1, j);
25 }
26
27 int main()
28 {
29 freopen("castle.in", "r", stdin);
30 freopen("castle.out", "w", stdout);
31
32 cin >> m >> n;
33 for (int i = 0; i < n; i++)
34 for (int j = 0; j < m; j++)
35 cin >> castleStructure[i][j];
36
37 memset(castleRegion, 255, sizeof(castleRegion));
38
39 for (int i = 0; i < n; i++)
40 for (int j = 0; j < m; j++)
41 if (castleRegion[i][j] == -1)
42 {
43 getRegion(i, j);
44 regionCnt++;
45 }
46
47 //ans 1
48 cout << regionCnt << endl;
49
50 for (int i = 0; i < n; i++)
51 for (int j = 0; j < m; j++)
52 areaOfRegions[castleRegion[i][j]]++;
53
54 int maxAreaOfRegions = 0;
55 for (int i = 0; i < regionCnt; i++)
56 maxAreaOfRegions >?= areaOfRegions[i];
57
58 //ans 2
59 cout << maxAreaOfRegions << endl;
60
61 int maxAreaAfterRemoveOneWall = 0;
62 struct { int x, y, dir; } theWallToRemove;
63
64 for (int j = 0; j < m; j++)
65 for (int i = n - 1; i >= 0; i--)
66 {
67 if ((castleStructure[i][j] & 1) == 1 && j - 1 >= 0) //W
68 {
69 if (castleRegion[i][j] == castleRegion[i][j - 1])
70 continue;
71 int t = areaOfRegions[castleRegion[i][j]] + areaOfRegions[castleRegion[i][j - 1]];
72 if (t > maxAreaAfterRemoveOneWall)
73 {
74 maxAreaAfterRemoveOneWall = t;
75 theWallToRemove.x = i;
76 theWallToRemove.y = j;
77 theWallToRemove.dir = 1;
78 }
79 }
80 if ((castleStructure[i][j] & 2) == 2 && i - 1 >= 0) //N
81 {
82 if (castleRegion[i][j] == castleRegion[i - 1][j])
83 continue;
84 int t = areaOfRegions[castleRegion[i][j]] + areaOfRegions[castleRegion[i - 1][j]];
85 if (t > maxAreaAfterRemoveOneWall)
86 {
87 maxAreaAfterRemoveOneWall = t;
88 theWallToRemove.x = i;
89 theWallToRemove.y = j;
90 theWallToRemove.dir = 2;
91 }
92 }
93 if ((castleStructure[i][j] & 4) == 4 && j + 1 < m) //E
94 {
95 if (castleRegion[i][j] == castleRegion[i][j + 1])
96 continue;
97 int t = areaOfRegions[castleRegion[i][j]] + areaOfRegions[castleRegion[i][j + 1]];
98 if (t > maxAreaAfterRemoveOneWall)
99 {
100 maxAreaAfterRemoveOneWall = t;
101 theWallToRemove.x = i;
102 theWallToRemove.y = j;
103 theWallToRemove.dir = 4;
104 }
105 }
106 if ((castleStructure[i][j] & 8) == 8 && i + 1 < n) //S
107 {
108 if (castleRegion[i][j] == castleRegion[i + 1][j])
109 continue;
110 int t = areaOfRegions[castleRegion[i][j]] + areaOfRegions[castleRegion[i + 1][j]];
111 if (t > maxAreaAfterRemoveOneWall)
112 {
113 maxAreaAfterRemoveOneWall = t;
114 theWallToRemove.x = i;
115 theWallToRemove.y = j;
116 theWallToRemove.dir = 8;
117 }
118 }
119 }
120
121 //ans 3
122 cout << maxAreaAfterRemoveOneWall << endl;
123 cout << theWallToRemove.x + 1 << ' '
124 << theWallToRemove.y + 1 << ' ';
125 if (theWallToRemove.dir == 1) cout << 'W' << endl;
126 if (theWallToRemove.dir == 2) cout << 'N' << endl;
127 if (theWallToRemove.dir == 4) cout << 'E' << endl;
128 if (theWallToRemove.dir == 8) cout << 'S' << endl;
129
130 return 0;
131 }
132
1 #include <iostream>
2
3 using namespace std;
4
5 bool C[50], A[50], B[50];
6 bool * x = C + 25, * LR = A + 25, * RL = B + 25;
7
8 int n;
9 int cnt;
10
11 void search(int i, int pos[])
12 {
13 if (cnt == 3)
14 return;
15 if (i == n)
16 {
17 cnt++;
18 for (int k = 0; k < n; k++)
19 cout << pos[k] + 1 << (k == n - 1 ? '\n' : ' ');
20 return;
21 }
22
23 for (int j = 0; j < n; j++)
24 if (x[j] == false)
25 {
26 pos[i] = j;
27
28 int k;
29 for (k = 0; k < i; k++)
30 if (abs(i - k) == abs(pos[i] - pos[k]))
31 break;
32
33 if (k == i)
34 {
35 x[j] = true;
36
37 search(i + 1, pos);
38
39 x[j] = false;
40 }
41 }
42 }
43
44 void search_odd(int i, const int x0, const int x1)
45 {
46 if (i == n)
47 {
48 if (x0 == x1)
49 cnt += 1;
50 else
51 cnt += 8;
52 return;
53 }
54 if (i == x0 || i == x1)
55 {
56 search_odd(i + 1, x0, x1);
57 return;
58 }
59 for (int j = 0; j < n; j++)
60 if (x[j] || LR[i - j] || RL[i + j])
61 ;
62 else
63 {
64 x[j] = LR[i - j] = RL[i + j] = true;
65
66 search_odd(i + 1, x0, x1);
67
68 x[j] = LR[i - j] = RL[i + j] = false;
69 }
70 }
71
72 void search_even(int i)
73 {
74 if (i == n)
75 {
76 cnt += 2;
77 return;
78 }
79
80 int t = (i ? n : n / 2);
81 for (int j = 0; j < t; j++)
82 if (x[j] || LR[i - j] || RL[i + j])
83 ;
84 else
85 {
86 x[j] = LR[i - j] = RL[i + j] = true;
87
88 search_even(i + 1);
89
90 x[j] = LR[i - j] = RL[i + j] = false;
91 }
92 }
93
94 int main()
95 {
96 freopen("checker.in", "r", stdin);
97 freopen("checker.out", "w", stdout);
98
99 cin >> n;
100
101 int pos[13];
102 search(0, pos);
103
104 for (int i = -n + 1; i < n; i++)
105 LR[i] = false;
106 for (int i = 0; i <= 2 * n - 2; i++)
107 RL[i] = false;
108
109 cnt = 0;
110 if (n % 2 == 0)
111 search_even(0);
112 else
113 {
114 int x0, y0, x1, y1;
115
116 x0 = n / 2, y1 = n / 2;
117 for (x1 = 0; x1 < n / 2 - 1; x1++)
118 for (y0 = x1 + 1; y0 < n / 2; y0++)
119 if (abs(x0 - x1) != abs(y0 - y1))
120 {
121 x[y0] = x[y1] = true;
122 LR[x0 - y0] = RL[x0 + y0] = true;
123 LR[x1 - y1] = RL[x1 + y1] = true;
124
125 search_odd(0, x0, x1);
126
127 x[y0] = x[y1] = false;
128 LR[x0 - y0] = RL[x0 + y0] = false;
129 LR[x1 - y1] = RL[x1 + y1] = false;
130 }
131 x[n / 2] = LR[0] = RL[n - 1] = true;
132 search_odd(0, n / 2, n / 2);
133 x[n / 2] = LR[0] = RL[n - 1] = false;
134 }
135
136 cout << cnt << endl;
137
138 return 0;
139 }
140
1 #include <math.h>
2 #include <iostream>
3
4 using namespace std;
5
6 bool isPrime(int n)
7 {
8 if (n == 1)
9 return false;
10 if (n == 2)
11 return true;
12 for (int i = 3; i <= (int)sqrt(n); i += 2)
13 if (n % i == 0)
14 return false;
15 return true;
16 }
17
18 void generateSuperprime(int i, int n, int cur)
19 {
20 if (i == n)
21 {
22 cout << cur << endl;
23 return;
24 }
25 if (i == 0)
26 {
27 generateSuperprime(i + 1, n, 2);
28 generateSuperprime(i + 1, n, 3);
29 generateSuperprime(i + 1, n, 5);
30 generateSuperprime(i + 1, n, 7);
31 }
32 else
33 {
34 if (isPrime(cur * 10 + 1))
35 generateSuperprime(i + 1, n, cur * 10 + 1);
36 if (isPrime(cur * 10 + 3))
37 generateSuperprime(i + 1, n, cur * 10 + 3);
38 if (isPrime(cur * 10 + 7))
39 generateSuperprime(i + 1, n, cur * 10 + 7);
40 if (isPrime(cur * 10 + 9))
41 generateSuperprime(i + 1, n, cur * 10 + 9);
42 }
43 }
44
45 int main()
46 {
47 freopen("sprime.in", "r", stdin);
48 freopen("sprime.out", "w", stdout);
49
50 int n;
51
52 cin >> n;
53 generateSuperprime(0, n, 0);
54
55 return 0;
56 }
57
1 #include <math.h>
2 #include <iostream>
3
4 using namespace std;
5
6 int ansCnt, ansNum[50000];
7
8 bool isPrime(const int n)
9 {
10 if (n == 1)
11 return false;
12 if (n == 2)
13 return true;
14 int t = (int)sqrt(n);
15 for (int i = 3; i <= t; i += 2)
16 if (n % i == 0)
17 return false;
18 return true;
19 }
20
21 void generatePalindrome(int x[], int l, int r)
22 {
23 if (l < 1)
24 return;
25
26 for (int i = 0; i < 10; i++)
27 {
28 x[l] = x[r] = i;
29
30 //=================
31 int n0 = 0, n1 = 0, t;
32
33 if (x[l] != 0 && x[r] % 2 != 0)
34 {
35 t = 1;
36 for (int k = r; k >= l; k--)
37 n0 += x[k] * t, t *= 10;
38
39 t = 1;
40 for (int k = r; k >= l; k--)
41 {
42 n1 += x[k] * t, t *= 10;
43 if (k == 4)
44 n1 += x[k] * t, t *= 10;
45 }
46
47 if (isPrime(n0)) ansNum[ansCnt++] = n0;
48 if (isPrime(n1)) ansNum[ansCnt++] = n1;
49 }
50
51 generatePalindrome(x, l - 1, r + 1);
52 }
53 }
54
55 int main()
56 {
57 freopen("pprime.in", "r", stdin);
58 freopen("pprime.out", "w", stdout);
59
60 int s, t, x[10];
61
62 cin >> s >> t;
63
64 //--------
65 //12345678
66 generatePalindrome(x, 4, 4);
67
68 sort(ansNum, ansNum + ansCnt);
69 for (int i = 0; i < ansCnt; i++)
70 {
71 if (ansNum[i] < s)
72 continue;
73 if (ansNum[i] > t)
74 break;
75 cout << ansNum[i] << endl;
76 }
77
78 return 0;
79 }
80
1 #include <iostream>
2
3 using namespace std;
4
5 int main()
6 {
7 freopen("numtri.in", "r", stdin);
8 freopen("numtri.out", "w", stdout);
9
10 int n;
11 int x[1000][1000] = { 0 };
12 int f[1000][1000] = { 0 };
13
14 cin >> n;
15 for (int i = 0; i < n; i++)
16 for (int j = 0; j <= i; j++)
17 cin >> x[i][j];
18
19 f[0][0] = x[0][0];
20 for (int i = 0; i < n - 1; i++)
21 for (int j = 0; j <= i; j++)
22 {
23 f[i + 1][j] >?= (f[i][j] + x[i + 1][j]);
24 f[i + 1][j + 1] >?= (f[i][j] + x[i + 1][j + 1]);
25 }
26
27 int ans = 0;
28 for (int i = 0; i < n; i++)
29 ans >?= f[n - 1][i];
30
31 cout << ans << endl;
32
33 return 0;
34 }
35
1 #include <queue>
2 #include <iostream>
3
4 using namespace std;
5
6 int A, B, C;
7
8 bool x[25][25][25];
9
10 void search(int a, int b, int c)
11 {
12 if (x[a][b][c] == true)
13 return;
14
15 x[a][b][c] = true;
16
17 if (a)
18 {
19 search(a - min(a, B - b), b + min(a, B - b), c);
20 search(a - min(a, C - c), b, c + min(a, C - c));
21 }
22 if (b)
23 {
24 search(a + min(b, A - a), b - min(b, A - a), c);
25 search(a, b - min(b, C - c), c + min(b, C - c));
26 }
27 if (c)
28 {
29 search(a + min(c, A - a), b, c - min(c, A - a));
30 search(a, b + min(c, B - b), c - min(c, B - b));
31 }
32 }
33
34 int main()
35 {
36 freopen("milk3.in", "r", stdin);
37 freopen("milk3.out", "w", stdout);
38
39 cin >> A >> B >> C;
40
41 search(0, 0, C);
42
43 queue <int> q;
44 for (int b = B; b >= 0; b--)
45 if (x[0][b][C - b])
46 q.push(C - b);
47
48 while (q.empty() == false)
49 {
50 cout << q.front() << (q.size() == 1 ? '\n' : ' ');
51 q.pop();
52 }
53
54 return 0;
55 }
56
|