Zadanie

Biorąc pod uwagę dodatnią liczbę całkowitą wejściową n(od 1 do limitu twojego języka, włącznie), zwróć lub wypisz maksymalną liczbę różnych dodatnich liczb całkowitych, które sumują się n.

Przypadki testowe

Niech fokreślić prawidłową funkcję w zależności od zadania:

Sekwencja fod 1:

1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, ...

Jako większy przypadek testowy:

>>> f(1000000000) // Might not be feasible with brute-forcers
44720

Kod testowy

W przypadku przypadków testowych, które nie zostały wyraźnie podane, dane wyjściowe kodu powinny być zgodne z wynikiem:

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        System.out.println((int) Math.floor(Math.sqrt(2*x + 1./4) - 1./2));
    }
}

Wypróbuj online!

05AB1E , 4 bajty

ÅTg<

Wypróbuj online!

Idealne narzędzie do pracy.

ÅTPlony lista nm ll ţ numery riangular włącznie N (niestety zawiera 0 też w inny sposób byłoby 3 bity), g<dostaje len g p i zmniejsza się.

Galaretka , 6 5 bajtów

R+\»ċ

Wypróbuj online!

Nieco wydajne. Ta sekwencja zwiększa się przy liczbach trójkątnych, więc liczy tylko, ile liczb trójkątnych jest mniejszych niż n .

Wyjaśnienie:

        # Main link
R       # Range, generate [1..n]
 +\     # Cumulative sum (returns the first n triangular numbers)
   »    # For each element, return the maximum of that element and 'n'
    ċ   # How many elements are 'n'? (implicit right argument is n)

Haskell , 26 bajtów

-2 bajty dzięki H.PWiz.

(!!)$do x<-[0..];x<$[0..x]

Wypróbuj online!

Zwraca n-ty element liczb całkowitych, w którym każdy i jest replikowany i + 1 razy.

Brain-Flak , 36 bajtów

<>(())({()<(({}())){<>({}[()])}>{}})

Wypróbuj online!

Wykorzystuje tę samą strukturę co standardowy algorytm podziału, z tym wyjątkiem, że „dzielnik” jest zwiększany za każdym razem, gdy jest czytany.

Pari / GP , 19 bajtów

n->((8*n+1)^.5-1)\2

Wypróbuj online!

Brain-Flak , 82 bajty

Dodano spację dla „Czytelności”

(())

{
    {}

    ((({})[[]]))

    ([({}<(())>)](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}

}{}{}{}

([]<>)

Wypróbuj online!

Galaretka , 7 bajtów

×8‘½’:2

Wypróbuj online!

Galaretka , 9 bajtów

Ḥ+4ݤ½_.Ḟ

Wypróbuj online!

To dłużej niż Dennisa i DJ-ów, ale tym razem celowo . Bardzo, bardzo wydajny .

R , 28 bajtów

function(n)rep(1:n,1:n+1)[n]

Wypróbuj online!

Tworzy wektor 1powtarzanych 2czasów, 2powtarzanych 3czasów, ..., npowtarzanych n+1czasów i przyjmuje nthelement. Spowoduje to błąd pamięci albo dlatego, że 1:njest zbyt duży, albo dlatego, że lista powtarzanych n*(n+1)/2 - 1elementów jest zbyt duża.

R , 29 bajtów

function(n)((8*n+1)^.5-1)%/%2

Wypróbuj online!

Oblicza wartość bezpośrednio, korzystając ze wzoru znalezionego w odpowiedzi Alephalpha . Powinno to działać bez żadnych problemów, z wyjątkiem możliwie dokładności liczbowej.

R , 30 bajtów

function(n)sum(cumsum(1:n)<=n)

Wypróbuj online!

Liczy liczby trójkątne mniejsze lub równe n. Prawdopodobnie spowoduje to błąd pamięci, jeśli 1:njest wystarczająco duży - na przykład przy 1e9jego rzucaniu Error: cannot allocate vector of size 3.7 Gb.

APL (Dyalog) , 8 bajtów

+/+\∘⍳<⊢

Wypróbuj online!

TI-Basic, 12 bajtów

int(√(2Ans+1/4)-.5

JavaScript (Node.js) , 18 bajtów

x=>(x-~x)**.5-.5|0

Wypróbuj online!

Japt , 8 bajtów

Zamknięte rozwiązanie formuły.

*8Ä ¬É z

Spróbuj

Wyjaśnienie

Pomnóż przez 8, dodaj 1 ( Ä), uzyskaj pierwiastek kwadratowy ( ¬), odejmij 1 ( É) i podziel wynik przez 2 ( z).

Alternatywnie, 8 bajtów

Port rozwiązania galaretki DJMcMayhem .

õ å+ è§U

Spróbuj

Wygeneruj tablicę liczb całkowitych ( õ) od 1 do wejścia, łącznie zmniejsz ( å) dodając ( +) i zlicz ( è) elementy, które są mniejsze lub równe ( §) wejściowi ( U).

Befunge, 32 20 bajtów

1+::1+*2/&#@0#.-`#1_

Wypróbuj online!

Brain-Flak , 70 56 48 bajtów

{([(({}[({}())()])[()])]<>){<>({}())}{}<>{}}<>{}

Wypróbuj online!

Wyjaśnienie

Główną częścią tego jest następujący fragment, który napisałem:

([(({})[()])]<>){<>({}())}{}<>{}

Nie zrobi to nic, jeśli TOS będzie dodatni i w przeciwnym razie zmieni stosy. To jest super nieczyste, ale działa. Teraz główna część programu odejmuje coraz większe liczby od danych wejściowych, dopóki dane wejściowe nie będą dodatnie. Akumulator uruchamiamy od 1 za każdym razem odejmując o 1 więcej niż akumulator od wejścia.

({}[({}())()])

Możemy to umieścić we fragmencie powyżej

([(({}[({}())()])[()])]<>){<>({}())}{}<>{}

To jest umieszczone w pętli, aby działało, dopóki nie zmienimy stosów. Po zakończeniu pętli odzyskujemy akumulator, zmieniając stosy i usuwając śmieci.

Pyth , 7 bajtów

lh{I#./

Wypróbuj online!

Filtruj - zachowuj partycje całkowite, które nie Iróżnią się od deduplikacji, chwyć head i uzyskaj jego length.

Dowód ważności

_{^{Niezbyt rygorystyczne ani dobrze sformułowane.}}

Niech a = ₁ + A ₂ + ... + a _n i b = ₁ + b ₂ + ... + B _m dwa oddzielne przegrody o tej samej liczby całkowitej N . Zakładamy, że A jest najdłuższą unikalną partycją. Po my deduplikuj B , czyli zastąpienie wielu wystąpień tej samej liczby całkowitej ze tylko jeden z nich, wiemy, że suma B jest mniejsza niż N . Ale wiemy również, że wynik funkcji rośnie (nie ściśle), więc możemy wywnioskować, że najdłuższa unikalna partycja A zawsze ma co najmniej taką samą liczbę elementów, jak liczba unikalnych elementów w innych partycjach.

Trójkątność , 49 bajtów

....)....
...2)2...
..)1/)8..
.)1/)IE/.
@^)1_+/i.

Wypróbuj online!

Jak to działa

Trójkątność wymaga, aby kod miał trójkątny rozkład kropek. Oznacza to, że długość każdego wiersza musi być równa liczbie wierszy pomnożonej przez 2 i zmniejszonej, a każdy wiersz musi mieć (z każdej strony) liczbę kropek równą swojej pozycji w programie (dolny wiersz to wiersz 0, ten powyżej to rząd 1 i tak dalej). Jest tylko kilka poleceń, a każdy znak inny niż wymieniony na stronie „Wiki / Commands” jest traktowany jako brak działania (zewnętrzne kropki nie wpływają w żaden sposób na program, o ile ogólny kształt programu pozostaje prostokątny).

Zauważ, że w przypadku poleceń dwuparametrowych użyłem a i b w całym objaśnieniu. Mając to na uwadze, zobaczmy, co robi rzeczywisty program, po usunięciu wszystkich obcych znaków, które składają się na dopełnienie:

)2)2)1/)8)1/)IE/@^)1_+/i | Input from STDIN and output to STDOUT.

)                        | Push a 0 onto the stack. Must precede integer literals.
 2                       | Push ToS * 10 + 2 (the literal 2, basically).
  )2                     | Again, push a 2 onto the stack. This can be replaced by D
                         | (duplicate), but then the padding would discard the saving.
    )1                   | Literal 1.
      /                  | Division. Push b / a (1 / 2).
       )8)1              | The literal 8 and the literal 1 (lots of these!).
           /             | Division. Push b / a (1 / 8).
            )IE          | Get the 0th input from STDIN and evaluate it.
               /         | Divide it by 1 / 8 (multiply by 8, but there isn't any
                         | operand for multiplication, and I'm not willing to add one).
                @        | Add 1 to the result.
                 ^       | Exponentiation. Here, it serves as a square too.
                  )1_+   | Decrement (add literal -1).
                      /  | Divide (by 2).
                       i | Cast to an integer.

Alternatywne rozwiązanie i krótsze, jeśli wypełnienie nie byłoby konieczne:

....)....
...2)1...
../DD)I..
.E/)4)1/.
+^s_+i...

Wypróbuj online!

PowerShell 3.0, 45 bajtów

[math]::Sqrt(2*$args[0]+.25)-.5-replace'\..*'

Wezwanie matematyczne boli, a zaokrąglanie przez bankiera PS jest faktycznym diabłem (stąd potrzeba wyrażenia regularnego, aby obciąć bajt), ale wydaje się to całkiem w porządku.

Java (JDK) , 28 bajtów

n->~-(int)Math.sqrt(8*n+1)/2

Wypróbuj online!

Ponieważ przykład nie był tak naprawdę dobrze golfowany: str

Kredyty

• -2 bajty dzięki Kevin Cruijssen

Galaretka , 7 bajtów

ŒPfŒṗṪL

Działa z grubsza w czasie O (2 ⁿ ) .

Wypróbuj online!

Jak to działa

ŒPfŒṗṪL  Main link. Argument: n

ŒP       Powerset; yield all subarrays of [1, ..., n], sorted by length.
   Œṗ    Yield all integer partitions of n.
  f      Filter; keep subarrays that are partitions.
     Ṫ   Tail; extract the last result.
      L  Compute its length.

JavaScript (ES7), 22 19 bajtów

n=>(8*n+1)**.5-1>>1

-3 bajty dzięki produktom ETH.

Spróbuj

o.innerText=(f=
n=>(8*n+1)**.5-1>>1
)(i.value=1000000000);oninput=_=>o.innerText=f(+i.value)

<input id=i type=number><pre id=o>

Wyjaśnienie

Pomnóż wartość wejściową przez 8 i dodaj 1, podnieś ją do potęgi .5, dając nam pierwiastek kwadratowy, odejmij 1 i bitowo przesuń wynik o 1.

Python 2/3, 32 bajty

Implementacja formuły zamkniętej w języku Python

lambda n:int((sqrt(1+8*n)-1)//2)

Podział liczb całkowitych //2zaokrągla się do zera, więc nie jest floor( )wymagany

Haskell , 28 bajtów

Trochę nudno, ale to znacznie krótsze niż inne rozwiązanie Haskell i ma naprawdę fajny, bezcelowy wyraz. Niestety nie mogłem go skrócić, gdyby system typów nie przeszkadzał:

g x=floor$sqrt(2*x+0.25)-0.5

Wypróbuj online!

Pointfree, 33 bajty

ceiling.(-0.5+).sqrt.(0.25+).(2*)

Alternatywnie 33 bajty

Taka sama długość jak wersja bez pointa, ale o wiele bardziej interesująca.

g n=sum[1|x<-scanl1(+)[1..n],n>x]

Droga Mleczna , 12 bajtów

'8*1+g1-2/v!

Wyjaśnienie

code         explanation       value

'            push input        n          
 8*          push 8, multiply  8n
   1+        add 1             8n+1
     g       square root       sqrt(8n+1)
      1-     subtract 1        sqrt(8n+1)-1
        2/   divide by 2       (sqrt(8n+1)-1)/2
          v  floor             floor((sqrt(8n+1)-1)/2)
           ! output

Pyt , 7 5 bajtów

Đř△>Ʃ

Wyjaśnienie:

                      Implicit input
Đř△                   Gets a list of the first N triangle numbers
   >                  Is N greater than each element in the list? (returns an array of True/False)
    Ʃ                 Sums the list (autoconverts booleans to ints)

Szybciej, ale dłużej

Pyt , 11 9 bajtów

Đ2*√⌈ř△>Ʃ

Wyjaśnienie:

Đ2*√⌈ř△           Gets a list of triangle numbers up to the ceiling(sqrt(2*N))-th
       >          Is N greater than each element of the list? (returns an array of True/False)
        Ʃ         Sums the array

Alternatywny sposób - port odpowiedzi Kudłaty

Pyt , 8 7 bajtów

8*⁺√⁻2÷

J , 11 bajtów

2&!inv<.@-*

Wypróbuj online!

2&!inv       solve [x choose 2 = input]
         -*  minus 1
      <.     and floor

Biała spacja , 111 bajtów

[S S S N
_Push_0][S N
S _Duplicate_0][T   N
T   T   _Read_integer_from_STDIN][T T   T   _Retrieve_input][S S S T    S S S N
_Push_8][T  S S N
_Multiply][S S S T  N
_Push_1][T  S S S _Add][S S T   T   N
_Push_n=-1][N
S S N
_Create_Label_SQRT_LOOP][S S S T    N
_Push_1][T  S S S _Add][S N
S _Duplicate_n][S N
S _Duplicate_n][T   S S N
Multiply][S T   S S T   S N
_Copy_0-based_2nd_(the_input)][S S S T  N
_Push_1][T  S S S _Add][T   S S T   _Subtract][N
T   T   N
_If_negative_jump_to_Label_SQRT_LOOP][S S S T   S N
_Push_2][T  S S T   _Subtract][S S S T  S N
_Push_2][T  S T S _Integer_divide][T    N
S T _Print_integer]

Litery S(spacja), T(tab) i N(nowa linia) dodane tylko jako wyróżnienia.
[..._some_action]dodano tylko jako wyjaśnienie.

Wypróbuj online (tylko z surowymi spacjami, tabulatorami i nowymi wierszami).

Objaśnienie w pseudo-kodzie:

Korzysta ze wzoru:

UWAGA: Białe znaki nie mają wbudowanego pierwiastka kwadratowego, więc musimy to zrobić ręcznie.

Integer i = read STDIN as integer
i = i * 8 + 1
Integer n = -1
Start SQRT_LOOP:
  n = n + 1
  If(n*n < i+1):
    Go to next iteration of SQRT_LOOP
n = (n - 2) integer-divided by 2
Print n as integer to STDOUT

Vitsy , 16 bajtów

2*14/+12/^12/-_N

Wypróbuj online!

Równie dobrze mogę dodać własny wkład do miksu. Jest to krótsze niż rozwiązanie iteracji partycji w Vitsy.

Oaza , 14 bajtów

n8*1+1tm1%_b+0

Wypróbuj online!

W jaki sposób?

n8*1+           8n + 1
     1tm        sqrt
        1%_     integer?
           b+   add f(n-1)

             0  f(0) is 0

Jest to rozwiązanie rekurencyjne, które zwiększa wynik, gdy napotka trójkątny indeks, zaczynając od 0 dla wejścia 0.

Perl 5 -p , 19 (++) bajtów

$_=0|-.5+sqrt$_*2+1

Wypróbuj online!

Rubinowy , 27 bajtów

Trzy za cenę jednego. Jestem rozczarowany, że nie mogę skrócić się.

->n{a=0;n-=a+=1while n>a;a}

->n{((8*n+1)**0.5-1).div 2}

->n{((n-~n)**0.5-0.5).to_i}

Wypróbuj online! (aby wybrać funkcję, dodaj f = przed nią)