Kondensatory są znane z tego, że są produkowane z wysoką tolerancją. Jest to do przyjęcia w wielu przypadkach, ale czasami wymagana jest pojemność z wąskimi tolerancjami. Powszechną strategią uzyskiwania pojemności o dokładnie takiej wartości, jakiej potrzebujesz, jest stosowanie dwóch dokładnie mierzonych kondensatorów równolegle, tak aby ich pojemności dodawały się do czegoś w potrzebnym zakresie.

Celem tego wyzwania jest, biorąc pod uwagę (wiele) zestaw pojemności, sparowanie kondensatorów tak, aby całkowita pojemność każdej pary mieściła się w danym zakresie. Musisz także znaleźć najlepszy zestaw par, to znaczy zestaw par, aby znaleźć jak najwięcej par.

Ograniczenia

1. Dane wejściowe obejmują wybrany format
   • nieuporządkowana lista pojemności reprezentujących (wiele) zestaw kondensatorów, które masz
   • para pojemności reprezentujących dolną i górną granicę zakresu docelowego (włącznie)
2. wszystkie pojemności na wejściu są dodatnimi liczbami całkowitymi mniejszymi niż 2 ³⁰ , jednostką jest pF (to nie ma znaczenia).
3. Oprócz listy pojemności na wejściu, zestaw kondensatorów, które masz, zawiera również nieskończoną liczbę kondensatorów o wartości 0 pF.
4. Dane wyjściowe zawierają w wybranym formacie listę par pojemności, tak aby suma każdej pary mieściła się w określonym zakresie docelowym . Nie określono ani kolejności par, ani kolejności pojemności w parze.
5. Żadna pojemność na wyjściu może nie pojawiać się częściej niż w zestawie kondensatorów, który masz . Innymi słowy: Wyprowadzane pary nie mogą się pokrywać.
6. Nie będzie możliwe wyjście spełniające warunki 4 i 5, które zawierałoby więcej par pojemności niż wyjście, które wytwarza twój program.
7. Twój program zakończy się w czasie O ( n !), Gdzie n jest długością listy reprezentującej zestaw kondensatorów, które masz
8. Luki nie mogą być nadużywane
9. Zakres docelowy nie może być pusty

Punktacja

Twój wynik to długość twojego rozwiązania w oktetach. Jeśli twojemu rozwiązaniu uda się rozwiązać ten problem w czasie wielomianowym O ( n ^k ) dla jakiegoś k , podziel swój wynik przez 10. Nie wiem, czy to jest rzeczywiście możliwe.

Przykładowe dane wejściowe

• zakres od 100 do 100, tablica wejściowa 100 100 100, prawidłowe dane wyjściowe:

  0 100
  0 100
  0 100
  

• zakres od 100 do 120, tablica wejściowa 20 80 100, prawidłowe dane wyjściowe:

  0 100
  20 80
  

  wynik 20 100nie jest prawidłowy

• zakres od 90 do 100, tablica wejściowa 50 20 40 90 80 30 60 70 40, prawidłowe dane wyjściowe:

  0 90
  20 80
  30 70
  40 60
  40 50
  

• zakres od 90 do 90, tablica wejściowa 20 30 40 40 50 60 70 80 90, prawidłowe dane wyjściowe:

  0 90
  20 70
  30 60
  40 50
  

• zakres od 90 do 110, tablica wejściowa 40 60 50, prawidłowe dane wyjściowe:

  40 60
  

CJam, 5.6

Jest to bezpośrednia ponowna implementacja algorytmu w odpowiedzi ORLP . Jeśli głosujesz za moją odpowiedzią, upewnij się, że głosujesz również za tą odpowiedzią . Sugeruję również, że odpowiedź z oryginalnym algorytmem jest akceptowana, ponieważ bardzo wątpię, czy wymyśliłbym, jak rozwiązać to elegancko w O (n * log (n)).

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

Wypróbuj online

Przykładowe dane wejściowe:

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

Wyjaśnienie:

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

Golf Python raz:

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

Dodam jeden kondensator 0 pF na każdy zwykły, nigdy więcej nie jest potrzebny. Następnie sortujemy kondensatory i kontynuujemy parowanie najniższego i najwyższego kondensatora. Jeśli suma mieści się w dopuszczalnym zakresie, drukujemy ją, jeśli jest powyżej zakresu, odrzucamy najwyższy, jeśli jest niższy, odrzucamy najniższą.

Przykładowe wejście / wyjście:

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

0 90
20 80
30 70
40 60
40 50