Dajemy listę liczb całkowitych p1, ..., pk (niekoniecznie różne), gdzie każda z nich ma wartość od 1 do 9 włącznie. Używając każdego z p1, ..., pk dokładnie raz, możemy utworzyć konkatenację cyfr, aby uzyskać nową listę liczb; następnie wyprowadzamy produkt z tej nowej listy. Celem jest maksymalizacja tego produktu poprzez wybranie najlepszej kombinacji cyfr.
Na przykład dostajemy listę: 2 3 2 (oddzielone spacjami). Możemy utworzyć następujące konkatenacje:
2 3 2
(produktem tych konkatenacji jest12
)23 2
(produkt jest46
)32 2
(produkt jest64
)22 3
(produkt jest66
)
Ponieważ największym produktem, który możemy stworzyć w postaci konkatenacji, jest 66, wytwarzamy to.
Zasady:
- Musi istnieć co najmniej jedno mnożenie (tzn. Nie można po prostu połączyć wszystkich cyfr i wygenerować tego).
- Nie możesz używać innych operatorów niż mnożenie, ani wstawiać nawiasów itp.
- Załóżmy, że podana lista liczb całkowitych jest oddzielona spacjami, a wszystkie liczby całkowite mają wartości od 1 do 9.
Najkrótszy kod (w bajtach) wygrywa!
Przypadki testowe:
Wejście: 1 2 3
; Wyjście: 63
(tj. 21*3
)
Wejście: 2 5 9
; Wyjście: 468
( 52*9
)
Wejście: 1 2 3 4
; Wyjście: 1312
( 41*32
)
Odpowiedzi:
CJam,
32282312 bajtówWypróbuj online w interpretatorze CJam .
Dzięki @ user23013 za pomoc w uratowaniu 16 całych bajtów!
Pomysł
Dopuszczenie znaków w ciągu wejściowym dzieli go na liczby całkowite (grupy kolejnych cyfr) oddzielone spacjami. Naciskając zero, a następnie oceniając permutowany ciąg wejściowy, wypychamy dwie lub więcej liczb całkowitych. Pomnożenie dwóch najwyższych spowoduje wynik iloczynu wejścia podzielonego na dokładnie dwie liczby całkowite lub pewną nieoptymalną wartość.
Kod
źródło
l2%_,,1>\e!m*{~S+m<~*}%$W=
.l2%S+e!{0\~*}%$W=
.CJam,
3635 bajtówCałkiem prosto. Powtarza wszystkie możliwe kombinacje i sortuje je według produktu. Następnie wypisuje największy. Wszystko to, pamiętając, że powinno być obecne co najmniej 1 mnożenie.
Wkrótce doda wyjaśnienie.
Wypróbuj online tutaj
źródło
JavaScript (ES6) 125
Edytować Myślę, że @oberon ma rację: „każda nowa cyfra musi być powiązana z najmniejszą liczbą”
Nie zmienię tej odpowiedzi, kradnąc jego pomysł. Implementacja w ES6 miałaby 70 bajtów (znak zmieniony w porównaniu do porównania jako liczba, a nie łańcuchy)
Moje rozwiązanie
Jak powiedziałem w komentarzach, dla każdej pary liczb a, b iloczyn a * b jest mniejszy niż zwykła konkatenacja ab (= a * 10 ^ (cyfry b) + b). Lepiej więc unikać produktów i preferować konkatenację, ale ponieważ wymagany jest co najmniej 1 produkt, musimy zbudować 2 liczby i pomnożyć je.
Próbuję wszystkich możliwych grupowań cyfr, budując parę liczb do pomnożenia. Każda liczba jest oczywiście budowana przy użyciu cyfr w malejącej kolejności.
Na przykład z listą 4 cyfr [1 2 3 4] - spróbuj:
Maksymalna z tych wartości to wynik, którego potrzebujemy.
Zgrupowania można wyliczyć zapętlając mapę bitową o 4 bitach, z wartością minimalną 0001 i wartością maksymalną 0111 (czyli 1 << (4 -1) - 1)
Nie tak golfa
Przetestuj za pomocą poniższego fragmentu w przeglądarce Firefox.
źródło
Python 3, 111 bajtów
Prawdopodobnie jest o wiele bardziej golfowy. Lubię jednak jego czas działania (O ( n log n ), prawda?).
Nie obeznany z wyjaśnieniem.
źródło
Pyth, 25 bajtów
Pętlę nad każdą permutacją wejścia. Ponieważ więc każda optymalna kombinacja składa się z dwóch liczb całkowitych, po prostu dzielę ją w każdej możliwej pozycji i mnożę konkatenowane podziały. Następnie sortuję i otrzymuję ostatni element.
źródło
R, 164
Jako metoda nie jestem pewien, czy jest to solidne. W przypadkach, które przetestowałem, wydaje się, że działa za każdym razem. Próbowałem przetestować go pod kątem rozwiązania optymalizującego i wydaje się, że jest to również w porządku. Jestem więcej niż przygotowany na udowodnienie, że się mylę :) Jest miejsce na grę w golfa, ale miałem nadzieję, że najpierw otrzymam opinię na temat tej metody.
Ogólny proces to:
Rozszerzony o kilka komentarzy
I niektóre testy (zaimplementowane jako funkcja o nazwie g)
źródło