Moocast – Omówienie zadania z Amerykańskiej Olimpiady Informatycznej USACO

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

—–
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

———-
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
——–
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%

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz