Nov 2016
1 / 49
Nov 2016
Feb 2024
aku
Nov '16

http://ideone.com/1yb2rj29
Przechodzi podane testy, mimo to zwraca WA.
Czy ktoś orientuje się w czym może być problem?

#include <iostream>
 
long int  nNWD(long int nLiczba1, long int nLiczba2) 
{
	long int c=0; 
	while(nLiczba2!=0)
	{
		c=nLiczba1%nLiczba2;
		nLiczba1=nLiczba2;
		nLiczba2=c;
	}
	return nLiczba1;
}
 
 
int main()
{
	int nLiczbaZestawow;
 
	std::cin>>nLiczbaZestawow;
 
	long int nWymiarPierwszy, nWymiarDrugi; 
 
	for(int i=1; i<=nLiczbaZestawow; i++) 
	{
		std::cin>>nWymiarPierwszy>>nWymiarDrugi;
		std::cout<<nNWD(nWymiarPierwszy, nWymiarDrugi)<<std::endl;
	}
 
	return 0;
}

  • created

    Nov '16

  • last reply

    Feb '24
  • 48

    replies

  • 2.5k

    views

  • 18

    users

  • 17

    likes

  • 12

    links

mariusz193
Nov '16

tak, ja się orientuję :slight_smile:

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

8 months later
i6g7g6y5
Jul '17

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.

dtk7c2
Jul '17

"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?

i6g7g6y5
Jul '17

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?

8 days later
markoyee
Jul '17

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

loginus
Jul '17

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 .

narbej
Jul '17
markoyee

to:

        while (a%i!=0)
        {
            i--;
        }

jest głównym "winowajcą" i powodem tle [time limit ...] - za wolno..

7 months later
5 months later
konradu99
Aug '18
1

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

fulse
Aug '18

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.

konradu99
Aug '18

@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ź…

fulse
Aug '18

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

fulse
Aug '18
1

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++;

konradu99
Aug '18

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? :wink:

fulse
Aug '18

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 ?

konradu99
Aug '18

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.