Szczegółowe omówienie zadania Moocast:
Link do powyższego omówienia zadania Moocast:
https://youtu.be/UOei4vez6LM?t=1752
Link do treści zadania Moocast:
http://usaco.org/index.php?page=viewproblem2&cpid=668
——
Zadanie Moocast jest zadaniem pokazującym grafy i algorytm DFS.
Co to jest graf? Po co nam grafy?
https://youtu.be/UOei4vez6LM?t=118
–
Chodzimy po grafie – Co to jest DFS?
https://youtu.be/UOei4vez6LM?t=884
–
Graf w C++ – trzymamy graf w komputerze:
https://youtu.be/UOei4vez6LM?t=4090
–
Do trzymania grafu wykorzystujemy wektor:
https://youtu.be/UOei4vez6LM?t=6053
a tak naprawdę tablicę wektorów:
https://youtu.be/UOei4vez6LM?t=6100
Co to jest graf? Po co nam grafy?
https://youtu.be/UOei4vez6LM?t=118
–
Chodzimy po grafie – Co to jest DFS?
https://youtu.be/UOei4vez6LM?t=884
–
Graf w C++ – trzymamy graf w komputerze:
https://youtu.be/UOei4vez6LM?t=4090
–
Do trzymania grafu wykorzystujemy wektor:
https://youtu.be/UOei4vez6LM?t=6053
a tak naprawdę tablicę wektorów:
https://youtu.be/UOei4vez6LM?t=6100
—–
Zadanie Moocast to zadanie z dywizji srebrnej Amerykańskiej Olimpiady Informatycznej USACO – odpowiednika naszej Olimpiady Informatycznej Juniorów (II/III etap).
Daje piękny wpis do CV:
https://youtu.be/K7fZfJ8nN6A?t=6310
https://youtu.be/K7fZfJ8nN6A?t=6310
———-
Link do wszystkich zadań z tej edycji konkursu USACO:
http://usaco.org/index.php?page=dec16results
Dlaczego warto brać udział w Amerykańskiej Olimpiady Informatycznej USACO?
https://youtu.be/K7fZfJ8nN6A?t=6848
https://youtu.be/K7fZfJ8nN6A?t=6848
——–
Jak się uczyć na podstawie tego zadania?
https://youtu.be/QgLyXYmFQeU?t=2019
Pamiętaj by zajrzeć max 1 raz – wtedy się rozwijasz:
https://youtu.be/pkLXuuOe_qA?t=3625
Jak się uczyć na podstawie tego zadania?
https://youtu.be/QgLyXYmFQeU?t=2019
Pamiętaj by zajrzeć max 1 raz – wtedy się rozwijasz:
https://youtu.be/pkLXuuOe_qA?t=3625
——-
–
#include <bits/stdc++.h>
using namespace std;
const int MAX_COWS = 210;
int cows_x[MAX_COWS];
int cows_y[MAX_COWS];
int cows_power[MAX_COWS];
vector <int> graph[MAX_COWS];
bool visited[MAX_COWS];
int act_range;
void DFS_alg (int v) {
int i;
visited[v] = true;
++act_range;
for(i=0; i<graph[v].size(); i++){
if( visited[ graph[v][i] ] == false ){
DFS_alg( graph[v][i] );
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("moocast.in", "r", stdin);
freopen("moocast.out", "w", stdout);
int number_of_cows;
int cows_dist, cows_dist_x, cows_dist_y;
int max_range;
int i, j;
cin >> number_of_cows;
for (i=0; i<number_of_cows; ++i) {
cin >> cows_x[i];
cin >> cows_y[i];
cin >> cows_power[i];
cows_power[i] = cows_power[i]*cows_power[i];
}
for (i=0; i<number_of_cows; ++i) {
for (j=i; j<number_of_cows; ++j) {
cows_dist_x = (cows_x[i]-cows_x[j]);
cows_dist_y = (cows_y[i]-cows_y[j]);
cows_dist = cows_dist_x*cows_dist_x + cows_dist_y*cows_dist_y;
if ( cows_dist <= cows_power[i] )
graph[i].push_back(j);
if ( cows_dist <= cows_power[j] )
graph[j].push_back(i);
}
}
max_range = 0;
for (i=0; i<number_of_cows; ++i) {
for (j=0; j<number_of_cows; ++j) {
visited[j] = 0;
}
act_range = 0;
DFS_alg(i);
max_range = max(act_range,max_range);
}
cout << max_range << "\n";
return 0;
}
Kod C++ programu Moocast, który jest omówiony w powyższym filmie i który otrzymuje 100%