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 = 15obie [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.

05AB1E , 23 11 8 bajtów

ΔÍN-;иg=

Wypróbuj online!

Wykorzystuje indeksowanie 0.

Wyjaśnienie:

             # start from the implicit input
Δ            # loop forever
 Í           # subtract 2
  N-         # subtract the current iteration number
    ;        # divide by 2
     и       # create a list of length x
      g      # get the length of the list
       =     # print

иgwyglą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 ).

Python 2 , 75 bajtów

f=lambda n,i=0:n>=i<<i and f(n,i+1)or[min(n,2**j*i-i+j)for j in range(1,i)]

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, 31który daje łańcuchy 4 1 8 1 16 1 32(posortowane:) 1 1 1 4 8 16 32.

Wszystkie numery mogą być wykonane:

1       1
2       1 1
3       1 1 1
4       4
...
42      1 1 8 32
...
62      1 1 4 8 16 32
63      1 1 1 4 8 16 32

Inne przykłady:

18: 4,11        ->  3 1 6 1 7
27: 5,14,27     ->  4 1 8 1 13 1
36: 5,14,31     ->  4 1 8 1 16 1 5
86: 6,17,38,79  ->  5 1 10 1 20 1 40 1 7

R , 77 69 bajtów

-8 bajtów dzięki Aaronowi Haymanowi

pmin(n<-scan(),0:(k=sum((a=2:n)*2^a<=n))+cumsum((k+2)*2^(0:k))+1)[-n]

Wypróbuj online!

$k$$k$$(k+1)\cdot2^k\geq n$$1,1,\ldots,1$$k$$(k+1), 2(k+1), 4(k+1), 8(k+1), \ldots, (k+1)\cdot 2^{k-1}$

(Ostatni łańcuch może wymagać skrócenia, jeśli przekroczymy całkowitą długość łańcucha).

Ungolfed (na podstawie poprzedniej, podobnej wersji):

n = scan()                            # read input
if(n - 1){                            # If n==1, return NULL
  k = match(F, (a = 2:n) * 2 ^ a > n) # compute k
  b = (k + 1) * 2 ^ (1:k - 1)         # lengths of subchains
  c = 1:k + cumsum(b)                 # positions of cuts
  pmin(c, n )                         # if last value is >n, coerce it to n
}

$k$$k$$k$$k+1$$2k+1$$2k+2$$4k+4$$k$$(k+1)\cdot 2^k-1$.)

$a(k)$$n$$k$$a(k)$

Galaretka , 12 bajtów

’_‘ɼ:2»-µƬṖḊ

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!

JavaScript (ES6), 66 bajtów

To jest port odpowiedzi TFeld .

n=>(g=a=>n<++i<<i?a.map(j=>(j+=(i<<j)-i)>n?n:j):g([...a,i]))(i=[])

Wypróbuj online!

C ++, 109 , 107 bajtów

-2 bajty dzięki Kevinowi

#include<iostream>
main(){int n,k=0;for(std::cin>>n;++k<<k<n;);for(n-=k;n>0;k*=2,n-=k+1)std::cout<<n<<',';}

Algorytm jest podobny do odpowiedzi Robina Rydera. Kod jest napisany w kompilowalnej, całej formie. Spróbuj!

Detale:

std::cin>>n;               // get the value of n as input
while(++k<<k<n);           // determine k
for(n-=k;n>0;k*=2,n-=k+1)  // we don't need n, so the lengths...
    std::cout<<n<<' ';     // of links are subtracted repeatedly

Ma to odmianę C o tej samej długości bajtów (wydaje się, że nie wymaga osobnej odpowiedzi):

#include<stdio.h>
main(){int n,k=0;for(scanf("%d",&n);++k<<k<n;);for(n-=k;n>0;k*=2,n-=k+1)printf("%d,",n);}

Retina 0.8.2 , 61 bajtów

.+
11,$&$*
+`\b(1+),(\1(1*)1?\3)$
1$2¶1$1,$3
1+,
1
1A`
1+
$.&

Wypróbuj online! 1-indeksowany port odpowiedzi @ Grimy. Wyjaśnienie:

.+
11,$&$*

Zacznij od, N=2a dane wejściowe zostaną przekonwertowane na jednoargumentowe.

+`\b(1+),(\1(1*)1?\3)$

Wielokrotnie spróbuj odjąć Nod danych wejściowych, a następnie podzielić przez 2.

1$2¶1$1,$3

Jeśli się powiedzie, pamiętaj o 1 więcej niż dane wejściowe w poprzednim wierszu, zwiększ Nwartość w bieżącym wierszu i zaktualizuj dane wejściowe do nowej wartości.

1+,
1

Usuń Ni zwiększ ostatnią wartość, aby była ona również indeksowana 1.

1A`

Usuń pierwotnie zwiększoną wartość wejściową.

1+
$.&

Konwertuj wyniki na dziesiętne.

Rubin , 62 bajty

->n{(1...c=(0..n).find{|r|n<r<<r}).map{|b|[n,b-c+(c<<b)].min}}

Wypróbuj online!

Najczęściej skradziony z odpowiedzi TFeld na Python.