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
- 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)
- wszystkie pojemności na wejściu są dodatnimi liczbami całkowitymi mniejszymi niż 2 30 , jednostką jest pF (to nie ma znaczenia).
- 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.
- 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.
- Ż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ć.
- 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.
- 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
- Luki nie mogą być nadużywane
- 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 100
nie jest prawidłowyzakres 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
a <= b <= c <= d
takie, którea + d, a + c, b + d
są w zakresie, ale ichb + c
nie ma, ale to daje sprzeczność.Odpowiedzi:
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)).
Wypróbuj online
Przykładowe dane wejściowe:
Wyjaśnienie:
źródło
Python 2, 11.5
Golf Python raz:
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:
źródło