Untitled
unknown
plain_text
6 months ago
9.0 kB
8
Indexable
Never
Địa điểm Pizza
Người bạn Picko của chúng tôi rất tiếp cận và anh ấy muốn mở nhiều nhà hàng có giao hàng. Thức ăn chính sẽ là, tất nhiên, pizza. Anh ấy có một số địa điểm tiềm năng nhất định cho các nhà hàng và anh ấy biết vị trí của các solitaires với rất nhiều người thường sẽ là khách hàng của anh ấy. Giao hàng của mỗi nhà hàng sẽ bao gồm tất cả các solitaires trong bán kính nhất định.
Picko chỉ có thể mở một số lượng hạn chế các nhà hàng và ông muốn rằng các nhà hàng trên các địa điểm sẽ bao gồm số lượng người tối đa trong các đơn độc.
Viết một chương trình sẽ tính toán số lượng người tối đa mà chúng tôi có thể bao gồm khi giao hàng.
Nhập
Trong dòng đầu tiên của tệp đầu vào có hai số nguyên K và R, được phân tách bằng không gian, số lượng nhà hàng và bán kính giao hàng, 1 ≤ K ≤ 10, 1 ≤ R ≤ 500.
Trong dòng thứ hai có số nguyên M, số vị trí, K ≤ M ≤ 20.
Trong mỗi dòng M tiếp theo có hai số nguyên X và Y, cách nhau bằng không gian, tọa độ của mỗi vị trí, -1000 ≤ X, Y ≤ 1000.
Trong dòng tiếp theo có số nguyên N, số solitaires, 1 ≤ N ≤ 100.
Trong mỗi dòng N tiếp theo có ba số nguyên X, Y và S, cách nhau bằng khoảng trắng, X và Y là tọa độ của mỗi solitaire và S là số người trong solitaire đó, -1000 ≤ X, Y ≤ 1000, 1 ≤ S ≤ 100.
Chúng tôi xem xét rằng solitaire nằm trong bán kính của một số nhà hàng nếu khoảng cách giữa chúng nhỏ hơn hoặc bằng R. Không có hai địa điểm của các nhà hàng trên cùng một nơi.
Ra
Chỉ trong dòng của tệp đầu ra, chúng ta phải viết số tối đa từ văn bản trên.
Nhập
3
2 2
3
1 0
4 0
7 0
4
0 0 1
3 0 7
5 0 9
8 0 1
2 2
3
-2 0
0 1
3 0
8
-3 1 1
-3 0 1
-3 -1 1
-2 -1 1
0 0 3
0 2 1
2 1 3
4 0 2
3 3
5
0 0
1 6
2 3
6 6
7 2
8
0 1 2
0 5 3
0 6 1
1 0 1
3 2 3
3 6 2
6 2 4
8 6 3
Ra
#1 18
#2 12
#3 17
#include <iostream>
using namespace std;
int k, r; // 1 <= k <= 10, 1 <= r <= 500
int m; // k <= m <= 20
int A[20][2];
int n; // 1 <= n <= 100
int B[100][3];
bool C[20][100];
int D[20];
bool Vis[100];
int res;
void inputF () {
cin >> k >> r;
cin >> m;
for (int i = 0; i < m; i++) {
cin >> A[i][0] >> A[i][1];
}
cin >> n;
for (int i = 0; i < n; i++) {
cin >> B[i][0] >> B[i][1] >> B[i][2];
}
}
void resetF () {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
C[i][j] = false;
}
}
for (int i = 0; i < m; i++) {
D[i] = 0;
}
res = 0;
}
void markF () {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (( (A[i][0] - B[j][0])*(A[i][0] - B[j][0]) + (A[i][1] - B[j][1])*(A[i][1] - B[j][1]) ) <= r*r) {
C[i][j] = true;
}
}
}
}
void pizzaF (int loop) {
if (loop > m) {
return;
}
int sum = 0;
for (int i = 0; i < m; i++) {
sum += D[i];
}
if (sum == k) {
int cnt = 0;
for (int i = 0; i < n; i++) {
Vis[i] = false;
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (D[i] == 1 && Vis[j] == false && C[i][j] == true) {
cnt += B[j][2];
Vis[j] = true;
}
}
}
if (res < cnt) {
res = cnt;
}
return;
}
for (int i = 1; i >= 0; i--) {
D[loop] = i;
pizzaF(loop+1);
}
}
int main () {
int TestCase;
cin >> TestCase;
for (int tc = 1; tc <= TestCase; tc++) {
inputF();
resetF();
markF();
pizzaF(0);
cout << "#" << tc << " " << res << endl;
}
return 0;
}
/*
Robot làm sạch
Chúng ta phải lên kế hoạch cho một robot dọn dẹp để làm sạch sàn phòng hình chữ nhật có kích thước NxM. Sàn phòng được lát bằng gạch vuông có kích thước phù hợp với robot dọn dẹp (1 × 1). Có gạch sạch và gạch bẩn, và robot có thể thay đổi gạch bẩn thành gạch sạch bằng cách truy cập gạch. Ngoài ra có thể có một số chướng ngại vật (đồ nội thất) có kích thước phù hợp với một viên gạch trong phòng. Nếu có chướng ngại vật trên gạch, robot không thể ghé thăm nó. Robot di chuyển đến một ô liền kề bằng một lần di chuyển. Ô mà robot di chuyển phải là một trong bốn ô (tức là đông, tây, bắc hoặc nam) liền kề với ô nơi robot có mặt. Robot có thể ghé thăm một ô hai lần trở lên.
Nhiệm vụ của bạn là viết một chương trình tính toán số lần di chuyển tối thiểu để robot thay đổi tất cả các ô bẩn thành gạch sạch, nếu có thể.
Giới hạn thời gian: 1s (C / C ++), 2s (Java)
Giới hạn gửi: 10 lần
Example:
The following is a room of size 5x7, with 3 dirty tiles, and 0 furniture. The answer for this case is 8.
Nhập
Đầu vào bao gồm nhiều bản đồ, dòng đầu tiên là số trường hợp kiểm thử T (T < = 50).
Mỗi trường hợp kiểm thử bắt đầu bằng N và M đại diện cho kích thước của căn phòng. ( 5 = < N, M <= 100)
Dòng N tiếp theo đại diện cho sự sắp xếp của căn phòng với mô tả sau:
0 : một viên gạch sạch 1 : một viên gạch
bẩn 2 : một mảnh đồ nội thất (chướng ngại vật) 3: robot (vị trí ban đầu)
Trong bản đồ, số lượng gạch bẩn không vượt quá 10 và chỉ có một robot.
Ra
In mỗi trường hợp kiểm thử trên hai dòng, dòng đầu tiên của mỗi trường hợp kiểm thử là "Case #x", trong đó x là số test case. Dòng tiếp theo là số lần di chuyển tối thiểu để robot thay đổi tất cả các ô bẩn thành gạch sạch. Nếu bản đồ bao gồm các ô bẩn mà robot không thể với tới, chương trình của bạn sẽ xuất ra -1.
Mẫu
Nhập
5
5 7
0 0 0 0 0 0 0
0 3 0 0 0 1 0
0 0 0 0 0 0 0
0 1 0 0 0 1 0
0 0 0 0 0 0 0
5 15
0 0 0 0 2 0 2 0 0 0 0 1 2 0 1
0 0 0 1 0 2 0 2 2 0 1 2 0 0 0
2 1 0 2 0 1 0 2 0 0 0 0 0 0 0
0 0 0 1 0 2 0 0 1 2 0 0 2 0 0
0 2 1 0 2 0 0 0 0 0 3 0 0 0 0
...............
Ra
Trường hợp #1
8
Trường hợp #2
38
Trường hợp #3
37
Trường hợp #4
-1
Trường hợp #5
49
*/
#include <iostream>
using namespace std;
int N, M;
int a[105][105];
int visited[105][105];
int cnt[105][105];
int dx[] = {-1, 0, 1, 0};
int dy[] = { 0, 1, 0, -1};
int qx[100000];
int qy[100000];
int front;
int rear;
int done[105][105];
int cntDirty;
// Queue
bool isEmpty(){
return front == -1;
}
void push(int x, int y){
if(front == -1) front = 0;
rear++;
qx[rear] = x;
qy[rear] = y;
}
void pop(){
if(front >= rear) front = rear = -1;
else front++;
}
// BFS
int XDirty, YDirty;
int total;
int BFS(int x, int y){
front = rear = -1;
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
visited[i][j] = 0;
cnt[i][j] = 0;
}
}
visited[x][y] = 1;
push(x,y);
int step = 1000000;
while(!isEmpty()){
int topx = qx[front];
int topy = qy[front];
pop();
for(int i = 0; i < 4; i++){
int x1 = topx + dx[i];
int y1 = topy + dy[i];
if(x1 >= 0 && x1 < N && y1 >= 0 && y1 < M && a[x1][y1] >= 0 && a[x1][y1] < 2 && visited[x1][y1] == 0){
cnt[x1][y1] = cnt[topx][topy] + 1;
visited[x1][y1] = 1;
push(x1,y1);
if(a[x1][y1] == 1 && done[x1][y1] == 0) {
if(cnt[x1][y1] < step){
step = cnt[x1][y1];
XDirty = x1;
YDirty = y1;
done[x1][y1] = 1;
}
}
}
}
}
return step;
}
void in(){
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
cout << done[i][j];
}
cout << endl;
}
}
int main(){
int T; cin >> T;
for(int tc = 1; tc <= T; tc++){
cin >> N >> M;
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
done[i][j] = 0;
}
}
cntDirty = 0; total = 0;
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
cin >> a[i][j];
if(a[i][j] == 1) cntDirty++;
if(a[i][j] == 3){
XDirty = i;
YDirty = j;
}
}
}
done[XDirty][YDirty] = 3;
for(int i = 0; i < cntDirty; i++){
a[XDirty][YDirty] = 0;
total += BFS(XDirty, YDirty);
}
cout << "Case #" << tc << endl;
if(total >= 1000000){
cout << -1 << endl;
}else{
cout << total << endl;
}
}
return 0;
}