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

PIEK - Magda-Piekarnie

Pani Magda bardzo lubi ciasteczka, i postanowiła że w wakacje zorganizuje wyprawę, której głównym celem jest skosztowanie wyrobów z każdej piekarni. Nasza bohaterka już długo męczy się nad znalezieniem minimalnej długości trasy, która przechodzi przez wszystkie piekarnie tylko raz i wraca do punktu początkowego. Sporządziła już tabelę odległości pomiędzy każdymi piekarniami. Ty jako dobry kolega postanowiłeś pomóc koleżance z tym problemem, i oto nasz cel należy napisać program który wyznaczy najkrótszą trasę, w zamian Magda wynagrodzi Cię ciasteczkami tym więcej im bardziej będzie zadowolona z twej trasy.

Przykład:

Mamy 4 piekarnie: 1,2,3,4.

Tabela odległości wygląda następująco:


1 2 3 4
1 0 4 7 3
2 4 0 5 8
3 7 5 0 6
4 3 8 6 0

Najkrótsza trasa to:18.

Przykładowa możliwość najkrótszej trasy :1->4->3->2->1

Wejście

W pierwszej linii liczba piekarni (n).

Następnie n linii każda składająca się z n liczb (które są odległościami między piekarniami).

Wyjście

W pierwszej linii obliczona długość trasy.W drugiej linii (n+1) liczb oddzielonych spacjami (od 1 do n włącznie) przy czym pierwsza i ostatnia muszą być takie same, jest to kolejność odwiedzania piekarni.

n<=400

Przykład:

Wejście:
4
0 4 7 3
4 0 5 8
7 5 0 6
3 8 6 0
Wyjście: 18
1 4 3 2 1

Punktacja:

To ilość ciasteczek jaką daje Ci Magda, a da ich więcej jeśli trasa będzie krótsza .
 

Dodane przez:Marek Mystkowski
Data dodania:2012-07-11
Limit czasu wykonania programu:0.100s-0.600s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU

ukryj komentarze
2012-08-13 23:36:48 Marek Mystkowski
Jest nowy sędzia , i aby mieć zadanie zaliczona trzeba mieć co najmniej 1000 pkt. (jak będzie już dobry ranking to próg zmniejszę ,a na razie zastanawiam się czy jeszcze nie zwiększyć). Nowy sędzia jest troszkę mądrzejszy :)
2012-08-05 10:11:07 Marek Mystkowski
Do pierwszych 7 testów znam najkrótszą ścieżkę (są to małe testy i jak je układałem to burtę przez dłuższy czas generowałem do nich najlepszą ścieżkę i wyniki jakie można dostać to:
1-5
2-200
3-200
4-333(przybliżone)
5-200
6-400
7-200
więc za pierwsze 7 testów można dostać 1538 pkt, a to tylko 7 z 20 testów przy czym w pozostałych testach można dostać zapewne więcej punktów niż w tych (bo 200 pkt dają obecne programy które dla pierwszych siedmiu testów dają nie najlepsze rezultaty) więc w tym zadaniu można zawalczyć o dużę pulę punktów

Ostatnio edytowany: 2012-08-07 10:44:51
2012-08-05 09:27:30 Marek Mystkowski
Jeśli chodzi o test z 386 jest to mały test ale podchwytliwy i max można dostać 400 (ale to jeden z nie licznych testów dla których znam najkrótszą trasę a i tak mój program jej nie wpisuje :) ), a tak w pozostałych testach nie wiadomo jaka jest minimalna trasa i jest tylko oszacowana , mam nadzieje że po jakimś czasie wyniki będą coraz lepsze .
2012-08-05 00:20:49 Piotr KÄ…kol
@Karol Kalinowski - Bo większość osób, która ma AC w tamtym zadaniu nie kodzi już na SPOJPLu. ;-)
@Krystian Plackowski - Nie no wiem, że jestem głupi, ale podstawową wiedzę mam. ;-) Wiem, że to jest problem NP-trudny, ale znając maxa, którego można osiągnąć w tym zadaniu zobaczymy jak optymalne są nasze heury. Bo powiedzmy max może być 5000 (przy teraźniejszym najlepszym wyniku ~4k) a może i być 10k, więc fajnie by było chyba wiedzieć, jak stoimy.

Edit: Krystian - No fakt, to było głupie z mojej strony.
Karol - A Twój program z ALGWLACZ nie ma żadnych WA? Bo mój dostaje 1242 i ma WA na 7 testach. Masz coś większego od long longów?

Ostatnio edytowany: 2012-08-05 02:55:41
2012-08-05 00:16:40 Krystian Plackowski
@Piotr Kąkol: możliwe że nie istnieje algorytm dokładny o złożoności lepszej niż (O)n^2*n!, dlatego właśnie to zadanie jest w challenge.

edit: to nie jest tak, że sposób naliczania punktów za każdy test jest jakoś wyskalowany, żeby najkrótsza możliwa droga dostawała dokładnie 200 pkt. Skala jest dobrana "na oko". Sam w jednym teście mam 386 pkt.
W zadaniu "Kompresor prac domowych" też nie wiemy, jaki jest najlepszy możliwy do uzyskania wynik (na chwilę obecną 0.445999).

Ostatnio edytowany: 2012-08-05 00:45:50
2012-08-04 21:33:56 Karol Kalinowski
http://pl.spoj.pl/problems/ALGWLACZ/
Algorytm włączania daje dokładnie 1753 punktów :P dziwię się trochę, że więcej osób tamtego kodu nie skopiowała do tego zadania ;]
2012-08-04 20:14:00 Piotr KÄ…kol
W sumie może by dodać gdzieś najlepszy możliwy wynik sumaryczny w zadaniu, żebyśmy wiedzieli jak kiepskie są nasze programy? ;-)
2012-08-04 14:18:43 Marek Mystkowski
Pani Magda poradzi sobie nawet jeśli nie zacznie się od 1 ważne żeby pierwsza i ostatnia była taka sama
2012-08-04 13:46:42 Julia Ostrowska
A ja mam pytanie o punkt startowy, czy to jest pierwsza piekarnia czy dowolna i wracamy do niej?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.