6441. Prostokąty

aku · Nov '16

17 http://ideone.com/jhqkJa17 Przechodzi test 100 50 105 9, a mimo to WA.

#include <iostream>
#include <cmath>

void vCzyDrugiMiesciSieWPierwszym(int A, int B, int C, int D)// funkcja sprawdza czy drugi prostokat o podanych bokach miesci sie w pierwszym(nie dotykajac jego bokow) o podanych bokach i wypisuje TAK lub NIE
{
		// ponizsze dwie instrukcje sortuja boki prostokatow w rosnaco
		if(A>B)
		{
			int zmiennaPomocnicza;
			zmiennaPomocnicza=A;
			A=B;
			B=zmiennaPomocnicza;
		}
		if(C>D)
		{
			int zmiennaPomocnicza;
			zmiennaPomocnicza=C;
			C=D;
			D=zmiennaPomocnicza;
		}

	if(C<A && D<B)
		std::cout<<"TAK\n";
	else if( D>B && A>((2*D*C*B+(D*D - C*C)*sqrt(D*D+C*C -B*B))/(D*D +C*C)) )
    	std::cout<<"TAK\n";
	else
		std::cout<<"NIE\n";
}

int main()
{
	int nLiczbaTestow;
	std::cin>>nLiczbaTestow;

	int A, B, C, D;
	for(int i=1; i<=nLiczbaTestow; i++)
	{
		std::cin>>A>>B>>C>>D;
		vCzyDrugiMiesciSieWPierwszym(A, B, C, D);
	}

	return 0;
}

aku · Nov '16

Zaimplementowane rozwiązanie: 92 http://www.jstor.org/stable/2691523?seq=1#page_scan_tab_contents92

Ktoś ma jakiś pomysł co tu może nie działać?

konradni · Jul '17

Witam!

Mam pytanie o to jak mógłbym jeszcze przyśpieszyć swój program napisany w javie.
Oto link: http://ideone.com/JgdBFw41

narbej · Jul '17

Perzepisać w C/C++ ?

write.flush(); jest w złym miejscu.

Stosujesz zamianę a z b, ale do tego służy funkcja swap i jest chyba szubsza, od twojej metody?
w skrócie:
swap(a, b)
///// if (a warunek b)
tmp = a
a = b
b = tmp

Na moje oko, masz tam za dużo warunków-sprawdzań i przez to gubisz jeszcze jeden potrzebny. Mimo takich poprawek, już nie TLE, ale WA, więc może zły lub źle użyty wzór?

Co do wzoru, to napisałem już sądzę wystarczająco na ten temat w wątku: http://discuss.spoj.com/t/czy-spoj-forum-pomaga-w-pisaniu-dobrych-podpowiedzi/23397/14

redysz · Jul '17

Polecam nie używać wzoru. Siedziałem od wczoraj i zaimplementowanie wszystkich warunków (które nie jest trudno wymyślić) wystarczyło. Natomiast sam wzór (tylko wzór) nie wystarcza.

anikou · Jul '17

Dobry wieczór,
zmagam się z tym problemem już czwarty dzień z kolei i wyczerpałem wszystkie pomysły co mogło być nie tak. Znalazłem równanie, znalazłem wymagane warunki, wszystko na nic.
Bardzo proszę o wskazówki gdzie popełniam błąd. Dodam, że program przechodzi pozytywnie wszystkie testy.

#include <iostream>
#include <math.h>

using namespace std;

int main()
{
    int test;
    cin >>test;
    string answer[test];
    for(int i=0;i<test;i++)
    {
    int a=0,b=0,c=0,d=0,tmp=0;
    cin>>a>>b>>c>>d;
    if (a<b ){tmp=a; a=b; b=tmp;}
    if(c<d){tmp=c;c=d;d=tmp;}
    if (c+d>a+b) answer[i]="NIE";
    else if (c*d>a*b) answer[i]="NIE";
    else if (c*c+d*d>a*a+b*b) answer[i]="NIE";
    else if ((a+b-(a-b))/2<(c+d-(c-d))/2) answer[i]="NIE";
   // else if (a>c&&b>d) answer[i]="TAK";

        else if(    d < b && (c < a || b * (c*c+d*d) > (2*c*d*a + (c*c-d*d)*sqrt(c*c+d*d-a*a)))   ){ answer[i]="TAK";   }
        else answer[i]="NIE";
    }

    for(int i=0;i<test;i++)
    {
    cout<<answer[i]<<endl;
    }

    return 0;
}

tarpauwatratar · Aug '17

Nie podoba mi się, że używasz tablicy. Formatowanie ifów jest wg mnie straszne (nawiasy klamrowe), a jeżeli wykonują one swapy to nie wiem dlaczego nie napisać po prostu swap(a, b). Poza tym jak na mnie to c++ więc czemu math.h a nie cmath?

Nie podobają mi się również Twoje warunki... Według mnie są błędne, choć będąc szczerym nie wczytywałem się. Jak wolisz - moje są zupełnie inne.

anikou · Aug '17

Dziękuję za sugestie, faktycznie główny problem tkwił w warunkach, nie pokrywały one całego spectrum możliwości. Jednakże warunki były inspirowane artykułem na dokładnie ten temat, także nie są chyba błędne, a niekompletne W moim przypadku luka tkwiła w specyficznych warunkach, gdzie jeden prostokąt był wpisany w drugi. Co do formatowania i nieładnej składni - dopiero uczę się C++
Z ciekawości - co jest złego w używaniu tablicy jako zbiornika na dane tymczasowe(chcę najpierw przyjąć serie danych, przetworzyć i dopiero wyświetlić wyniki)?

tarpauwatratar · Aug '17

Był już na forum temat poświęcony temu artykułowi. I owszem - są błędne. Chyba nawet ktoś miał wysłać maila w tej sprawie. Więcej info: http://discuss.spoj.com/t/czy-spoj-forum-pomaga-w-pisaniu-dobrych-podpowiedzi/23397/3, ale niestety musisz się przez to przebić.

Co do kompletności a błędu... to trochę jak dowód na to, że liczb pierwszych jest nieskończenie wiele: 2 - pierwsza. 3 - pierwsza. 5 - pierwsza. Więc jest nsk wiele liczb pierwszych. Taki dowód jest niekompletny bo brakuje wielu innych liczb, a zatem jest błędny. Dowody są poprawne albo nie i tyle.

Ok. Dlatego już Cię opierniczam Czym skorupka za młodu nasiąknie, tym na starość trąci

Absolutnie nic. Sam często tak robię.

Pytanie brzmi: czy taki zbiornik jest zawsze potrzebny? W tym przypadku dane można było przetwarzać na bieżąco w pętli. W ten sposób oszczędzasz czas i pamięć.

anikou · Aug '17

Wielkie dzięki za wskazówki, które mi podałeś, niezmiernie cenię sobie konstruktywną krytykę

redysz · Aug '17

To ja byłem, jeszcze nie dostałem odpowiedzi. Żeby wyjaśnić wszystkim co w przyszłości będą mieli problem z tym zadaniem. Na stronie jstor jest takie twierdzenie:

Twierdzenie zatem w skrócie brzmi:
Spełnienie poniższego wzoru jest konieczne i wystarczające by określić czy jeden prostokąt mieści się w drugim. Błąd. Chyba nikt nie zrobił tego zadania (przynajmniej nie ja, nie @narbej nie @tarpauwatratar) tylko przy pomocy tego wzoru. Wzór możliwe, że jest prawdziwy (przynajmniej testy z tego zadania podpadają pod niego), ale wcale nie jest wystarczający jak stwierdził jego autor (trzeba jeszcze kilka warunków dołożyć).

Nie otrzymałem jeszcze odpowiedzi czy w ogólnym przypadku wzór jest prawdziwy czy też nie, na potrzeby spoja można uznać, że tak, ale twierdzenie mówiące, że wystarczy wykorzystać tylko ów wzór nie jest prawdziwe.

narbej · Aug '17

Ja sam sobie wyprowadziłem wzór i potrzebne warunki, ale widze, że może co nie którzy nie umieją czytać i rozumieć in english? Przecież tu [powyżej] nie ma samego gołego wzoru, tylko najpierw są podane dokładne warunki i założenia, a dopiero potem wzór. Bo chyba każdy rozumie co to znaczy or i co oznacza słowo condition, a także p >= q i a >= b?

Jeszcze raz powtórzę, sam sobie to wyprowadziłem, korzystając z samodzielnie narysowanego rysunki [i korzystając z myślenia ] a ten powyższy fragment widzę pierwszy raz na oczy, ale wygląda mi ok. Tzn conditrions + if and only if ..... or. wzór [spełnienien nierówności). Być może ;powinna to być nierówność ostra [b> wzor] - nie chce mi się myśleć i analizować, ale na pewno nie:

Tylko najpierw warunki i jeden mieści się w drugim [bez wzoru] albo przy dodatkowym warunku [p> a] dopiero sprawdzanie nierówności.

redysz · Aug '17

O to właśnie tu chodzi, że na powyższym screenie (do którego wielu doszło) nie ma wszystkich warunków (albo te są właśnie niepełne). Skoro jest or to można by przypuszczać, że wystarczy tylko część pod or (no bo lub tak by znaczyło), ale ta część nie jest wystarczająca. Może to nawet błąd wydawnictwa, które źle coś zacytowało.

narbej · Aug '17

Nie można. Należy te or traktować jak or w języku c/c++. Najpierw jest sprawdzany warunek przed or i jeżeli jest spełniony, to co po prawej jest niesprawdzane, nawet jeżeli jest bzdurą lub prawdą. Dopiero gdy warunek[ki] przed or nie są prawdą sprawdzane jest to wszystko co jest po or. Jeżeli już na wstępie odetniemy wszystko co powyżej [po lewej stronie] or grubą kreską, to w efekcie może powstać błąd i może właśnie to prowadzi do nieporozumień? Dla mnie jest niezrozumiałe, jak można w ogóle tak sobie pomyśleć i potraktować wzór [sam wzór] jako wystarczający warunek. Przecież tam jest to jedno pełne zdanie, zaczynające się: "W. Carver [3] ....." a kończące się [wyraźną] kropką i n ie można wyrywać fragmentu [wzoru] z kontekstu całego zdania.

PS
Może warto jednak sobie zrobić dokładny rysunek z oznaczenniami?

tarpauwatratar · Aug '17

Ah to leniwe wartościowanie Choć dla mnie zwykła logika. Pójdę do kina lub do dziewczyny - może pójdę do kina, a może jednak do dziewczyny, a może tu i tu? Przynajmniej tak rozumiem słowo lub.

Ale ad rem. Napisałem na szybko program wg tych wzorów. Efekt to WA.

Tylko co z tego? Na double porównania mogą się wysypać, na intach sqrt to średni pomysł, a nade wszystko pisać kod mając 40 stopnii w mieszkaniu to zły pomysł (darujcie błędy w kodzie i wypowiedzi)

Jeżeli twierdzenie jest błędne to najłatwiej pokazać to na kontrprzykładzie. Chętnie bym czegoś poszukał, ale padam…

Jak coś mój kod:
[EDIT: by narbej usunięty “prawie” AC kod]

Chętni niech się bawią. Jeżeli któryś warunek jest zły - nie musicie mi tego pisać. Wystarczy poprawić i powiedzieć: AC czy WA?

narbej · Aug '17

Po poprawce AC: zgłoszenie ID = 19954430 -- > http://pl.spoj.com/status/XIWTPZA/62

PS
Nie piszę co i jak - bo ... AC

PS
Zamiast zastanawiać się czy iść do dziewczyny czy do kina, poprostu zaproś ją do kina, a zaoszczędzoną energię [na zbędne dywagacje i chodzenie samopas] spożytkuj na proste przekształcenie wzoru [nierówności]. Pozbądź się dzielenia i pierwiastkowannia, ale to oczywiście nie ta poprawka, prowadząca do AC.

redysz · Aug '17

Źle mnie chyba zrozumiałeś. Uwierz mi, jestem matematykiem, nie mylę się tutaj (w ciul innych matematyków już mi to też potwierdziło). Tłumaczę (numery 1 i 2 - moje):

W. Carver przedstawił następujący, tajemniczo-wyglądający konieczny i dostateczny warunek:
Prostokąt p na q (gdzie p jest większe bądź równe od q) mieści się w prostokącie a na b (gdzie a jest większe bądź równe b) wtedy i tylko wtedy gdy zachodzi:
1. p jest mniejsze bądź równe a i q jest mniejsze bądź równe b
LUB
2. p jest większe od a i b jest większe bądź równe temu ułamkowi

Tak więc jest LUB. Jeżeli warunek 1. jest spełniony to 2. nie musi być, podobnie jeżeli warunek 2. jest spełniony to 1. nie musi być (w obu przypadkach może)

Teraz weź prostokąt a=8 i b=8 oraz prostokąt p=10 i q=10 i sprawdź warunek 2. - będzie spełniony (sprawdź to). Tak więc z alternatywy wynika, że skoro 2. jest spełnione to prostokąt 10x10 da się zmieścić w prostokącie 8x8. Co jest bzdurą. Czemu tak wychodzi? Bo brakuje m.in. warunku na pole.

Wydawnictwo potwierdziło, że "coś jest nie tak" (tylko po angielsku). Przekazało jednak moją wiadomość dalej. Tak więc... jest coś źle.

narbej · Aug '17

Zamieszczony powyżej program @tarpauwatratar 'a na test 8 8 10 10 odpowiada TAK, ten sam program, po mojej poprawce odpowiada NIE. Musiałbyś wymyśleć trudniejszy test

PS
@tarpauwatratar użył else if zamiast or i dodał na końcu else, ale w tym twoim teście nie robi CI to chyba dużej różnicy? -

PS 2
W c/c++ są dwa operatory: & oraz && - ale na pewno to wiesz.

narbej · Aug '17

Wczoraj było duszno i parno i późno, więc mała poprawka.
Miałem na myśli nie & and && tylko | i ||
Program @tarpauwatratar 'a można też zapisać tak:
Jeżeli ({pierwsze warunki} || { dwa inne warunki}) to TAK
ELSE NIE
gdzie || == or

PS
Ale rzeczywiście, porównując przedstawione znalezisko z internetu z moim programem, widzę 4 różnice [błędy] w tym znalezisku w stosumku do mojego [nie porównuję wzoru]. Jednak nadal uważam, że nie chodzi tu o or.
Ponieważ jednak nie jestem matematykiem i chciałbym jednak zmotywować [nie tylko matematyków] do [bardziej] samodzielnej pracy, a nie poleganiu na znaleziskach, zostawiam to bez komentarza.

redysz · Aug '17

A nie chodziło mi, że błąd jest w samym or. Muszę popracować nad umiejętnością konkretnego przekazywania o co mnie się rozchodzi

share a link to this topic