Wir definieren ein Binarray als ein Array, das die folgenden Eigenschaften erfüllt:
- es ist nicht leer
- Der erste Wert ist a
1
- Der letzte Wert ist a
1
- Alle anderen Werte sind entweder
0
oder1
Zum Beispiel das Array [ 1, 1, 0, 1 ]
ein gültiges Binarray .
Die Aufgabe
Bei einem nicht leeren Array A mit nicht negativen Ganzzahlen und einer positiven Ganzzahl N müssen Sie ein Binarray B mit der Länge N finden , mit dem Sie A durch Summieren einer uneingeschränkten Anzahl von Kopien von B generieren können , die um eine uneingeschränkte Anzahl von verschoben sind Positionen.
Beispiel
A = [ 1, 1, 2, 4, 1, 2, 2, 1, 0, 1, 0, 1, 1, 0, 1 ]
N = 4
Für diese Eingabe wäre das Binarray B = [ 1, 1, 0, 1 ]
eine gültige Antwort, da wir Folgendes tun können:
[ 1, 1, 0, 1 ]
+ [ 1, 1, 0, 1 ]
+ [ 1, 1, 0, 1 ]
+ [ 1, 1, 0, 1 ]
+ [ 1, 1, 0, 1 ]
+ [ 1, 1, 0, 1 ]
-----------------------------------------------
= [ 1, 1, 2, 4, 1, 2, 2, 1, 0, 1, 0, 1, 1, 0, 1 ]
Regeln
- Die Eingabe kann in jedem vernünftigen Format erfolgen.
- Die Ausgabe kann entweder ein natives Array (z. B.
[1, 1, 0, 1]
) oder eine Binärzeichenfolge mit oder ohne Trennzeichen (z. B."1,1,0,1"
oder"1101"
) sein. - Sie müssen nur ein gültiges Binarray ausdrucken oder zurücksenden . Alternativ können Sie alle drucken oder zurückgeben , wenn mehrere Lösungen vorhanden sind.
- Sie müssen keine Eingaben unterstützen, die zu keiner Lösung führen.
- Die Summe kann implizite Nullen enthalten, die sich mit keiner Kopie von B überschneiden . Die zweite Null in der obigen Summe ist eine solche implizite Null.
- Sie können davon ausgehen, dass die maximale Größe von A 100 und die maximale Größe von B 30 beträgt.
- Das ist Code-Golf, also gewinnt die kürzeste Antwort in Bytes. Standardlücken sind verboten.
Testfälle
Input : N = 1 / A = [ 1, 2, 3, 4, 5 ]
Output: [ 1 ]
Input : N = 2 / A = [ 1, 2, 100, 99 ]
Output: [ 1, 1 ]
Input : N = 3 / A = [ 1, 1, 1 ]
Output: [ 1, 1, 1 ]
Input : N = 3 / A = [ 1, 1, 3, 2, 2 ]
Output: [ 1, 1, 1 ]
Input : N = 3 / A = [ 1, 0, 2, 1, 1, 1, 0, 0, 1, 0, 1 ]
Output: [ 1, 0, 1 ]
Input : N = 4 / A = [ 1, 2, 2, 2, 1 ]
Output: [ 1, 1, 1, 1 ]
Input : N = 4 / A = [ 1, 1, 2, 4, 1, 2, 2, 1, 0, 1, 0, 1, 1, 0, 1 ]
Output: [ 1, 1, 0, 1 ]
Input : N = 4 / A = [ 1, 1, 0, 2, 1, 0, 1 ]
Output: [ 1, 0, 0, 1 ] or [ 1, 1, 0, 1 ]
Input : N = 5 / A = [ 1, 3, 6, 9, 8, 6, 3, 4 ]
Output: [ 1, 1, 1, 0, 1 ]
Input : N = 8 / A = [ 2, 1, 0, 2, 3, 3, 1, 2, 1 ]
Output: [ 1, 0, 0, 1, 1, 1, 0, 1 ]
Input : N = 10 / A = [ 1, 2, 1, 2, 2, 1, 3, 3, 3, 2, 3, 0, 2, 1, 1, 0, 1 ]
Output: [ 1, 1, 0, 1, 0, 1, 1, 1, 0, 1 ]
Input : N = 13 / A = [ 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1 ]
Output: [ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 ]
Input : N = 5 / A = [ 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1 ]
Output: [ 1, 1, 1, 1, 1 ]
Input : N = 6 / A = [ 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1 ]
Output: [ 1, 0, 0, 0, 0, 1 ]
Input : N = 7 / A = [ 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1 ]
Output: [ 1, 1, 0, 0, 0, 1, 1 ]
Input : N = 9 / A = [ 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1 ]
Output: [ 1, 0, 1, 0, 1, 0, 1, 0, 1 ]
code-golf
array-manipulation
polynomials
Arnauld
quelle
quelle
N
vernünftigerweise unterstützt werden sollte?N=4, A = [ 1, 1, 2, 4, 1, 2, 2, 2, 1, 2, 2, 1, 2, 0, 1 ]
bekommst du 30459, das sowohl durch 11 als auch durch 13 teilbar ist und doch nur eine von[ 1, 1, 0, 1 ]
und[ 1, 0, 1, 1 ]
eine gültige Antwort ist.Antworten:
PHP,
105 92 9086 BytesJörgs Lösung fixiert und golfen:
Nimmt
N
vom ersten Kommandozeilenargument Werte danach; Laufen Sie mit-r
oder testen Sie es online .druckt Binärzahl (Format
10001
); Gibt eine ungültige Lösung aus oder wird beendet, wenn keine gültige Lösung vorhanden ist.Erste Version (jetzt 97 Byte), die nichts für ungültige Eingaben ausgibt: Testen Sie sie online
Nervenzusammenbruch
quelle
111
wenn das einzig richtige Ergebnis [1, 0, 1] ist.PHP , 219 Bytes
Probieren Sie es online!
-4 Bytes mit
[$g,$z]=$_GET
PHP 7.1 stattlist($g,$z)=$_GET
quelle
[1,0,1,0,1,0,1,0,1]
) als auch eine ungültige Antwort ([1,0,0,0,1,0,1,1,1]
) für den letzten Testfall ausgegeben.while($_GET[0])$s+=2**$i++*array_pop($_GET[0]);
. -5 Bytesrange(1|.5*$m=2**$_GET[1],$m,2)
.[ 1,0,1,1,1,0,2,2,2,2,2,1 ]
.for($g=$_GET[0];$g;)
.Python, 166 Bytes
Probieren Sie es online!
Wie es funktioniert
Betrachten Sie A und B als die Ziffern der Basis- k- Zahlen u und v . Zum Beispiel ( zur Veranschaulichung verwenden wir k = 1000):
A = [1, 2, 1, 3, 2, 1, 2]
B = [1, 0, 0, 1]
u = 1 002 001 003 002 001 002
v = 1 000 000 001
Wie viele der anderen Antwortenden bemerkt haben, ist u durch v teilbar , wenn B eine gültige Antwort ist . In diesem Fall,
u = 1 002 001 002 ⋅ v
Dieser Quotient, der in das Array [1, 2, 1, 2] zurückübersetzt wird, gibt genau an, wie viele Kopien von B an jede Position verschoben werden müssen.
(Warum? Denn genau so lange funktioniert die Multiplikation in der Basis k .)
Was die anderen Antwortenden nicht bemerkten, ist, dass die obige Bedingung nicht ausreicht . Beispielsweise:
A = [1, 2, 1, 3, 2, 1, 2]
B = [1, 1, 1, 1]
u = 1 002 001 003 002 001 002
v = 1 001 001 001
u = 1 000 999 002 ⋅ v
Mathematisch gesehen können wir diesen Quotienten immer noch zurück in das Array [1, 1, −1, 2] übersetzen, was gut funktioniert, wenn wir negative Kopien von B verwenden dürfen:
Aber natürlich erlaubt die Herausforderung keine negativen Kopien. Wir brauchen also einen zusätzlichen Scheck.
Mit diesem Ziel, wählen wir eine Basis k = 10 e , wo k > 10 ⋅ Summe (A), und sicherstellen , dass keine von der Basis k Ziffern Überlauf in die nächsten Basis k digit wenn multiplizieren wir die Quotienten von zehn. Das heißt, jeder e ten Basiszehnstellige, am Ende ausgehend, in der Basis - Zehn - Darstellung des Quotienten mal zehn muss 0. Dies garantiert sein , dass der Quotient mit nicht - negativen Elementen auf ein Array zurück übersetzt.
quelle
PHP, 213 Bytes
Genauso ein bisschen golfen
Probieren Sie es online!
PHP, 344 Bytes zuerst funktioniert
Nach meiner ersten Antwort habe ich beschlossen, einen längeren Versuch zu machen, der alle gültigen Lösungen zurückgibt.
Online Version
Nervenzusammenbruch
quelle
=
in der ersten Schleife für die kürzere Version gesetzt werden müssen. In der größeren Version müssen vier Bytes gelöscht werdenPython, 205 Bytes
Gibt eine Binärzeichenfolge ohne Trennzeichen zurück. Wie @AndersKaseorg ausführt, gibt es Eingaben, für die die @ fəˈnəˈtɪk-Lösung nicht funktioniert, weil die Division einen negativen Koeffizienten darstellt, der nicht zulässig ist. Um das zu umgehen, benutze ich eine sehr große Basis und teste, dass es in der Abteilung kein Darlehen gibt.
quelle
f([1, 1, 1, 0, 0, 0, 1, 1, 1], 3)
Gibt fälschlicherweise zurück101
.f([1, 0, 2, 0, 2, 0, 1], 3)
, und sowohl die Vorwärts- als auch die Rückwärtsvariante schlagen fehlf([1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0], 5)
.i
als ungerade markieren, schlagen sowohl die Vorwärts- als auch die Rückwärtsvariante fehlf([1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0]*10, 5)
.(x^kn-1)/(x^k-1)
immer(x^n-1)/(x-1)
einen Faktor, der die Lösung von @ fɛnɪtɛk in einer beliebigen Basis zum Narren hält.Pyth, 32 Bytes
Probieren Sie es online aus
Wie es funktioniert
Die Strategie ist meiner Python-Antwort ähnlich , außer dass wir, da Pyth über integrierte Funktionen für die Basiskonvertierung verfügt, eine effizientere Basis k = 2 ⋅ sum (A) verwenden und direkt überprüfen können, ob jede Ziffer des Quotienten höchstens sum (A) ist ).
quelle
Pari / GP ,
77749680 BytesGibt alle Lösungen zurück.
Zuerst konvertiert das Array
a
in ein Polynomb
. Dann wählt man aus den Teilernb
die Polynomed
so, dass die Koeffizienten vond
alle1
und0
und die Koeffizienten vonb / d
alle nichtnegativ sind undd(0) = 1
unddeg(d) = n + 1
. Konvertiert sie schließlich wieder in Arrays.Probieren Sie es online!
quelle