1299. Stefan, co robię źlę?

[mariusz193]

nie, ale w wątku jest informacja jak to zrobić poprawnie
i jest jeszcze kilka innych wątków dla tego zadania, w nich chyba też jest coś ciekawego

[narbej]

Spróbujesz mnie jakoś naprowadzić na dobrą ścieżkę?

Problemem jest tutaj nie to czy użyjesz tablicy czy nie ale jak. Jeżeli wczytasz wszystko [do tablicy] i [tylko] jednorazowo ją “przejrzysz” zmieścisz się w limicie czasu. Ale jeżeli tylko do tego ma służyć tablica, to można sobie wyobraźić, że nie jest konieczna. Możemy od razu, jednorazowo, przeglądnąć wejście, bez zapisywania wszystkiego do tablicy…

Praktyka czyni mistrza, więc na początek popraktykuj na takim, twoim kawałku kodu - popraw go:

    cin>>t;
    for(int a=1; a<=t; a++)
    {
        cin>>tab[a-1];
        suma+=a;
    }

i objaśnij o co tu chodzi, w kontekście tego zadania!?

[baq97]

i objaśnij o co tu chodzi, w kontekście tego zadania!?

Chodzi o zmienną ‘suma’ ?
Trochę się pobawiłem w matematyka i obliczyłem, że wszystkich możliwych przypadków przy n-tej liczbie miast jest 1+2+…+n.

A jeśli chodzi o jednorazowe przejrzenie liczb to muszę się nad tym głębiej zastanowić jak to ma działać. Dzięki narbej za nakierowanie

[narbej]

Tak, ale …
czyż w matematyce [informatyce] nie 1 + 2 + … + n == n * (n+1) / 2

no i przyjżyj się dokładniej samej pętli:

for (int a = 1; a <= t; a++) <-- nie można inaczej, lepiej [chyba, że za bardzo skupiłeś się na zmiennej suma] ,
a potem tab[a] zamiast tab[a-1]j?

W C++ zamiast tablic można i używa się często vektora, więc można:

cin >> t;
vector <int> tab(t);
for (int i = 0; i < t; ++i)
   cin >> tab[i];

lub, też w C++ ale może dopiero w nowszych wersjiach kompilatora:

cin >> t;
vector <int> tab(t);
for (auto &i : tab)
   cin >> i;

… wszystkich możliwych przypadków przy n-tej liczbie miast jest 1+2+…+n.

Tyle, że rozpatrywanie wszystkich przypadków = TLE - przekroczenie limitu czasu.

[baq97]

for (int a = 1; a <= t; a++) <-- nie można inaczej, lepiej [chyba, że za bardzo skupiłeś się na zmiennej suma] ,

a potem tab[a] zamiast tab[a-1]j?

Tutaj chciałem wpisywanie do tablicy oraz sumowanie dać w jednym forze, żeby kodu było mniej.
Dlatego taki a nie inny for.

Co do vectorów, to jeszcze tego nie poznałem, ale na pewno trochę o tym poczytam.

Sugerując się twoim poprzednim postem, napisałem nowy kod. Wydaje mi się, że jest znacznie lepszy, co prawda jeszcze go nie doszlifowałem bo sędzia pokazuje błędną odpowiedź Ale chyba o tym pisałeś prawda?

EDIT:
dodałem

if(zysk<1)
    {
        cout<<"0"<<endl;
        return 0;
    }

[narbej]

Wydaje mi się, że jest znacznie lepszy,

Też mi się tak wydaje, ale nadal masz za dużo razy przeglądanie tablicy.

Musisz wymyśleć taki kod [algorytm] w którym naprawdę tylko raz przeglądasz tablicę od początku do końca. Jeżeli przy wczytywaniu szukasz najlepszego miasta, to traktuję taką sytuację jako pierwsze przeglądanie tablicy. Dlaczego? Bo gdy jest tylko wczytywanie do tablicy, swojego rodzaju bufora, [pojemnika], kompilator prawdopodobnie potrafi to “samodzielnie” zoptymalizować - przy ustawionych opcjach optymalizacji. Gdy przy okazji wczytywania jest coś robione dodatkowo, może być już trochę gorzej.
Przy oddzielnych przeglądaniach od najlepszego w dół , a potem w górę dochodzi, może niewielki, ale jednak koszt zorganizowania pętli, a przy okazji zaciemnia to czytelność kodu. Na początku zakładasz zysk = 0, więc może być on tylko lepszy lub pozostać dalej zerowy, przy poprawnie napisanym kodzie. Nie potrzebne jest więc dodatkowe sprawdzanie, a także [błędne?] zerowanie obliczonego już wcześniej zysku, [w kilku miejscach twojego kodu].

[baq97]

Musisz wymyśleć taki kod [algorytm] w którym naprawdę tylko raz przeglądasz tablicę od początku do końca.

Dziękuję ci niezmiernie za pomoc, sędzia zaakceptował kod.

Poczułem mega ulgę, że w końcu się udało, siedziałem nad tym 5-6 godzin, i zrobiłem 4 albo 5 różnie działających programów, jeszcze raz bardzo Ci dziękuje za pomoc

[narbej]

Powinieneś niestety usunąć link do działającego kodu.

Teraz powinieneś też zauważyć, że tablica jednak nie jest w tym zadaniu niezbędna.

[baq97]

Kod usunięty, a co do tablicy to zorientowałem sie dosyć szybko, ale o dziwo sędzia pokazał czas bez tablicy 0,08 a z tablicą 0,07

[narbej]

ale o dziwo sędzia pokazał czas bez tablicy 0,08 a z tablicą 0,07

Napisałem, tylko że nie jest niezbędna. A że czas się zmienił, to nic dziwnego, raz będzie tak innym razem tak, ale chyba nie chodzi Ci tylko i wyłącznie o czas i o AC?

Jeżeli jednak zależy Ci na czasie, to mozesz dodać linijkę ios::sync_with_stdio (0);
Jeżeli chcesz, mogę Ci wysłać “wygładzony” twój kod na priv.

[baq97]

Jeżeli chcesz, mogę Ci wysłać “wygładzony” twój kod na priv.

Nie trzeba jestem początkującym programistą, wystarczy mi zwykłe AC

[mariusz193]

zobacz wynik dla danych, gdzie będziesz miał 50000 miast, każde 100000 (oczywiście łatwiej 5 miast po 1000000000, dane niezgodne e specyfikacją wejścia, ale wynik ten sam)

[ag_90]

rozumiem, że przekracza zakres long long inta ale w takim razie jak to obejść skoro na long double również testów nie przechodzi

[tarpauwatratar]

rozumiem, że przekracza zakres long long inta ale w takim razie jak to obejść skoro na long double również testów nie przechodzi

Myślę, że właśnie udało Ci się znaleźć na czym polega trudność tego zadania

PS1
A od kiedy long double można używać kiedy long long int nie działa? Toż to chyba jakiś zelentyzm…

PS2
Twój algorytm przechodzi np po zastosowaniu BigIntów (przynajmniej tych mojego autorstwa). Pytanie, czy potrzebujesz takiej klasy, zostawiam otwarte

[ag_90]

Właśnie dostałem accept, dzięki za pomoc.
btw poprzedni pomysł z long double też by przeszedł tylko skrócony wynik gryzł się z oczekiwanym przez sprawdzarkę wystarczyło ustawić precyzję.

[mariusz193]

rozumiem, że przekracza zakres long long inta ale w takim razie jak to obejść skoro na long double również testów nie przechodzi

proponuję, abyś zapoznał się z zakresami i dokładnością typów w C/C++, jest to omówione na początku każdego dobrego podręcznika C/C++ - a te informacje przydadzą CI się jeszcze wiele razy przy rozwiązywaniu zadań na spoj-u.

[niedzwiedz89]

Czesc, siedze juz jakis czas nad tym kodem i nie moge wymyslec gdzie robie błąd- proszę o jakąś wskazówke. Dopiero zaczynam przygode z C++ stąd proszę o wyrozumiałość - z góry dzięki za wsparcie.

Ideone.com

[tarpauwatratar]

Test:

9
-1
-2
-3
10
-100
1
2
3
-10

[niedzwiedz89]

Poprawiłem ale dalej dostaje błąd wrrrr… Czy mogę prosić o jeszcze jedną wskazówkę?

Ideone.com

PS.Dzięki za pomoc

[tarpauwatratar]

Twój kod jest strasznie skomplikowany jak na coś co można rozwiązaćw trzech liniach… Może zamiast usilnie poprawiać ten algorytm:

1. zapoznaj się z funkcją max
2. zapoznaj się z algorytmem Kadane (rozwiązanie tego problemu strasznie mi przypomina ten algorytm)
3. pomyśl nad tym problemem wykorzystując wiedzę z 2)

Myślę, że da Ci to dużo więcej teraz i w przyszłości niż poprawianie obecnego kodu.