Los condensadores son conocidos por ser fabricados con altas tolerancias. Esto es aceptable en muchos casos, pero a veces se requiere una capacidad con tolerancias estrictas. Una estrategia común para obtener una capacidad con el valor exacto que necesita es usar dos condensadores medidos cuidadosamente en paralelo, de modo que sus capacidades se sumen a algo en el rango que necesita.

El objetivo en este desafío es, dado un (múltiple) conjunto de capacidades, emparejar los condensadores de modo que la capacidad total de cada par esté en un rango dado. También necesita encontrar el mejor conjunto de emparejamientos, es decir, el conjunto de emparejamientos de modo que se encuentren tantos pares como sea posible.

Restricciones

1. La entrada comprende en un formato de elección
   • una lista desordenada de capacidades que representan el (multi) conjunto de condensadores que tiene
   • Un par de capacidades que representan el límite inferior y superior del rango objetivo (inclusive)
2. todas las capacidades en la entrada son enteros positivos menores que 2 ³⁰ , la unidad es pF (no es lo que importa).
3. Además de la lista de capacidades en la entrada, el conjunto de condensadores que tiene también contiene una cantidad infinita de condensadores con un valor de 0 pF.
4. La salida comprende, en un formato de elección, una lista de pares de capacidades de modo que la suma de cada par esté en el rango objetivo especificado. No se especifica ni el orden de los pares ni el orden de las capacidades dentro de un par.
5. Ninguna capacidad en la salida puede aparecer con más frecuencia que en el conjunto de condensadores que tiene . En otras palabras: los pares que genera no deben superponerse.
6. No habrá salida posible que satisfaga las condiciones 4 y 5 que contenga más pares de capacidades que la salida que produce su programa.
7. Su programa terminará en O ( n !) Tiempo donde n es la longitud de la lista que representa el conjunto de condensadores que tiene
8. Las lagunas no se abusarán
9. El rango objetivo no debe estar vacío

Puntuación

Su puntaje es la longitud de su solución en octetos. Si su solución logra resolver este problema en tiempo polinomial O ( n ^k ) para algunos k , divida su puntaje entre 10. No sé si esto es realmente posible.

Entrada de muestra

• rango 100 a 100, matriz de entrada 100 100 100, salida válida:

  0 100
  0 100
  0 100
  

• rango de 100 a 120, matriz de entrada 20 80 100, salida válida:

  0 100
  20 80
  

  la salida 20 100no es válida

• rango de 90 a 100, matriz de entrada 50 20 40 90 80 30 60 70 40, salida válida:

  0 90
  20 80
  30 70
  40 60
  40 50
  

• rango 90 a 90, matriz de entrada 20 30 40 40 50 60 70 80 90, salida válida:

  0 90
  20 70
  30 60
  40 50
  

• rango de 90 a 110, matriz de entrada 40 60 50, salida válida:

  40 60
  

CJam, 5.6

Esta es una re-implementación directa del algoritmo en la respuesta de orlp . Si votó mi respuesta, asegúrese de que también votó esta respuesta . También sugiero que se acepte la respuesta con el algoritmo original, porque dudo mucho que hubiera descubierto cómo resolver esto elegantemente en O (n * log (n)).

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

Pruébalo en línea

Entrada de muestra:

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

Explicación:

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

Un golf de Python por una 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)]

Agrego un condensador de 0 pF por cada uno normal, nunca más se necesitan. Luego clasificamos los condensadores y seguimos emparejando el condensador más bajo y el más alto. Si la suma está dentro del rango permitido, la imprimimos, si está por encima del rango descartamos el más alto, si está por debajo descarta el más bajo.

Ejemplo de entrada / salida:

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

0 90
20 80
30 70
40 60
40 50