Rozważmy trzy zestawy A, Ba Ckażda zawiera nliczby całkowite. Z tego możemy zrobić zestaw

S_n = {a * b + c | a in A, b in B, c in C}.

Biorąc pod uwagę n, istnieje jeden lub więcej minimalnych rozmiarów, S_nktóre zależą od tego, które zestawy A,B and Czostały wybrane.

Zestawy mogą zawierać dowolne nodrębne liczby całkowite (dodatnie, zerowe lub ujemne). Nie ma potrzeby, aby były to kolejne liczby całkowite lub żeby zestawy były sobie równe, na przykład. A = {-1, 0, 5, 10, 27}, B = {2, 5, 6, 10, 14} and C = {-23, 2, 100, 1000,10000}jest na przykład do przyjęcia (choć nie jest to dobry pomysł).

Zadanie

Zadaniem jest napisanie kodu w celu znalezienia najmniejszego zestawu, S_njaki może dla każdego nod 1do 20.

Dla każdego nz 1do 20kodu powinna wyjście wybrana A, Ba Cwraz z wynikającym z wielkościS_n

Wynik

Twój wynik będzie sumą rozmiarów stworzonych przez S_nCiebie. To będzie suma dwudziestu liczb.

Im niższy wynik, tym lepiej.

Przykłady

Jeśli A = B = C = {1, 2, 3, 4}to, S_4 = {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}które jest wielkości 19.

Nie jest to jednak w żaden sposób optymalne. Na przykład A = B = C = {-1, 0, 1, 2}daje, S_4 = {0, 1, 2, 3, 4, 5, 6, -1, -3, -2}który ma rozmiar 10.

Czasy

Ponieważ będę musiał uruchomić kod, aby zweryfikować dane wyjściowe, upewnij się, że nie zajmuje to więcej niż 30 minut i 4 GB pamięci RAM, aby uruchomić się na normalnym pulpicie.

Notatki

Twój kod musi faktycznie obliczyć dane wyjściowe. Nie możesz zakodować w swoim kodzie wstępnie obliczonych odpowiedzi.

Rdza, wynik 1412 1411

src/main.rs

extern crate gmp;

use std::collections::BinaryHeap;
use std::collections::hash_map::{HashMap, Entry};
use gmp::mpz::Mpz;

fn visit(
    queue: &mut BinaryHeap<(i32, i32, i32, Mpz, Mpz)>,
    visited: &mut HashMap<(i32, Mpz), i32>,
    score: i32,
    h: i32,
    k: i32,
    d: Mpz,
    c: Mpz,
) {
    match visited.entry((k, d.clone())) {
        Entry::Occupied(mut e) => {
            if *e.get() < score {
                e.insert(score);
                queue.push((score, h, k, d, c));
            }
        }
        Entry::Vacant(e) => {
            e.insert(score);
            queue.push((score, h, k, d, c));
        }
    }
}

fn main() {
    let mut total = 0;
    for n in 1..21 {
        let a_range = n / 2 - n + 1..n / 2 + 1;
        let min_ab = a_range.start * (a_range.end - 1);
        let mut ab = Mpz::zero();
        for a in a_range.clone() {
            for b in a_range.clone() {
                ab.setbit((a * b - min_ab) as usize);
            }
        }

        let heuristic = |k: i32, d: &Mpz| if k == n {
            0
        } else {
            k + 1 - n -
                (0..d.bit_length())
                    .map(|i| (&ab & !(d >> i)).popcount())
                    .min()
                    .unwrap() as i32
        };

        let mut queue = BinaryHeap::new();
        let mut visited = HashMap::new();

        let (k1, d1) = (0, Mpz::zero());
        let h1 = heuristic(k1, &d1);
        visit(&mut queue, &mut visited, h1, h1, k1, d1, Mpz::zero());
        while let Some((score, h, k, d, c)) = queue.pop() {
            if k == n {
                println!("n={} |S|={}", n, -score);
                println!("  A={:?}", a_range.clone().collect::<Vec<_>>());
                println!("  B={:?}", a_range.clone().collect::<Vec<_>>());
                println!(
                    "  C={:?}",
                    (0..c.bit_length())
                        .filter(|&i| c.tstbit(c.bit_length() - 1 - i))
                        .collect::<Vec<_>>()
                );
                total += -score;
                break;
            }

            let kd = (k, d);
            if score < visited[&kd] {
                continue;
            }
            let (k, d) = kd;

            let (k1, d1) = (k, &d >> 1);
            let h1 = heuristic(k1, &d1);
            visit(
                &mut queue,
                &mut visited,
                score - h + h1,
                h1,
                k1,
                d1,
                &c << 1,
            );

            let (k1, d1) = (k + 1, (&d | &ab) >> 1);
            let h1 = heuristic(k1, &d1);
            visit(
                &mut queue,
                &mut visited,
                score - h - (&ab & !&d).popcount() as i32 + h1,
                h1,
                k1,
                d1,
                &c << 1 | Mpz::one(),
            );
        }
    }

    println!("total={}", total);
}

Cargo.toml

[package]
name = "small"
version = "0.1.0"
authors = ["Anders Kaseorg <[email protected]>"]

[dependencies]
rust-gmp = "0.5.0"

Skompiluj i uruchom z cargo run --release.

Wynik

n=1 |S|=1
  A=[0]
  B=[0]
  C=[0]
n=2 |S|=3
  A=[0, 1]
  B=[0, 1]
  C=[0, 1]
n=3 |S|=5
  A=[-1, 0, 1]
  B=[-1, 0, 1]
  C=[0, 1, 2]
n=4 |S|=10
  A=[-1, 0, 1, 2]
  B=[-1, 0, 1, 2]
  C=[0, 1, 2, 3]
n=5 |S|=13
  A=[-2, -1, 0, 1, 2]
  B=[-2, -1, 0, 1, 2]
  C=[0, 1, 2, 3, 4]
n=6 |S|=21
  A=[-2, -1, 0, 1, 2, 3]
  B=[-2, -1, 0, 1, 2, 3]
  C=[0, 2, 3, 4, 5, 6]
n=7 |S|=25
  A=[-3, -2, -1, 0, 1, 2, 3]
  B=[-3, -2, -1, 0, 1, 2, 3]
  C=[0, 2, 3, 5, 6, 7, 8]
n=8 |S|=35
  A=[-3, -2, -1, 0, 1, 2, 3, 4]
  B=[-3, -2, -1, 0, 1, 2, 3, 4]
  C=[0, 3, 4, 6, 7, 8, 10, 11]
n=9 |S|=39
  A=[-4, -3, -2, -1, 0, 1, 2, 3, 4]
  B=[-4, -3, -2, -1, 0, 1, 2, 3, 4]
  C=[0, 3, 4, 6, 7, 8, 10, 11, 14]
n=10 |S|=53
  A=[-4, -3, -2, -1, 0, 1, 2, 3, 4, 5]
  B=[-4, -3, -2, -1, 0, 1, 2, 3, 4, 5]
  C=[0, 1, 4, 5, 6, 9, 10, 11, 14, 15]
n=11 |S|=58
  A=[-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5]
  B=[-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5]
  C=[0, 1, 4, 5, 6, 9, 10, 11, 14, 15, 19]
n=12 |S|=74
  A=[-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6]
  B=[-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6]
  C=[0, 4, 5, 6, 9, 10, 11, 12, 15, 16, 17, 21]
n=13 |S|=80
  A=[-6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6]
  B=[-6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6]
  C=[0, 4, 5, 6, 9, 10, 11, 12, 15, 16, 17, 21, 22]
n=14 |S|=100
  A=[-6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7]
  B=[-6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7]
  C=[0, 1, 6, 7, 8, 12, 13, 14, 15, 19, 20, 21, 26, 27]
n=15 |S|=106
  A=[-7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7]
  B=[-7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7]
  C=[0, 5, 6, 7, 11, 12, 13, 14, 18, 19, 20, 21, 25, 26, 27]
n=16 |S|=128
  A=[-7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8]
  B=[-7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8]
  C=[0, 6, 7, 8, 13, 14, 15, 16, 20, 21, 22, 23, 28, 29, 30, 36]
n=17 |S|=135
  A=[-8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8]
  B=[-8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8]
  C=[0, 6, 7, 8, 13, 14, 15, 16, 20, 21, 22, 23, 28, 29, 30, 36, 44]
n=18 |S|=161
  A=[-8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  B=[-8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  C=[0, 7, 8, 9, 15, 16, 17, 18, 23, 24, 25, 26, 27, 32, 33, 34, 35, 41]
n=19 |S|=167
  A=[-9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  B=[-9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  C=[0, 7, 8, 9, 15, 16, 17, 18, 23, 24, 25, 26, 27, 32, 33, 34, 35, 41, 42]
n=20 |S|=197
  A=[-9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
  B=[-9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
  C=[0, 1, 8, 9, 10, 11, 17, 18, 19, 20, 21, 26, 27, 28, 29, 30, 36, 37, 38, 46]
total=1411

Na moim laptopie zajęło to około 8 minut i około 1,5 GiB pamięci.

Jak to działa

Zakładamy (bez szczególnego powodu), które i B są oczywiste szereg kolejnych liczb wyśrodkowany 0 lub pół, a następnie wykonać A * do optymalnego C danego i B .

Aksjomat, wynik 1466

)time on

g(a:List INT,b:List INT,c:List INT):List INT==
   s:List INT:=[]
   for i in 1..#a repeat
     for j in 1..#b repeat
       for h in 1..#c repeat
            s:=cons(a.i*b.j+c.h, s)
   removeDuplicates(s)

inc(a:List INT, b:INT):List INT==
    #a=0=>a
    i:=1; len:=#a
    repeat
       if i>len then
             for j in 1..len repeat a.j:=0
             return a
       if i<len then 
         if a.i<a.(i+1) then
               if a.i<b then  
                          a.i:=a.i+1
                          for j in 1..(i-1) repeat a.j:=0
                          break
               for j in 1..i repeat a.j:=0 
       else 
         if a.i<b then 
                   a.i:=a.i+1
                   for j in 1..(len-1) repeat a.j:=0
                   break
       i:=i+1
    a

f(n:PI):List List INT==
   a:List INT:=[0];  b:List INT:=[0];   c :List INT:=[0]
   aix:List INT:=[]; cmin:List INT:=[]; cp:List INT:=[ ]
   s:List INT :=[ ];   c1:List INT:=[0]; smin:INT
   -- costruisce gli insiemi a,b
   i:=1
   for j in 1..n-1 repeat 
      if member?(i,a) then (a:=cons(-i,a);b:=cons(-i,b);i:=i+1)
      else                 (a:=cons( i,a);b:=cons( i,b))
   if n=1 then return [a,b,c,[0],[1]]
   a:=sort(a)
   c :=copy(a); cmin:=copy(a); cp:=copy(a)
   for i in 1..n repeat c.i:=i-3
   for i in 1..n repeat aix:=cons(0, aix)
   -- ottimizzati per i vari casi... si parte da particolari insiemi c
   -- da cui fare le variazioni
   if n>=8         then c.n:=c.n+2  
   if n=10 or n=13 then c.(n-1):=c.(n-1)+2
   if n=9  or n=16 or n=19 then (c.(n-2):=c.(n-2)+1; c.(n-1):=c.(n-1)+1; c.n:=c.n+1)
   smin:=n*n+10  
   repeat
       for i in 1..n repeat cp.i:=c.i+aix.i
       k:=# g(a,b,cp)
       if k<smin then 
                smin:=k; 
                for i in 1..n repeat cmin.i:=cp.i 
                --output ["assign",c,aix,cmin, k]
       inc(aix, 3)
       --output aix
       i:=0;repeat(i:=i+1;if i>n or aix.i~=0 then break)
       if i>n then break
   [sort(a),sort(b),sort(cmin),g(a,b,cmin),[smin]]


h(n:PI):NNI==
    k:=0
    r:List List INT:=[]
    for i in 1..n repeat
         r:=f(i)
         output [i,r.5.1,r.1,r.3]
         k:=k+r.5.1
    k

Zbiory byłyby A = B = [- n / 2..n / 2], jeśli n% 2 == 0 w innym przypadku A = B = [- n / 2 .. ((n / 2) +1)]

Zbiór C jest sumą tablicy jako [-2, -1, .. (n-2)] do jednej tablicy arr [] tego rodzaju [0,0,0,0,0] lub [0,1 , 1,1,2] lub [0,0,0,0,3], aby tablica miała właściwość

 arr[i] <= arr[i+1] for i in 1..n-1

Jeśli chcesz być bardziej precyzyjny lub komputer działa szybciej, możesz spróbować zwiększyć „3” w „inc (aix, 3)”, które zwiększą liczbę tablic dla wariantu zestawu C, a więc zwiększy to dokładność wyniku.

W wynikach drukowany jest łańcuch

 [n, |{a*b+c for a in A for b in B for c in C}|,A,C]

gdzie B = A i | S | to liczba elementów S

(6) -> h 20
   [1,1,[0],[0]]
   [2,3,[0,1],[- 2,- 1]]
   [3,5,[- 1,0,1],[- 2,- 1,0]]
   [4,10,[- 1,0,1,2],[- 2,- 1,0,1]]
   [5,13,[- 2,- 1,0,1,2],[- 2,- 1,0,1,2]]
   [6,21,[- 2,- 1,0,1,2,3],[- 2,- 1,0,1,2,3]]
   [7,25,[- 3,- 2,- 1,0,1,2,3],[- 2,- 1,0,1,2,3,4]]
   [8,35,[- 3,- 2,- 1,0,1,2,3,4],[- 2,- 1,1,2,3,5,6,9]]
   [9,39,[- 4,- 3,- 2,- 1,0,1,2,3,4],[- 2,1,2,4,5,6,8,9,12]]
   [10,53,[- 4,- 3,- 2,- 1,0,1,2,3,4,5],[- 2,- 1,2,3,4,6,7,8,11,12]]
   [11,59,[- 5,- 4,- 3,- 2,- 1,0,1,2,3,4,5],[- 2,- 1,0,2,3,4,5,7,8,9,12]]
   [12,76,[- 5,- 4,- 3,- 2,- 1,0,1,2,3,4,5,6],[- 2,- 1,0,3,4,5,6,8,9,10,11,14]]
   [13, 82, [- 6,- 5,- 4,- 3,- 2,- 1,0,1,2,3,4,5,6],[- 2,- 1,0,3,4,5,6,8,9,10,11,14,15]]
   [14, 103, [- 6,- 5,- 4,- 3,- 2,- 1,0,1,2,3,4,5,6,7],[- 2,- 1,0,3,4,5,6,7,9,10,11,12,13,16]]
   [15, 110, [- 7,- 6,- 5,- 4,- 3,- 2,- 1,0,1,2,3,4,5,6,7],[- 2,- 1,0,1,4,5,6,7,8,10,11,12,13,14,17]]
   [16, 134, [- 7,- 6,- 5,- 4,- 3,- 2,- 1,0,1,2,3,4,5,6,7,8],[- 2,- 1,0,1,4,5,6,7,8,9,11,12,13,15,16,19]]
   [17, 142, [- 8,- 7,- 6,- 5,- 4,- 3,- 2,- 1,0,1,2,3,4,5,6,7,8],[- 2,- 1,0,1,4,5,6,7,8,9,11,12,13,14,15,16,19]]
   [18, 169, [- 8,- 7,- 6,- 5,- 4,- 3,- 2,- 1,0,1,2,3,4,5,6,7,8,9],[- 2,- 1,0,1,2,3,4,6,7,8,9,10,11,12,15,16,17,20]]
   [19, 178, [- 9,- 8,- 7,- 6,- 5,- 4,- 3,- 2,- 1,0,1,2,3,4,5,6,7,8,9],[- 2,- 1,0,1,2,5,6,7,8,9,10,11,13,14,15,16,18,19,22]]
   [20, 208, [- 9,- 8,- 7,- 6,- 5,- 4,- 3,- 2,- 1,0,1,2,3,4,5,6,7,8,9,10],[- 2,- 1,0,1,2,3,4,5,7,8,9,10,11,12,13,14,17,18,19,22]]

   (6)  1466
                                                    Type: PositiveInteger
      Time: 0.03 (IN) + 910.75 (EV) + 0.02 (OT) + 24.00 (GC) = 934.80 sec

SQL Server, 1495

declare @N int=20;
--set @N=40;
with
  n as(select 1 n union all select n+1 from n where n<@N),
  s as(select n,n/2-n+1 m from n union all select n,m+1 from s where m<n/2),
  t as(select n,m,row_number()over(partition by n order by m) p from s),
  a as(select n,m a,p from t),
  b as(select n,m b,p from t),
  c as(select n,m c,p from t),
  u as(
    select a.n,count(distinct a*b+c) q
    from a,b,c
    where b.n=a.n and c.n=a.n
    group by a.n
  )
select u.n,a,b,c,q,sum(distinct q) N
from u,a,b,c
where a.n=u.n and b.n=u.n and c.n=u.n and b.p=a.p and c.p=a.p
group by grouping sets((u.n,a,b,c,q),());

Rozwiązanie można zweryfikować tutaj .

Przepraszam, ponieważ dane wyjściowe mają formę tabelaryczną.

C, wynik 1448 1431

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define P printf
#define R return
#define F for

int cmp(const void*a,const void*b)
{int aa, bb;
 aa=*(int*)a; bb=*(int*)b;
 R aa>bb?1:(aa<bb?-1:0);
}

void show(int* a,unsigned n){unsigned i;P("[ ");F(i=0;i<n;++i) P("%d ", a[i]);P("]");}

// l'insieme "a" deve essere del tipo {0,1} {-1,0,1} {-1,0,1,2} {-2,-1,0,1,2} ecc di numero elementi n
// l'insieme "c" e' un insieme di numero elementi n
// l'insieme a cui "r" punta sarà *r={x*y+z : x in a, y in a, z in c }
// ritorna -1 per errore altrimenti il numero di elementi
// di {x*y+z : x in a, y in a, z in c }

int g(int**r,int*a,int*c,unsigned n)
{static int *arrs,*res;
 static unsigned  alen;
 unsigned i,j,k,m,v,vv,len;

 if(a==0||c==0||n<=0||n>128) R -1;
 len=n*n*n;
 if(alen<n)
    {if(arrs) free(arrs);  // leaks: arrs and res remain until the program end
     if(res ) free(res);
     arrs=0; res=0; alen=0;
     arrs=malloc(sizeof(int)*len);
     if(arrs==0)             R -1;
     res =malloc(sizeof(int)*len);
     if(res==0)
         {free(arrs); arrs=0;R -1;}
     alen=n;
    }
 v=0;
 F(k=0;k<n;++k) arrs[v++]=c[k]; // il caso 0 

 F(m=0;m<n&&a[m]<0;++m);// da una parte i positivi dall'altra i negativi; m punta a 0 
                        // il caso 0 non e' trattato
 F(i=0;i<m;++i)    // positivi per negativi
   F(j=m+1;j<n;++j)
      F(k=0;k<n;++k)
         if(-a[i]<=a[j]) arrs[v++]=a[i]*a[j]+c[k];
 F(i=m+1;i<n;++i)  // positivi per positivi
   F(j=i;j<n;++j)
      F(k=0;k<n;++k)
          arrs[v++]=a[i]*a[j]+c[k];
 qsort(arrs,v,sizeof(int),cmp);
 res[0]=arrs[0];  // elimina i doppioni
 F(vv=1,i=1; i<v; ++i)
       if(arrs[i-1]!=arrs[i]) res[vv++]=arrs[i];
 *r=res;
 R vv;
}


int inc(int* a,int len,int b)
{int i,j;
 if(len<1||b<1)R 1;
 F(i=0;;)
   {if(i>=len)
         {F(j=0;j<len;++j)a[j]=0;
          R 1;
         }
    if(i==len-1||a[i]<a[i+1])
               {if(a[i]<b)
                   {a[i]+=1;
                    F(j=0;j<i;++j)a[j]=0;
                    break;
                   }
               }
    i+=1;
   }
 R 0;
}

// a,b,c,cmin sono array e devono avere size n
// s          e' un array deve avere size n*n*n
//            come risultato la sua lunghezza e' *slen
//
int f(int* a,int* b,int* cmin,int* s,int* slen, int n)
{int i,j,k, *c, *aix, *cp, smin, *rs;

 if(slen)*slen=0;
 if(n<1||a==0||b==0||cmin==0||s==0||slen==0)R -1;

 // costruisce a e b
 j=-n/2;
 if(n%2==0)++j;
 F(i=0;i<n;++i,++j) s[i]=cmin[i]=a[i]=b[i]=j;
 // {-x..x}  oppure {-x..(x+1)}

 *slen=n;
 if(n==1)R 1; // caso di un solo elemento
 c  =malloc(sizeof(int)*(n+1)); // **
 if(c==0)R -1;
 aix=malloc(sizeof(int)*(n+1)); // **
 if(aix==0){free(c);R -1;}
 cp =malloc(sizeof(int)*(n+1)); // **
 if(cp==0){free(aix);free(c);R -1;}

 F(i=0;i<n;++i){cp[i]=aix[i]=0;c[i]=i;}
 if(n>=16)//16
    {c[n-1]=c[n-1]+3;c[n-2]=c[n-2]+3;c[n-3]=c[n-3]+3;}
 F(smin=n*n+10;;)
    {cp[0]=c[0];
     F(i=1;i<n;++i) cp[i]=c[i]+aix[i-1];
     k=g(&rs,a,cp,n);
     if(k<smin){F(smin=k,i=0;i<n;++i) cmin[i]=cp[i];
                //P("Assign: %d,  ", k);
                //show(aix,n);P(",");
                //P("Cmin=");show(cmin,n);P("\n");
               }
     //show(aix,n);P("\n");
     if(inc(aix,n-1,7))break;
    }
 free(cp);free(aix);free(c);
 k=g(&rs,a,cmin,n);
 if(k==-1)R -1;
 F(i=0;i<k;++i)s[i]=rs[i];
 *slen=k;
 R k;
}

unsigned h(unsigned nmax)
{time_t                             ti, tf;
 double  dft;
 int i,j, *a, *b, *cmin, *s, slen, rlen, r;
 unsigned                            n,len;
 if(nmax>128||nmax<1)R -1;
 len =nmax*nmax*nmax+1;
 s   =malloc(sizeof(int)*len);      // **
 a   =malloc(sizeof(int)*(nmax+1)); // **
 b   =malloc(sizeof(int)*(nmax+1)); // **
 cmin=malloc(sizeof(int)*(nmax+1)); // **
 if(s==0||a==0||b==0||cmin==0){free(s);free(a);free(b);free(cmin);R -1;}
 ti=time(0);
 F(n=1,r=0;n<=nmax;++n)
    {rlen=f(a,b,cmin,s,&slen,n);
     if(rlen!=-1)
         {P("%d %d", n, rlen); show(cmin,n);P("\n");}
     else break;
     r+=rlen;
    }
 tf=time(0);
 dft=difftime(tf, ti);
 P("Result=%d  secondi=%.0f  minuti=%.0f\n", r, dft, dft/60.0);
free(s);free(a);free(b);free(cmin);
 R r;
}

int main(){h(20); R 0;}

Byłby to ten sam +/- algo implementacji Axiom

wyniki

1 1[ 0 ]
2 3[ 0 1 ]
3 5[ 0 1 2 ]
4 10[ 0 1 2 3 ]
5 13[ 0 1 2 3 4 ]
6 21[ 0 1 2 3 4 5 ]
7 25[ 0 1 2 3 4 5 6 ]
8 35[ 0 1 3 4 5 7 8 11 ]
9 39[ 0 3 4 6 7 8 10 11 14 ]
10 53[ 0 1 4 5 6 8 9 10 13 14 ]
11 59[ 0 1 2 4 5 6 7 9 10 11 14 ]
12 75[ 0 1 2 5 6 7 8 11 12 13 17 18 ]
13 81[ 0 1 2 5 6 7 8 11 12 13 14 17 18 ]
14 101[ 0 1 2 3 6 7 8 9 10 13 14 15 16 20 ]
15 107[ 0 1 2 3 6 7 8 9 10 13 14 15 16 20 21 ]
16 130[ 0 1 2 6 7 8 9 10 13 14 15 16 17 21 22 23 ]
17 137[ 0 1 2 3 7 8 9 10 11 15 16 17 18 19 23 24 25 ]
18 163[ 0 1 2 3 7 8 9 10 11 12 16 17 18 19 20 25 26 27 ]
19 171[ 0 1 2 3 4 8 9 10 11 12 13 17 18 19 20 21 26 27 28 ]
20 202[ 0 1 2 3 7 8 9 10 11 12 13 17 18 19 20 21 22 27 28 29 ]
Result=1431  secondi=618  minuti=10

Python 2 , wynik 1495

f=lambda n:range(-n/2+1,n/2+1)
f_A=f_B=f_C=f

def comb_set(A, B, C):
	return sorted({a*b+c for a in A for b in B for c in C})

def S(n):
	return comb_set(f_A(n), f_B(n), f_C(n))

Wypróbuj online!

Prosta linia bazowa polegająca na tym, że każdy zestaw jest przedziałem długości n wyśrodkowanym wokół 0, nieco niezrównoważonym dla parzystego n. TIO ma kod Python do obliczania wyniku.

1   1
2   3
3   5
4   10
5   13
6   21
7   25
8   36
9   41
10  55
11  61
12  78
13  85
14  105
15  113
16  136
17  145
18  171
19  181
20  210

Total: 1495

Rozmiar dotyczy (n*n+1)/2nieparzystego n, a (n*n+n)/2nawet parzystego n.

Mathematica, wynik 1495

z = 0;
For[n = 1, n <= 20, n++,
r = Range[n] - Ceiling[n/2];
Print["S_n size=", x = (s = Length@#;
  Length@
   Union@Flatten@
     Table[#[[i]]*#[[j]] + #[[k]], {i, s}, {j, s}, {k, s}]) &[r], 
"  ", "A=B=C=", r]; z = z + x]
Print["SCORE=", z]

S_n rozmiar = 1 A = B = C = {0}
S_n rozmiar = 3 A = B = C = {0,1}
Rozmiar S_n = 5 A = B = C = {- 1,0,1}
Rozmiar S_n = 10 A = B = C = {- 1,0,1,2}
Rozmiar S_n = 13 A = B = C = {- 2, -1,0,1,2}
Rozmiar S_n = 21 A = B = C = { -2, -1,0,1,2,3}
Rozmiar S_n = 25 A = B = C = {- 3, -2, -1,0,1,2,3}
Rozmiar S_n = 36 A = B = C = {- 3, -2, -1,0,1,2,3,4}
S_n rozmiar = 41 A = B = C = {- 4, -3, -2, -1,0,1,2 , 3,4}
S_n rozmiar = 55 A = B = C = {- 4, -3, -2, -1,0,1,2,3,4,5}
S_n rozmiar = 61 A = B = C = {-5, -4, -3, -2, -1,0,1,2,3,4,5}
Rozmiar S_n = 78 A = B = C = {- 5, -4, -3, -2 , -1,0,1,2,3,3,4,5,6}
S_n rozmiar = 85 A = B = C = {- 6, -5, -4, -3, -2, -1,0,1 , 2,3,4,5,6}
S_n rozmiar = 105 A = B = C = {- 6, -5, -4, -3, -2, -1,0,1,2,3,4, 5,6,7}
S_n rozmiar = 113 A = B = C = {- 7, -6, -5, -4, -3, -2, -1,0,1,2,3,4,5, 6,7}
Rozmiar S_n = 136 A = B = C = {- 7, -6, -5, -4, -3, -2, -1,0,1,2,3,4,5,6,7,8}
Rozmiar S_n = 145 A = B = C = {- 8, -7, -6, -5, -4, -3, -2, -1,0,1,2,3,4,5,6,7 , 8}
S_n rozmiar = 171 A = B = C = {- 8, -7, -6, -5, -4, -3, -2, -1,0,1,2,3,4,5, 6,7,8,9}
S_n rozmiar = 181 A = B = C = {- 9, -8, -7, -6, -5, -4, -3, -2, -1,0,1, 2,3,4,5,6,7,8,9}
S_n rozmiar = 210 A = B = C = {- 9, -8, -7, -6, -5, -4, -3, -2 , -1,0,1,2,3,3,4,5,6,7,8,9,10}
WYNIK = 1495

C ++, wynik 1411

Domysł A i B to kolejne liczby całkowite wyśrodkowane w pobliżu 0, wystarczy użyć symulowanego wyżarzania, aby znaleźć C.

Źródło:

#include <algorithm>
#include <iostream>
#include <random>
#include <bitset>
#include <cmath>

using namespace std;

using bools = bitset<270>;
using irand = uniform_int_distribution<int>;
ranlux48 gen;
uniform_real_distribution<double> frand(0, 1);

int evaluate(const bools& a, const vector<int>& v)
{
    bools t = a;
    for (int i : v) t |= a << i;
    return t.count();
}

vector<int> best;
int best_score, prev_score;

void transition(double Temp, int Q, const bools& a, vector<int>& now)
{
    int rep, pos, tmp;
    do rep = irand(1, Q)(gen); while (find(now.begin(), now.end(), rep) != now.end());
    pos = irand(0, now.size() - 1)(gen);
    tmp = now[pos];
    now[pos] = rep;
    int now_score = evaluate(a, now);
    if (now_score <= prev_score || frand(gen) < exp((double)(prev_score - now_score))) {
        prev_score = now_score;
        if (now_score < best_score) best_score = now_score, best = now;
    }
    else now[pos] = tmp;
}

int main()
{
    int score = 0;
    for (int N = 1; N <= 20; N++) {
        gen.seed(0);
        int first = -N / 2, last = first + N, Q = N * 3;
        bools st;

        for (int i = first; i < last; i++)
            for (int j = first; j < last; j++)
                st[i * j + last * last] = true;

        vector<int> lst;
        for (int i = 1; i < N; i++) lst.push_back(i);

        best = lst;
        prev_score = best_score = evaluate(st, lst);

        if (N != 1)
            for (double Temp = 70.; Temp > 0; Temp -= 3e-5) transition(Temp, Q, st, lst);
        sort(best.begin(), best.end());
        cout << "N = " << N << "; |S| = " << best_score << endl;
        cout << " A = B = {";
        for (int i = first; i < last; i++) cout << i << (i != last - 1 ? ", " : "}\n");
        cout << " S = {0";
        for (int i : best) cout << ", " << i;
        cout << "}\n";

        score += best_score;
    }
    cout << "Score: " << score << endl;
}

Wyniki:

N = 1; |S| = 1
 A = B = {0}
 S = {0}
N = 2; |S| = 3
 A = B = {-1, 0}
 S = {0, 1}
N = 3; |S| = 5
 A = B = {-1, 0, 1}
 S = {0, 1, 2}
N = 4; |S| = 10
 A = B = {-2, -1, 0, 1}
 S = {0, 1, 2, 3}
N = 5; |S| = 13
 A = B = {-2, -1, 0, 1, 2}
 S = {0, 1, 2, 3, 4}
N = 6; |S| = 21
 A = B = {-3, -2, -1, 0, 1, 2}
 S = {0, 1, 2, 3, 4, 5}
N = 7; |S| = 25
 A = B = {-3, -2, -1, 0, 1, 2, 3}
 S = {0, 1, 2, 3, 4, 5, 6}
N = 8; |S| = 35
 A = B = {-4, -3, -2, -1, 0, 1, 2, 3}
 S = {0, 3, 4, 6, 7, 10, 11, 14}
N = 9; |S| = 39
 A = B = {-4, -3, -2, -1, 0, 1, 2, 3, 4}
 S = {0, 3, 4, 6, 7, 8, 10, 11, 14}
N = 10; |S| = 53
 A = B = {-5, -4, -3, -2, -1, 0, 1, 2, 3, 4}
 S = {0, 1, 4, 5, 6, 9, 10, 11, 14, 15}
N = 11; |S| = 58
 A = B = {-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5}
 S = {0, 1, 4, 5, 6, 9, 10, 11, 14, 15, 19}
N = 12; |S| = 74
 A = B = {-6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5}
 S = {0, 4, 5, 6, 9, 10, 11, 12, 15, 16, 17, 21}
N = 13; |S| = 80
 A = B = {-6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6}
 S = {0, 6, 10, 11, 12, 15, 16, 17, 18, 21, 22, 23, 27}
N = 14; |S| = 100
 A = B = {-7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6}
 S = {0, 5, 6, 7, 11, 12, 13, 14, 18, 19, 20, 21, 25, 26}
N = 15; |S| = 106
 A = B = {-7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7}
 S = {0, 5, 6, 7, 11, 12, 13, 14, 18, 19, 20, 21, 25, 26, 32}
N = 16; |S| = 128
 A = B = {-8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7}
 S = {0, 6, 7, 8, 13, 14, 15, 16, 21, 22, 23, 24, 29, 30, 31, 37}
N = 17; |S| = 135
 A = B = {-8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8}
 S = {0, 6, 7, 8, 13, 14, 15, 16, 21, 22, 23, 24, 29, 30, 31, 37, 45}
N = 18; |S| = 161
 A = B = {-9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8}
 S = {0, 7, 8, 9, 14, 15, 16, 17, 18, 22, 23, 24, 25, 26, 31, 32, 33, 40}
N = 19; |S| = 167
 A = B = {-9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
 S = {0, 7, 8, 9, 15, 16, 17, 18, 23, 24, 25, 26, 27, 32, 33, 34, 35, 41, 42}
N = 20; |S| = 197
 A = B = {-10, -9, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
 S = {0, 8, 9, 10, 16, 17, 18, 19, 20, 25, 26, 27, 28, 29, 35, 36, 37, 38, 45, 46}
Score: 1411

Z opcją -O2 na moim komputerze, obliczenie wszystkich wyników zajmuje 50 sekund.