Разделите биты!

17

Мы определим как список различных степеней 2, которые суммируются с x . Например, V ( 35 ) = [ 32 , 2 , 1 ] .V(x)2xV(35)=[32,2,1]

По соглашению, полномочия сортируются здесь от наивысшего к низшему. Но это не влияет ни на логику задачи, ни на ожидаемые решения.

задача

При заданном полупростом замените каждый член в V ( N ) другим списком степеней 2 , суммирующим этот термин, таким образом, чтобы объединение всех результирующих подсписков было точным покрытием матрицы M, определенной как:NV(N)2M

Mi,j=V(P)i×V(Q)j

где и Q являются главными факторами N .PQN

Это гораздо легче понять на некоторых примерах.

Пример № 1

Для имеем:N=21

  • V(N)=[16,4,1]
  • и V ( P ) = [ 4 , 2 , 1 ]P=7V(P)=[4,2,1]
  • и V ( Q ) = [ 2 , 1 ]Q=3V(Q)=[2,1]
  • M=(842421)

Чтобы превратить в точное покрытие M , мы можем разбить 16 на 8 + 4 + 4 и 4 на 2 + 2 , а 1 оставить без изменений. Таким образом, возможный вывод:V(N)M168+4+442+21

[[8,4,4],[2,2],[1]]

Еще один действительный вывод:

[[8,4,2,2],[4],[1]]

Пример № 2

Для имеем:N=851

  • V(N)=[512,256,64,16,2,1]
  • и V ( P ) = [ 32 , 4 , 1 ]P=37V(P)=[32,4,1]
  • и V ( Q ) = [ 16 , 4 , 2 , 1 ]Q=23V(Q)=[16,4,2,1]
  • M=(512641612816464823241)

Возможный вывод:

[[512],[128,64,64],[32,16,16],[8,4,4],[2],[1]]

правила

  • Поскольку факторизация не является основной частью задачи, вы можете попеременно принимать P и Q в качестве входных данных.NPQ
  • Если существует несколько возможных решений, вы можете вернуть только одно из них или все из них.
  • Вы можете поочередно возвращать показатели степени (например, вместо [ [ 8 , 4 , 4 ] , [ 2 , 2 ] , [ 1 ] ] ).[[3,2,2],[1,1],[0]][[8,4,4],[2,2],[1]]
  • Порядок подсписков не имеет значения, равно как и порядок терминов в каждом подсписке.
  • Для некоторых полупримесов вам не придется разбивать какой-либо термин, потому что уже является идеальным прикрытием M (см. A235040 ). Но вам все равно придется возвращать список (одноэлементных) списков, таких как [ [ 8 ] , [ 4 ] , [ 2 ] , [ 1 ] ] для N = 15 .V(N)M[[8],[4],[2],[1]]N=15
  • Это !

Контрольные примеры

 Input | Possible output
-------+-----------------------------------------------------------------------------
 9     | [ [ 4, 2, 2 ], [ 1 ] ]
 15    | [ [ 8 ], [ 4 ], [ 2 ], [ 1 ] ]
 21    | [ [ 8, 4, 4 ], [ 2, 2 ], [ 1 ] ]
 51    | [ [ 32 ], [ 16 ], [ 2 ], [ 1 ] ]
 129   | [ [ 64, 32, 16, 8, 4, 2, 2 ], [ 1 ] ]
 159   | [ [ 64, 32, 32 ], [ 16 ], [ 8 ], [ 4 ], [ 2 ], [ 1 ] ]
 161   | [ [ 64, 32, 16, 16 ], [ 8, 8, 4, 4, 4, 2, 2 ], [ 1 ] ]
 201   | [ [ 128 ], [ 64 ], [ 4, 2, 2 ], [ 1 ] ]
 403   | [ [ 128, 64, 64 ], [ 32, 32, 16, 16, 16, 8, 8 ], [ 8, 4, 4 ], [ 2 ], [ 1 ] ]
 851   | [ [ 512 ], [ 128, 64, 64 ], [ 32, 16, 16 ], [ 8, 4, 4 ], [ 2 ], [ 1 ] ]
 2307  | [ [ 1024, 512, 512 ], [ 256 ], [ 2 ], [ 1 ] ]
Arnauld
источник
мы можем взять P и Q вместо N?
СПП
@ngn Я скажу «да», потому что разложение N не является основной частью проблемы.
Арно
1
Можем ли мы вернуть вывод сглаженный?
Эрик Outgolfer
@EriktheOutgolfer ... Сглаженный вывод - это просто раздел ввода (например, 1 + 2 + 2 + 4 = 9). Я не думаю, что это должно быть разрешено
мистер Xcoder
@EriktheOutgolfer Я не думаю, что это может быть однозначно, так как последний член подсписка может совпадать с первым членом следующего.
Арно

Ответы:

4

K (нгн / к) , 66 63 байта

{(&1,-1_~^(+\*|a)?+\b)_b:b@>b:,/*/:/2#a:{|*/'(&|2\x)#'2}'x,*/x}

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

принимает (P; Q) вместо N

алгоритм:

  • вычислить A как частичные суммы V (P * Q)

  • умножить каждое V (P) на каждое V (Q), отсортировать произведения в порядке убывания (назовем это R) и вычислить их частичные суммы B

  • найти позиции тех элементов в B, которые также встречаются в A; вырезать R сразу после этих позиций

СПП
источник
3

Желе , 24 байта

BṚT’2*
Ç€×þ/FṢŒṖ§⁼Ç}ɗƇPḢ

Монадическая ссылка, принимающая список из двух целых чисел, [P, Q]который выдает один возможный список списков, как описано в вопросе.

Попробуйте онлайн! (нижний колонтитул выводит строковое представление, чтобы показать список таким, какой он есть на самом деле)

Или посмотрите набор тестов (взяв список N и переупорядочив результаты, чтобы они были такими же, как в вопросе)

Как?

Мы всегда можем жадно нарезать элементы снизу вверх (либо в M есть 1, либо у нас было 4 , когда M = [ [ 4 ] ]M1M4M=[[4]] ), чтобы найти решение.

Примечание: код собирает все (одно!) Такие решения в список, а затем получает результат заголовка (только) - т.е. необходим окончательный заголовок, поскольку разделы не всех возможных порядков.

BṚT’2* - Link 1, powers of 2 that sum to N: integer, N    e.g. 105
B      - binary                                                [1,1,0,1,0,0,1]
 Ṛ     - reverse                                               [1,0,0,1,0,1,1]
  T    - truthy indices                                        [1,4,6,7]
   ’   - decrement                                             [0,3,5,6]
    2  - literal two                                           2
     * - exponentiate                                          [1,8,32,64]

Ç€×þ/FṢŒṖ§⁼Ç}ɗƇPḢ - Main Link: list of two integers, [P,Q]
Ç€                - call last Link (1) as a monad for €ach
    /             - reduce with:
   þ              -   table with:
  ×               -     multiplication
     F            - flatten
      Ṣ           - sort
       ŒṖ         - all partitions
              Ƈ   - filter keep if:
             ɗ    -   last three links as a dyad:
         §        -     sum each
            }     -     use right...
               P  -       ...value: product (i.e. P×Q)
           Ç      -       ...do: call last Link (1) as a monad
          ⁼       -     equal? (non-vectorising so "all equal?")
                Ḣ - head
Джонатан Аллан
источник
3

Python 2 , 261 233 232 231 байт

g=lambda n,r=[],i=1:n and g(n/2,[i]*(n&1)+r,i*2)or r
def f(p,q):
 V=[[v]for v in g(p*q)];i=j=0
 for m in sorted(-a*b for a in g(p)for b in g(q)):
	v=V[i]
	while-m<v[j]:v[j:j+1]=[v[j]/2]*2
	i,j=[i+1,i,0,j+1][j+1<len(v)::2]
 return V

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

1 байт от Джо Кинга ; и еще 1 байт из-за Кевина Круйссена .

Принимает в качестве ввода p,q. Преследует жадный алгоритм.

Час Браун
источник
-k-1может быть ~k.
Джонатан Фрех
i,jНазначение может быть i,j=[i+1,i,0,j+1][j+1<len(v)::2]для -1 байт
Jo King
@ Джо Кинг: Хахаха! Это искажено!
Час Браун
while v[j]>-mможет бытьwhile-m<v[j]
Кевин Круйссен
@Kevin Cruijssen: Да, действительно. Спасибо!
Час Браун
2

Желе , 41 байт

Œṗl2ĊƑ$Ƈ
PÇIP$ƇṪÇ€Œpµ³ÇIP$ƇṪƊ€ŒpZPṢ⁼FṢ$µƇ

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

ÇIP$Ƈ[P,Q]

Мистер Xcoder
источник
Не то чтобы это проблема, но это не совсем быстро, не так ли? :)
Арно
@Arnauld Он использует примерно 3 целочисленных функции разбиения за один прогон :) Конечно, это не слишком быстро
Mr. Xcoder
Теперь жду, когда тебя обойдут. Я думаю, что это возможно в sub-35/30, но я не думаю, что смогу сделать что-то намного более короткое
Mr. Xcoder
2

Желе , 34 байта

BṚT’2*
PÇŒṗæḟ2⁼ƊƇ€ŒpẎṢ⁼Ṣ}ʋƇÇ€×þ/ẎƊ

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

Формат ввода: [P, Q](ссылка TIO выше не принимает это, но вместо этого одно число, чтобы помочь с тестовыми случаями).

Выходной формат: список всех решений (отображается как сеточное представление трехмерного списка через TIO).

Скорость: черепаха.

Эрик Outgolfer
источник
1

Haskell, 281 195 байт

import Data.List
r=reverse.sort
n#0=[]
n#x=[id,(n:)]!!mod x 2$(n*2)#div x 2
m!0=[]
m!x=m!!0:tail m!(x-m!!0)
m%[]=[]
m%n=m!head n:drop(length$m!head n)m%tail n
p&q=r[x*y|x<-1#p,y<-1#q]%r(1#(p*q))
Евгений Новиков
источник
1
Вот несколько советов: определение операторов вместо бинарных функций обходится дешевле, перестановка ограждений и сопоставление с образцом может спасти вас (==), использовать 1>0вместо Trueи не использовать where. Также n'можно сократить. С этим вы можете сэкономить 72 байта: попробуйте онлайн!
ბიმო
Btw. Вы должны проверить раздел советов Haskell, если у вас нет.
ბიმო
Я снова посмотрел на ситуацию с охраной, еще 13 байт: попробуйте онлайн!
მოიმო
@ ОМо, спасибо. Я новичок в Haskell, так что это выглядит для меня как фокусы
Евгений Новиков
Не беспокойтесь :) Если у вас есть вопросы, не стесняйтесь задавать их в разделе «Монады и мужчины» .
მოიმო