tak, ja się orientuję

problem leży w zrozumieniu treści zadania (autor był złośliwy)

Co oznacza, że autor był złośliwy?
Mam ten sam problem - myślałem, że NWD wystarczy, a wygląda na to, że jednak nie.

"Złośliwy" to lekka przesada, w końcu autor napisał wszystko co potrzebne w treści zadania bez ukrytych między wierszami haczyków. Mała podpowiedź ode mnie: a co jeśli działka nie jest prostokątem?

Dobra, w końcu ogarnąłem o co chodzi...
Ale po co te zagadki na forum?
Nie można od razu powiedzieć, że chodzi o kwadrat?

a chcesz zadanie rozwiązać, czy tylko znać odpowiedź ?

Witam, zastanawiam się nad tym zadaniem i obmyśliłem taki algorytm:
1. sprawdzam, czy działka nie jest kwadratem:
-> jeżeli jest kwadratem to znajduje największy dzielnik liczby mniejszy od niej samej żeby jednak podzielić na jak największe części tą działkę.
->jeżeli nie jest kwadratem to rekurencyjnie liczę NWD

Akceptacji nie ma, w komentarzu jest że odpowiedź za wolna.
może ktoś zerknąć na kod ? ewentualnie podpowiedzieć czy coś źle zrozumiałem ? albo czy źle podchodzę do tego zadania ?
tu jest mój kod
https://ideone.com/gqYEvG69

Rekurencja !!! -- naprawde !!! -- really !!!

1. Rekurencja to chyba jedna z najwolniejszych metod . Każde odwołanie to wrzucenie na stos całej masy danych co jest kosztowne . Do tego może się zdarzyć że zabraknie prędzej pamięci niż znajdziesz rozwiązanie . NASA podobno zakazuje stosowania rekurencji w algorytmach które obsługuje sprzęt w kosmosie .

2. Nazwanie funkcji "rekurencja" to nie najlepszy pomysł - lepiej ją nazwać NWD lub GCD - od razu wiesz co ten kawałek kodu robi .

3. Ja to zadanie zrobiłem z użyciem SITA - generuje tablice w której dla indeksów liczb pierwszych wstawiam jeden a dla pozostałych najmniejszy dzielnik danej liczby ( indeksu ). Dla takiej metody tylko raz ustalasz która liczba jest pierwsza . Sprawdzenie na jakie kwadraty podzielić działkę to sprawdzenie jednej zmiennej z SITA .

Witam. Mógłbym się spytać gdzie jest błąd?
>Tu był kod<
Pozdrawiam.

1
999983	 999983

Dzięki. Zaliczone.

Hej, mógłby ktoś zobaczyć, co jest nie tak, podać dodatkowe testy itp…

Po zastanowieniu nasz bohater doszedł do wniosku, że owszem podziału trzeba dokonać, ale powstałe kwadratowe pola powinny być jak największe.

Musi być podział, dlatego to:

if(a==b)
{
cout << a << endl;
}

nie ma sensu.

@fulse dzięki za podpowiedź, rzeczywiście to nie ma sensu, bo dla kwadratu działa, ale po zrobieniu tej korekty dalej daje błędną odpowiedź…

Ja też dalej szukam jak znajdę to dam jakąś wskazówkę

in
1
6127 6127

out
557

@konradmal
Uwaga na liczby pierwsze oraz na szukanie dzielnika w taki sposób:

i = 2;
while( a % i != 0 )
i++;

Właśnie sprawdziłem test 6127 6127 i zarówno na ideone, jak i u mnie w Dev-C++ out wynosi 6127… Co do liczb pierwszych, to możesz mi powiedzieć coś więcej? Bo wg. mnie ten program działa na liczby pierwsze poprawnie?

Z liczbą pierwszą chodziło mi o taki przypadek:
1
10007 10007
lub
1
13 13

Jaka będzie maksymalna długość boku działki kwadratowej w tej działce ?

Dla dwóch takich samych liczb pierwszych właśnie ta liczba pierwsza. Tyle, że program taką odpowiedź zwraca. Zresztą dla każdego kwadratu odpowiedzią jest właśnie bok tego kwadratu.

Ach rozumiem… Spróbuję coś z tą wiedzą zrobić i później dam znać, co mi wyszło!

Parę ciekawszych testów (wyniki różne od 1) do kontroli

In

32
530 795
539 847
442 425
667 828
980 360
716 358
624 768
740 200
665 490
341 713
186 589
684 804
693 396
803 803
38 874
350 854
182 468
525 945
468 576
343 735
104 663
13 962
145 174
960 840
714 483
325 117
627 304
507 247
803 803
570 228
506 836
112 784

Mój out:

265
77
17
23
20
358
48
20
35
31
31
12
99
73
38
14
26
105
36
49
13
13
29
120
21
13
19
13
73
114
22
112

Ok, to znowu ja, byłem akurat poza domem przez kilka ostatnich dni, troszkę poprzerabiałem i w końcu zaakceptowało. Dzięki Wam za pomoc!

https://ideone.com/UnQbsM23

Witam,
mam problem z zadaniem MWP3_1C1 - Działka. Mój kod zwarca poprawne wartości, ale sędzia nie chce tego zaakceptować. Stosowałem rózne wskazówki do tego kodu, które znalazłem w internecie lub na tym forum, jednakże sędzia dalej jest nieugięty. Miałbym prośbę, o w miarę możliwości przejrzenie mojego kodu.

Pozdrawiam
Tomasz

in:
2
2 2
803 803
etc.
Tj. gdy a == b jest błąd, zadanie dopuszcza chyba i takie przypadki. Mowa o prostokącie ale kwadrat to też prostokąt.

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ć.

I jeszcze taki przykład 37600%36425=1175 i właśnie 1175 jest największym możliwym bokiem kwadratu. Tak więc, jak nadmieniłem, w niektórych przypadkach, trzeba będzie sprawdzić cały zakres <0,1175>

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ą…