Проблема с монетами

20

Фон

Официальная валюта мнимой нации 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
Zgarb
источник
5
FrobeniusNumberв Mathematica.
15:30
3
Существует способ улучшить верхнюю границу, найденную в этой статье, которая устанавливает (p - 1)(q - 1)верхнюю границу, где pи qявляются наименьшим и наибольшим элементом множества.
orlp
2
Есть ли ограничения по времени работы или использованию памяти?
Деннис
1
На Stack Overflow был код для гольфа вопрос , как этот некоторое время назад
Downgoat
1
У меня есть 13-байтовое решение Pyth, которое может сделать [2,3]за разумное количество времени и ничего больше. [2,5]создаст около миллиона списков Python в памяти.
Исаак

Ответы:

4

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
PurkkaKoodari
источник
8

Perl, 60 54 51 байт

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

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

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

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

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

printf "101\n10" | perl -p entry.pl
Jarmex
источник
3

R , 84 78 байт

a1,a2,...

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

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

aя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)])
Сиань
источник
1

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, это должны быть табуляции.

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

orlp
источник
1

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
})
Qwertiy
источник
1
Вы можете заменить forEach(сmap(
Ypnypn