Twoim zadaniem jest, biorąc pod uwagę dodatnią liczbę całkowitą n
, wygenerowanie wyrażenia równego liczbie n
.
Haczyk polega na: dozwolona jest tylko liczba 1
na wyjściu.
Operatorzy do Twojej dyspozycji to:
+
,-
,*
I/
/
jest dzieleniem zmiennoprzecinkowym (so5/2 = 2.5
).
sqrt
(ass
)ceil
orazfloor
( odpowiednioc
if
)!
(Factorial)- W tym przypadku silnia działa tylko dla dodatnich liczb całkowitych.
Możesz także układać w stosy 1
razem, więc coś takiego 11
jest dopuszczalne na wyjściu. Liczą się jednak jako ta sama liczba 1
, która jest w liczbie (więc 11
liczy się jako 2 1
).
Musisz również dołączyć nawiasy wyjściowe, aby wyrażenie na wyjściu, gdy zostanie wykonane według kolejności operacji, dało wynik. Nie liczą się jednak jako operacje.
Przykłady:
- Wejście = 24, jedno możliwe wyjście =
(1+1+1+1)!
- Wejście = 11, jedno możliwe wyjście =
11
- Wejście = 5, jedno możliwe wyjście =
c(s((1+1+1+1)!))
- Sufit pierwiastka kwadratowego
24
jest5
.
- Sufit pierwiastka kwadratowego
Zasady:
- Masz gwarancję, że wejście jest dodatnią liczbą całkowitą od
1
do2^31-1
. - Twój program musi działać dla dowolnej dodatniej liczby całkowitej
2^31-1
, nawet jeśli nie są testowane. - Twój program musi zakończyć przetwarzanie wszystkich danych wyjściowych dla wszystkich liczb w zestawie w ciągu 1 godziny.
- Wyniki dla każdego uruchomienia programu muszą być dokładnie takie same - również żadnych nasion.
- Możesz zakodować wyrażenia tylko na stałe dla maksymalnie 10 wartości liczbowych.
- Nie możesz mieć wyimaginowanych liczb w dowolnym miejscu na wyjściu (więc nie
s(some negative number)
). - Nie możesz również mieć liczb większych
2^31-1
lub mniejszych niż-2^31+1
gdziekolwiek na wyjściu, nawet jeśli są onesqrt
edytowane lub/
edytowane (więc nie(((1+1+1)!)!)!
lub((1+1+1+1)!)!
).
Zestaw liczb:
945536, 16878234, 32608778, 42017515, 48950830, 51483452, 52970263, 54278649, 63636656, 78817406, 89918907, 90757642, 95364861, 102706605, 113965374, 122448605, 126594161, 148064959, 150735075, 154382918, 172057472, 192280850, 194713795, 207721209, 220946392, 225230299, 227043979, 241011012, 248906099, 249796314, 250546528, 258452706, 276862988, 277140688, 280158490, 286074562, 308946627, 310972897, 322612091, 324445400, 336060042, 346729632, 349428326, 352769482, 363039453, 363851029, 392168304, 401975104, 407890409, 407971913, 425780757, 459441559, 465592122, 475898732, 482826596, 484263150, 506235403, 548951531, 554295842, 580536366, 587051904, 588265985, 588298051, 590968352, 601194306, 607771869, 618578932, 626776380, 667919873, 681786366, 689854904, 692055400, 697665495, 711608194, 734027104, 750869335, 757710567, 759967747, 777616154, 830071127, 833809927, 835873060, 836438554, 836945593, 863728236, 864158514, 871273503, 881615667, 891619600, 897181691, 918159061, 920521050, 924502226, 929983535, 943162304, 950210939, 950214176, 962610357, 974842859, 988572832
(Jest to 100 liczb losowych od 1 do 1 miliarda).
System oceniania:
Twój wynik jest ustalany w następujący sposób:
- Twój program zostanie przetestowany na losowych liczbach w zestawie.
- Musisz podać dane wyjściowe wygenerowane przy użyciu liczb losowych w zestawie (w odpowiedzi lub w linku do wklejania).
- Twoje następnie mają dwa „wyniki”: wynik główny i wynik dodatkowy.
- Twój główny wynik to
(no. of 1's in output)*(no. of operators in output)
. Jeśli twój główny wynik jest najniższy, wygrywasz. - Drugi wynik to czas przesłania, w GMT i za 24 godziny. Tak więc, jeśli prześlesz swój program 12 września, 00:00 GMT, twój wynik to
12/09/2016, 00:00
(użyjDD/MM/YYYY HH:MM
do formatowania).
- Twój główny wynik to
Wyświetl swój wynik w następujący sposób:
(language name)
Primary Score = (primary score)
Secondary Score = (secondary score)
(no. of 1's) `1`'s, (no. of operators) operators
Zamień wszystkie elementy w nawiasach odpowiednio na swoje imię, wynik główny i wynik dodatkowy.
Aktualny zwycięzca:
Obecnym zwycięzcą jest @ChrisJefferson, który ma podstawowy wynik 3,810,660
.
źródło
Odpowiedzi:
C ++ 11
Dalsza niewielka aktualizacja: znacznie mniej dodawaj i wypróbuj wszystkie liczby w postaci A * B + C. Wierzę, że w terminie, to jest dość blisko do optymalnego, zakładając że używasz tylko
+
,*
i!
. Pozostawiam innych operatorów ludziom, którzy mają więcej czasu niż ja!Mała aktualizacja: Staraj się bardziej wykorzystywać silnie i liczby, takie jak 11 .... 111. Naprawiono również błąd, którego nie liczyłem
!
w kosztachNowy wynik:
Pierwotny wynik = 3810,660
Drugi wynik = 12/09/2016 20:00
2532
1
s, 1505 operatorów.Różne sztuczki razem wzięte. Mój program zaczyna się od ustawienia najkrótszego programu dla wszystkich silni i liczb w postaci 111..111 (nie sądzę, że jest to sprzeczne z zasadą okablowania, ponieważ są to najkrótsze sposoby tworzenia tych liczb. Mógłbym zmienić kolejność mój kod, więc sprawdzam te wzorce w programowaniu dynamicznym, jeśli chcesz). Następnie zastosuj częściowe podejście do programowania dynamicznego, wypróbowując różne formy:
Niestety nie mogę wypróbować wszystkich sposobów dekompozycji liczby, więc wybrałem silnię i 11 ... 11, aby wypróbować tylko najbliższą liczbę, dla A + B, aby spróbować rzeczy w pobliżu A / 2, i dla A * B + C, aby spróbować tylko dość małych As.
Łatwo byłoby to rozszerzyć, aby wypróbować niektóre, próbując czasami nieco przeregulować (szczególnie w A * B - C), ale lubię tylko próbować rosnąć.
Ponadto bardzo trudno jest zoptymalizować warunek optymalizacji (nie podoba mi się to!), Ponieważ w zasadzie nie można wymyślić „najlepszej” wartości dla każdej liczby w oderwaniu, należy rozważyć swój zestaw odpowiedzi globalnie (czego nie zamierzam robić).
Ostrzeżenie: ten program wymaga komputera 64-bitowego i około 10 GB pamięci (ponieważ nieefektywnie tworzę gigantyczną tablicę dla wszystkich częściowo obliczonych wyników).
Program:
Wyniki:
źródło
!
. Myślę, że to 1632 operatorów, a nie 1407. (Co jednak nadal prowadzi do świetnego wyniku).long maxval
grumble grumbleHaskell
Główny wynik: 27242281
Drugi wynik: 12/09/2016 09:01
11891
1
, 2291 operatorówZasadniczo znajduje najkrótszą drogę, aby użyć tylko + i -
Wynik:
źródło
Python, wynik 17136288
wynik wtórny: 12/09/2016 08:53
(4784 z nich i 3582 operacji)
Prace w toku, ale OP poprosił o mój obecny kod ...
Wyjście - uwaga, że
t
jest to funkcja silnia, tak aby nie mylić zf
dlafloor
jeśli przyzwyczaja - I każdy oceniany za pomocą funkcjit
(powyżej), aby dokładnie sprawdzić, że są poprawne:źródło
t
dane wyjściowe?JavaScript (ES6), 27212498, 12.09.2016 09: 46: 34Z
Używa tylko + i -. Na podstawie mojej odpowiedzi, aby zminimalizować tych
źródło
Pyton
Pierwotny wynik = 2214138604871819402525
Drugi wynik = 12/09/2016, 07:53
Oto kod:
Tylko po to, żeby piłka się toczyła.
Zasadniczo dane wyjściowe
1+1+1...+1
, gdzie liczba1
wyrażeń w wyprowadzonym wyrażeniu jest równan
.W sumie istnieje
47054634305
1
zestaw liczb i47054634205
operatorów (wszystkie są+
).Nie zamierzam tu zamieszczać pastebinu, bo masz pomysł.
źródło
2**31-1
.n-1
? Działa dla mnie dobrze.awk
wynik główny 46933701
wynik wtórny 12/09/2016 19:20
(6901, 6801 operacji)
Wystarczy wydrukować reprezentację binarną obliczoną od lewej do prawej.
Na przykład 19 to 10011, co oznacza ((((( 1 ) * 2 + 0 ) * 2 + 0 ) * 2 + 1 ) * 2 + 1 ).
Po prostu pomijam
+0
i piszę2
jako(1+1)
.Byłem ciekawy, jak ta metoda byłaby punktowana.
Wynik:
źródło
Python 3
Podstawowy wynik:
69720516
Drugi wynik:
09:30 14/09/2016
Edycja: Teraz używa mnożenia, aby znacznie zmniejszyć wynik.
To świetnie wykorzystuje czynniki i rekurencję. W sumie program wykorzystuje:
5958
te11702
operatorzyIdeone to!
źródło
JAWA
Podstawowy wynik
1045978739
Drugi wynik
12/09/2016 16:05
37193
1s
28123
operators
źródło
1
na początku każdego(1*11*11*...*11)
.Emacs Lisp
Główny wynik: 81638725
Drugi wynik: 12/09/2016 09:35
Zasadniczo buduje sumę w domenie (1, 11, 111, ...), która jest równoważna n.
źródło
111+11+1+1
, prawda? (Popraw mnie, jeśli się mylę.)1
s na całej liczbie wynikowej 100 i pomnożyłeś to przez całkowitą liczbę+
operacji na całej wartości wyjściowej?AWK , 15642720
Drugi wynik = 30.05.2017, 21:11
Wypróbuj online!
Jeden: 4590
Ops: 3408 Podstawowy wynik = 15642720 Drugi wynik = 30/05/2017 21:11
źródło