Paire de condensateurs

12

Les condensateurs sont connus pour être fabriqués avec des tolérances élevées. Ceci est acceptable dans de nombreux cas, mais parfois une capacité avec des tolérances serrées est requise. Une stratégie courante pour obtenir une capacité avec la valeur exacte dont vous avez besoin consiste à utiliser deux condensateurs soigneusement mesurés en parallèle de sorte que leurs capacités s'additionnent à quelque chose dans la plage dont vous avez besoin.

Le but de ce défi est, étant donné un (multi) ensemble de capacités, de coupler les condensateurs de telle sorte que la capacité totale de chaque paire soit dans une plage donnée. Vous devez également trouver le meilleur ensemble de paires, c'est-à-dire l'ensemble de paires de sorte que le plus de paires possibles soient trouvées.

Contraintes

  1. L'entrée comprend dans un format de choix
    • une liste non ordonnée de capacités représentant le (multi) ensemble de condensateurs que vous avez
    • une paire de capacités représentant la limite inférieure et supérieure de la plage cible (inclus)
  2. toutes les capacités en entrée sont des entiers positifs inférieurs à 2 30 , l'unité est pF (pas ce qui compte).
  3. En plus de la liste des capacités en entrée, l'ensemble de condensateurs que vous avez contient également une quantité infinie de condensateurs d'une valeur de 0 pF.
  4. La sortie comprend dans un format de choix une liste de paires de capacités de telle sorte que la somme de chaque paire soit dans la plage cible spécifiée. Ni l'ordre des paires ni l'ordre des capacités au sein d'une paire n'est spécifié.
  5. Aucune capacité en sortie ne peut apparaître plus souvent qu'elle n'apparaît dans l'ensemble de condensateurs dont vous disposez . En d'autres termes: les paires que vous générez ne doivent pas se chevaucher.
  6. Il ne doit pas y avoir de sortie satisfaisant aux conditions 4 et 5 contenant plus de paires de capacités que la sortie produite par votre programme.
  7. Votre programme se terminera en temps O ( n !) Où n est la longueur de la liste représentant l'ensemble des condensateurs que vous avez
  8. Il ne faut pas abuser des échappatoires
  9. La plage cible ne doit pas être vide

Notation

Votre score est la longueur de votre solution en octets. Si votre solution parvient à résoudre ce problème en temps polynomial O ( n k ) pour certains k , divisez votre score par 10. Je ne sais pas si c'est réellement possible.

Exemple d'entrée

  • plage 100 à 100, tableau d'entrée 100 100 100, sortie valide:

    0 100
    0 100
    0 100
    
  • plage 100 à 120, tableau d'entrée 20 80 100, sortie valide:

    0 100
    20 80
    

    la sortie 20 100n'est pas valide

  • plage 90 à 100, tableau d'entrée 50 20 40 90 80 30 60 70 40, sortie valide:

    0 90
    20 80
    30 70
    40 60
    40 50
    
  • plage 90 à 90, tableau d'entrée 20 30 40 40 50 60 70 80 90, sortie valide:

    0 90
    20 70
    30 60
    40 50
    
  • plage 90 à 110, tableau d'entrée 40 60 50, sortie valide:

    40 60
    
FUZxxl
la source
3
Je suis assez certain que cela peut facilement être résolu dans O (n log n). Tout d'abord, associez n'importe quel condensateur dans la plage à un avec 0 pF. Triez le reste. Continuez à associer le condensateur le plus bas et le plus haut, s'il est au-dessus de la plage, jetez le plus haut, s'il est en dessous, jetez le plus bas.
orlp
1
Certains tests d'entrée / sortie seraient bien.
orlp
@orlp Je l'ai déjà demandé, l'OP y travaille
Beta Decay
2
L'algorithme de @ orlp fonctionne, mais la preuve est longue pour un commentaire. En substance, un contre-exemple minimal doit en avoir a <= b <= c <= dqui a + d, a + c, b + dsont tous dans la plage, mais b + cne le sont pas, mais cela donne une contradiction.
Peter Taylor
@orlp L'échantillon fourni vous est-il utile?
FUZxxl

Réponses:

1

CJam, 5,6

Il s'agit d'une réimplémentation directe de l'algorithme dans la réponse d' orlp . Si vous votez pour ma réponse, assurez-vous que vous votez également pour cette réponse . Je suggère également que la réponse avec l'algorithme d'origine soit acceptée, car je doute fort que j'aurais compris comment résoudre cela avec élégance dans O (n * log (n)).

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

Essayez-le en ligne

Exemple d'entrée:

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

Explication:

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.
Reto Koradi
la source
Vous pouvez modifier le format de sortie pour mieux l'adapter à votre langue. Le format exact de sortie n'est pas spécifié, seules les données que vous devez sortir le sont.
FUZxxl
6

Python 2, 11,5

Un golf Python pour une fois:

(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)]

J'ajoute un condensateur 0 pF pour chaque régulier, il n'y en a plus jamais besoin. Ensuite, nous trions les condensateurs et continuons d'associer le condensateur le plus bas et le plus élevé. Si la somme est dans la plage autorisée, nous l'imprimons, si elle est au-dessus de la plage, nous rejetons la plus élevée, si elle est inférieure à la plus basse.

Exemple d'entrée / sortie:

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

0 90
20 80
30 70
40 60
40 50
orlp
la source