Задание
Учитывая входное положительное целое число n
(от 1 до ограничения вашего языка включительно), верните или выведите максимальное количество различных положительных целых чисел, которые суммируются n
.
Тестовые случаи
Давайте f
определим действительную функцию согласно задаче:
Последовательность для f
, начиная с 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, ...
Как большой тестовый пример:
>>> f(1000000000) // Might not be feasible with brute-forcers
44720
Тестовый код
Для любых тестовых случаев, не указанных явно, вывод вашего кода должен соответствовать результату следующего:
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
Аддисон Крамп
источник
источник
Ответы:
05AB1E , 4 байта
Попробуйте онлайн!
Идеальный инструмент для работы.
ÅT
дает перечень Å будет T riangular числа до и включая N ( к сожалению , включает в себя-тоже, в противном случае было бы 3 байта),g<
получает Len г - й и уменьшает его.источник
Желе ,
65 байтПопробуйте онлайн!
Несколько эффективнее. Эта последовательность увеличивается на треугольные числа, поэтому она просто подсчитывает, сколько треугольных чисел меньше n .
Объяснение:
источник
Haskell , 26 байтов
-2 байта благодаря H.PWiz.
Попробуйте онлайн!
Это возвращает n-й элемент целых чисел, где каждый i реплицируется i + 1 раз.
источник
succ
обозначаетsuccessor
.Brain-Flak , 36 байт
Попробуйте онлайн!
При этом используется та же структура, что и в стандартном алгоритме деления, за исключением того, что «делитель» увеличивается каждый раз, когда он читается.
источник
Пари / ГП , 19 байт
Попробуйте онлайн!
источник
Brain-Flak , 82 байта
Добавлены пробелы для «читабельности»
Попробуйте онлайн!
источник
Желе , 7 байт
Попробуйте онлайн!
Желе , 9 байт
Попробуйте онлайн!
Это длиннее, чем у
Денисаи диджея, но на этот раз специально . Очень, очень эффективно .источник
M
.R , 28 байт
Попробуйте онлайн!
Создает вектор
1
повторяющихся2
времен,2
повторяющихся3
времен, ...,n
повторяющихсяn+1
времен и принимаетnth
элемент. Это приведет к ошибке памяти либо из-за1:n
слишком большого размера, либо из-за слишком большого повторного списка сn*(n+1)/2 - 1
элементами.R , 29 байт
Попробуйте онлайн!
Вычисляет значение напрямую, используя формулу из ответа алефальфы . Это должно выполняться без проблем, кроме, возможно, числовой точности.
R , 30 байт
Попробуйте онлайн!
Считает треугольные числа меньше или равно
n
. Возможно, это приведет к ошибке памяти, если она1:n
будет достаточно большой, например, при1e9
ее выдачеError: cannot allocate vector of size 3.7 Gb
.источник
APL (Дьялог) , 8 байт
Попробуйте онлайн!
источник
TI-Basic, 12 байт
источник
JavaScript (Node.js) , 18 байт
Попробуйте онлайн!
источник
floor((sqrt(8x+4)-1)/2)
(ваша формула) иfloor((sqrt(8x+1)-1)/2)
(правильная формула) дают одинаковый результат для каждогоx
.Japt , 8 байт
Закрытое формульное решение.
Попытайся
объяснение
Умножьте на 8, добавьте 1 (
Ä
), получите квадратный корень (¬
), вычтите 1 (É
) и поделите результат на 2 (z
).Альтернатива, 8 байт
Порт решения DJMcMayhem's Jelly .
Попытайся
Создайте массив целых чисел (
õ
) от 1 до input, кумулятивно уменьшите (å
) на добавление (+
) и count (è
) элементов, которые меньше или равны (§
) input (U
).источник
Befunge,
3220 байтПопробуйте онлайн!
источник
Brain-Flak ,
705648 байтПопробуйте онлайн!
объяснение
Основной частью этого является следующий фрагмент, который я написал:
Это ничего не изменит, если TOS будет положительным, и переключит стеки в противном случае. Это супер стека нечисто, но это работает. Теперь основная часть программы вычитает все большие числа из входных данных, пока входные данные не являются положительными. Мы запускаем аккумулятор в 1 каждый раз, вычитая 1 больше, чем аккумулятор из входа.
Мы можем поместить это в фрагмент выше
Это помещается в цикл, поэтому он выполняется до тех пор, пока мы не переключим стеки. Как только цикл заканчивается, мы извлекаем аккумулятор, переключая стеки и удаляя ненужные.
источник
Pyth , 7 байт
Попробуйте онлайн!
Фильтруйте целочисленные разделы, которые не
I
зависят от дедупликации, сохраняйте целочисленные разделы и получайтеh
ихl
значение.Доказательство действительности
Не очень строгий и не сформулированный.
Пусть A = a 1 + a 2 + ... + а п и B = B 1 + B 2 + ... + Ь т две различные разделы одноготого же целого числа N . Предположим, что A - самое длинное уникальное разбиение. После того, как мы дедуплицируем B , то есть заменяем несколько вхождений одного и того же целого числа только одним из них, мы знаем, что сумма B меньше, чем N, . Но мы также знаем, что результат функции увеличивается (не строго), поэтому мы можем сделать вывод, что самый длинный уникальный раздел A всегда имеет по крайней мере такое же количество элементов, что и количество уникальных элементов в других разделах. ,
источник
Треугольность , 49 байтов
Попробуйте онлайн!
Как это устроено
Треугольность требует, чтобы код имел треугольное распределение точек. То есть длина каждой строки должна быть равна числу строк, умноженному на 2 и уменьшенному, и каждая строка должна иметь (с каждой стороны) количество точек, равное ее позиции в программе (нижняя строка - строка 0, тот, что выше, это строка 1 и т. д.). Есть только пара команд, и любой символ, кроме тех, которые перечислены на странице 'Wiki / Commands', обрабатывается как недопустимый (посторонние точки никак не влияют на программу, пока общая форма программы остается прямоугольной).
Обратите внимание, что для команд с двумя аргументами я использовал a и b в объяснении. Имея это в виду, давайте посмотрим, что делает настоящая программа, после удаления всех посторонних символов, которые восполняют отступы:
Альтернативное решение и короче, если заполнение не требуется:
Попробуйте онлайн!
источник
PowerShell 3.0, 45 байт
Математический колл больно, а округление банкира PS - это настоящий дьявол (следовательно, ему нужно регулярное выражение для усечения, чтобы сохранить байт), но это выглядит довольно хорошо.
источник
Java (JDK) , 28 байт
Попробуйте онлайн!
Потому что пример действительно не был удачным: p
кредиты
источник
Желе , 7 байт
Работает примерно за O (2 н ) времени.
Попробуйте онлайн!
Как это устроено
источник
JavaScript (ES7),
2219 байт-3 байта благодаря ETHproductions.
Попытайся
объяснение
Умножьте входное значение на 8 и прибавьте 1, увеличьте его до степени .5, получив квадратный корень, вычтите 1 и сдвиньте результат сдвига вправо на 1.
источник
n=>(8*n+1)**.5-1>>1
сохранить 3 байта? (не проверял)Python 2/3, 32 байта
Python реализация формулы закрытой формы
Целочисленное деление
//2
округляет до нуля, поэтому неfloor( )
требуетсяисточник
from math import sqrt
работать? Если так, это должно быть включено в bytecount. (В этом случаеlambda n:int((math.sqrt(1+8*n)-1)//2) import math
немного короче. )Haskell , 28 байт
В некотором роде скучно, но оно
намного короче, чем другое решение на Haskell, иимеет действительно приятное, бессмысленное выражение. К сожалению, я не мог бы сделать это короче без мешающей системы типов:Попробуйте онлайн!
Pointfree, 33 байта
В качестве альтернативы, 33 байта
Та же длина, что и у точечной версии, но гораздо интереснее.
источник
Млечный Путь , 12 байт
объяснение
источник
Пыть ,
75 байтОбъяснение:
Быстрее, но дольше
Пыть ,
119 байтОбъяснение:
Альтернативный способ - порт Шегги
Пыть ,
87 байтисточник
J 11 байт
Попробуйте онлайн!
источник
*
для производства 1Пробел , 111 байт
Буквы
S
(пробел),T
(табуляция) иN
(новая строка) добавляются только как подсветка.[..._some_action]
добавлено только в качестве объяснения.Попробуйте онлайн (только с необработанными пробелами, вкладками и новыми строками).
Объяснение в псевдокоде:
Использует формулу:
ПРИМЕЧАНИЕ. В пробелах нет встроенного квадратного корня, поэтому мы должны сделать это вручную.
источник
Витси , 16 байтов
Попробуйте онлайн!
Могу также добавить свой собственный вклад в микс. Это короче, чем решение итераций разбиения в Vitsy.
источник
Оазис , 14 байт
Попробуйте онлайн!
Как?
Это рекурсивное решение, которое увеличивает результат, когда встречает треугольный индекс, начиная с 0 для ввода 0.
источник
Perl 5
-p
, 19 (++) байтовПопробуйте онлайн!
источник
Рубин , 27 байт
Три по цене одного. Я разочарован тем, что не могу идти короче.
Попробуйте онлайн! (чтобы выбрать функцию, добавьте перед ней f =)
источник