Максимальный каскадный продукт

11

Нам дан список целых чисел p1, ..., pk (не обязательно различимых), где каждое имеет значение от 1 до 9 включительно. Используя каждый из p1, ..., pk ровно один раз, мы можем сформировать конкатенацию цифр, чтобы получить новый список чисел; затем мы выводим произведение этого нового списка. Цель состоит в том, чтобы максимизировать этот продукт, выбирая лучшие комбинации цифр.

Например, нам дают список: 2 3 2 (разделенные пробелами). Мы можем сформировать следующие объединения:

  • 2 3 2(продукт этих объединений есть 12)
  • 23 2(продукт есть 46)
  • 32 2(продукт есть 64)
  • 22 3(продукт есть 66)

Поскольку наибольшим продуктом, который мы можем сформировать, является 66, мы выводим его.

Правила:

  • Должно быть хотя бы одно умножение (т. Е. Вы не можете просто объединить все цифры и вывести их).
  • Вы не можете использовать другие операторы, кроме умножения, или вставлять скобки и т. Д.
  • Предположим, что указанный список целых чисел разделен пробелами, и все целые числа имеют значения от 1 до 9.

Самый короткий код (в байтах) побеждает!

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

Входные данные : 1 2 3; Выход: 63(т.е. 21*3)

Входные данные : 2 5 9; Выход: 468( 52*9)

Входные данные : 1 2 3 4; Выход: 1312( 41*32)

Райан
источник
Должны ли мы написать целую программу или функцию, принимающую входные параметры и возвращающую результат, тоже хорошо?
Рандомра
@randomra Да, все в порядке.
Райан
Для каждой пары чисел a, b произведение a * b. меньше, чем простая конкатенация ab (= a * 10 ^ (цифры b) + b). Так что просто 1 товар (так как это обязательно). Добавьте это: codegolf.stackexchange.com/q/49854/21348
edc65

Ответы:

8

CJam, 32 28 23 12 байт

0le!f{~*}:e>

Попробуйте онлайн в интерпретаторе CJam .

Спасибо @ user23013 за помощь в сохранении 16 целых байтов!

идея

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

Код

 le!         e# Push all possible character permutations of the input.
0   f{  }    e# For each permutation:
             e#   Push 0, then the permuted string.
      ~      e#   Evaluate the string. Pushes one or more integers.
       *     e#   Multiply the two topmost integers.
         :e> e# Retrieve the greatest integer in the array.
Деннис
источник
1
l2%_,,1>\e!m*{~S+m<~*}%$W=,
jimmy23013
2
l2%S+e!{0\~*}%$W=,
jimmy23013
2

CJam, 36 35 байт

q~]_,([SL]m*{s},\e!\m*{z[s~]:*}%$W=

Довольно прямо вперед. Перебирает все возможные комбинации и сортирует их по продуктам. Затем выводит наибольшее. Все это с учетом того, что должно присутствовать хотя бы 1 умножение.

Скоро добавлю объяснение.

Попробуйте онлайн здесь

оптимизатор
источник
1

JavaScript (ES6) 125

Редактировать Я думаю, что @oberon понял это правильно: «каждая новая цифра должна быть соединена с наименьшим числом»

Я не буду менять этот ответ, крадя его идею. Реализация в ES6 будет 70 байтов (знак изменился по сравнению, чтобы сравнить как число, а не строки)

f=l=>l.split(' ').sort().reverse().map(d=>-a>-b?a+=d:b+=d,a=b='')||a*b

Мое решение

f=l=>(i=>{for(r=0;a=b='',k=--i;r<a*b?r=a*b:0)for(v of l)k&1?a+=v:b+=v,k/=2})(1<<~-(l=l.split(' ').sort().reverse()).length)|r

Как я уже говорил в комментариях, для каждой пары чисел a, b произведение a * b меньше простой конкатенации ab (= a * 10 ^ (цифры b) + b). Поэтому лучше избегать продуктов и предпочитать конкатенацию, но так как запрашивается как минимум 1 продукт, мы должны построить 2 числа и умножить их.

Я пробую все возможные группировки цифр, создавая пару чисел для умножения. Каждое число построено из цифр в порядке убывания.

Например, со списком из 4 чисел [1 2 3 4] - попробуйте:

  • 4 * 321
  • 43 * 21
  • 42 * 31
  • 41 * 32
  • 432 * 1
  • 431 * 2
  • 421 * 3

Максимум этих значений - результат, который нам нужен.

Группировки могут быть пронумерованы зацикливанием на битовой карте из 4 битов с минимальным значением 0001 и максимальным значением 0111 (то есть 1 << (4 -1) - 1)

Не так играли в гольф

f=l=>{
  l = l.split(' '); // string to array
  l.sort().reverse(); // decreasing order 
  m = 1 << (l.length-1); starting value fro loop
  r = 0 
  // loop from m-1 down to 1
  for(i=m; --i; )
  {
    a = b = '';
    k = i;
    for(v of l) // divide the digits base on bits of i
    {
      k & 1 ? a+=v : b+=v;
      k /= 2;
    }
    if (r < a*b) r = a*b; // remember max value in r
  }
  return r
}

Протестируйте с помощью фрагмента ниже в Firefox.

f=l=>(i=>{for(r=0;a=b='',k=--i;r<a*b?r=a*b:0)for(v of l)k&1?a+=v:b+=v,k/=2})(1<<~-(l=l.split(' ').sort().reverse()).length)|r

t=l=>(i=>{for(x=r='';a=b='',k=--i;r<a*b?(r=a*b,x=' = '+a+'x'+b):0)for(v of l)k&1?a+=v:b+=v,k/=2})
(1<<~-(l=l.split(' ').sort().reverse()).length)|| x

function go()
{
  R.value = f(I.value) // TEST AS IS
   + t(I.value) // Some more info
}

test=['1 2 3 4','1 2 3','2 5 9','8 9 8']

test.forEach(t => O.innerHTML = O.innerHTML + (t + ' -> ' + f(t)) + '\n')
Type your list: <input id=I><button onclick='go()'>-></button><input readonly id=R><br>
<pre id=O></pre>

edc65
источник
1

Python 3, 111 байт

Это, вероятно, намного более пригодно для игры в гольф. Мне нравится время его работы, хотя (O ( n log n ), не так ли?).

l=sorted(map(int,input().split()),reverse=1);m=[0,0]
for x in l:i=m[0]>m[1];m[i]=m[i]*10+x
print(m[0]*m[1])

Разгромленный с объяснением.

# edc65 has already explained that the optimal solution can be found applying a single
# multiplication. thus, given that
#     (10x + d)y > (10y + d)x
# where x, y are the two numbers and d is the next digit to insert, it follows that
#     y > x
# and thus each new digit must be concatenated to the smallest number. obviously, digits
# should be added in descending order.
l = sorted(map(int, input().split()), reverse=1)
m = [0,0]
for x in l:
    i = m[0] > m[1]
    m[i] = m[i]*10 + x
print(m[0] * m[1])
Oberon
источник
0

Pyth, 25 байт

eSsmm*ss<dkss>dkr1ld.pcz)

Я зацикливаюсь на каждой перестановке ввода. Тогда, поскольку каждая оптимальная комбинация состоит из двух целых чисел, я просто делю ее в каждой возможной позиции и умножаю каскадные разбиения. Затем я сортирую и получаю последний элемент.

orlp
источник
0

R 164

function(n){l=length(n);a=sort(n,T);i=1;while(a[i]==a[i+1]&&i<l-2)i=i+2;a[c(i,i+1)]=a[c(i+1,i)];eval(parse(t=paste0(c(a[1:l%%2==1],"*",a[1:l%%2==0]),collapse='')))}

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

Общий процесс:

  • Сортировать список по убыванию
  • Поменяйте местами первую пару четных / нечетных
  • Объединить четные и нечетные элементы списка
  • Оценить произведение двух результатов

Расширен с некоторыми комментариями

function(n){
    l=length(n);
    a=sort(n,T);    # sort descending order
    # Determine which pair to swap
    i=1;
    while(a[i]==a[i+1]&&i<l-2)i=i+2;
    a[c(i,i+1)]=a[c(i+1,i)];  # swap pair   
    # concatenate the even and odd indices items around a * and evaluate    
    eval(parse(t=paste0(c(a[1:l%%2==1],"*",a[1:l%%2==0]),collapse=''))) 
}

И некоторые тестовые прогоны (реализованные как функция с именем g)

> g(c(1,2,3))
[1] 63
> g(c(2,5,9))
[1] 468
> g(c(1,2,3,4))
[1] 1312
> g(c(1,2,3,5,5,5))
[1] 293132
> g(c(1,5,7,7,9,9))
[1] 946725
> g(c(1,7,8,9,9,9))
[1] 978117
> g(c(7,8,9,9,9))  #Test case provided edc65 to randomra
[1] 97713
MickyT
источник