7988 Działka [MWP3_1C1]

Nie każdy prostokąt jest kwadratem, ale każdy kwadrat jest prostokątem.

Odpowiedzią dla np:
13 13
czy
21 21
nie jest wcale 13
czy 21

Napisałem program, ale od dłuższego czasu nie jestem w stanie go skutecznie zoptymalizować - sędzia zgłasza przekroczenie limitu czasu.
Oczywiście zapoznałem się z postami wyżej, np.

tak jak w powyższym cytacie nie szukam NWD za pomocą Brute Force, a staram się mój ,counter" maksymalnie ,zniżyć" za pomocą warunków (wszystko widoczne jest w kodzie).
Dodatkowo, do testowania programu użyłem ok. 350 zestawów danych - wygenerowanych w Excelu (w tym zestwy z powyżej), co w mojej opinii jest wystarczające do przetestowania.

Mój kod załączam tu:
https://pastebin.com/RvJm9SGJ9

Poproszę o wskazówkę
Dziękuję

Pierwsza sprawa:
Po co w ogóle Ci tablica? Załóżmy, że masz do napisania program co wyznacza sumę liczb podanych na wejściu (na początku jeszcze liczba zestawów).
Twój program by wyglądał:

...
cin >> data;
for (int i = 0; i < data; ++i) {
cin >> tablica[i][0] >> tablica[i][1];
}
for (int i = 0; i < data; ++i) {
cout << tablica[i][0] + tablica[i][1];
}

Podczas gdy powinien wyglądać tak:

...
cin >> data;
for (int i = 0; i < data; ++i) {
cin >> a >> b;
cout << a + b;
}

Inaczej mówiąc: nie tabelaryzuj tych danych tylko po to by po nich przejsć. Po prostu operuj na nich przy wczytywaniu.

Druga sprawa:
W twoim kodzie jest: jeśli A==B to weź max(A,B)/2. Po co ten max skoro są równe?

Trzecia sprawa:
Czy na pewno chcąc sprawdzić czy liczba się przez coś dzieli musisz brać counter liczący (w dół) od mniejszej z nich? Wydaje mi się (nie wydaje mi się, tak z grzeczności piszę), że można sprawdzić o wiele mniejszy zbiór kolejnych dzielników.

Czwarta sprawa:
Masz jakiś błąd wykonania:
błąd7

Same odpowiedzi wyglądają poprawnie.

Dziękuję za odpowiedź!
Poprawiłem następujące punkty: 1, 2 i 4.
Co do trzeciej sprawy - niekiedy (szczególności dla małych wartości <20) zachodzi własność, że wynik A%B często jest równy dugości boku kwadratu. Ale problem jest już znaczący przy liczbach >10^5, gdy przykładowo A%B = 1456, a bok kwadratu wyniesie np. 5. Wówczas algorytm musi ,piłować " w dół do 5. Z kolei stosując algorytm liczący ,w górę" będzie musiał przejść cały przedział, by odnaleźć maksymalnie duży kwadrat (chodzi mi o to, że znajdzie kwadrat dla 1, 5, 7, … ale i tak będzie musiał liczyć, aż do A%B, by sprawdzić, że np dla 1000 nie zachodzi optymalniejszy warunek).
W każdym razie dziękuję i będę dalej próbować. Skoncentruję się by ten zakres jeszcze bardziej zawężyć.

Ciekawe jest Twoje podejście (w sensie rozkmina zadania). Tak, są takie przypadki, ale stwierdzenie, że trzeba będzie sprawdzić cały zakres <0,1175> jest nieprawdziwe. Dla przypadku 37600 36425 kilkoma obliczeniami da się dojść do wartości 1175, a gdyby warunek sprawiający “korzystność” tego przypadku nie występował to i tak bym sprawdził zaledwie <2,~200> (nie znaczy, że wynik będzie w tym przedziale), ale to już wystarczająco się nagadałem. Teraz kombinuj.

Minęło kilka dni i w mojej ocenie zoptymalizowałem kod maksymalnie.
Tj. zastosowałem ulepszony alg. Euklidesa a nie klasyczny alg, a także rozpatrzyłem oddzielny przypadek dla kwadratu, by maksymalnie proces przyśpieszyć.
Tu jest mój kod:

Jest miejsce na optymalizację dla fragmentu:

    while(b%(a/counter)!=0)
        counter++;
    a = a/counter;

Dla liczby pierwszej (a=b=duża liczba pierwsza) pętla while wykona się mniej więcej a/2 razy. To jest wciąż za dużo razy.

Dzięki wielkie pawoj20 i redysz, poprawiłem i zaakceptowało mi
Życzę powodzenia pozostałym i wytrwałości, sam bym zakwalifikował to zadanie jako średnie.

Witam. Napisałem program do tego zadania, działa w visual studio 2019 i w codeblocks, a na Ideone dla pewnych konkretnych przypadków nie działa, nie rozumiem dlaczego. Może za słabo rozumiem rekurencję, porobiłem “Print it” i rezultat też mnie zadziwił. Oto kod, z góry dziękuję za wyjaśnienie/rozjaśnienie:) https://ideone.com/xPWmmV7

1. Jeśli masz VS to zapewne masz też / możesz mieć łatwo debugger. Warto z niego skorzystać. Ja mam się gorzej, bo nigdy nie chce mi się ogarniać na SPOJa armat większych niż Vim i kompilator.

2. Jeżeli argument przekazany do funkcji nie jest modyfikowany, oznaczaj go jako const. Taka drobna poprawka jakościowa i dobry nawyk na przyszłość. Np:

   NWD(const int Liczba1, const int Liczba2)
   

3. zaprzyjaźnij się z assertem. Pomaga przy debuggowaniu na SPOJu. Aczkolwiek nie w tym przypadku - również uwaga ogólna. Na start IFy są jak najbardziej ok, by się sprawdzić i pozytywnie zaskoczyć, że kod działa. Ale z czasem zarządzanie nimi staje się męczące. I nieprofesjonalne.

4. W tym przypadku wskazane jest, żebyś rozpisał na kartce co się dzieje w kodzie krok po kroku. Trochę to zajmie, ale łatwo namierzysz błąd. W 16 linii. Co robisz ze zwracanym wynikiem?

No tak, przecież funkcja rekurencyjna musi wrócić z zagnieżdżenia Assert jak zrozumiałem jest bardziej rozbudowaną metodą printit? A czego lepiej używać zamiast ifów ?

"Niestety, Pan Jan nie jest mocny z matematyki …"i dla niego, kwadrat, to też prostokąt ;-). A może odwrotnie, to matematycy nie potrafią odróżnić kwadrata od prostokąta?

Jak nie musisz, nie używaj endl’a. Lepiej '\n'
Ja raczej deklaruję zmienne, przed (poza) pętlą…

Zapamiętam assert, jako bajer na przyszłość Dzięki cout mogę łatwo wyświetlić wartość zmiennych, i nr linii też. Ale warto uczyć się nowych rzeczy więc skorzystam. A te ify w main to nie były do debugu, na początku pomyślałem że NWD nie działa jeśli drugi argument jest większy niż pierwszy.
A dlaczego lepsze ‘\n’ niż endl? Co do zmiennych, w tym przykładzie akurat to nie ma znaczenia, ale często w takiej pętli “testów” zapominałem zerować jakieś zmienne i kolejne testy były nie poprawne. A tak się same zerują. Jeśli mamy zagnieżdżoną pętlę for(), to “j” w wewnętrznej pętli też jest wiele razy(dokładniej “i” razy ) inicjowane.

Miałeś SIGABORT? (sigsegv)
Masz przekroczenie limitu czasu?
Będziesz miał WA - błędną odpowiedź.
Więc po prostu skorzystaj z podpowiedzi

Inicjowanie == zerowanie !? ?! No no

Miałem sigsegv przez głupotę którą wskazał mr. T, limit czasu oczywiście też, ale jakieś zadania z dzielnikami na spoju już rozwiązałem, i przypomniało mi się jak to skrócić (w czasie). I oczywiście masz rację, inicjacja nie żeruje zmiennych, chyba że dopisze się do niej =0. A jeśli Wynik+=Podwynik to chyba trzeba ją tak zainicjować, i wtedy nie trzeba pamiętać o żerowaniu jej na końcu pętli. Nie wiem czy to dobrze czy źle, dopiero się uczę, to chyba widać. Tak samo nie wiem dlaczego lepiej używać /n niż endl. Wiem że czepiam się szczegółów, co potrafi być irytujące, ale uważam je za ważne, tym bardziej w kodowaniu🙂

https://duckduckgo.com/?t=ffab&q=different+endl+'%2Fn'&ia=web3