Szczegółowe omówienie zadania Modern Art 2 z dywizji Gold Amerykańskiej Olimpiady Informatycznej USACO:
–
Link do zadania:
Link do zadania:
–
Zadanie wymaga jedynie pomysłu i jest świetnym przygotowaniem do Olimpiad i konkursów informatycznych.
——-
Poniżej kod wzorcowy zadania “Modern Art 2” użyty w powyższym omówieniu.
–
#include <bits/stdc++.h>
using namespace std;
const int MAX_PIXELS = 1e5+7;
int pixels[MAX_PIXELS];
int colors_start[MAX_PIXELS];
int colors_end[MAX_PIXELS];
int pixel_stack[MAX_PIXELS];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("art2.in", "r", stdin);
freopen("art2.out", "w", stdout);
int number_of_pixels;
int max_depth;
int stack_depth;
int i;
cin >> number_of_pixels;
for (i=1; i<=number_of_pixels; ++i) {
cin >> pixels[i];
if ( colors_start[ pixels[i] ] == 0 ) {
colors_start[ pixels[i] ] = i;
}
colors_end[ pixels[i] ] = i;
}
number_of_pixels += 2;
colors_start[0] = 0;
colors_end[0] = number_of_pixels-1;
stack_depth = max_depth = 0;
for (i=0; i<number_of_pixels; ++i) {
if (colors_start[ pixels[i] ] == i) {
pixel_stack[stack_depth] = pixels[i];
++stack_depth;
max_depth = max(max_depth,stack_depth);
}
if (colors_end[ pixels[i] ] == i) {
--stack_depth;
if (pixel_stack[stack_depth] != pixels[i]) {
cout << "-1\n";
return 0;
}
}
}
--max_depth;
cout << max_depth;
return 0;
}
Link do pobrania pliku z kodem C++ zadania "Modert Art 2"