6441. Prostokąty

[tarpauwatratar]

Jednakże warunki były inspirowane artykułem na dokładnie ten temat, także nie są chyba błędne, a niekompletne

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.

Co do formatowania i nieładnej składni - dopiero uczę się C++

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

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

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]

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

[redysz]

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

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]

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:

Spełnienie poniższego wzoru jest konieczne i wystarczające by określić czy jeden prostokąt mieści się w drugim.

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

[redysz]

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

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]

Skoro jest or to można by przypuszczać, że wystarczy tylko część pod or

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]

Należy te or traktować jak or w języku c/c++.

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]

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

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]

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

Ź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]

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]

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]

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 samodzielnej pracy a nie poleganiu na znaleziskach zostawiam to bez komentarza.

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

[tarpauwatratar]

Po poprawce AC:

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

Zrobione i wciąż WA. Rzecz jasna zrobione poza poprawką dającą AC. No i zaproszeniem Z czystej ciekawości dorzuciłem jeszcze kilka warunków z kodu mającego AC, ale wciąż WA. Pewnie brakuje jeszcze jednego ifa albo mam błąd typu > a <, albo > a >=, ale w sumie to bez znaczenia - my tu o twierdzeniu, a nie o zadaniu.

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

I tu dochodzimy do największego problemu - Twojej poprawki. A jej w twierdzeniu nie podano co jak na mnie oznacza, że jest ono niepoprawne (o ile @redysz dobrze rachuje, ale wierzę mu na słowo )

Program @tarpauwatratar 'a można też zapisać tak:Jeżeli ({pierwsze warunki} || { dwa inne warunki}) to TAKELSE NIEgdzie || == or

W sumie mogłem to uwzględnić... ale za to jest czytelniej

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.

Nie twierdzę, że wzór jest błędny. Podobnie uważam za prawdziwy wzór a^2 - b^2 = a - b. Sprawdza się dla nieskończenie wielu liczb, np. dla a = 1 i b = 1

Po prostu wzór w artykule dotyczy szczególnego przypadku a brakuje jeszcze jakiegoś (jakichś?) warunków. Błędne jest zatem twierdzenie. Nie wiem, czy błąd dotyczy alternatywy czy warunków czy czego (wszak to nie mój artykuł i nie ja go publikowałem). Wierzę na słowo, że chodzi o coś innego (wszak wiesz co zrobić by program miał AC).

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.

Kiedyś bym się z Tobą sprzeczał twierdząc, że część zadań polega właśnie na wyszukaniu jakiegoś wzoru, mało znanego algorytmu, ... chyba się starzeję, albo nabrałem już jakiejś wprawy (wszak nie jest mnie już tak bardzo ciężko odszukać w rankingu ). Choć to chyba normalne, że z czasem człowiek wraca do rozwiązanych daaawno zadań (jak tego), poprawia stare kody, szuka alternatywnych rozwiązań, ...

PS

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

Trochę mnie to martwi. Wstawią poprawną wersję i mówiąc po wsiowemu: po ptokach. Tak ludzie mieli cenną lekcję - zamiast szukać gotowca albo półgotowca szukamy nudzących się neuronów w naszych głowach i każemy im pracować

[narbej]

Ponieważ "odległość" od twojego kodu, zainteresowani wiedzą o czym piszę, zwiększyła się znacząco, podam różnice. Wystarczy tylko jedna poprawka, ponieważ nie ma testów typu a=p i b=q. Brak w zadaniu takiego typu testów, powoduje, że nie potrzebne [do AC] są dwie poprawki, ale wynikająca stąd [mentalnie] trzecia jest już konieczna. Napisałem o tym zresztą już dużo wcześniej: "Być może ;powinna to być nierówność ....... ".
Czwartą różnicą w stosunku do dyskutowanego artykułu, nie mającą jednak wpływu na AC/WA jest taka, że ja użyłem: q < b zamiast p > a <--- ale nie będę [się z tego ] tłumaczył.

PS
Mam nadzieję, że napisałem wystarczająco zagmatwanie oraz wniosek, że problemem nie są warunki ale tylko ich bardzo drobna modyfikacja. W sumie 4 drobne różnice w porównaniu do mojego kodu a samodzielne znalezienie ich [przynajmniej 3] wymaga tylko trochę [matematycznego?] pomyślenia

PS 2
"Mój" warunek - q < b, + wcześniejsze dwa "z automatu" odrzucają bzdurne pomysły*

---
*/ - tu bzdurne pomysły = [bz]durne tetsy typu 8 8 10 10 [sorry @redysz] oraz typu a = p i b = q. Może są jednak inne [bzdurne albo nie], których program nie "wyłapuje"?

[tarpauwatratar]

Myślę, że czas zakończyć ten temat. Jeszcze trochę, a zaczniemy rzucać kodami i (o zgrozo!) rysunkami i dowodami Szczególnie, że "zagmatwanie" kusi, aby je rozwikłać Wydaj mi się, że ustaliliśmy co trzeba było ustalić, a potomni będą mieli co czytać. I ewentualnie "rozgmatwać"

[narbej]

Myślę, że czas zakończyć ten temat.

Jak dla mnie jakieś dziwne to twoje myślęnie, żeby nie napisać głupie czy złe.

Jeszcze trochę, a zaczniemy rzucać kodami

A niby jeszcze nie zaczęliśmy? A niby co sam zrobiłeś parę postów wyżej? Twój kod wymaga tylko bardzo małej poprawki - usunięcia jednego znaku w kodzie i już AC.

i (o zgrozo!) rysunkami i dowodami

Czemu o zgrozo. Czy to nie byłoby lepiej i nie lepsza lektóra do czytania, niż ciągłe czytanie: co kto + błędny i brzydki kod? Lub ciągłe pytania jak wkleić kod do wiadomości na forum.

Szczególnie, że "zagmatwanie" kusi, aby je rozwikłać

Zagmatwanie jest tylko i wyłącznie z tego powodu, że wyżej wkleiłeś kod, który wprost, po rozgmatwaniu mojej podpowiedzi daje AC.

Wydaj mi się, że ustaliliśmy co trzeba było ustalić,

Tylko tak Ci się wydaje. Jak wyżej. Twój kod nie pozwala mi ustalić i rozgmatwać podpowiedzi.

[tarpauwatratar]

Jak dla mnie jakieś dziwne to twoje myślęnie, żeby nie napisać głupie czy złe.

A wg mnie bardzo dobre.

A niby jeszcze nie zaczęliśmy? A niby co sam zrobiłeś parę postów wyżej? Twój kod wymaga tylko bardzo małej poprawki - usunięcia jednego znaku w kodzie i już AC.

W efekcie ludzie mają gotowca...

Czemu o zgrozo. Czy to nie byłoby lepiej i nie lepsza lektóra do czytania, niż ciągłe czytanie: co kto + błędny i brzydki kod? Lub ciągłe pytania jak wkleić kod do wiadomości na forum.

Myślę, że lepiej, aby ludzie myśleli. Sami. A nie uczyli się, że rozwiązania zadań są na forum.

Zadania tracą sens, gdy polegają na kopiowaniu rozwiązań z forum, bo przestają być zadaniami.

Zagmatwanie jest tylko i wyłącznie z tego powodu, że wyżej wkleiłeś kod, który wprost, po rozgmatwaniu mojej podpowiedzi daje AC.

I właśnie status quo powinien zostać dla potomnych. Aktualnie zagadka została rozgmatwan...

Tylko tak Ci się wydaje. Jak wyżej. Twój kod nie pozwala mi ustalić i rozgmatwać podpowiedzi.

Ok. Właśnie ustaliliśmy co zrobić, aby zaliczyć to zadanie. Skopiować kod i zamienić nierówność na ostrą (bo po informacji o usunięciu jednego znaku każdy to wymyśli).

W efekcie ciekawe i nienajprostsze (jak na łatwe) zadanie zamiast uczyć ludzi myślenia i wyszukiwania odpowiedzi poza najbardziej oczywistymi źródłami (forum) pokazuje, że zadania z algorytmiki to sztuka kopiowania gotowców, a gotowce znjdują się (nawet) na forum.

Czy analogiczne dyskusje będziemy toczyć w przypadku innych zadań, np http://pl.spoj.com/problems/KWACIK/ albo http://pl.spoj.com/problems/AL_10_02/ ? Co najmniej do drugiego da się znaleźć błędne wywody w sieci.

Może zamiast uczyć ludzi, że geometria wymaga siedzenia z kartką papieru oraz ołówkiem, a także cierpliwości i myślenia (mówię o osobach, które nie wiedziały od razu jak rozwiązać to zadanie niezależnie od tego, jaka była tego przyczyna) pokażemy im, że geometria to sztuka szukania gotowych rozwiązań w sieci?

Jak wolisz - podobało mi się to, że zadanie było nietrywialne i czegoś mnie nauczyło, np. nie opierania się w sposób bezmyślny na gotowcach. Obecnie stanowi ono żywy dowód, że zamiast myśleć nad rozwiązaniem lepiej szukać rozwiązań w sieci bo zajmuje to dużo mniej czasu. A przynajmniej ja utwierdziłbym się w przekonaniu, że SPOJ polega na googlowaniu rozwiązań, co swojego czasu robiłem będąc przekonanym o słuszności tego postępowania. O zgrozo do znalezienia solucji wystarczy wejść na forum SPOJa...

I temu byłem za przerwaniem dyskusji, która musiała skończyć się w taki sposób.

[manjaro]

@narbej chciałbym widzieć te Twoje wyprowadzenia wzoru… Bardzo Cie szanuję za ogromną wiedzę z programowania. Naprawdę. Ale nie pisz bzdur że wziąłeś ołówek i papier i tak sobie wyprowadziłeś podobny wzór. W dodatku jak sam twierdzisz nie jesteś matematykiem. A szybciej to policzyłeś niż ten Carver… Dostałem przed chwilą AC więc już nie drążę tematu. Pozdrawiam

[narbej]

Rozumiem że autorowi chodziło chyba o coś zupełnie innego ale może niech sprecyzuje o co bo ja nie mam pojęcia. Zamiast układać algorytmy to mamy do rozwiązania zagadki z dziedziny absurdu.

Przecież nikt nie każe tego robić, chcesz to rozwiązujesz zadanie, nie to nie. Jeżeli nie podobają się zadania na SPOJ’u, to nikt nie broni wymyślenia swoich, lepszych i wstawienia ich tutaj.
Może nie chodzi tu o wymyślenie jakiegoś szczególnie finezyjnego algorytmu, ale autor nie owija w bawełnę i [wyraźnie] pyta, czy można drugi prostokąt na płaszczyźnie ustawić w taki sposób… Na płaszczyźnie figry płaskie, jak wiadomo, nawet nie będąc matematykiem, można przesuwać i obracać. A potem wystarczy już tylko twierdzenie Pitagorasa, podobieństwo trójkątów, linijka … no i może faktycznie, długopis jest czasami lepszy niż ołówek, ale trochę trudniej go wygumkować…To też nie jest jeszcze jakąś wyższą↓ matematyką czy alchemią.

[manjaro]

Dlaczego odnosisz się do postu który skasowałem a nie do tego ostatniego? Jakim cudem w ogóle jesteś w stanie czytać skasowany post? Uważasz że to jest tak trywialne że w gimnazjum można to rozwiązać pitagorasem? Ciekawe że sztab matematyków na całym świecie się nad tym głowi latami.