Рассмотрим три группы A, Bи Cкаждая из которых содержит nцелые числа. Из этого мы можем сделать множество

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

Учитывая n, есть один или несколько минимальных размеров, S_nкоторые зависят от того, какие наборы A,B and Cбыли выбраны.

Наборы могут содержать любые nразличные целые числа (положительные, нулевые или отрицательные). Нет необходимости, чтобы они были последовательными целыми числами или наборы были равны друг другу, например. A = {-1, 0, 5, 10, 27}, B = {2, 5, 6, 10, 14} and C = {-23, 2, 100, 1000,10000}приемлемо (хотя и не очень хорошая идея), например.

задача

Задача состоит в том, чтобы написать код, чтобы найти наименьшее множество, которое S_nон может для каждого nиз 1от 20.

Для каждого nиз 1к 20вашему коду должен выводиться выбранный A, Bа Cвместе с результирующим размеромS_n

Гол

Ваша оценка будет суммой размеров, которые S_nвы создаете. То есть это будет сумма из двадцати чисел.

Чем ниже оценка, тем лучше.

Примеры

Если A = B = C = {1, 2, 3, 4}то, S_4 = {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}который имеет размер19 .

Это, однако, никоим образом не является оптимальным. Например, A = B = C = {-1, 0, 1, 2}дает, S_4 = {0, 1, 2, 3, 4, 5, 6, -1, -3, -2}который имеет размер10 .

Задержки

Поскольку для проверки вывода мне потребуется запустить ваш код, убедитесь, что для его запуска на обычном рабочем столе требуется не более 30 минут и 4 ГБ ОЗУ.

Примечания

Ваш код должен на самом деле вычислить вывод. Вы не можете жестко закодировать предварительно вычисленные ответы в ваш код.

Руст, оценка 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 <andersk@mit.edu>"]

[dependencies]
rust-gmp = "0.5.0"

Скомпилируйте и запустите cargo run --release.

Выход

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

На моем ноутбуке это заняло около 8 минут и около 1,5 ГБ памяти.

Как это устроено

Мы предполагаем (без какого-либо конкретного обоснования), что A и B являются очевидным диапазоном последовательных целых чисел с центром в 0 или ½, затем выполняем поиск A * для оптимального C с учетом A и B .

Аксиома, оценка 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

Наборы будут A = B = [- n / 2..n / 2], если n% 2 == 0, иначе A = B = [- n / 2 .. ((n / 2) +1)]

Множество C представляет собой сумму массива в виде [-2, -1, .. (n-2)] к одному массиву arr [] такого типа [0,0,0,0,0] или [0,1 , 1,1,2] или [0,0,0,0,3], чтобы массив имел свойство

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

Если вы хотите быть более точным или ваш компьютер работает быстрее, вы можете попытаться увеличить «3» на «inc (aix, 3)», что увеличит количество массивов для вариации набора C и, таким образом, увеличит точность результата.

В результате строка выводится

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

где B = A и | S | это номер элемента 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),());

Решение можно проверить здесь .

Извините за вывод в табличной форме.

С, оценка 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;}

Это был бы тот же самый +/- алгоритм реализации Аксиомы

Результаты

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 , оценка 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))

Попробуйте онлайн!

Простая базовая линия каждого набора - это интервал длины n с центром в 0, слегка несбалансированный для четного n. TIO имеет код Python для вычисления вашего счета.

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

Размер (n*n+1)/2для нечетного n и (n*n+n)/2для четного n.

Mathematica, оценка 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 = 1 A = B = C = {0}
Размер S_n = 3 A = B = C = {0,1}
Размер S_n = 5 A = B = C = {- 1,0,1}
Размер S_n = 10 A = B = C = {- 1,0,1,2}
Размер S_n = 13 A = B = C = {- 2, -1,0,1,2}
Размер S_n = 21 A = B = C = { -2, -1,0,1,2,3}
размер S_n = 25 A = B = C = {- 3, -2, -1,0,1,2,3}
размер S_n = 36 A = B = C = {- 3, -2, -1,0,1,2,3,4}
Размер S_n = 41 A = B = C = {- 4, -3, -2, -1,0,1,2 , 3,4}
Размер S_n = 55 A = B = C = {- 4, -3, -2, -1,0,1,2,3,4,5}
Размер S_n = 61 A = B = C = {-5, -4, -3, -2, -1,0,1,2,3,4,5}
Размер S_n = 78 A = B = C = {- 5, -4, -3, -2 , -1,0,1,2,3,4,5,6}
Размер S_n = 85 A = B = C = {- 6, -5, -4, -3, -2, -1,0,1 , 2,3,4,5,6}
S_n размер = 105 A = B = C = {- 6, -5, -4, -3, -2, -1,0,1,2,3,4, 5,6,7}
S_n size = 113 A = B = C = {- 7, -6, -5, -4, -3, -2, -1,0,1,2,3,4,5, 6,7}
Размер S_n = 136 A = B = C = {- 7, -6, -5, -4, -3, -2, -1,0,1,2,3,4,5,6,7,8}
Размер 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 size = 171 A = B = C = {- 8, -7, -6, -5, -4, -3, -2, -1,0,1,2,3,4,5, 6,7,8,9}
Размер S_n = 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 = 210 A = B = C = {- 9, -8, -7, -6, -5, -4, -3, -2 , -1,0,1,2,3,4,5,6,7,8,9,10}
SCORE = 1495

С ++, оценка 1411

Гипотеза A и B являются последовательными целыми числами с центром около 0, просто используйте имитированный отжиг, чтобы найти C.

Источник:

#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;
}

Результаты:

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

Если на моем компьютере установлена ​​опция -O2, то для вычисления всех результатов потребуется 50 секунд.