Фон

Официальная валюта мнимой нации Golfenistan является Foo , и есть только три вида монет в обращении: 3 Foos, 7 и 8 Foos Foos. Можно видеть, что с помощью этих монет невозможно заплатить определенную сумму, например 4 фо. Тем не менее, все достаточно большие суммы могут быть сформированы. Ваша задача - найти наибольшую сумму, которая не может быть сформирована монетами (в данном случае 5 фу), которая известна как проблема с монетами .

вход

Ваш ввод представляет собой список натуральных чисел, представляющих ценности монет в обращении. Об этом гарантированы две вещи:L = [n1, n2, ..., nk]

• GCD элементов L- 1.
• L не содержит номер 1.

Он может быть несортированным и / или содержать дубликаты (например, монеты специального издания).

Выход

Поскольку GCD Lравен 1, каждое достаточно большое целое число mможет быть выражено как неотрицательная линейная комбинация его элементов; другими словами, мы имеем

 m = a1*n1 + a2*n2 + ... + ak*nk 

для некоторых целых чисел . Ваш вывод является наибольшим целым числом, которое не может быть выражено в этой форме. Как подсказка, известно, что выходные данные всегда меньше, чем , если и являются максимальными и минимальными элементами ( ссылка ).ai ≥ 0(n1 - 1)*(nk - 1)n1nkL

правила

Вы можете написать полную программу или функцию. Побеждает меньшее количество байтов, и стандартные лазейки запрещены. Если ваш язык имеет встроенную операцию для этого, вы не можете использовать его. Нет никаких требований к времени или эффективности использования памяти, за исключением того, что вы должны быть в состоянии оценить тестовые примеры перед публикацией вашего ответа.

После того, как я опубликовал эту проблему, пользователь @vihan указал, что переполнение стека имеет точную копию . Основываясь на этой мета-дискуссии , эта задача не будет удалена как дубликат; тем не менее, я прошу, чтобы все ответы, основанные на ответах версии SO, содержали ссылки на оригиналы, имели статус Wiki сообщества и удалялись, если автор оригинала хочет опубликовать свой ответ здесь.

Тестовые случаи

[3, 7, 8] -> 5
[25, 10, 16] -> 79
[11, 12, 13, 14, 13, 14] -> 43
[101, 10] -> 899
[101, 10, 899] -> 889
[101, 10, 11] -> 89
[30, 105, 70, 42] -> 383
[2, 51, 6] -> 49

Pyth, 23 байта

ef!fqTs.b*NYQY^UTlQS*FQ

Это очень медленно, так как проверяет все значения вплоть до произведения всех монет. Вот версия, которая почти идентична, но 1) уменьшает набор монет до тех, которые не делятся друг на друга, и 2) проверяет только значения до (max(coins) - 1) * (min(coins) - 1)(47 байт):

=Qu?.A<LiHdG+GHGQYef!fqTs.b*NYQY^UTlQS*thSQteSQ

объяснение

                   S            range 1 to
                    *FQ         product of input
 f                             filter by
               UT                range 0 to T 
              ^  lQ              cartesian power by number of coins
   f                            filter by
      s.b*NYQY                   sum of coin values * amounts
    qT                           equals desired number T
  !                             nothing matching that filter
e                             take last (highest) element

Perl, 60 54 51 байт

Код 50 байтов + командная строка 1 байт

$.*=$_,$r.=1x$_."|"}{$_=$.while(1x$.--)=~/^($r)+$/

Продолжу игру в гольф и опубликую объяснение позже. Основной подход состоит в том, чтобы позволить механизму регулярных выражений выполнять тяжелую работу с сопоставлением строк. Например, он создаст регулярное выражение, подобное ^(.{3})*(.{7})*(.{8})*$и сопоставленное со строкой длины, nгде nспускается из произведения входных данных до тех пор, пока не будет найдено совпадение.

Обратите внимание, что это будет становиться экспоненциально медленным по мере увеличения количества аргументов.

Использование: Аргументы считываются из STDIN (новая строка отделена), например:

printf "101\n10" | perl -p entry.pl

R , 84 78 байт

$a_1, a_2,\ldots$

a=scan();max((1:(b<-min(a)*max(a)))[-colSums(combn(outer(a,0:b),sum(!!a)))])

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

$a_i$outercolSums а не за "применить (..., 2, сумма)".

Более быстрая, но более длинная (на два байта) версия учитывает только max(a):

a=scan();max((1:(min(a)*(b<-max(a))))[-apply(combn(outer(a,0:b,"*"),sum(!!a)),2,sum)])

Немного более короткая версия (78 байт) , который чаще всего занимает слишком войти или слишком много места , чтобы работать на Попробовать онлайн является

a=scan();max((1:(b<-prod(a)))[-apply(combn(outer(a,0:b,"*"),sum(!!a)),2,sum)])

Python2, 188 187 байт

def g(L):
 M=max(L);i=r=0;s=[0]*M;l=[1]+s[1:]
 while 1:
    if any(all((l+l)[o:o+min(L)])for o in range(M)):return~-s[r]*M+r
    if any(l[(i-a)%M]for a in L):l[i]=1
    else:r=i
    s[i]+=1;i=(i+1)%M

Второй отступ отображается как 4 пробела на SO, это должны быть табуляции.

На самом деле «быстрое» решение, а не грубое, использует «метод Уилфа», как описано здесь .

Javascript ES6, 120 130 126 128 127 125 символов

f=a=>`${r=[1|a.sort((a,b)=>a-b)]}`.repeat(a[0]*a[a.length-1]).replace(/./g,(x,q)=>r[q]|a.map(x=>r[q+x]|=r[q])).lastIndexOf(0)

Альтернативная версия на 126 символов:

f=a=>{r=[1];a.sort((a,b)=>a-b);for(q=0;q<a[0]*a[a.length-1];++q)r[q]?a.map(x=>r[q+x]=1):r[q]=0;return r.join``.lastIndexOf(0)}

Тестовое задание:

"[3, 7, 8] -> 5\n\
[25, 10, 16] -> 79\n\
[11, 12, 13, 14, 13, 14] -> 43\n\
[101, 10] -> 899\n\
[101, 10, 899] -> 889\n\
[101, 10, 11] -> 89\n\
[30, 105, 70, 42] -> 383\n\
[2, 51, 6] -> 49".replace(/(\[.*?\]) -> (\d+)/g, function (m, t, r) {
  return f(JSON.parse(t)) == r
})