Moocast
Pista 1
Consideremos comparar los valores del cuadrado de la distancia para mantener las cosas simples.
Pista 2
¿Cómo podemos buscar en la red de vacas para determinar cuántas vacas puede alcanzar una vaca dada?
Solución
Solución
Implementación
Complejidad temporal:
#include <bits/stdc++.h>
using namespace std;
vector<vector<bool>> connected;
vector<bool> visited;
/** @return cuántas vacas se pueden alcanzar desde una vaca c */
int reachable_cows(int c) {
visited[c] = true;
// siempre podemos alcanzar la vaca inicial c
int reached = 1;
for (int nc = 0; nc < connected.size(); nc++) {
// nos aseguramos de poder conectar con esta vaca y de que aún no se alcanzó
if (!visited[nc] && connected[c][nc]) {
visited[nc] = true;
reached += reachable_cows(nc);
}
}
return reached;
}
int main() {
freopen("moocast.in", "r", stdin);
int cow_num;
cin >> cow_num;
vector<int> x(cow_num), y(cow_num);
vector<int> power(cow_num);
for (int c = 0; c < cow_num; c++) { cin >> x[c] >> y[c] >> power[c]; }
connected = vector<vector<bool>>(cow_num, vector<bool>(cow_num));
for (int i = 0; i < cow_num; i++) {
for (int j = 0; j < cow_num; j++) {
int dist_squared =
((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
connected[i][j] = dist_squared <= power[i] * power[i];
}
}
int max_cows = 0;
for (int c = 0; c < cow_num; c++) {
visited.assign(cow_num, false);
max_cows = max(max_cows, reachable_cows(c));
}
freopen("moocast.out", "w", stdout);
cout << max_cows << endl;
}import java.io.*;
import java.util.*;
public class MooCast {
static boolean[][] connected;
static boolean[] visited;
public static void main(String[] args) throws IOException {
BufferedReader read = new BufferedReader(new FileReader("moocast.in"));
int cowNum = Integer.parseInt(read.readLine());
int[] x = new int[cowNum];
int[] y = new int[cowNum];
int[] power = new int[cowNum];
for (int c = 0; c < cowNum; c++) {
StringTokenizer cow = new StringTokenizer(read.readLine());
x[c] = Integer.parseInt(cow.nextToken());
y[c] = Integer.parseInt(cow.nextToken());
power[c] = Integer.parseInt(cow.nextToken());
}
connected = new boolean[cowNum][cowNum];
for (int i = 0; i < cowNum; i++) {
for (int j = 0; j < cowNum; j++) {
int distSquared =
((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
connected[i][j] = distSquared <= power[i] * power[i];
}
}
int maxCows = 0;
for (int c = 0; c < cowNum; c++) {
visited = new boolean[cowNum];
maxCows = Math.max(maxCows, reachableCows(c));
}
PrintWriter written = new PrintWriter("moocast.out");
written.println(maxCows);
written.close();
}
/** @return cuántas vacas se pueden alcanzar desde una vaca c */
static int reachableCows(int c) {
visited[c] = true;
int reached = 1; // siempre podemos alcanzar la vaca inicial c
for (int nc = 0; nc < connected.length; nc++) {
// nos aseguramos de poder conectar con esta vaca y de que aún no se alcanzó
if (!visited[nc] && connected[c][nc]) {
visited[nc] = true;
reached += reachableCows(nc);
}
}
return reached;
}
}with open("moocast.in") as read:
cow_num = int(read.readline())
x = [0 for _ in range(cow_num)]
y = [0 for _ in range(cow_num)]
power = [0 for _ in range(cow_num)]
for c in range(cow_num):
x[c], y[c], power[c] = [int(i) for i in read.readline().split()]
connected = [[False for _ in range(cow_num)] for _ in range(cow_num)]
for i in range(cow_num):
for j in range(cow_num):
dist_squared = (x[i] - x[j]) ** 2 + (y[i] - y[j]) ** 2
connected[i][j] = dist_squared <= power[i] ** 2
def reachable_cows(c: int) -> int:
""":return: cuántas vacas se pueden alcanzar desde una vaca c"""
global visited
visited[c] = True
reached = 1 # siempre podemos alcanzar la vaca inicial c
for nc in range(cow_num):
# nos aseguramos de poder conectar con esta vaca y de que aún no se alcanzó
if not visited[nc] and connected[c][nc]:
visited[nc] = True
reached += reachable_cows(nc)
return reached
max_cows = 0
for c in range(cow_num):
visited = [False for _ in range(cow_num)]
max_cows = max(max_cows, reachable_cows(c))
print(max_cows, file=open("moocast.out", "w"))