Mam takie zadanie:
Podróżnik
Limit pamięci: 16 MB
Podróżnik Bajtonson wrócił właśnie z kolejnej podróży w nieznane. Z oczywistych względów nie mógł wspomagać się mapą, więc notował jedynie, w którą stronę podróżuje. Dlatego zawsze po pokonaniu kilometra notował kierunek, w jakim się poruszał - N, S, E lub W (odpowiednio północ, południe, wschód lub zachód).
Jako że w notesie było niewiele miejsca, podróżnik korzystał ze skrótów np. 10 NSSW oznaczało, że Bajtonson 10 razy powtórzył sekwencję "1 km na północ, 2 km na południe, 1 km na zachód". W miejscu, w którym kończył dany odcinek trasy (opisany skrótem), zaczynał następny.
Po powrocie do domu, podróżnik zapragnął narysować mapę swoich podróży. Zdecydował, że każdemu kilometrowi jego podróży będzie odpowiadał jeden centymetr na mapie. Teraz potrzebuje kupić odpowiedni arkusz papieru, nie jest jednak w stanie ocenić, jak dużego arkusza będzie potrzebował. Dlatego poprosił Ciebie, swojego asystenta, o napisanie programu, który przetworzy zapiski z podróży i wyznaczy wymiary najmniejszego (pod względem pola powierzchni) arkusza, na którym zmieści się trasa Bajtonsona.
Oczywiście - jak każda mapa - mapa Bajtonsona musi być prostokątem o bokach równoległych do osi północ-południe i wschód-zachód.
Wejście
Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą n (1 <= n <= 1000). W następnych wierszach opisane są kolejne etapy podróży Bajtonsona. W i-tym z tych wierszy znajduje się liczba całkowita k(1 <= k <= 20 000) a po odstępie niepusty ciąg znaków złożony z liter N, S, E i W. Taki zapis oznacza, że w ramach i-tego etapu Bajtonson k razy powtórzył podaną sekwencję kierunków. Liczba znaków N, S, E i W na wejściu nie przekroczy 1 000 000.
Wyjście
Twój program powinien wypisać na standardowe wyjście dwie liczby całkowite oddzielone pojedynczym odstępem: wysokość i szerokość najmniejszego arkusza, na którym zmieści się trasa podróżnika, wyrażone w centymetrach. Możesz założyć, że obie liczby będą nie większe niż 1 000 000 000.
Przykład
Dla danych wejściowych:
3
3 NSSW
1 ES
10 E
poprawną odpowiedzią jest:
5 11
No i ma algorytm
#include <bits/stdc++.h>
using namespace std;
void reset(vector<long long> & tab){
for (int i = 0; i < tab.size(); i++)
tab[i] = 0;
}
void uaktualnij_max_now(vector<long long> & max_now, pair<long long, long long> & akt_poz){
max_now[0] = max(max_now[0], akt_poz.second);
max_now[1] = min(max_now[1], akt_poz.second);
max_now[2] = max(max_now[2], akt_poz.first);
max_now[3] = min(max_now[3], akt_poz.first);
}
void uaktualnij_max_all(vector<long long> & max_all, vector<long long> & max_now, pair<long long, long long> & poz, pair<long long, long long> & akt_poz, int k){
max_all[0] = max(max_all[0], max(max_now[0] + poz.second, poz.second + akt_poz.second * k));
max_all[1] = min(max_all[1], min(max_now[1] + poz.second, poz.second + akt_poz.second * k));
max_all[2] = max(max_all[2], max(max_now[2] + poz.first, poz.first + akt_poz.first * k));
max_all[3] = min(max_all[3], min(max_now[3] + poz.first, poz.first + akt_poz.first * k));
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
vector<long long> max_now(4, 0); // N, S, E, W
vector<long long> max_all(4, 0); // N, S, E, W
int n, k;
pair<long long, long long> akt_poz, poz;
string kierunki;
poz = make_pair(0, 0);
cin >> n;
for (int i = 0; i < n; i++){
cin >> k >> kierunki;
reset(max_now);
akt_poz = make_pair(0, 0);
for (char kier : kierunki){
if (kier == 'N')
akt_poz.second++;
else if (kier == 'S')
akt_poz.second--;
else if (kier == 'E')
akt_poz.first++;
else
akt_poz.first--;
uaktualnij_max_now(max_now, akt_poz);
}
uaktualnij_max_all(max_all, max_now, poz, akt_poz, k);
poz.first += akt_poz.first * k;
poz.second += akt_poz.second * k;
}
reset(max_now);
uaktualnij_max_all(max_all, max_now, poz, akt_poz, 0);
cout << max_all[0] - max_all[1] << " " << max_all[2] - max_all[3];
return 0;
}
Działa to tak że sprawdza maksymalne odchylenie w każdej sekwencji dla wszystkich kierunków, a następnie porównuje czy w którymś momencie odchylenie nie było większe niż te które mamy już zapisane, program przechodzi wszystkie testy z "Wstępnego sprawozdania" ale z końcowego wszystkie są błędne, przykładowy dane dla których mój program daje błędną odpowiedź to:
10
10 WENWE
28 WSWWW
15 SWWEN
24 NNNNE
13 NNNNNSEEEN
30 EEEWS
10 NNWWW
11 NNWNN
24 ESNEW
21 NSSNS
I tutaj znalazłem coś dziwnego, mój program odpowiada 197 127, a według sprawdzarki powinno być 197 128 co jest bardzo dziwne bo analizując te dane maksymalną wartość jaką może uzyskać y to 0, a minimalna dla y to -127, w następnych testach mój program myli się tylko o kilka jednostek. Gdzie robię błąd ?
LINK DO ZADANIA
TUTAJ TESTUJE