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 f
określić prawidłową funkcję w zależności od zadania:
Sekwencja f
od 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));
}
}
code-golf
math
number-theory
integer
integer-partitions
Addison Crump
źródło
źródło
Odpowiedzi:
05AB1E , 4 bajty
Wypróbuj online!
Idealne narzędzie do pracy.
ÅT
Plony 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ę.źródło
Galaretka ,
65 bajtówWypró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:
źródło
Haskell , 26 bajtów
-2 bajty dzięki H.PWiz.
Wypróbuj online!
Zwraca n-ty element liczb całkowitych, w którym każdy i jest replikowany i + 1 razy.
źródło
succ
oznaczasuccessor
.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.
źródło
Pari / GP , 19 bajtów
Wypróbuj online!
źródło
Brain-Flak , 82 bajty
Dodano spację dla „Czytelności”
Wypróbuj online!
źródło
Galaretka , 7 bajtów
Wypróbuj online!
Galaretka , 9 bajtów
Wypróbuj online!
To dłużej niż
Dennisai DJ-ów, ale tym razem celowo . Bardzo, bardzo wydajny .źródło
M
.R , 28 bajtów
Wypróbuj online!
Tworzy wektor
1
powtarzanych2
czasów,2
powtarzanych3
czasów, ...,n
powtarzanychn+1
czasów i przyjmujenth
element. Spowoduje to błąd pamięci albo dlatego, że1:n
jest zbyt duży, albo dlatego, że lista powtarzanychn*(n+1)/2 - 1
elementów jest zbyt duża.R , 29 bajtów
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
Wypróbuj online!
Liczy liczby trójkątne mniejsze lub równe
n
. Prawdopodobnie spowoduje to błąd pamięci, jeśli1:n
jest wystarczająco duży - na przykład przy1e9
jego rzucaniuError: cannot allocate vector of size 3.7 Gb
.źródło
APL (Dyalog) , 8 bajtów
Wypróbuj online!
źródło
TI-Basic, 12 bajtów
źródło
JavaScript (Node.js) , 18 bajtów
Wypróbuj online!
źródło
floor((sqrt(8x+4)-1)/2)
(twoja formuła) ifloor((sqrt(8x+1)-1)/2)
(poprawna formuła) dają taki sam wynik dla każdegox
.Japt , 8 bajtów
Zamknięte rozwiązanie formuły.
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 .
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
).źródło
Befunge,
3220 bajtówWypróbuj online!
źródło
Brain-Flak ,
705648 bajtówWypró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.
źródło
Pyth , 7 bajtów
Wypróbuj online!
Filtruj - zachowuj partycje całkowite, które nie
I
różnią się od deduplikacji, chwyćh
ead i uzyskaj jegol
ength.Dowód ważności
Niezbyt rygorystyczne ani dobrze sformułowane.
Niech a = 1 + A 2 + ... + a n i b = 1 + b 2 + ... + 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.
źródło
Trójkątność , 49 bajtów
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:
Alternatywne rozwiązanie i krótsze, jeśli wypełnienie nie byłoby konieczne:
Wypróbuj online!
źródło
PowerShell 3.0, 45 bajtów
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.
źródło
Java (JDK) , 28 bajtów
Wypróbuj online!
Ponieważ przykład nie był tak naprawdę dobrze golfowany: str
Kredyty
źródło
Galaretka , 7 bajtów
Działa z grubsza w czasie O (2 n ) .
Wypróbuj online!
Jak to działa
źródło
JavaScript (ES7),
2219 bajtów-3 bajty dzięki produktom ETH.
Spróbuj
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.
źródło
n=>(8*n+1)**.5-1>>1
zaoszczędzić 3 bajty? (nie testowałem)Python 2/3, 32 bajty
Implementacja formuły zamkniętej w języku Python
Podział liczb całkowitych
//2
zaokrągla się do zera, więc nie jestfloor( )
wymaganyźródło
from math import sqrt
działać? Jeśli tak, należy go uwzględnić w bajcie. (W takim przypadkulambda n:int((math.sqrt(1+8*n)-1)//2) import math
jest nieco krótszy. )Haskell , 28 bajtów
Trochę nudno, ale to
znacznie krótsze niż inne rozwiązanie Haskell ima naprawdę fajny, bezcelowy wyraz. Niestety nie mogłem go skrócić, gdyby system typów nie przeszkadzał:Wypróbuj online!
Pointfree, 33 bajty
Alternatywnie 33 bajty
Taka sama długość jak wersja bez pointa, ale o wiele bardziej interesująca.
źródło
Droga Mleczna , 12 bajtów
Wyjaśnienie
źródło
Pyt ,
75 bajtówWyjaśnienie:
Szybciej, ale dłużej
Pyt ,
119 bajtówWyjaśnienie:
Alternatywny sposób - port odpowiedzi Kudłaty
Pyt ,
87 bajtówźródło
J , 11 bajtów
Wypróbuj online!
źródło
*
produkcją 1Biała spacja , 111 bajtów
Litery
S
(spacja),T
(tab) iN
(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.
źródło
Vitsy , 16 bajtów
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.
źródło
Oaza , 14 bajtów
Wypróbuj online!
W jaki sposób?
Jest to rozwiązanie rekurencyjne, które zwiększa wynik, gdy napotka trójkątny indeks, zaczynając od 0 dla wejścia 0.
źródło
Perl 5
-p
, 19 (++) bajtówWypróbuj online!
źródło
Rubinowy , 27 bajtów
Trzy za cenę jednego. Jestem rozczarowany, że nie mogę skrócić się.
Wypróbuj online! (aby wybrać funkcję, dodaj f = przed nią)
źródło