Путешественник должен остановиться на n дней в отеле за городом. У него нет денег, а срок действия его кредитной карты истек. Но у него золотая цепочка с n звеньями.
Правило в этом отеле состоит в том, что жители должны платить за квартиру каждое утро. Путешественник приходит к соглашению с менеджером по оплате одного звена золотой цепочки за каждый день. Но менеджер также требует, чтобы путешественник наносил наименьший ущерб цепи при оплате каждый день. Другими словами, он должен найти решение, чтобы сократить как можно меньше ссылок.
Разрезание ссылки создает три подцепи: одну, содержащую только ссылку обрезки, и одну на каждой стороне. Например, разрезание третьего звена цепочки длиной 8 создает подцепи длины [2, 1, 5]. Менеджер рад внести изменения, поэтому путешественник может оплатить первый день цепочкой длины 1, а затем второй день цепочкой длины 2, получая первую цепочку обратно.
Ваш код должен вводить длину n и выводить список ссылок для вырезания минимальной длины.
Правила :
- n является целым числом> 0.
- Вы можете использовать индексацию на основе 0 или 1 для ссылок.
- Для некоторых чисел решение не является уникальным. Например, если
n = 15
оба[3, 8]
и[4, 8]
являются действительными выходами. - Вы можете либо вернуть список, либо распечатать его с любым разумным разделителем.
- Это код-гольф , поэтому выигрывает самый короткий код в байтах.
Тестовые случаи :
Input Output (1-indexed)
1 []
3 [1]
7 [3]
15 [3, 8]
149 [6, 17, 38, 79]
Подробный пример
Для n = 15 обрезка звеньев 3 и 8 приводит к подцепям длины [2, 1, 4, 1, 7]
. Это правильное решение, потому что:
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
Не существует решения с одним разрезом, так что это оптимальное решение.
добавление
Обратите внимание, что эта проблема связана с целочисленным разбиением. Мы ищем разбиения P из п , что все целые числа от 1 до п , по крайней мере , один patition , который является подмножеством P .
Вот видео на YouTube об одном из возможных алгоритмов этой проблемы.
источник
1+2
. Откуда появилась вторая 2-звенная цепь?Ответы:
05AB1E ,
23118 байтовПопробуйте онлайн!
Использует индексирование на основе 0.
Объяснение:
иg
выглядит как noop, но на самом деле он делает две полезные вещи: он усекает целое число (;
возвращает число с плавающей запятой) и сбивает интерпретатор, если x отрицателен (это единственное условие выхода).23-байтовое решение использовало совершенно другой подход, поэтому здесь оно для потомков:
ÅœʒR2äθP}ʒæOê¥P}θ2äθη€O
( TIO , объяснение ).источник
Ø.Ø
. Вы только что попробовали некоторые случайные вещи, чтобы выровнять и сопоставить все негативы-1
? Независимо от этого, очень хороший ответ и намного короче, чем я ожидал. Я думал о 20 байтах после того, как отправил свой плохой 42-байтовый код.Ø.Ø
была моя первая идея. Ваш комментарий вдохновил меня попробовать случайные вещи: я обнаружил®Ÿà
,ï®M
и, что более важно, тоиg
, что дает этот хороший 8-байтовый код. Меня всегда раздражало то, что osabie во многих случаях предпочитает ничего не делать, а только аварийно завершать работу (деление на 0, неправильный тип и т. Д.), Поэтому этот сбой пригодится.Python 2 , 75 байт
Попробуйте онлайн!
Объяснение:
Создает последовательность «двоичных» чанков, базовый номер которых соответствует количеству срезов.
Например:
63
может быть сделано в 3 разреза, что означает разделение в base-4 (так как у нас есть 3 одинарных кольца):Порезы:,
5, 14, 31
который дает цепочки4 1 8 1 16 1 32
(отсортировано:)1 1 1 4 8 16 32
.Все номера могут быть сделаны:
Другие примеры:
источник
f=
к началу? Поскольку вы используете вызовf
в лямбда-функции, и я могу только предположить, что вы ссылаетесь на ту же лямбду, которую вы определяете.f
не является рекурсивным, но, тем не менее, на него ссылаются в коде, и поэтому он должен быть назван.R ,
7769 байт-8 байт благодаря Аарону Хейману
Попробуйте онлайн!
ПозволятьК количество необходимых разрезов; К наименьшее целое число такое, что ( k + 1 ) ⋅ 2К≥ n , Действительно, тогда возможное решение состоит в том, чтобы иметь подцепи длин1 , 1 , … , 1 (К раз) и ( k + 1 ) , 2 ( k + 1 ) , 4 ( k + 1 ) , 8 ( k + 1 ) , … , ( k + 1 ) ⋅ 2к - 1 , Нетрудно убедиться, что этого достаточно и оптимально.
(Последняя подцепь может быть сокращена, если мы превысим общую длину цепочки.)
Ungolfed (на основе предыдущей, аналогичной версии):
(Доказательство того, что значениеК это как я утверждаю: предположим, у нас есть К порезы. Затем мы имеемК единичные подцепи, поэтому нам нужно, чтобы первая подцепь имела длину к + 1 . We can now handle all lengths up to 2k+1 , so we need the next one to be of length 2k+2 , then 4k+4 ... Thus the maximum we can get out of k cuts is obtained by summing all those lengths, which gives (k+1)⋅2k−1 .)
Ifa(k) is the smallest integer n requiring k cuts, then a(k) is OEIS A134401.
источник
n=1
, but an alternative way to generate the cutoffs is the recurrence1, 4, 4a(n-1)-4a(n-2)
.k
; this corresponds to OEIS A134401: oeis.org/A134401 But my implementation of the recurrence relation takes up more bytes than the current code.sum
instead ofmatch
.Jelly, 12 bytes
Try it online!
Translation of Grimy's 05AB1E answer so be sure to upvote that one too! Slightly disappointed this comes in a byte longer, but does at least have something a bit like an emoticon as the first three bytes!
источник
JavaScript (ES6), 66 bytes
This is a port of TFeld's answer.
Try it online!
источник
C++,
109,107 bytes-2 bytes thanks to Kevin
The algorithm is similar to the Robin Ryder's answer. The code is written in a compilable, whole form. Try it!
Details:
This has a C variation with the same byte length (doesn't seem to need a separate answer):
источник
=0
afterk
can be removed, since its0
by default.std::cin>>n;while(++k<<k<n);
can befor(std::cin>>n;++k<<k<n;);
. I also have the feelingfor(n-=k;n>0;k*=2,n-=k+1)
can be simplified somehow by combining stuff, but not sure how. PS: Changing the comma-delimiter to a space looks slightly better since you don't see the trailing one imo, but this is purely cosmetic :)=0
was necessary for portability ;) I also realized that the space after#include
is not necessary.std::cin>>n
inside it.Retina 0.8.2, 61 bytes
Try it online! 1-indexed port of @Grimy's answer. Explanation:
Start with
N=2
and the input converted to unary.Repeatedly try to subtract
N
from the input and then divide by 2.If successful, remember 1 more than the input on the previous line, increment
N
on the current line, and update the input to the new value.Remove
N
and increment the last value so that it's also 1-indexed.Remove the incremented original input.
Convert the results to decimal.
источник
Ruby, 62 bytes
Try it online!
Mostly stolen from TFeld's Python answer.
источник