Perfekte Kennzeichen

Ich habe vor ein paar Jahren angefangen, ein kleines Spiel zu machen, während ich herumfuhr: Überprüfen, ob die Nummernschilder in der Nähe "perfekt" sind. Es ist relativ selten, aber aufregend, wenn Sie eine finden.

So prüfen Sie, ob ein Nummernschild perfekt ist:

1. Fassen Sie die Zeichen mit A = 1, B = 2, ... Z = 26 zusammen.
2. Nimm jeden aufeinanderfolgenden Teil der Ziffern und addiere sie; Multiplizieren Sie jede dieser Summen.

Wenn die Werte in Teil 1 und Teil 2 gleich sind, herzlichen Glückwunsch! Sie haben ein perfektes Kennzeichen gefunden!

Beispiele

License plate: AB3C4F

Digits -> 3 * 4 
        = 12
Chars  -> A + B + C + F 
        = 1 + 2 + 3 + 6 
        = 12
12 == 12 -> perfect!


License plate: G34Z7T

Digits -> (3 + 4) * 7 
        = 49
Chars  -> G + Z + T 
        = 7 + 26 + 20 
        = 53
49 != 53 -> not perfect!


License plate: 10G61

Digits -> (1 + 0) * (6 + 1)
        = 7
Chars  -> G
        = 7
7 == 7 -> perfect!

Die Herausforderung

Ich habe als Beispiel Nummernschilder der Länge 5 und 6 verwendet, aber diese Prozedur ist für jede Nummernschildlänge gültig. Ihre Herausforderung besteht darin, für eine gegebene Länge N die Anzahl der perfekten Nummernschilder dieser Länge zurückzugeben. Ein gültiges Kennzeichen im Sinne der Herausforderung ist eine beliebige Kombination aus Ziffern 0-9 und Zeichen AZ. Die Platte muss sowohl ein Zeichen als auch eine Ziffer enthalten , um als potenziell perfekt angesehen zu werden. Zu Überprüfungszwecken sind hier die Werte, die ich erhalten habe (obwohl ich nicht 100% über ihre Korrektheit sein kann, hahaha)

N < 2: 0
N = 2: 18
N = 3: 355
N = 4: 8012 

Anmerkungen

Wenn es das Problem in Ihrer Sprache irgendwie einfacher macht, können Sie den Anteil perfekter Nummernschilder für ein bestimmtes N auf mindestens 2 signifikante Stellen ausgeben .

N < 2: 0
N = 2: 0.0138888...
N = 3: 0.0076088...
N = 4: 0.0047701...

ODER Sie können den Äquivalentwert mod 256 ausgeben

N < 2: 0
N = 2: 18
N = 3: 99
N = 4: 76

Kürzeste Gewinne!

Python 3.6, 150 Bytes

f=lambda n,t=-1,p=-1,a=0:sum(f(n-1,*((t,c+p*(p>=0),a),((t<0 or t)*(p<0 or p),-1,a-c))[c<0])for c in range(-26,10))if n else 0<(t<0 or t)*(p<0 or p)==a

Ergebnisse:

f(2) = 18
f(3) = 355
f(4) = 8012
f(5) = 218153

Ungolfed Version mit Erklärung:

digits=[*range(10)]
letters=[*range(1,27)]

def f(n, dt=-1, dp=-1, lt=0):
    if n:
        for d in digits:
            yield from f(n - 1,
                         dt,
                         d if dp < 0 else dp + d,
                         lt
                         )

        for l in letters:
            yield from f(n - 1,
                         dp if dt < 0 else dt if dp < 0 else dt*dp,
                         -1,
                         lt + l
                         )
    else:
        yield 0 < lt == (dt<0 or dt)*(dp<0 or dp)

Das Problem besteht darin, einen Baum zu suchen, in dem jede Ebene des Baums einer Position in einer Kennzeichen-Nummer entspricht und jeder Knoten 36 untergeordnete Elemente (10 Ziffern und 26 Buchstaben) aufweist. Die Funktion durchsucht den Baum rekursiv und sammelt dabei die Werte für die Ziffern und Buchstaben.

n is the number of levels to search. 
dp accumulates the sum of a group of digits.
dt accumulates the product of the digit sums.
lt accumulates the sum of the letter values.

For dp and dt, a value < 0 indicates it is not initialized.

Golf inklusive, Umwandlung der for-Schleifen in Summen von Generatoren:

sum(f(n-1, 
      dt,
      d if dp < 0 else dp + d,
      lt) for d in digits)
+
sum(f(n-1,
      dp if dt<0 else dt if dp<0 else dt*dp,
      -1,
      lt+l) for l in letters)

Dann die Generatoren kombinieren. Kodieren Sie die Buchstaben von A bis Z als -1 bis -26 und die Ziffern als 0 bis 9. Die Summe wird also zu:

sum(f(n-1, *args) for c in range(-26, 10)),

wo args ist:

((dp if dt<0 else dt if dp<0 else dt*dp, -1, lt-l) if c <0 else
 (dt, d if dp<0 else dp+d, lt))

Der Rest des Golfspiels besteht darin, die Funktion in ein Lambda umzuwandeln, Variablennamen zu verkürzen und Ausdrücke zu vereinfachen.

Dyalog APL, 57 56 Bytes

+/(+/0⌈a-9)=×/c*⍨-2-/0,⌈\(+\a×b)×c←2>/0,⍨b←9≥a←↑1↓,⍳⎕⍴36

(nimmt an ⎕io←0)

aMatrix aller gültigen Nummernschilder (außer 00...0) codiert mit: 0-9 für Ziffern, 10-35 für Buchstaben

b Bitmaske für Stellen, an denen Ziffern vorkommen

c Bitmaske für die letzte Ziffer in jeder Gruppe aufeinanderfolgender Ziffern

Python 2, 359 295 Bytes

Eher lang; Das ist die triviale Lösung. Ich bin zuversichtlich, dass dies korrekt ist, obwohl es nicht mit den Testfällen in der Herausforderung übereinstimmt. Die Lösungen, die ich bekomme, stimmen mit den Antworten von Dada überein.

import itertools as i,re as r,string as s
print len([''.join(x)for x in i.product(s.lowercase+s.digits,repeat=input())if(lambda t:r.search('\\D',t)and r.search('\\d',t)and reduce(int.__mul__,[sum(map(int,k))for k in r.split('\\D+',t)if k])==sum([k-96 for k in map(ord,t) if k>96]))(''.join(x))])

-64 Bytes dank Vorschlägen von @numbermaniac

Python 2 , 291 287 276 273 Bytes

lambda n:sum(1for x in s.product(y+z,repeat=n)if(lambda p,s=set:reduce(int.__mul__,[sum(map(int,i))for i in re.findall(r"\d+",p)],1)==sum(ord(i)-64for i in p if ord(i)>64)and s(p)&s(y)and s(p)&s(z))(''.join(x)))
import re,itertools as s,string as t
y=t.uppercase
z=t.digits

Probieren Sie es online!

Ergebnisse:

0 0
1 0
2 18
3 355
4 8012

Perl 5 , 117 Bytes

116 Byte Code + -pFlag.

$"=",";@F=(A..Z,0..9);map{$r=1;$r*=eval s/./+$&/gr for/\d+/g;$r+=64-ord for/\pl/g;$\+=!$r*/\pl/*/\d/}glob"{@F}"x$_}{

Probieren Sie es online!

Es fühlt sich ziemlich suboptimal an, aber ich habe momentan keine Ideen mehr.
Der Code selbst ist sehr ineffizient, da er jede Permutation von a..z,0..9Länge berechnet n(ca. 1 Sekunde n=3, ca. 15 Sekunden n=4und ca. 7 Minuten n=5).
Der Algorithmus ist ganz einfach: Berechnet für jede mögliche Platte der Größe n(generiert mit glob"{@F}"x$_- der globOperator ist ziemlich magisch) $r*=eval s/./+$&/gr for/\d+/g;das Produkt jedes Ziffernblocks und $r+=64-ord for/\pl/gsubtrahiert das Gewicht der Buchstaben. Dann erhöhen wir den Zähler, $\wenn das $rist 0( !$r) und wenn die Platte Zahlen und Buchstaben enthält ( /\pl/*/\d/). $\wird dank -pflag implizit am ende gedruckt .

Beachten Sie, dass die Zahlen , die ich erhalten sind n=2 -> 18, n=3 -> 355, n=4 -> 8012, n=5 -> 218153. Ich bin mir ziemlich sicher, dass dies die richtigen sind, aber ich könnte mich irren. In diesem Fall lass es mich wissen und ich werde diese Antwort löschen.

APL (Dyalog) , 71 Bytes

Voller Programmteil. Eingabeaufforderungen für N. N≥4 erfordern sehr viel Speicher und Rechenaufwand.

+/((+/⊢⍳∩)∘⎕A=(×/'\d+'⎕S{+/⍎¨⍵.Match}))¨l/⍨∧⌿∨/¨c∘.∊l←,(∊c←⎕D⎕A)∘.,⍣⎕⊂⍬

Probieren Sie es online!

Scala, 265 Bytes

(n:Int)=>{val i=('A'to'Z')++('0'to'9');Seq.fill(n)(i).flatten.combinations(n).flatMap(_.permutations).map(_.mkString).count(l=>"(?=.*[A-Z])(?=.*\\d)".r.findAllIn(l).size>0&&l.map(_-64).filter(_>0).sum==l.split("[A-Z]").filter(""<).map(_.map(_-48).sum).reduce(_*_))}

Erklärungen:

(n:Int) => {
    val i = ('A' to 'Z') ++ ('0' to '9');                       // All license plates available characters.
    Seq.fill(n)(i).flatten                                      // Simulate combination with repetition (each character is present n times)
        .combinations(n)                                        // and generate all combinations of size n (all license plates).
        .flatMap(_.permutations)                                // For each combination, generate all permutations (ex. : Seq('A', '1') => Seq('A', '1') and Seq('1', 'A')), and
        .map(_.mkString)                                        // convert each permutation to String (Seq('A', '1') => "A1").
        .count ( l =>                                           // Then count all strings having :
            "(?=.*[A-Z])(?=.*\\d)".r.findAllIn(l).size > 0 &&   // at least 1 character and 1 digit and
            l.map(_ - 64).filter(_ > 0).sum ==                  // a sum of characters (> 'A' or > 64) equals to
            l.split("[A-Z]").filter(""<)
                .map(_.map(_ - 48).sum)
                .reduce(_*_)                                    // the product of sum of digits groups (split String by letters to get digits groups)
        )
}

Anmerkungen :

• -64und -48werden verwendet , um ein zu transformieren Char(bzw. Buchstaben und Ziffern) auf seinen IntWert ( 'A' - 64 = 1, 'B' - 64 = 2..., '9' - 48 = 9)
• Mit dem Filter in l.split("[A-Z]").filter(""<)werden ""Werte entfernt, ldie mit einem Buchstaben beginnen (Beispiel:) "A1".split("[A-Z]") => Array("", 1). Es könnte eine bessere und kürzere Lösung geben

Testfälle:

val f = (n:Int) => ...  // assign function
(1 to 5).foreach ( i =>
    println(s"N = $i: ${f(i)}")
)

Ergebnisse :

N = 1: 0
N = 2: 18
N = 3: 355
N = 4: 8012
N = 5: 218153

Die Funktion ist ziemlich langsam, n > 4da alle Kombinationen generiert werden müssen.

Java, 382 365 Bytes

• Dank Kevin Cruijssen 17 Byte gespeichert

Golf gespielt

int h(String s){int m=0;for(int c:s.toCharArray())m+=c-48;return m;}
int g(String t){int d=1,c=0;for(String s:t.split("[^0-9]"))d*=h(s);for(String s:t.split("[^A-Z]"))c+=s.charAt(0)-65;return d==c?1:0;}
int f(String t,int n){int m=0;if(t.length()==n)return g(t);for(int d=48;d<58;)m+=f(t+d++,n);for(int c=65;c<91;)m+=f(t+c++,n);return m;}
int s(int n){return f("",n);}

Detailliert

// return sum of adjecent digits
int h(String s)
{
    int sum = 0;
    for(char c : s.toCharArray()) sum += c-'0';
    return sum;
}

// check if perfect
int g(String t)
{
    int d = 1;
    int c = 0;

    for(String s : t.split("[^0-9]")) d *= h(s);
    for(String s : t.split("[^A-Z]")) c += s.charAt(0)-'A';

    return d == c ? 1 : 0;
}

// tree of enumerations
int f(String t, int n)
{
    // base case
    if(t.length() == n)
    {
        return g(t);
    }

    // enumeration
    int sum = 0;
    for(char d='0'; d<='9'; d++) sum += f(t+d, n);
    for(char c='A'; c<='Z'; c++) sum += f(t+c, n);

    return sum;
}

int s(int n){ return f("",n); }

GAP , 416 Bytes

Gewinnt nicht mit der Codegröße und bei weitem nicht mit der konstanten Zeit, sondern verwendet Mathematik, um viel zu beschleunigen!

x:=X(Integers);
z:=CoefficientsOfUnivariatePolynomial;
s:=Size;

f:=function(n)
 local r,c,p,d,l,u,t;
 t:=0;
 for r in [1..Int((n+1)/2)] do
  for c in [r..n-r+1] do
   l:=z(Sum([1..26],i->x^i)^(n-c));
   for p in Partitions(c,r) do
    d:=x;
    for u in List(p,k->z(Sum([0..9],i->x^i)^k)) do
     d:=Sum([2..s(u)],i->u[i]*Value(d,x^(i-1))mod x^s(l));
    od;
    d:=z(d);
    t:=t+Binomial(n-c+1,r)*NrArrangements(p,r)*
         Sum([2..s(d)],i->d[i]*l[i]);
   od;
  od;
 od;
 return t;
end;

Um das unnötige Leerzeichen zu entfernen und eine Zeile mit 416 Bytes zu erhalten, gehen Sie folgendermaßen vor:

sed -e 's/^ *//' -e 's/in \[/in[/' -e 's/ do/do /' | tr -d \\n

Mein alter "für Windows XP entworfener" Laptop kann f(10)in weniger als einer Minute rechnen und in weniger als einer Stunde noch viel weiter gehen:

gap> for i in [2..15] do Print(i,": ",f(i),"\n");od;
2: 18
3: 355
4: 8012
5: 218153
6: 6580075
7: 203255386
8: 6264526999
9: 194290723825
10: 6116413503390
11: 194934846864269
12: 6243848646446924
13: 199935073535438637
14: 6388304296115023687
15: 203727592114009839797

Wie es funktioniert

Angenommen, wir möchten zunächst nur die Anzahl der perfekten Nummernschilder kennen, die zum Muster passen LDDLLDL, wobei Lein Buchstabe und Deine Ziffer bezeichnet werden. Angenommen, wir haben eine Liste lvon Zahlen, l[i]die die Anzahl der Möglichkeiten angibt, wie die Buchstaben den Wert angeben können i, und eine ähnliche Liste dfür die Werte, die wir aus den Ziffern erhalten. Dann ist die Anzahl der perfekten Nummernschilder mit gemeinsamem Wert igerade l[i]*d[i], und wir erhalten die Anzahl aller perfekten Nummernschilder mit unserem Muster, indem wir dies über alles summiereni . Lassen Sie uns die Operation bezeichnen, mit der diese Summe berechnet wird l@d.

Selbst wenn der beste Weg, um diese Listen zu erhalten, darin bestand, alle Kombinationen und Zählwerte auszuprobieren, können wir dies unabhängig für die Buchstaben und Ziffern tun und dabei 26^4+10^3Fälle anstelle von 26^4*10^3 Fällen betrachten, in denen wir einfach alle Platten durchlaufen, die zum Muster passen. Aber wir können viel besser: lIst nur die Liste der Koeffizienten, (x+x^2+...+x^26)^kwo kist die Anzahl der Buchstaben, hier 4.

In ähnlicher Weise erhalten wir die Anzahl der Möglichkeiten, um eine Summe von Ziffern in einer Folge von kZiffern als die Koeffizienten von zu erhalten (1+x+...+x^9)^k. Wenn es mehr als ein Lauf von Ziffern ist, müssen wir die entsprechenden Listen mit einer Operation kombinieren , d1#d2dass in der Position ials Wert die Summe aller , d1[i1]*d2[i2]wo i1*i2=i. Dies ist die Dirichlet-Faltung, die nur das Produkt ist, wenn wir die Listen als Koeffizienten von Dirchlet-Reihen interpretieren. Aber wir haben sie bereits als Polynome (endliche Potenzreihen) verwendet, und es gibt keine gute Möglichkeit, die Operation für sie zu interpretieren. Ich denke, dieses Missverhältnis ist Teil dessen, was es schwierig macht, eine einfache Formel zu finden. Verwenden wir es trotzdem für Polynome und verwenden die gleiche Notation #. Es ist einfach zu berechnen, wenn ein Operand ein Monom ist: wir habenp(x) # x^k = p(x^k). Zusammen mit der Tatsache, dass es bilinear ist, ergibt dies eine schöne (aber nicht sehr effiziente) Möglichkeit, es zu berechnen.

Beachten Sie, dass kBuchstaben einen Wert von höchstens 26kund k einzelne Ziffern einen Wert von ergeben können 9^k. So werden wir im dPolynom oft nicht benötigte hohe Potenzen bekommen . Um sie loszuwerden, können wir modulo berechnen x^(maxlettervalue+1). Dies beschleunigt erheblich und hilft, obwohl ich es nicht sofort bemerkt habe, sogar beim Golfen, da wir jetzt wissen, dass der Grad dnicht größer ist als der von l, was die Obergrenze im Finale vereinfacht Sum. Wir erreichen eine noch bessere Beschleunigung, wenn wir modim ersten Argument von Value (siehe Kommentare) eine Berechnung durchführen , und wenn wir die gesamte #Berechnung auf einer niedrigeren Ebene durchführen , erhalten wir eine unglaubliche Beschleunigung. Aber wir versuchen immer noch, eine legitime Antwort auf ein Golfproblem zu sein.

Damit haben wir unser lund dund können daraus die Anzahl der perfekten Kennzeichen mit Muster berechnen LDDLLDL. Das ist die gleiche Zahl wie für das Muster LDLLDDL. Generell können wir die Reihenfolge der Ziffernreihen unterschiedlicher Länge nach Belieben ändern, NrArrangementswas die Anzahl der Möglichkeiten ergibt. Und während zwischen den Ziffernfolgen ein Buchstabe stehen muss, sind die anderen Buchstaben nicht festgelegt. Das Binomialzählt diese Möglichkeiten.

Jetzt müssen noch alle möglichen Arten von Lauflängen-Ziffern durchlaufen werden. rLäuft durch alle Anzahlen von Läufen, cdurch alle Gesamtzahlen von Ziffern und pdurch alle Partitionen von cmit rSummanden.

Die Gesamtzahl der Partitionen, die wir betrachten, ist zwei weniger als die Anzahl der Partitionen n+1, und die Partitionsfunktionen wachsen wie folgt exp(sqrt(n)). Während es also immer noch einfache Möglichkeiten gibt, die Laufzeit zu verbessern, indem die Ergebnisse wiederverwendet werden (indem die Partitionen in einer anderen Reihenfolge durchlaufen werden), müssen wir für eine grundlegende Verbesserung vermeiden, jede Partition einzeln zu betrachten.

Schnell rechnen

Beachten Sie das (p+q)@r = p@r + q@r. Dies allein hilft nur, einige Multiplikationen zu vermeiden. Zusammen (p+q)#r = p#r + q#rbedeutet dies jedoch, dass wir durch einfache Addition Polynome kombinieren können, die verschiedenen Partitionen entsprechen. Wir können nicht einfach addieren sie alle, weil wir nach wie vor , mit denen müssen wissen , lwir haben @Mähdreschernahrung, welcher Faktor wir verwenden müssen, und welche #-extensions sind noch möglich.

Lassen Sie uns alle Polynome, die Partitionen entsprechen, mit derselben Summe und Länge kombinieren und bereits die verschiedenen Arten der Verteilung der Längen von Ziffernfolgen berücksichtigen. Anders als ich in den Kommentaren spekuliert habe, muss ich mich nicht um den kleinsten verwendeten Wert oder wie oft er verwendet wird kümmern, wenn ich sicher gehe, dass ich nicht mit diesem Wert verlängere.

Hier ist mein C ++ Code:

#include<vector>
#include<algorithm>
#include<iostream>
#include<gmpxx.h>

using bignum = mpz_class;
using poly = std::vector<bignum>;

poly mult(const poly &a, const poly &b){
  poly res ( a.size()+b.size()-1 );
  for(int i=0; i<a.size(); ++i)
    for(int j=0; j<b.size(); ++j)
      res[i+j]+=a[i]*b[j];
  return res;
}

poly extend(const poly &d, const poly &e, int ml, poly &a, int l, int m){
  poly res ( 26*ml+1 );
  for(int i=1; i<std::min<int>(1+26*ml,e.size()); ++i)
    for(int j=1; j<std::min<int>(1+26*ml/i,d.size()); ++j)
      res[i*j] += e[i]*d[j];
  for(int i=1; i<res.size(); ++i)
    res[i]=res[i]*l/m;
  if(a.empty())
    a = poly { res };
  else
    for(int i=1; i<a.size(); ++i)
      a[i]+=res[i];
  return res;
}

bignum f(int n){
  std::vector<poly> dp;
  poly digits (10,1);
  poly dd { 1 };
  dp.push_back( dd );
  for(int i=1; i<n; ++i){
    dd=mult(dd,digits);
    int l=1+26*(n-i);
    if(dd.size()>l)
      dd.resize(l);
    dp.push_back(dd);
  }

  std::vector<std::vector<poly>> a;
  a.reserve(n);

  a.push_back( std::vector<poly> { poly { 0, 1 } } );
  for(int i=1; i<n; ++i)
    a.push_back( std::vector<poly> (1+std::min(i,n+i-i)));
  for(int m=n-1; m>0; --m){
    //    std::cout << "m=" << m << "\n";
    for(int sum=n-m; sum>=0; --sum)
      for(int len=0; len<=std::min(sum,n+1-sum); ++len){
        poly d {a[sum][len]} ;
        if(!d.empty())
          for(int sumn=sum+m, lenn=len+1, e=1;
              sumn+lenn-1<=n;
              sumn+=m, ++lenn, ++e)
            d=extend(d,dp[m],n-sumn,a[sumn][lenn],lenn,e);
      }
  }
  poly let (27,1);
  let[0]=0;
  poly lp { 1 };
  bignum t { 0 };
  for(int sum=n-1; sum>0; --sum){
    lp=mult(lp,let);
    for(int len=1; len<=std::min(sum,n+1-sum); ++len){
      poly &a0 = a[sum][len];
      bignum s {0};
      for(int i=1; i<std::min(a0.size(),lp.size()); ++i)
        s+=a0[i]*lp[i];
      bignum bin;
      mpz_bin_uiui( bin.get_mpz_t(), n-sum+1, len );
      t+=bin*s;
    }
  }
  return t;
}

int main(){
  int n;
  std::cin >> n;
  std::cout << f(n) << "\n" ;
}

Dies verwendet die GNU MP-Bibliothek. Unter Debian installieren libgmp-dev. Kompilieren mit g++ -std=c++11 -O3 -o pl pl.cpp -lgmp -lgmpxx. Das Programm bezieht sein Argument aus stdin. Verwenden Sie für das Timing echo 100 | time ./pl.

Am Ende a[sum][length][i]wird die Anzahl der Möglichkeiten angegeben, auf die sum Ziffern in lengthLäufen die Anzahl angeben können i. Während der Berechnung am Anfang der mSchleife wird die Anzahl der Möglichkeiten angegeben, die mit Zahlen größer als ausgeführt werden können m. Alles beginnt mit a[0][0][1]=1. Beachten Sie, dass dies eine Obermenge der Zahlen ist, die wir benötigen, um die Funktion für kleinere Werte zu berechnen. So konnten wir fast gleichzeitig alle Werte bis zu berechnen n.

Es gibt keine Rekursion, daher haben wir eine feste Anzahl von verschachtelten Schleifen. (Die tiefste Verschachtelungsebene ist 6.) Jede Schleife durchläuft eine Reihe von Werten, die nim ungünstigsten Fall linear sind . Wir brauchen also nur Polynomzeit. Wenn wir uns das verschachtelte Element genauer ansehen iund es jeinschleifen extend, finden wir eine Obergrenze für jdas Formular N/i. Das sollte nur einen logarithmischen Faktor für die jSchleife ergeben. Die innerste Schleife f (mit sumnetc) ist ähnlich. Denken Sie auch daran, dass wir mit schnell wachsenden Zahlen rechnen.

Beachten Sie auch, dass wir O(n^3)diese Nummern speichern .

Experimentell erhalte ich diese Ergebnisse auf vernünftiger Hardware (i5-4590S): Benötigt f(50)eine Sekunde und 23 MB, f(100)benötigt 21 Sekunden und 166 MB, f(200)benötigt 10 Minuten und 1,5 GB und f(300)benötigt eine Stunde und 5,6 GB. Dies deutet auf eine Zeitkomplexität hin, die besser ist als O(n^5).

Pyth, 55 Bytes

FNQI<xrG1N0=+ZsN).?=+YZ=Z0;qu*G?HH1Y1sm?<xrG1d00hxrG1dQ