Painting the Barn – Omówienie zadania z Amerykańskiej Olimpiady Informatycznej USACO

Painting the Barn – Omówienie zadania z Amerykańskiej Olimpiady Informatycznej USACO

Szczegółowe omówienie zadania Painting the Barn:

Link do powyższego omówienia zadania Painting the Barn:
https://youtu.be/K7fZfJ8nN6A?t=6451
Pełne omówienie zadania Painting the Barn:
https://youtu.be/K7fZfJ8nN6A?t=1805

——-
Link do treści zadania Painting the Barn:
http://www.usaco.org/index.php?page=viewproblem2&cpid=919
——
Zadanie Painting the Barn realizuje podejście w algorytmice “na później”:
https://youtu.be/K7fZfJ8nN6A?t=23
—–

Zadanie Painting the Barn 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://www.usaco.org/index.php?page=feb19results

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_DIMENSION = 1e3; //1 i 3 zera 1000
int barn[MAX_DIMENSION+7][MAX_DIMENSION+7];

int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

 freopen("paintbarn.in", "r", stdin);
 freopen("paintbarn.out", "w", stdout);

int number_of_rect, k;
 int lower_left_x, lower_left_y, upper_right_x, upper_right_y;
 int area_of_k_colours;
 int x,y;
 int i;

 cin >> number_of_rect >> k;

 for (i=1; i<=number_of_rect; ++i) {
    cin >> lower_left_x >> lower_left_y;
    cin >> upper_right_x >> upper_right_y;
    ++barn[lower_left_x][lower_left_y];
    --barn[upper_right_x][lower_left_y]; 
    --barn[lower_left_x][upper_right_y];
    ++barn[upper_right_x][upper_right_y]; 
 }   

 area_of_k_colours = 0; 
 for (y=0; y<=1000; ++y) {
    for (x=0; x<=1000; ++x) {
       if ( (x!=0) && (y!=0) )
          barn[x][y] = barn[x][y] - barn[x-1][y-1];
       if (barn[x][y] == k) 
       	  ++area_of_k_colours;       
	   barn[x+1][y] = barn[x+1][y] + barn[x][y];
	   barn[x][y+1] = barn[x][y+1] + barn[x][y];    	
    }
 }    	

 cout << area_of_k_colours << "\n";

 return 0;
}
Kod C++ programu Painting the barn, który jest omówiony w powyższym filmie i który otrzymuje 100% 

 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz