355. Rysunki Bajtelka [BAJTELEK]

W końcu:

AC

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

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/IN7k7365
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ę.

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' });
   }

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

Dodałem do tego zadania 18 znalezionych na sieci testów -> https://ideone.com/1AU6EH#stdin46 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

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.

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.

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.

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

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

Rodział 3.2, drugi paragraf.

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)

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

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 KOD20

Mam problem z 2 ostatnimi zestawami od redysz. Bo tam zostaja zamienione kolejnoscia linijki z wierzcholkami, i wartosci pola dla 1 i 2 pola zamieniaja sie, co po przemnozeniu przez koszty tuszu daja 62 zamiast 88, i teraz nwm co jest nie tak.
Funkcja licząca wartosc pola jest ok na 100% bo sprawdzalem z innym kalkualtorem, wiec musialem cos zle zrozumiec w samej logice rysuowania przez bajtelka.

Utknąłem w martwym punkcie.

nadmierny optymizm, sprawdź dla danych:

1
1 1 2 1 1 2 1 1
0 0 5 0 0 5 0 0

ten problem jest łatwo usunąć

niezgodność dla podanego testu przez redysz tez można wyjaśnić - ostatnie dwa testy są błędne