Betrachten Sie alle 2^n
unterschiedlichen binären Zeichenfolgen der Länge n
und nehmen Sie an n > 2
. Sie können genau b < n/2
Bits aus jeder der binären Zeichenfolgen löschen , wobei Zeichenfolgen mit n-b
verbleibender Länge übrig bleiben. Die Anzahl der verbleibenden Zeichenfolgen hängt davon ab, welche Bits Sie löschen. Angenommen, Sie möchten so wenig verschiedene Zeichenfolgen wie möglich übrig lassen, besteht diese Herausforderung darin, Code zu schreiben, um zu berechnen, wie wenig Sie als Funktion von verlassen können n
.
Beispiel n=3
und b = 1
. Sie können nur die beiden Zeichenfolgen 11
und 00
.
Für n=9
und b = 1,2,3,4
wir haben70,18,6,2
Für n=8
und b = 1,2,3
wir haben40,10,4
Für n=7
und b = 1,2,3
wir haben20,6,2
Für n=6
und b = 1,2
wir haben12,4
Für n=5
und b = 1,2
wir haben6,2
Diese Frage wurde ursprünglich von mir 2014 in einer anderen Form zu MO gestellt .
Ein- und Ausgabe
Ihr Code sollte eine Ganzzahl aufnehmen n
und eine einzelne Ganzzahl für jeden Wert ausgeben, der mit " b
Beginnen bei" b = 0
und "Erhöhen" beginnt .
Ergebnis
Ihre Punktzahl ist die höchste, n
für die Ihr Code b < n/2
auf meinem Linux-basierten PC in weniger als einer Minute vollständig ist . Im Falle von Unentschieden wird der größte b
Ihrer Codes für die gemeinsamen größten n
Gewinne erreicht. Auch bei Unentschieden nach diesem Kriterium entscheidet der schnellste Code für die größten Werte von n
und b
. Wenn die Zeiten innerhalb einer oder zweier Sekunden liegen, gewinnt die erste gesendete Antwort.
Sprachen und Bibliotheken
Sie können jede Sprache der Bibliothek verwenden, die Sie mögen. Da ich Ihren Code ausführen muss, würde es helfen, wenn er kostenlos wäre (wie in Bier) und unter Linux funktioniert.
quelle
b > 0
als zusätzlichen eingabebedarf an? Oder würden=3
undb=0
einfach2^n
als Ergebnis ausgeben ?2^n
Tat ausgeben .n
und eine einzelne Eingabe handelt.b
Die Punktzahl ist jedoch die größte,n
für die der Codeb < n/2
in weniger als einer Minute vollständig ist . Wäre esn
in diesem Fall nicht besser, eine einzige Eingabe zu haben und alle Ergebnisse für auszugeben0 <= b < n/2
? Oder sollten wir bieten zwei Programme / Funktionen: eine Aufnahme zwei Eingängen
undb
, und eine einzige Eingabe nehmenn
und alle Ergebnisse im Bereich ausgibt0 <= b < n/2
?Antworten:
Python 2.7 / Gurobi n = 9
Diese Lösung ist eine sehr direkte Anwendung von Gurobis ILP-Löser für die Booleschen Mixed-Integer-Probleme (MIP).
Der einzige Trick besteht darin, die Symmetrie im 1er-Komplement zu ermitteln, um die Problemgröße zu halbieren.
Mit der zeitlich begrenzten "kostenlosen" Lizenz von Gurobi LLC sind wir auf 2000 Einschränkungen beschränkt, aber das Lösen von 10 del 1 liegt auf meinem Laptop ohnehin weit außerhalb der 60-Sekunden-Frist.
UPDATE + CORR: 10,2 hat die optimale Lösungsgröße 31 (siehe zB) Gurobi zeigt, dass keine symmetrische Lösung der Größe 30 existiert (Rückgabeproblem nicht realisierbar) Muster von ganzen Zahlen
0 7 13 14 25 28 35 36 49 56 63 64 95 106 118 128 147 159 170 182 195 196 200 207 225 231 240 243 249 252 255
oder0 7 13 14 19 25 28 35 36 49 56 63 64 95 106 118 128 159 170 182 195 196 200 207 225 231 240 243 249 252 255
quelle
C ++, n = 6
Brute Force mit kleinen Optimierungen.
Lokal ausführen:
quelle