Wystarczy zapytać chatbota po co się męczyć:
ja:
Napisz program w C++ rozwiązujący poniższy problem:
Stolica Bajtocji jest aktualnie bombardowana, a do centrum dowodzenia napływają informacje o zniszczeniach.
Terytorium Bajtocji można przedstawić na mapie jako prostokąt o wymiarach n na m i wierzchołkach w punktach (0, 0), (n, 0), (n, m), (0, m).
Każda informacja o zniszczeniu składa się z czterech liczb całkowitych x1, y1, x2, y2, oznaczających, że prostokątny obszar o przeciwległych wierzchołkach w punktach (x1, y1), (x2, y2) został zbombardowany, a w efekcie całkowicie zniszczony. Twoim zadaniem jest podać ile km2 Bajtocji zdołało ostatecznie ocaleć.
Wejście:
W pierwszym wierszu standardowego wejścia znajdują się trzy liczby całkowite n, m, q (1 <= n, m <= 10^3, 1 <= q <= 10^6), oznaczające odpowiednio wymiary Bajtocji i liczbę raportów o zniszczeniach.
W kolejnych q wierszach znajdują się opisy zniszczeń, składające się z liczb całkowitych x1, y1, x2, y2 (x1 < x2, y1 < y2, 0 <= x1, x2 <= n, 0 <= y1, y2 <= m), oznaczających, że prostokątny obszar o wierzchołkach w punktach (x1, y1), (x2, y2) został całkowicie zniszczony.
Wyjście:
Należy wypisać jedną liczbę całkowitą - powierzchnię ocalałego obszaru
chatGPT:
#include <iostream>
using namespace std;
const int MAX = 1003;
int n, m, q, x1, y1, x2, y2, area = n * m;
bool map[MAX][MAX];
int main() {
cin >> n >> m >> q;
area = n * m;
for (int i = 0; i < q; i++) {
cin >> x1 >> y1 >> x2 >> y2;
for (int x = x1; x < x2; x++) {
for (int y = y1; y < y2; y++) {
if (!map[x][y]) {
map[x][y] = true;
area--;
}
}
}
}
cout << area << endl;
return 0;
}
Ten program rozwiązuje problem, otrzymując dane wejściowe z pierwszego wiersza standardowego wejścia (wymiary Bajtocji i liczbę raportów o zniszczeniach), a następnie pobierając dane z kolejnych q wierszy wejścia (opisujące zniszczenia). Tworzy mapę Bajtocji jako tablicę dwuwymiarową bool map[MAX][MAX], gdzie MAX jest stałą oznaczającą maksymalny rozmiar mapy. W pętli for jest iterowane przez liczbę raportów o zniszczeniach, pobierając x1, y1, x2, y2 z wejścia i oznaczając obszar jako zniszczony na mapie (map[x][y] = true).
Jeśli obszar jest oznaczony jako zniszczony pierwszy raz, zmniejsza się zmienna area o 1. Po zakończeniu pętli program wyświetla liczbę całkowitą - powierzchnię ocalałego obszaru.
ja:
zoptymalizuj ten program używając sum prefiksowych
chatGPT:
#include <iostream>
using namespace std;
const int MAX = 1003;
int n, m, q, x1, y1, x2, y2, area = 0;
int map[MAX][MAX];
int main() {
cin >> n >> m >> q;
area = n * m;
for (int i = 0; i < q; i++) {
cin >> x1 >> y1 >> x2 >> y2;
map[x1][y1]++;
map[x2][y2]++;
map[x1][y2]--;
map[x2][y1]--;
}
for (int x = 0; x < n; x++) {
for (int y = 0; y < m; y++) {
map[x][y] += map[x - 1][y] + map[x][y - 1] - map[x - 1][y - 1];
if (map[x][y])
area--;
}
}
cout << area << endl;
return 0;
}
Ten program rozwiązuje problem używając sum prefiksowych. Tworzy mapę Bajtocji jako tablicę dwuwymiarową int map[MAX][MAX], gdzie MAX jest stałą oznaczającą maksymalny rozmiar mapy. W pętli for jest iterowane przez liczbę raportów o zniszczeniach, pobierając x1, y1, x2, y2 z wejścia i zwiększając map[x1][y1] oraz map[x2][y2], a następnie zmniejszając map[x1][y2] oraz map[x2][y1].
Następnie program iteruje po całej mapie, sumując map[x][y] z map[x-1][y] + map[x][y-1] - map[x-1][y-1] i jezeli map[x][y] jest różne od 0 area--;
Po zakończeniu pętli program wyświetla liczbę całkowitą - powierzchnię ocalałego obszaru.
czy nauka algorytmów ma jeszcze sens?
nie wiem tylko czemu MAX=1003 ale pewnie błędnie uznało że 10^3 to 1003
w sumie rozwiązanie banalne jak już się je widzi
//
Kazałem mu jeszcze zoptymalizować pod kątem pamięci ale zaczęło wypluwać nieprawidłowe kody z jednowymiarową tablicą, w końcu się zakręciło w miejscu i stwierdziło że lepiej będzie na dwuwymiarowej i wypluło z powrotem powyższy kod.
// edit 2:
nie jednak nie stwierdziło że 10^3 to 1003 bo podając mu 1000000 podstawił 1000003. widocznie uważa że dodanie 3 jest w dobrym guście. A może to taki watermark AI żeby nie oszukiwać na konkursach algorytmicznych?