Otrzymujesz mnóstwo ciężarów, a Twoim zadaniem jest zbudowanie małego, zrównoważonego telefonu komórkowego przy użyciu tych ciężarów.
Dane wejściowe to lista liczb całkowitych w zakresie od 1 do 9 włącznie. Mogą istnieć duplikaty.
Wyjście to obraz ascii telefonu komórkowego, który po zawieszeniu byłby zrównoważony. Być może najlepiej to pokazuje przykład:
Wejście
3 8 9 7 5
możliwa wydajność
|
+-----+---------+
| |
+--+-+ +----+------+
| | | |
8 ++--+ 7 5
| |
9 3
Musisz użyć znaków ascii, jak pokazano. Segmenty poziomy i pionowy mogą mieć dowolną długość. Żadna część telefonu komórkowego nie może dotykać (poziomo lub pionowo) innej niepołączonej części telefonu komórkowego. Wszystkie obciążniki muszą być zawieszone na pionowym segmencie o długości co najmniej 1 i musi istnieć pionowy segment, na którym zawieszony jest cały telefon.
Wielkość komórkowego jest całkowita liczba +
, -
i |
znaki wymagane, aby go zbudować. Niższe rozmiary są lepsze.
Możesz umieścić tyle połączeń w segmencie, ile chcesz. Na przykład:
Wejście
2 3 3 5 3 9
możliwa wydajność
|
+---+---+-----------+
| | |
+--+-+ 5 9
| | |
2 | 3
|
+++
| |
3 3
Zwycięskim programem jest ten, który może wygenerować najniższą średnią wielkość urządzeń mobilnych dla testowego zestawu danych wejściowych. Prawdziwy test jest super tajny, aby zapobiec kodowaniu na stałe, ale będzie on mniej więcej taki:
8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 7
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 7 7
3 4 4 4 4 5 5 5 5 6 6 6 6 7 7 7 7
źródło
total_weight_hung_from_point * distance_of_point_from_pivot
musi być taka sama po obu stronach punktu obrotu.Odpowiedzi:
Python 2.
Trochęoszukuję :Buduję tylko telefony komórkowe z jednym poziomym.
Mam wrażenie (ale tego nie udowodniłem), że optymalny telefon komórkowy w danych warunkach faktycznie zawsze ma tylko jeden poziom.Edycja: Nie zawsze prawda; z2 2 9 1
Nabb znalazł kontrprzykład w komentarzach poniżej:Po prostu robię głupie brutalne zmuszanie:
Moje wyniki dla twoich przykładowych danych wejściowych; każdy był uruchamiany przez 5 sekund (jestem świadomy, że jest to niedorzeczne dla małych - po prostu przejście przez wszystkie możliwe kombinacje byłoby szybsze). Zauważ, że ponieważ istnieje element losowy, kolejne testy mogą znaleźć lepsze lub gorsze wyniki.
Kod (pełny, ponieważ to nie jest kod golfowy):
źródło
1 9 2 8
generuje1-------8+-9--2
; z czubka głowy nie mogę wymyślić nic lepszego (ale nie polegałbym na tym) - masz coś?2 2 9 1
tj. (2 + 2) * 3 = 9 + 1 * 3 dla rozmiaru 16 zamiast2-9+--2----1
18. Domyślam się, że istnieje próg (może 5 lub 6 ), po którym pojedynczy poziomy rząd jest zawsze optymalny.2-2-+9-1
saldami, z wynikiem 13(4*2+2*2 = 9*1+1*3)
. Więc nie sądzę, że jest to dobry kontrprzykład.To stare pytanie, ale właśnie zobaczyłem, że pojawia się w zakładce górnych pytań, więc oto moje (optymalne) rozwiązanie:
Patrząc na zasady jestem pewien, że to nie oszustwo, choć wydaje się, że tak jest. Spowoduje to po prostu wyprowadzenie wszystkich podanych liczb w łańcuchu pionowym, przy całkowitym koszcie 2 * liczba_wejść (co jest minimalnym możliwym wynikiem, ponieważ każda liczba musi mieć słupek nad nim, bez względu na układ). Oto przykład:
Produkuje:
Co oczywiście jest w idealnej równowadze.
Początkowo zamierzałem spróbować czegoś więcej w duchu tego wyzwania, ale szybko okazało się, że i tak zoptymalizowałem tę strukturę
źródło
|
do dolnej części wagi.Oto rozwiązanie, które brutalnie wymusza najmniejsze jednorzędowe rozwiązanie. Kod iteruje wszystkie permutacje i oblicza środek masy dla każdego z nich. Jeśli środek masy ma współrzędne całkowite, znaleźliśmy rozwiązanie.
Po wypróbowaniu wszystkich permutacji dodajemy segment do mieszanki (równoważny masie masy 0) w naszym bieżącym zestawie wag i ponawiamy próbę.
Aby uruchomić program, wykonaj
python balance.py 1 2 2 4
.który produkuje te najlepsze rozwiązania:
źródło
Python 3
Uważam, że nie jest to gorsze niż 1 więcej niż optymalne w każdym z przypadków testowych i robi to w 5 sekund.
Zasadniczo używam podejścia z pojedynczym paskiem. Losowo zamawiam dane wejściowe, a następnie wkładam odważniki do pręta pojedynczo. Każdy element jest albo ustawiony w pozycji, która minimalizuje nadwagę po obu stronach, albo drugą najlepszą pozycję z tej perspektywy, wykorzystując pierwsze 75% czasu, a drugie 25% czasu. Następnie sprawdzam, czy telefon komórkowy jest zrównoważony na końcu i czy jest lepszy niż najlepszy telefon komórkowy znaleziony do tej pory. Przechowuję najlepszy, a następnie zatrzymuję się i drukuję go po 5 sekundach wyszukiwania.
Wyniki w 5-sekundowych seriach:
Kod:
Jedyne z tych rozwiązań, które moim zdaniem są nieoptymalne, jest najdłuższe, które ma takie rozwiązanie, które znalazłem po 10 minutach pracy:
źródło