Kondensatoren sind dafür bekannt, dass sie mit hohen Toleranzen hergestellt werden. Dies ist in vielen Fällen akzeptabel, aber manchmal ist eine Kapazität mit engen Toleranzen erforderlich. Eine übliche Strategie, um eine Kapazität mit dem genauen Wert zu erhalten, den Sie benötigen, besteht darin, zwei sorgfältig abgemessene Kondensatoren parallel zu verwenden, so dass sich ihre Kapazitäten zu etwas in dem Bereich summieren, den Sie benötigen.
Das Ziel bei dieser Herausforderung besteht darin, die Kondensatoren bei einem (Mehr-) Satz von Kapazitäten so zu koppeln, dass die Gesamtkapazität jedes Paares in einem bestimmten Bereich liegt. Sie müssen auch den besten Satz von Paaren finden, dh den Satz von Paaren, so dass so viele Paare wie möglich gefunden werden.
Einschränkungen
- Die Eingabe erfolgt in einem Format Ihrer Wahl
- eine ungeordnete Liste von Kapazitäten, die die (Mehr-) Menge von Kondensatoren darstellt, die Sie haben
- ein Kapazitätspaar, das die Unter- und Obergrenze des Zielbereichs darstellt (einschließlich)
- Alle Kapazitäten in der Eingabe sind positive ganze Zahlen kleiner als 2 30 , die Einheit ist pF (nicht das, was zählt).
- Zusätzlich zu der Liste der Kapazitäten im Eingang die Menge der Kondensatoren, die Sie haben enthält auch eine unendliche Menge von Kondensatoren mit einem Wert von 0 pF.
- Die Ausgabe umfasst in einem Format der Wahl eine Liste von Kapazitätspaaren, so dass die Summe jedes Paares im Zielbereich liegt . Weder die Reihenfolge der Paare noch die Reihenfolge der Kapazitäten innerhalb eines Paares ist festgelegt.
- Möglicherweise wird keine Kapazität im Ausgang häufiger angezeigt als in den vorhandenen Kondensatoren . Mit anderen Worten: Die von Ihnen ausgegebenen Paare dürfen sich nicht überlappen.
- Es darf keine Ausgabe geben, die die Bedingungen 4 und 5 erfüllt und mehr Kapazitätspaare enthält als die Ausgabe, die Ihr Programm erzeugt.
- Ihr Programm endet in der Zeit O ( n !), In der n die Länge der Liste ist, die den Satz von Kondensatoren darstellt, die Sie haben
- Lücken dürfen nicht missbraucht werden
- Der Zielbereich darf nicht leer sein
Wertung
Ihre Punktzahl ist die Länge Ihrer Lösung in Oktetten. Wenn Ihre Lösung es schafft, dieses Problem in der Polynomzeit O ( n k ) für einige k zu lösen , dividieren Sie Ihre Punktzahl durch 10. Ich weiß nicht, ob dies tatsächlich möglich ist.
Probeneingabe
Bereich 100 bis 100, Eingangsarray
100 100 100
, gültige Ausgabe:0 100 0 100 0 100
Bereich 100 bis 120, Eingangsarray
20 80 100
, gültige Ausgabe:0 100 20 80
Die Ausgabe
20 100
ist ungültigBereich 90 bis 100, Eingabearray
50 20 40 90 80 30 60 70 40
, gültige Ausgabe:0 90 20 80 30 70 40 60 40 50
Bereich 90 bis 90, Eingabearray
20 30 40 40 50 60 70 80 90
, gültige Ausgabe:0 90 20 70 30 60 40 50
Bereich 90 bis 110, Eingabearray
40 60 50
, gültige Ausgabe:40 60
a <= b <= c <= d
solche haben,a + d, a + c, b + d
die alle im Bereich liegen, aberb + c
nicht sind, aber das gibt einen Widerspruch.Antworten:
CJam, 5.6
Dies ist eine direkte Neuimplementierung des Algorithmus in der Antwort von orlp . Wenn Sie meine Antwort positiv bewerten, stellen Sie bitte sicher, dass Sie diese Antwort ebenfalls positiv bewerten . Ich schlage auch vor, dass die Antwort mit dem ursprünglichen Algorithmus akzeptiert wird, weil ich sehr bezweifle, dass ich herausgefunden hätte, wie man dies elegant in O (n * log (n)) löst.
Probieren Sie es online aus
Beispieleingabe:
Erläuterung:
quelle
Python 2, 11.5
Ein Python-Golf für einmal:
Ich füge einen 0 pF Kondensator für jeden regulären hinzu, es wird nie mehr benötigt. Dann sortieren wir die Kondensatoren und koppeln weiterhin den niedrigsten und den höchsten Kondensator. Wenn die Summe innerhalb des zulässigen Bereichs liegt, drucken wir sie, wenn sie über dem Bereich liegt, verwerfen wir die höchste, wenn sie unter dem niedrigsten Wert liegt, verwerfen wir die niedrigste.
Beispiel Ein- / Ausgabe:
quelle