Разрежь золотую цепочку

32

Путешественник должен остановиться на 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 об одном из возможных алгоритмов этой проблемы.

Полфосол ఠ_ఠ
источник
Я не понимаю вашу ссылку "сделать изменение". В опубликованном вами примере, во второй день вы платите цепочкой из 2 ссылок (и возвращаете цепочку из 1 ссылки (которую вы заплатили днем ​​ранее) в соответствии с вашим объяснением). Но на третий день вы платите 1+2. Откуда появилась вторая 2-звенная цепь?
Флэтер
4
@Flater У менеджера уже есть. Мы просто платим дополнительный. Фактически, RHS - это ссылки, которыми владеет менеджер каждый день
polfosol ఠ_ఠ

Ответы:

15

05AB1E , 23 11 8 байтов

ΔÍN-;иg=

Попробуйте онлайн!

Использует индексирование на основе 0.

Объяснение:

             # 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

иgвыглядит как noop, но на самом деле он делает две полезные вещи: он усекает целое число ( ;возвращает число с плавающей запятой) и сбивает интерпретатор, если x отрицателен (это единственное условие выхода).


23-байтовое решение использовало совершенно другой подход, поэтому здесь оно для потомков: ÅœʒR2äθP}ʒæOê¥P}θ2äθη€O( TIO , объяснение ).

Grimmy
источник
2
Я удалил свой ответ. Мне 42, а твоему 11 - слишком большая разница для меня, чтобы не чувствовать смущения, хаха. ;) Хороший ответ, хотя, и лол в Ø.Ø. Вы только что попробовали некоторые случайные вещи, чтобы выровнять и сопоставить все негативы -1? Независимо от этого, очень хороший ответ и намного короче, чем я ожидал. Я думал о 20 байтах после того, как отправил свой плохой 42-байтовый код.
Кевин Круйссен
2
@KevinCruijssen Nnope, это Ø.Øбыла моя первая идея. Ваш комментарий вдохновил меня попробовать случайные вещи: я обнаружил ®Ÿà, ï®Mи, что более важно, то иg, что дает этот хороший 8-байтовый код. Меня всегда раздражало то, что osabie во многих случаях предпочитает ничего не делать, а только аварийно завершать работу (деление на 0, неправильный тип и т. Д.), Поэтому этот сбой пригодится.
Grimmy
2
Хе-хе, 05AB1E, как предполагается, никогда не падает, но вы правы, что иногда это немного раздражает, но никогда не дает. Ноль ошибок мы могли бы вызвать вручную. xD В новой версии он все еще часто вылетает с ошибкой, когда дает неправильные аргументы некоторым встроенным функциям. И опять приятно -3.
Кевин Круйссен
2
msgstr "вылетает интерпретатор, если x отрицателен (это единственное условие выхода)." - Мне это нравится
Джон Дворжак
9

Python 2 , 75 байт

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)]

Попробуйте онлайн!


Объяснение:

Создает последовательность «двоичных» чанков, базовый номер которых соответствует количеству срезов.

Например:

63 может быть сделано в 3 разреза, что означает разделение в base-4 (так как у нас есть 3 одинарных кольца):

Порезы:, 5, 14, 31который дает цепочки 4 1 8 1 16 1 32(отсортировано:) 1 1 1 4 8 16 32.

Все номера могут быть сделаны:

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

Другие примеры:

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
TFeld
источник
1
Разве вы не должны добавить f=к началу? Поскольку вы используете вызов fв лямбда-функции, и я могу только предположить, что вы ссылаетесь на ту же лямбду, которую вы определяете.
randomdude999
@ randomdude999, да, я забыл ...
TFeld
@ randomdude999 распространяется ли это правило на все языки или только на python? Потому что я вижу ответ javascript, который является чистой лямбда в этом вызове ...
Тень
3
@Shadow Это относится ко всем языкам, но только для рекурсивных лямбд.
TFeld
1
@Shadow Более общее правило заключается в том, что вы не можете ссылаться на то, что не определено ни в вашем коде, ни глобально не определено в вашем языке, если только это явно не разрешено задачей. Наиболее распространенным случаем является рекурсивная функция, но это относится и к другим ситуациям. Этот ответ является еще одним примером: fне является рекурсивным, но, тем не менее, на него ссылаются в коде, и поэтому он должен быть назван.
Арно
8

R , 77 69 байт

-8 байт благодаря Аарону Хейману

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

Попробуйте онлайн!

Позволять К количество необходимых разрезов; К наименьшее целое число такое, что (К+1)2КN, Действительно, тогда возможное решение состоит в том, чтобы иметь подцепи длин1,1,...,1 (К раз) и (К+1),2(К+1),4(К+1),8(К+1),...,(К+1)2К-1, Нетрудно убедиться, что этого достаточно и оптимально.

(Последняя подцепь может быть сокращена, если мы превысим общую длину цепочки.)

Ungolfed (на основе предыдущей, аналогичной версии):

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
}

(Доказательство того, что значение К это как я утверждаю: предположим, у нас есть Кпорезы. Затем мы имеемК единичные подцепи, поэтому нам нужно, чтобы первая подцепь имела длину К+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)2k1.)

If a(k) is the smallest integer n requiring k cuts, then a(k) is OEIS A134401.

Robin Ryder
источник
I doubt it would help with the special case for n=1, but an alternative way to generate the cutoffs is the recurrence 1, 4, 4a(n-1)-4a(n-2).
Peter Taylor
@PeterTaylor I had a similar recurrence for computing k; this corresponds to OEIS A134401: oeis.org/A134401 But my implementation of the recurrence relation takes up more bytes than the current code.
Robin Ryder
A bit of rearrangement I got it down to 73. Try it online!
Aaron Hayman
@AaronHayman Thanks! Smart move using sum instead of match.
Robin Ryder
69 bytes and got rid of that if statement that was upsetting you: Try it online!
Aaron Hayman
3

Jelly, 12 bytes

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

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!

Nick Kennedy
источник
2

C++, 109,107 bytes

-2 bytes thanks to Kevin

#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<<',';}

The algorithm is similar to the Robin Ryder's answer. The code is written in a compilable, whole form. Try it!

Details:

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

This has a C variation with the same byte length (doesn't seem to need a separate answer):

#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);}
polfosol ఠ_ఠ
источник
Two minor things to golf: =0 after k can be removed, since its 0 by default. std::cin>>n;while(++k<<k<n); can be for(std::cin>>n;++k<<k<n;);. I also have the feeling for(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 :)
Kevin Cruijssen
1
@KevinCruijssen Thanks, but some compilers don't assign a default value to non-static variables. So I thought =0 was necessary for portability ;) I also realized that the space after #include is not necessary.
polfosol ఠ_ఠ
Ah ok. I don't know C++ too well, so I've used that online compiler you linked in your answer to test some things. :) You forgot the second change I proposed in my comment: the while-loop to a for-loop and putting the std::cin>>n inside it.
Kevin Cruijssen
103 bytes
ceilingcat
1

Retina 0.8.2, 61 bytes

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

Try it online! 1-indexed port of @Grimy's answer. Explanation:

.+
11,$&$*

Start with N=2 and the input converted to unary.

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

Repeatedly try to subtract N from the input and then divide by 2.

1$2¶1$1,$3

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.

1+,
1

Remove N and increment the last value so that it's also 1-indexed.

1A`

Remove the incremented original input.

1+
$.&

Convert the results to decimal.

Neil
источник