355. Rysunki Bajtelka [BAJTELEK]

[narbej]

Twój sposób jest poprawny, ale skąd wziąłeś poniższą wartość?

(i=100000000

W zadaniu nie ma jej podanej. W takim wypadku najbezpieczniej jest użyć vektora i funkcji push_back(x..)
Drugą metodą, jest zrezygnowanie z tablicy i zapamiętać tylko pierwsze wartości x0, y0, a na bieżąco wczytywać tylko dwie kolejne [xi, yi] i pamiętać tylko dwie poprzednie [xi-1, yi-1] i na bieżąco obliczać pole i oczywiście sprawdzać, czy już jest koniec.

[anim_90]

chodziło mi o wartość "ile", a nie "i" oczywiście.... tak jak wzięła justyna_8

hm. w takim razie, skoro mój sposób jest poprawny, to tak będę kombinował dziękuję

[narbej]

Kod @justyna_8 nie był kodem wzorcowym i tam, w jej kodzie, ile było dziesięc razy mniejsze. Użycie vektora też było w jej kodzie niezbyt szczęśliwe mówiąc delikatnie. Mimo, że w zadaniu występuje wzór pole / 2 w tym zadaniu można użyć zmiennych całkowitych [int i long long] - nawet sam autor zadania o tym wspomina:

Bitokula jest tak dobraną jednostką, że ilość zużytego tuszu zawsze wychodzi całkowita

Nie do końca wiadomoo co autor ma na myśli, ale dodatkowo można i należy zrezygnować z dzielenia przez dwa, a mnożyć nie przez dziesięć i sześć tylko pięć i trzy.

Jeżeli chcesz użyć tablicy lub vektora, a nie wiesz jakiej wielkości jest potrzebny [w tym lub dowolnym innym zadaniu], możesz to "wydedukować" metodą prób i błędów. Zakładasz wielkość np 100. Wysyłasz na SPOJ'a. Dostajesz sigabrt, więc zwiększasz sukcesywnie, póki nie otrzymasz AC, WA lub TLE, czyli dotąd aż przestaniesz dostawać SIGABRT.

[anim_90]

hm. metoda prób i błędów zawsze działa ;p dziękuję za pomoc. wieczorem wrócę do rozwiązywania tego zadania mam nadzieję, że mi się uda pozdrawiam

[anim_90]

W końcu:

AC

[redysz]

Testy ze starego forum, które mogą pomóc (mi pomogły)

Wejście

6
5 3 4 5 5 4 6 5 5 3
8 8 6 4 8 0 5 3 2 0 4 4 2 8 5 5 8 8
-1 1 0 0 1 1 0 -1 -1 1
-3 4 0 1 3 4 1 0 3 -4 0 -1 -3 -4 -1 0 -3 4
50000 30000 40000 50000 50000 40000 60000 50000 50000 30000
80000 80000 60000 40000 80000 0 50000 30000 20000 0 40000 40000 20000 80000 50000 50000 80000 80000
-10000 10000 0 0 10000 10000 0 -10000 -10000 10000
-30000 40000 0 10000 30000 40000 10000 0 30000 -40000 0 -10000 -30000 -40000 -10000 0 -30000 40000
8 8 6 4 8 0 5 3 2 0 4 4 2 8 5 5 8 8
5 3 4 5 5 4 6 5 5 3
-3 4 0 1 3 4 1 0 3 -4 0 -1 -3 -4 -1 0 -3 4
-1 1 0 0 1 1 0 -1 -1 1

Wyjście

88
88
8800000000
8800000000
88
88

[czarnooch]

Witam,

Mam problem z tym zadaniem. Na początku zaznaczę, że program tworzę w C#. Testuje kod na ideone.com z wszystkimi zestawami danych, jakie udało mi się znaleźć. Wyniki wychodzą poprawne. Udało mi się dotrzeć do kodu z AC napisanego w C++. Jedyna różnica, to sposób pobierania danych. W C++ wykorzystywany jest cin, natomiast w C# pobieram całą linię z konsoli i dopiero później dzielę ją na elementy. Czy ktoś mógłby zerknąć na kod na ideone
http://ideone.com/IN7k73
i zasugerować ewentualną podpowiedź, albo wrzucić przykładowy zestaw testowy na podstawie którego będę mógł znaleźć błąd. Z góry dziękuję.

[j4rooo]

Po każdym teście następuje pusta linia.

Gdzieś tutaj leży problem. W C++ po prostu wczytujemy liczby i ignorujemy białe znaki. W C# czytasz uczciwie linia po linii.

W załączonym programie masz zakomentowane wczytanie tej pustej linii przez co dla przypadku testowego liczy tylko pole pierwszego podanego obszaru, więc teoretycznie po odkomentowaniu tego powinno działać ok. Niestety wali gdzieś wtedy wyjątkiem (NZEC).

Żeby dużo nie modyfikować wejścia zrobiłem taki myk żeby ignorować puste linie jeśli takowe wystąpią i przeszło:

   // Prepare data for calculation area.
   inputData = Console.ReadLine().Split(new char[] { ' ', '\t' });
   while (inputData.Length == 0 || (inputData.Length == 1 && inputData[0] == ""))
   {
       inputData = Console.ReadLine().Split(new char[] { ' ', '\t' });
   }

[czarnooch]

Co do pustej linii, to dlatego właśnie wczytywanie było zakomentowane, ponieważ sędzia zwracał NZEC. Myślałem, że coś źle się parsuje z wejścia i może po prostu w zadaniu jest błąd i nie wczytywałem tej linii. Wtedy zwracało błędna odpowiedź, więc poszedłem tym tropem. Wprowadziłem zmiany i faktycznie przeszło. Dziękuję bardzo !
Na koniec jeszcze krótkie pytanie odnośnie sprawdzania pustych linii.
inputData.Length == 0 to jest oczywiste,
ale skąd wymyśliłeś
inputData.Length == 1 && inputData[0] == ""
OK -> nie ma tematu. Sprawdziłem sobie co ląduje w zmiennej dla wczytania pustej linii i wszystko się zgadza. Jeszcze raz dzięki za podpowiedź.

[pw1983]

Dodałem do tego zadania 18 znalezionych na sieci testów -> https://ideone.com/1AU6EH#stdin wygląda ok. Ale sędzie wyrzuca błędna odpowiedź.
Wydaje mi się, że to może być związane ze sposobem pobierania danych, robię to tak:

1. Pobieram dla każdego testu całą linijkę jako string
   1a. Następnie na tym ciągu znaków używam funkcji explode i po spacji wydobywam kolejne numery do tablicy i faktycznie jeśli jest więcej niż jedna spacja to dostaję złe wyniki, pytanie tylko czy spoj może podawać wyniki z różną ilością białych znaków
2. Drugim podejrzanym punktem jest sposób liczenia ja używam wzoru:
   P = 1/2*|suma xi * (yi-1 - yi+1)| przy y0 = yn i yn+1 = y1
   sprawdzę ten drugi P = 1/2*|suma ((xi * yi+1) - (xi+1 * yi))| dla x0 = xn i y0 = yn

Szczerze mówiąc to nie wiem czy te wzory są sobie równoważne ale przetestuje też drugą opcję, chyba że ktoś coś jeszcze widzi lub ma szersze testy do sprawdzenia

[j4rooo]

1. Czasem autorzy są złośliwi i wrzucają więcej białych znaków na wejściu.

2. Ja używam wzoru z Algorytmiki Praktycznej: 1/2*|suma (xi + xi+1) * (yi - yi+1)|

w tej sumie, jeśli pukt początkowy jest tylko raz to dla ostatniego punktu dodaje się jeszcze (xi + x1) * (yi - y1)

Ale skoro wyniki są identyczne to te wzory powinny być tożsame.

[pw1983]

Na 99% już wiem co było problemem a mianowicie to: getline(cin, czarne_liczby); czyli moje założenie, że jeden przypadek przypada na jedną linię.
Efekt tego jest taki, że jak ktoś wsadzi więcej spacji pomiędzy liczbami lub złączy wyniki dla szarego pola i czarnego w jedne wiersz albo rozdzieli enterem współrzędne dla czarnego/szarego pola to będą błędne wyniki.

[narbej]

Używanie do tego zadania getline a także używanie go [do innych] bez zabezpieczeń, to proszenie się o kłopoty. A przecież wystarczy tylko dokładnie przeczytać treść zadania, odpowiednią ilość razy.

Uważam, że nigdy i żaden autor zadania nie był i nie jest złośliwy. Czasami mogą zdarzyć się błędy, ale nie jest to złośliwość autora zadania. A przecież twój program może i powinien być odporny na takiego typu proste błędy, a używając odpowiedniego sposobu wczytywania, nie ma żadnego problemu. Chyba, że używasz do tego zadania języka typu brainfuck lub niepotrzebnie komplikujesz i bawisz się w explozje.

[maciorrus]

Mam takie pytanko. Podajecie tutaj wzór z którego korzystacie, ale coś mi się wydaje, że ten wzór nie będzie działał dla figur wklęsłych. Sędzia akceptuje ten wzór? Może źle z niego korzystam, ale nawet dla przykładowych danych:
2 3 5 2 3 3 5 4 2 3
wzór 1/2*|suma (xi + xi+1) * (yi - yi+1)| wylicza 7 a powinien jeden (tak mi przynajmniej wyszło z ręcznych obliczeń). Może mi ktoś to wytłumaczyć?

[j4rooo]

Nie wytłumaczę tego lepiej niż sam autor: https://www-users.mat.umk.pl/~stencel/acm/algorytmika_praktyczna.pdf

Rodział 3.2, drugi paragraf.

[narbej]

dla przykładowych danych:

2 3 5 2 3 3 5 4 2 3

wzór 1/2*|suma (xi + xi+1) * (yi - yi+1)| wylicza 7 a powinien jeden (tak mi przynajmniej wyszło z ręcznych obliczeń). Może mi ktoś to wytłumaczyć?

Też tego nie rozumiem, może masz za mało palców - do ręcznego liczenia?
0.5*abs((2+5)(3-2)+(5+3)(2-3)+(3+5)(3-4)+(5+2)(4-3)) ==!?? 7
Mi wyszło - liczyłem ręcznie - jeden.

PS
Tłumaczenia algorytmów lepiej są opisane i wytłumaczone chociażby we Wprowadzeniu do Algorytmów. Stańczyk podaje raczej gotowe wzorce, a tylko trochę tłumaczy.

[tarpauwatratar]

(…) gotowe wzorce (…)

Autor zapewne zakłada, że czytelnik szukający czegoś więcej niż gotowca sam wyszuka w innych źródłach stosownych tłumaczeń, a być może nawet sam wyprowadzi stosowne wzory i wykona dowód poprawności oraz złożoności algorytmu Nota bene polecam (stańczyka i przedstawione podejście)

[panpeter]

Witam wszystkich.
Ja też męczę się z tym zadaniem. Początkowo, jak pewnie wielu przede mną, stworzyłem tablice, wywalał mi SIGSEGV. Teraz, dzięki Waszym postom, zmieniłem zupełnie podejście i wczytuję tylko bieżące współrzędne z zapamiętaniem poprzednich oraz pierwszych i obliczaniem pola na bieżąco. Na razie jestem na tym etapie, że po wprowadzeniu powyższych (tzn. tych: 355. Rysunki Bajtelka [BAJTELEK] ) danych program mi wszystko ładnie oblicza, natomiast sędzia wywala Błędną odpowiedź ;(

[lumper7876]

Dzień dobry
Czy mógłby ktoś mi podpowiedzieć dlaczego wywala złą odpowiedz, dziękuje z góry za pomoc kod.txt (2.0 KB)

[szwarceneger16]

Testowałem dla wszystkich zestawów danych zostawionych tutaj przez użytkowników. Mój program daje prawidłowe wyniki, natomiast sędzia wyświetla bledną odpowiedz. Czy ktoś orientuje się o co chodzi?
MOJ KOD