Sparuj kondensatory

12

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 30 , 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
    
FUZxxl
źródło
3
Jestem całkiem pewien, że można to łatwo rozwiązać w O (n log n). Najpierw sparuj dowolny kondensator w zakresie do jednego z 0 pF. Sortuj resztę. Kontynuuj parowanie najniższego i najwyższego kondensatora, jeśli jest on powyżej zakresu, odrzuć najwyższy, jeśli poniżej, odrzuć najniższy.
orlp
1
Przydałyby się niektóre testy wejścia / wyjścia.
orlp
@orlp Już zapytałem, OP pracuje nad tym
Beta Decay
2
Algorytm @ orlp działa, ale dowód jest trochę długi na komentarz. Zasadniczo minimalna kontrprzykład musi mieć a <= b <= c <= dtakie, które a + d, a + c, b + dsą w zakresie, ale ich b + cnie ma, ale to daje sprzeczność.
Peter Taylor
@orlp Czy podane przykładowe dane wejściowe są dla Ciebie przydatne?
FUZxxl,

Odpowiedzi:

1

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.
Reto Koradi
źródło
Możesz zmienić format wyjściowy, aby był bardziej odpowiedni dla twojego języka. Dokładny format danych wyjściowych nie jest określony, tylko dane, które musisz wyprowadzić.
FUZxxl,
6

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
orlp
źródło