Przegląd
Biorąc pod uwagę listę fajerwerków a-z
i godziny 3-78
, ułóż je za pomocą bezpieczników, aby wszystkie zapalały się we właściwym czasie.
Wiersz wprowadzania jest podawany jako litery i cyfry oddzielone spacjami:
a 3 b 6 c 6 d 8 e 9 f 9
Że przykład pokazuje, że fajerwerk a
zapotrzebowanie na światło w czasie 3
, b
a c
zarówno na 6
, d
na 8
, z e
, a f
zarówno na 9
. Każda linia odpowiada jednej mapie.
Wyjście jest mapą bezpieczników / fajerwerków dla każdej linii, używając symboli |-
do pokazania bezpieczników i liter do pokazania fajerwerków.
A -
łączy bezpiecznik bezpieczników i fajerwerków bezpośrednio w lewo / prawo od niego, natomiast |
Łéczy bezpieczników z tymi powyżej / poniżej. Na przykład bezpieczniki nie||
są podłączone i są .-|
Na przykład dwie możliwe odpowiedzi na powyższe to:
---a ---------f
| ||| ||
|-c ||| de
--|--d a||
| b | |c
f e b
Wszystkie mapy bezpieczników powinny zaczynać się od jednego -
w lewym górnym rogu. To jest punkt, w którym zapalasz bezpiecznik. Każda postać bezpiecznika potrzebuje jednej sekundy na spalenie. Jak widać, a
osiąga się go w ciągu trzech sekund na obu schematach, b
w sześciu itd.
Teraz obie powyższe mapy są prawidłowe dla podanych danych wejściowych, ale jedna jest wyraźnie bardziej wydajna. Lewy zużywa tylko 13 jednostek bezpiecznika, a prawy 20.
Bezpieczniki nie przepalają fajerwerków! W przypadku danych wejściowych a 3 b 5
jest to nieprawidłowe:
---a--b
Wyzwanie
Twoim celem jest zminimalizowanie ilości bezpiecznika używanego we wszystkich przypadkach testowych. Punktacja jest bardzo prosta, całkowita liczba użytych bezpieczników.
Jeśli nie możesz stworzyć mapy dla przypadku testowego, bez względu na to, czy jest to przypadek niemożliwy, czy nie, wynik dla tego przypadku jest sumą wszystkich czasów (41 w powyższym przykładzie).
W przypadku remisu punktacja jest modyfikowana, aby wygrać najbardziej kompaktowe mapy. Wynik rozstrzygnięcia jest obszarem obwiedni każdej mapy. Oznacza to, że długość najdłuższej linii razy liczba linii. W przypadku map „niemożliwych” jest to kwadrat największej liczby (81 w powyższym przykładzie).
W przypadku, gdy zgłoszenia wiążą obie te metody punktacji, remis przechodzi do wcześniejszego wpisu / edycji.
Twój program musi być deterministyczny dla celów weryfikacji.
Przypadki testowe
Istnieje 250 przypadków testowych, zlokalizowanych tutaj . Każdy z nich ma od 4 do 26 fajerwerków. Minimalny czas bezpiecznika dla fajerwerku to 3. Fajerwerki w każdym przypadku są „sortowane” według czasu i litery, co oznacza, b
że nigdy wcześniej się nie zapali a
.
Podczas publikowania prosimy o podanie pełnego programu, całkowitej liczby punktów oraz wynikowej mapy (przynajmniej) pierwszego przypadku testowego podanego w pliku:
a 6 b 8 c 11 d 11 e 11 f 11 g 12 h 15 i 18 j 18 k 21 l 23 m 26 n 28 o 28 p 30 q 32 r 33 s 33 t 34
źródło
rand.nextInt(5)%4
więc 40% szansy0
i 20% na każdy1,2,3
.-+-
zamiast---
nie podłączać automatycznie fajerwerków powyżej / poniżej, nadal musi znajdować się|
nad / poniżej, aby połączyć fajerwerki.-+-
w miejsce-|-
jest w porządku, jak jest.Odpowiedzi:
C ++
Całkowita długość: 9059, całkowita powierzchnia: 27469, awarie: 13.
Uwaga: Wynik obejmuje kary za niepowodzenie.
Przykładowe dane wyjściowe:
Pełna wydajność: http://pastebin.com/raw.php?i=spBUidBV
Czy nie lubisz tylko brutalnych rozwiązań? To trochę więcej niż prosty algorytm cofania: nasz niestrudzony pracownik porusza się po mapie, w razie potrzeby umieszczając bezpieczniki i fajerwerki, jednocześnie testując wszystkie możliwe ruchy w dowolnym momencie. Cóż, prawie --- ograniczamy zestaw ruchów i wcześnie porzucamy nieoptymalne stany, aby nie trwało to nieznośnie długo (a w szczególności, aby zakończyło się). Szczególną uwagę należy zwrócić na to, aby nie tworzyć żadnych cykli lub niezamierzonych ścieżki i nie wracać tą samą drogą, którą przyszliśmy, więc gwarantujemy, że nie odwiedzimy dwukrotnie tego samego stanu. Mimo to znalezienie optymalnego rozwiązania może zająć trochę czasu, więc ostatecznie rezygnujemy z optymalizacji rozwiązania, jeśli zajmie to zbyt dużo czasu.
Ten algorytm ma jeszcze trochę miejsca. Po pierwsze, można znaleźć lepsze rozwiązania poprzez zwiększenie
FRUSTRATION
parametrów. Nie ma konkurencyjnych bankomatów, ale te liczby można zwiększyć, jeśli i kiedy ...Skompilować z:
g++ fireworks.cpp -ofireworks -std=c++11 -pthread -O3
.Uruchom z:
./fireworks
.Odczytuje dane wejściowe ze STDIN i zapisuje dane wyjściowe do STDOUT (być może poza kolejnością).
Pyton
Całkowita długość: 17387, całkowita powierzchnia: 62285, awarie: 44.
Przykładowe dane wyjściowe:
Pełna wydajność: http://pastebin.com/raw.php?i=mgiqXCRK
Dla porównania, oto znacznie prostsze podejście. Próbuje połączyć fajerwerki z jedną główną linią bezpiecznika, tworząc kształt „klatki schodowej”. Jeśli fajerwerk nie może połączyć się bezpośrednio z linią główną (co dzieje się, gdy dwa lub więcej fajerwerków zapala się jednocześnie), śledzi linię główną w poszukiwaniu punktu, w którym może rozgałęzić się prostopadle w dół lub w prawo (i zawiedzie, jeśli nie ma takiego punktu).
Nic dziwnego, że działa gorzej niż solver z brutalną siłą, ale nie z ogromną przewagą. Szczerze mówiąc, spodziewałem się, że różnica będzie nieco większa.
Uruchom z:
python fireworks.py
.źródło