Os capacitores são famosos por serem fabricados com altas tolerâncias. Isso é aceitável em muitos casos, mas algumas vezes é necessária uma capacidade com tolerâncias rígidas. Uma estratégia comum para obter uma capacidade com o valor exato de que você precisa é usar dois capacitores cuidadosamente medidos em paralelo, para que suas capacidades correspondam a algo na faixa necessária.

O objetivo deste desafio é, dado um (multi) conjunto de capacidades, emparelhar os capacitores de modo que a capacidade total de cada par esteja em um determinado intervalo. Você também precisa encontrar o melhor conjunto de pares, ou seja, o conjunto de pares, para que o maior número possível de pares seja encontrado.

Restrições

1. A entrada compreende em um formato de escolha
   • uma lista não ordenada de capacidades que representa o (multi) conjunto de capacitores que você possui
   • um par de capacidades representando o limite inferior e superior do intervalo de destino (inclusive)
2. todas as capacidades na entrada são números inteiros positivos menores que 2 ³⁰ , a unidade é pF (não é o que importa).
3. Além da lista de capacidades na entrada, o conjunto de capacitores que você possui também contém uma quantidade infinita de capacitores com um valor de 0 pF.
4. A saída compreende em um formato de escolha uma lista de pares de capacidades, de modo que a soma de cada par esteja no intervalo de destino especificado. Nem a ordem dos pares nem a ordem das capacidades dentro de um par são especificadas.
5. Nenhuma capacidade na saída pode aparecer com mais frequência do que aparece no conjunto de capacitores que você possui . Em outras palavras: Os pares que você produz não devem se sobrepor.
6. Não deve haver saída possível que satisfaça as condições 4 e 5 que contenham mais pares de capacidades do que a saída produzida pelo seu programa.
7. Seu programa será encerrado em O ( n !) Tempo em que n é o comprimento da lista que representa o conjunto de capacitores que você possui
8. As brechas não devem ser abusadas
9. O intervalo alvo não deve estar vazio

Pontuação

Sua pontuação é o comprimento da sua solução em octetos. Se sua solução conseguir resolver esse problema no tempo polinomial O ( n ^k ) por algum k , divida sua pontuação por 10. Não sei se isso é realmente possível.

Entrada de amostra

• faixa de 100 a 100, matriz de entrada 100 100 100, saída válida:

  0 100
  0 100
  0 100
  

• faixa de 100 a 120, matriz de entrada 20 80 100, saída válida:

  0 100
  20 80
  

  a saída 20 100não é válida

• faixa de 90 a 100, matriz de entrada 50 20 40 90 80 30 60 70 40, saída válida:

  0 90
  20 80
  30 70
  40 60
  40 50
  

• faixa de 90 a 90, matriz de entrada 20 30 40 40 50 60 70 80 90, saída válida:

  0 90
  20 70
  30 60
  40 50
  

• faixa de 90 a 110, matriz de entrada 40 60 50, saída válida:

  40 60
  

CJam, 5.6

Esta é uma reimplementação direta do algoritmo na resposta do orlp . Se você aprovou minha resposta, certifique-se de que também votou nesta resposta . Sugiro também que a resposta com o algoritmo original seja aceita, porque duvido muito que eu tivesse descoberto como resolver isso elegantemente em O (n * log (n)).

l~_,0a*+${(\)@_2$+4$~2$\>{;;\;\+}{<{;+}{oSop}?}?_,1>}g;;

Experimente online

Entrada de amostra:

[90 100] [50 20 40 90 80 30 60 70 40]

Explicação:

l~      Get and interpret input.
_,      Get length of resistor list.
0a*+    Append the same number of 0 values.
$       Sort the list.
{       Loop until less than 2 entries in list.
  (       Pop off first value.
  \)      Pop off last value.
  @_      Pull first value to top, and copy it.
  2$      Copy last value to top.
  +       Add first and last value.
  4$~     Copy specified range to top, and unwrap the two values.
  2$      Copy sum to top.
  \>      Swap and compare for sum to be higher than top of range.
  {       It's higher.
    ;;\;    Some stack cleanup.
    \+      Put first value back to start of resistor list.
  }
  {       Not higher, so two cases left: value is in range, or lower.
    <       Compare if sum is lower than bottom of range.
    {       It's lower.
      ;+      Clean up stack and put last value back to end of resistor list.
    }
    {       Inside range, time to produce some output.
      o       Output first value.
      So      Output space.
      p       Output second value and newline.
    }?      Ternary operator for comparison with lower limit.
  }?      Ternary operator for comparison with upper limit.
  _,      Get length of remaining resistor list.
  1>      Check if greater 1.
}g      End of while loop for processing resistor list.
;;      Clean up stack, output was generated on the fly.

Python 2, 11,5

Um golfe Python pela primeira vez:

(a,b),l=input()
l=[0]*len(l)+sorted(l)
while l:
 e=l[0]+l[-1]
 if a<=e<=b:print l[0],l[-1]
 l=l[e<=b:len(l)-(a<=e)]

Eu adiciono um capacitor de 0 pF para cada um regular, nunca mais é necessário. Depois, classificamos os capacitores e continuamos emparelhando o capacitor mais baixo e mais alto. Se a soma estiver dentro do intervalo permitido, imprimi-lo; se estiver acima do intervalo, descartamos o mais alto; se estiver abaixo, descartamos o mais baixo.

Exemplo de entrada / saída:

[[90,100], [20,30,40,40,50,60,70,80,90]]

0 90
20 80
30 70
40 60
40 50