Untitled
unknown
plain_text
2 years ago
12 kB
17
Indexable
//Hugo di tau
TC:
50
10
4 5
6 2
10 2
10
8 5
9 1
10 2
24
15 3
20 4
23 7
39
17 8
30 5
31 9
60
57 12
31 19
38 16
10
2 2
8 3
5 2
10
9 3
3 3
5 2
10
8 8
2 1
6 1
10
2 2
5 2
3 2
10
2 2
5 2
4 2
20
12 5
19 6
10 2
20
16 4
15 3
4 4
20
14 2
5 6
2 5
20
8 4
5 4
3 2
20
4 5
2 5
10 6
20
11 5
3 5
9 3
20
5 4
9 3
7 4
20
11 4
7 3
2 4
20
4 1
5 3
15 5
20
17 1
12 4
9 3
30
14 9
18 3
29 10
30
12 10
4 9
6 5
30
1 4
28 7
27 2
30
6 1
15 10
23 8
30
4 7
28 1
13 2
30
7 6
6 5
18 2
30
23 2
21 5
11 7
30
11 8
28 8
12 8
30
18 10
4 10
6 9
30
12 7
19 7
3 1
40
14 1
9 4
21 5
40
11 11
40 8
25 10
40
36 11
2 12
3 17
40
15 2
21 9
37 20
40
29 3
5 2
2 11
40
19 6
21 13
29 11
40
14 11
9 4
4 11
40
18 10
14 12
35 8
40
12 10
1 6
10 10
40
24 8
25 6
9 1
50
3 6
46 8
36 12
50
38 9
15 1
4 3
50
19 15
31 2
47 6
50
49 9
10 7
8 11
50
43 15
39 10
30 7
60
12 17
16 12
29 3
60
55 20
33 20
16 20
60
27 10
36 3
54 5
60
37 20
42 20
19 20
60
60 13
18 10
37 16
Res:
Case #1
18
Case #2
25
Case #3
57
Case #4
86
Case #5
339
Case #6
11
Case #7
13
Case #8
33
Case #9
9
Case #10
9
Case #11
33
Case #12
25
Case #13
42
Case #14
21
Case #15
64
Case #16
31
Case #17
27
Case #18
21
Case #19
18
Case #20
14
Case #21
85
Case #22
150
Case #23
41
Case #24
60
Case #25
23
Case #26
42
Case #27
34
Case #28
104
Case #29
202
Case #30
39
Case #31
20
Case #32
112
Case #33
433
Case #34
227
Case #35
79
Case #36
163
Case #37
155
Case #38
147
Case #39
163
Case #40
62
Case #41
87
Case #42
35
Case #43
89
Case #44
133
Case #45
229
Case #46
235
Case #47
416
Case #48
51
Case #49
604
Case #50
206
Code:
#include<iostream>
using namespace std;
#define MAX 65
#define max(a, b) a > b ? a : b
#define min(a, b) a < b ? a : b
#define INF 100000000
int N, G;
int dis[MAX];
int infor[3][2];
int open[3];
int visited[MAX];
int ans;
void unvisit(int g)
{
for(int i = 1; i <= N; i++)
{
if(visited[i] == g)
visited[i] = 0;
}
}
int minRdis(int g)
{
for(int i = g; i <= N; i++)
{
if(visited[i] == 0)
return i - g + 1;
}
return INF;
}
int minLdis(int g)
{
for(int i = g; i >= 1; i--)
{
if(visited[i] == 0)
return g - i + 1;
}
return INF;
}
bool isAllOpen()
{
for(int i = 0; i < 3; i++)
{
if(open[i] == 0)
return false;
}
return true;
}
void backtrack(int k, int csum)
{
int gate, nums, left, right, add;
if(csum >= ans)
return;
if(isAllOpen())
{
ans = min(csum, ans);
return;
}
for(int i = 0; i < 3; i++)
{
if(open[i] == 0)
{
open[i] = 1;
add = 0;
gate = infor[i][0];
nums = infor[i][1];
for(int j = 1; j <= nums - 1; j++)
{
left = minLdis(gate);
right = minRdis(gate);
if(left < right)
{
add += left;
visited[gate - left + 1] = gate;
}
else
{
add += right;
visited[right + gate - 1] = gate;
}
}
left = minLdis(gate);
right = minRdis(gate);
if(left == right)
{
add += left;
visited[gate - left + 1] = gate;
backtrack(k + 1, csum + add);
visited[gate - left + 1] = 0;
visited[right - gate + 1] = gate;
backtrack(k + 1, csum + add);
visited[right - gate + 1] = 0;
}
else
{
if(left < right)
{
add += left;
visited[gate - left + 1] = gate;
}
else
{
add += right;
visited[right + gate - 1] = gate;
}
backtrack(k + 1, csum + add);
}
open[i] = 1;
unvisit(gate);
}
}
}
int main()
{
int tc;
int T;
freopen("input.txt", "r", stdin);
cin >> T;
for(tc = 1; tc <= T; ++tc)
{
cin>>N;
for(int i = 0; i < 3; i++)
{
cin>>infor[i][0]>>infor[i][1];
}
for(int i = 1; i <= N; i++)
{
visited[i] = 0;
}
backtrack(0, 0);
ans = INF;
cout<<"Case #"<<tc<<endl;
cout<<ans<<endl;
}
return 0;
}
Code 2:
#include <iostream>
using namespace std;
// có 3 cổng. sắp xếp số người của mỗi cổng sao cho khoảng cách số người của cổng đó cách cổng đó ít nhất.
/* hướng giải bài toán : nếu bên trái còn vị trí gần hơn thì đẩy hết vào trái, bên phải còn vị trí gần hơn thì đẩy bên phải.Để lại người cuối cùng để check
// xem: nếu mà khoảng cách từ cổng đó đến bên trái gần hơn thì ném vào trái, nếu khoảng cách từ cổng đó đến bên phải gần hơn thì ném vào bên phải. Nếu khoảng cách
từ vị trí đó đến 2 bên trái phải bằng nhau thì ta phải thử đặt cả vào bên trái hoặc phái.
Lưu ý: cứ đặt hết số người vào vị trí trái hoặc phải gần cổng đó nhát. chỉ để lại 1 người cuối cùng để backtrack, điều này sẽ tránh time limit và dễ dàng hơn.
*/
int n;
// mảng spots lưu trạng thái vị trí đã có người ngồi hay chưa và nếu có người rồi thì vị trí đó lưu người của cổng số mấy ngồi
// -1 không có người ngồi
// x là người cổng bao nhiêu ngồi.
int spots[100];
// lưu trạng thái các cổng đã duyệt hay chưa
bool visited[3];
// mảng 2 chiều trả về số người sau cổng đó là bao nhiêu.
int gates[3][2];
// lưu kết quả
int answer;
// hàm kiểm tra xem cổng đó đã mở để người vào hết hay chưa.
// true ~ là mở
// false ~ chưa mở
bool isOpened()
{
for (int i = 0; i < 3; i++)
{
if (!visited[i]) return false;
}
return true;
}
// khoảng cách từ cổng đó đến vị trí bên phải còn trống gần nhất nếu không còn thì trả về giá trị rất lớn đề ta không lấy nó nữa.
int distanceToRightSpot(int start)
{
for (int i = start; i <= n; i++)
{
if (spots[i] == -1) return i - start;
}
return 100000;
}
// khoảng cách từ cổng đó đến vị trí bên trái còn trống gần nhất nếu không còn thì trả về giá trị rất lớn đề ta không lấy nó nữa.
int distanceToLeftSpot(int start)
{
for (int i = start; i >= 1; i--)
{
if (spots[i] == -1) return start - i;
}
return 100000;
}
void backtrack(int sum)
{
// kiểm tra xem cổng đã mở hết chưa, nếu đã mở hết thì return giá trị.
if (isOpened())
{
if (sum < answer)answer = sum;
return;
}
for (int i = 0; i < 3; i++)
{
// nếu cổng đã được mở thì ta bỏ qua.
if (visited[i]) continue;
// nếu chưa mở thì ta thăm cổng đó và đánh dấu cổng đó đã thăm.
visited[i] = true;
// lưu khoảng cách tạm = số người tại cổng đó. vì khi người tại cổng X có vị trí là 3 đặt vào ô thứ 3 còn trống thì biến đếm tại ô thứ 3 là 1. ở 2 hàm
// check trái và phải thì mình chỉ check nó là 0 nên biến add cần được cộng thêm. tý cậu đọc 2 hàm check trái vs check phải là biết. nếu cậu bỏ cái add này
// đi và chạy thử kết quả nó sẽ tường minh hơn.
int add = gates[i][1];
// ta xếp hết người tại cổng đó vào vị trí. chỉ để lại 1 người cuối cùng để check.
for (int j = 0; j < gates[i][1] - 1; j++)
{
int left = distanceToLeftSpot(gates[i][0]); // khoảng cách cổng đó đến trái.
int right = distanceToRightSpot(gates[i][0]); // khoảng cách cổng đó đến phải.
// nếu trái nhỏ hơn phải thì thêm vào trái, nếu không thì thêm vào phải.
if (left < right)
{
spots[gates[i][0] - left] = i;
add += left;
}
else
{
spots[gates[i][0] + right] = i;
add += right;
}
}
//trả về khoảng cách người cuối cùng của cổng đó so với bên trái và phải.
int left = distanceToLeftSpot(gates[i][0]);
int right = distanceToRightSpot(gates[i][0]);
// nếu khoảng cách đó khách nhau thì ta check xem trái nhỏ hơn hay phải nhỏ hơn để thêm vào.
if (left != right)
{
if (left < right)
{
spots[gates[i][0] - left] = i;
add += left;
}
else
{
spots[gates[i][0] + right] = i;
add += right;
}
backtrack(sum + add);
}
// nếu khoảng cách bằng nhau thì ta cần phải đặt thử cả 2 bên trái và bên phải.
else
{
add += left;
spots[gates[i][0] + right] = i;
backtrack(sum + add);
spots[gates[i][0] + right] = -1;
spots[gates[i][0] - left] = i;
backtrack(sum + add);
spots[gates[i][0] - left] = -1;
}
// trả lại cổng chưa thăm để backtrack lại
visited[i] = false;
// trả lại những vị trí cổng đó đã ngồi.
for (int j = 1; j <= n; j++)
{
if (spots[j] == i) spots[j] = -1;
}
}
}
void readInput()
{
cin >> n;
for (int i = 0; i < 3; i++)
{
cin >> gates[i][0] >> gates[i][1];
}
}
int main()
{
int tcs;
cin >> tcs;
// reset toàn bộ mảng để đến test case sau
for (int i = 0; i < 100; i++) spots[i] = -1;
for (int i = 0; i < 3; i++) visited[i] = false;
for (int tc = 1; tc <= tcs; tc++)
{
readInput();
answer = 10000;
backtrack(0);
cout << "#" << tc << " " << answer << endl;
}
}
Hugo Phá hủy hệ thống điện
Sau khi biết tin Eagle xây dựng hệ thống điện và ăn bớt được rất nhiều kinh phí, Hugo rất tức vì khi anh xây cầu anh đã không ăn bớt được đồng nào. Do đó anh quyết phá hệ thống điện của Eagle.
Do sợ bị phát hiện nên anh sẽ chỉ phá hệ thống điện ở trên 1 hòn đào, và anh muốn tìm hòn đảo nào sau khi phá xong thì hệ thống điện của Eagle bị chia cắt thành nhiều phần nhất.
Hãy giúp Hugo tìm hòn đảo này.
Input:
Dòng đầu tiên ghi số bộ test, không lớn hơn 100.
Mỗi bộ test được tổ chức theo khuôn dạng sau:
Dòng đầu tiên ghi lại số tự nhiên N không lớn hơn 100 là số hòn đảo.
Những dòng kế tiếp ghi lại ma trận biểu diễn hệ thong mạng lưới điện, trong đó 0 được hiểu là không có đường dây điện nối giữa điểm i và j, 1 được hiểu có đường dây điện trực tiếp giữa điểm i và điểm j (1<=i, j <= N).
Output
Với mỗi bộ test, in ra màn hình trên một dòng một số duy nhất là hòn đảo bị phá hủy hệ thống điện thỏa mãn yêu cầu bài toán (nếu có nhiều đảo cùng thỏa mãn yêu cầu thì in ra đảo có giá trị nhỏ nhất). Nếu không thể chia cắt được hệ thống điện, hãy in ra số 0.
Example
Input:
2
5
0 1 1 0 0
1 0 1 0 0
1 1 0 1 1
0 0 1 0 0
0 0 1 0 0
5
0 1 1 0 0
1 0 1 0 1
1 1 0 1 1
0 0 1 0 1
0 1 1 1 0
Output:
3
0
TC:
5
10
0 1 1 1 0 0 0 0 0 0
1 0 1 0 0 0 1 0 0 0
1 1 0 1 0 1 0 0 0 0
1 0 1 0 1 0 0 0 0 0
0 0 0 1 0 1 0 0 0 1
0 0 1 0 1 0 1 0 1 0
0 1 0 0 0 1 0 1 0 0
0 0 0 0 0 0 1 0 1 0
0 0 0 0 0 1 0 1 0 1
0 0 0 0 1 0 0 0 1 0
10
0 1 1 1 0 0 0 0 0 0
1 0 0 0 0 0 1 0 0 0
1 0 0 0 0 1 0 0 0 0
1 0 0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0 0 1
0 0 1 0 0 0 0 0 1 0
0 1 0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0 0 0
15
0 1 1 1 0 0 0 0 0 0 0 0 0 0 0
1 0 1 0 0 0 1 0 0 0 0 0 0 0 0
1 1 0 1 0 1 0 0 0 0 0 0 0 0 0
1 0 1 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 1 0 0 0 1 0 0 0 0 0
0 0 1 0 1 0 1 0 1 0 0 0 0 0 0
0 1 0 0 0 1 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 1 1 0 0 1
0 0 0 0 0 1 0 0 0 1 0 0 1 0 0
0 0 0 0 1 0 0 0 1 0 0 0 0 1 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
15
0 1 0 0 1 0 1 0 0 0 0 0 0 0 0
1 0 1 0 1 0 0 0 0 0 0 0 0 0 0
0 1 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 1 1 0 0 1
1 1 0 0 0 1 1 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 1 0 0 0 0 0 0
1 0 0 0 1 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
15
0 1 0 0 1 0 1 0 0 0 0 0 0 0 0
1 0 1 0 1 0 0 0 0 0 0 0 0 0 0
0 1 0 1 0 1 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 1 0 1 1 0 0 1
1 1 0 0 0 1 1 0 0 0 0 0 0 0 0
0 0 1 0 1 0 0 1 1 0 0 0 0 0 0
1 0 0 0 1 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 1 1 0 0 1 0 0 0 0 0
0 0 0 1 0 1 0 0 0 1 0 0 1 0 0
0 0 0 0 0 0 0 1 1 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 0 0 1 0 0 1
0 0 0 1 0 0 0 0 0 0 1 0 1 0 0
0 0 0 0 0 0 0 0 1 0 0 1 0 1 0
0 0 0 0 0 0 0 0 0 1 0 0 1 0 0
0 0 0 1 0 0 0 0 0 0 1 0 0 0 0
Editor is loading...
Leave a Comment