Podróżny musi zostać na n dni w hotelu poza miastem. Brakuje mu gotówki, a jego karta kredytowa wygasła. Ale ma złoty łańcuch z n ogniwami.
W tym hotelu obowiązuje zasada, że mieszkańcy powinni płacić czynsz każdego ranka. Podróżny dochodzi do porozumienia z menedżerem, aby płacić jedno ogniwo złotego łańcucha za każdy dzień. Ale menedżer wymaga również, aby podróżny wyrządzał jak najmniejsze szkody w łańcuchu, płacąc codziennie. Innymi słowy, musi znaleźć rozwiązanie, aby wyciąć jak najmniej linków.
Wycięcie linku tworzy trzy podłańcuchy: jeden zawierający tylko wycięty link i jeden z każdej strony. Na przykład przecięcie trzeciego ogniwa łańcucha o długości 8 tworzy podłańcuchy o długości [2, 1, 5]. Menedżer chętnie dokonuje zmian, aby podróżny mógł zapłacić pierwszego dnia łańcuchem długości 1, a następnie drugiego dnia łańcuchem długości 2, odzyskując pierwszy łańcuch.
Twój kod powinien wprowadzić długość n i wypisać listę linków do wycięcia o minimalnej długości.
Zasady :
- n jest liczbą całkowitą> 0.
- Możesz użyć indeksowania opartego na 0 lub 1 dla linków.
- W przypadku niektórych liczb rozwiązanie nie jest unikalne. Na przykład, jeśli
n = 15
obie[3, 8]
i[4, 8]
są ważne wyjścia. - Możesz albo zwrócić listę, albo wydrukować ją z dowolnym rozsądnym separatorem.
- To jest golf golfowy , więc wygrywa najkrótszy kod w bajtach.
Przypadki testowe :
Input Output (1-indexed)
1 []
3 [1]
7 [3]
15 [3, 8]
149 [6, 17, 38, 79]
Szczegółowy przykład
Dla n = 15 przecięcie ogniw 3 i 8 powoduje utworzenie podłańcuchów długości [2, 1, 4, 1, 7]
. To prawidłowe rozwiązanie, ponieważ:
1 = 1
2 = 2
3 = 1+2
4 = 4
5 = 1+4
6 = 2+4
7 = 7
8 = 1+7
9 = 2+7
10 = 1+2+7
11 = 4+7
12 = 1+4+7
13 = 2+4+7
14 = 1+2+4+7
15 = 1+1+2+4+7
Nie ma rozwiązania z tylko jednym cięciem, więc jest to optymalne rozwiązanie.
Uzupełnienie
Zauważ, że ten problem dotyczy partycjonowania liczb całkowitych. Szukamy partycji P od n takie, że wszystkie liczby całkowite od 1 do n mają co najmniej jeden patition który jest podzbiorem P .
Oto film na YouTube o jednym możliwym algorytmie dla tego problemu.
źródło
1+2
. Skąd wziął się drugi 2-ogniwowy łańcuch?Odpowiedzi:
05AB1E ,
23118 bajtówWypróbuj online!
Wykorzystuje indeksowanie 0.
Wyjaśnienie:
иg
wygląda jak noop, ale w rzeczywistości robi dwie użyteczne rzeczy: obcina się do liczby całkowitej (;
zwraca liczbę zmiennoprzecinkową) i powoduje awarię interpretera, jeśli x jest ujemny (jest to jedyny warunek wyjścia).W rozwiązaniu 23-bajtowym zastosowano zupełnie inne podejście, więc tutaj jest to dla potomności:
ÅœʒR2äθP}ʒæOê¥P}θ2äθη€O
( TIO , wyjaśnienie ).źródło
Ø.Ø
. Czy próbowałeś tylko losowych rzeczy, aby zmapować i zmapować wszystkie negatywy-1
? Niezależnie od tego bardzo miła odpowiedź i znacznie krótsza niż się spodziewałem. Myślałem o około 20 bajtach po tym, jak opublikowałem mój zły 42-bajt.Ø.Ø
był właściwie moim pierwszym pomysłem. Twój komentarz zainspirowało mnie do próby losowe rzeczy: znalazłem®Ÿà
,ï®M
i co ważniejszeиg
, co daje ten miły 8-byter. Zawsze denerwowało mnie to, że w wielu przypadkach osabie woli nic nie robić niż awarie (div przez 0, zły typ itp.), Więc ta awaria się przyda.Python 2 , 75 bajtów
Wypróbuj online!
Wyjaśnienie:
Tworzy sekwencję „binarnych” fragmentów, których liczba bazowa odpowiada liczbie cięć.
Na przykład:
63
można wykonać w 3 cięciach, co oznacza partycję w podstawie 4 (ponieważ mamy 3 pojedyncze pierścienie):Cięcia:,
5, 14, 31
który daje łańcuchy4 1 8 1 16 1 32
(posortowane:)1 1 1 4 8 16 32
.Wszystkie numery mogą być wykonane:
Inne przykłady:
źródło
f=
na początek? Ponieważ używasz wywołania dof
w funkcji lambda, a ja mogę jedynie założyć, że odwołujesz się do tej samej lambda, którą definiujesz.f
nie jest rekurencyjna, ale jest jednak wymieniona w kodzie i dlatego musi zostać nazwana.R ,
7769 bajtów-8 bajtów dzięki Aaronowi Haymanowi
Wypróbuj online!
(Ostatni łańcuch może wymagać skrócenia, jeśli przekroczymy całkowitą długość łańcucha).
Ungolfed (na podstawie poprzedniej, podobnej wersji):
źródło
n=1
, ale alternatywnym sposobem generowania wartości odcięcia jest powtórzenie1, 4, 4a(n-1)-4a(n-2)
.k
; odpowiada to OEIS A134401: oeis.org/A134401 Ale moja implementacja relacji powtarzalności zajmuje więcej bajtów niż bieżący kod.sum
zamiastmatch
.Galaretka , 12 bajtów
Wypróbuj online!
Tłumaczenie odpowiedzi 05AB1E firmy Grimy, więc pamiętajcie o tym! Nieco rozczarowany pojawia się to w bajcie dłużej, ale ma przynajmniej coś w rodzaju emotikonu jako pierwsze trzy bajty!
źródło
JavaScript (ES6), 66 bajtów
To jest port odpowiedzi TFeld .
Wypróbuj online!
źródło
C ++,
109, 107 bajtów-2 bajty dzięki Kevinowi
Algorytm jest podobny do odpowiedzi Robina Rydera. Kod jest napisany w kompilowalnej, całej formie. Spróbuj!
Detale:
Ma to odmianę C o tej samej długości bajtów (wydaje się, że nie wymaga osobnej odpowiedzi):
źródło
=0
pok
można usunąć, ponieważ0
jest to domyślnie.std::cin>>n;while(++k<<k<n);
może byćfor(std::cin>>n;++k<<k<n;);
. Mam też wrażenie, żefor(n-=k;n>0;k*=2,n-=k+1)
można to jakoś uprościć, łącząc różne rzeczy, ale nie jestem pewien, jak to zrobić. PS: Zmiana separatora przecinków na spację wygląda nieco lepiej, ponieważ nie widać końcowego imo, ale jest to czysto kosmetyczne :)=0
to konieczne do przenoszenia;) Zdałem sobie również sprawę, że miejsce po#include
nie jest konieczne.std::cin>>n
środku.Retina 0.8.2 , 61 bajtów
Wypróbuj online! 1-indeksowany port odpowiedzi @ Grimy. Wyjaśnienie:
Zacznij od,
N=2
a dane wejściowe zostaną przekonwertowane na jednoargumentowe.Wielokrotnie spróbuj odjąć
N
od danych wejściowych, a następnie podzielić przez 2.Jeśli się powiedzie, pamiętaj o 1 więcej niż dane wejściowe w poprzednim wierszu, zwiększ
N
wartość w bieżącym wierszu i zaktualizuj dane wejściowe do nowej wartości.Usuń
N
i zwiększ ostatnią wartość, aby była ona również indeksowana 1.Usuń pierwotnie zwiększoną wartość wejściową.
Konwertuj wyniki na dziesiętne.
źródło
Rubin , 62 bajty
Wypróbuj online!
Najczęściej skradziony z odpowiedzi TFeld na Python.
źródło