Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

TOFFMILL - Operator Jaś

Jaś, odkąd pamiętają jego rodzice, przejawiał zainteresowanie do wszelkich pojazdów na czterech kółkach i do... łamigłówek matematycznych. Rodzina Jasia, podobnie jak i ich sąsiedzi, mają duże ogrody wymagające częstej pielęgnacji. Postanowili zatem połączyć zamiłowania Jasia i sprezentowali mu najnowszy model kosiarki do trawy. Odtąd Jaś wytycza nowe trasy w ogrodach swoich rodziców i sąsiadów, optymalizując czasy ich przejazdów, przy okazji kosząc im trawę...

Wejście

Każdy ogród podzielony jest na pola kwadratowe o wymiarze jednostkowym. Jaś porusza się pomiędzy sąsiednimi polami, w dowolnym z czterech kierunków. Zakładać będziemy, że ogród nie posiada wewnątrz żadnych innych pól niż trawnik, który musi zostać skoszony. Zaczynając ze wskazanego pola, Jaś musi skosić cały ogród i powrócić do punktu startu, minimalizując przy tym łączną długość drogi. W pierwszej linii podana jest informacja o liczbie ogrodów (zestawów testowych), t <= 10. W każdym zestawie testowym, w pierwszej linijce podana jest łączna ilość odcinków z brzegu ogrodu, 4 <= n <= 20000. Druga linia zawiera dokładnie n liczb całkowitych a1,...,an opisujących długości kolejnych odcinków z brzegu ogrodu (1 <= |ai| <= 250). Każde dwa kolejne odcinki z brzegu ogrodu są do siebie prostopadłe. Długość i-tego odcinka jest równa wartości bezwględnej ai, znak określa kierunek: "+" oznacza N lub E, "-" oznacza S lub W, zakładając, że ogród obchodzi się dookoła zgodnie ze wskazówkami zegara. Pole początkowe wskazane jest przez początek pierwszego odcinka z brzegu ogrodu, który jest podany w kierunku N/S. Przyjmiemy, że cały ogród mieści się w kwadracie 1000 x 1000.

Ilustracja pomocnicza treści

Wyjście

Na wyjściu należy podać liczbe oraz sekwencje ruchów kosiarki Jasia z wykorzystaniem informacji o kierunkach N, S, E oraz W, zaczynając od pierwszego pola (początek pierwszego odcinka z brzegu).

Punktacja

Każdy zestaw testowy będzie punktowany niezależnie. Za wynik punktowy danego zestawu testowego przyjęty będzie stosunek długości trasy Jasia do całkowitej liczby pól w ogrodzie. Łączny wynik będzie sumą wszystkich wyników uzyskanych z poszczególnych testów. Dokładny wzór:

sum(max{(3 - scorei)*3,0},i=1,2,3)

Przykład

Wejście:
5
12
+1 +1 +1 +1 -1 +1 -1 -1 -1 -1 +1 -1
4
+2 +1 -2 -1
14
+2 +1 +2 +2 -1 +2 -3 -1 +1 -1 +1 -1 -2 -2
8
-2 -1 +1 -3 +2 +3 -1 +1
12
+7 +1 -3 +1 +3 +1 -7 -1 +1 -1 -1 -1

Wyjście:
8 ENSEWSNW
2 NS
18 NENNESEESSNWNWWSSW
10 WWWNEESESN
26 NNNNNNSSSEENNNSSSSSSNNWSWS

Wynik:
1.353


Dodane przez:mima
Data dodania:2006-05-28
Limit czasu wykonania programu:1s-20s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU

ukryj komentarze
2014-12-30 19:47:33 Witold D³ugosz
Probably, you get points (somehow) for inversion of calculated average.

Ostatnio edytowany: 2014-12-30 19:48:27
2014-12-29 05:18:00 Mitch Schwartz
Shouldn't assessment type be set to minimise score? But I don't understand how this could have gone unmentioned for over 8 years. Did I misunderstand something? (It seems simple enough: We want to minimise path lengths, which corresponds to minimising score. It's not hard to check score calculation of sample I/O, equal to (8/5+2/2+18/13+10/8+26/17)/5.)

Edit: @Witold, you are right; after submission one can see more details including another formula, "sum(max{(3 - score_i)*3,0},i=1,2,3)". It seems strange (and confusing) that it wasn't mentioned in the problem statement.

Edit 2: Thanks @Piotr Kąkol for updating the description.

Ostatnio edytowany: 2015-01-05 05:06:09
2010-11-09 23:06:45 Ewa Piotrowska
Zakładamy, że zawsze będzie można objechać ogród na zasadzie "do końca i spowrotem", czy czasem ogród będzie dużo bardziej skomplikowany niż na obrazku i trzeba będzie wykonywać bardziej skomplikowane manewry?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.