W przypadku innego wyzwania, które piszę, muszę sprawdzić, czy przypadki testowe można rozwiązać za pomocą ograniczonych liczb całkowitych. W szczególności muszę zweryfikować następujące elementy w przypadku niepustej tablicy liczb całkowitych Ai szerokości bitów liczb całkowitych n:

Wszystkie liczby całkowite aw Azaspokojenia -2**(n-1) <= a < 2**(n-1)(zakodowania z nbitowych liczb całkowitych w dwóch dopełniacza).
Długość Ajest mniejsza niż 2**n.
Suma Asatysfakcji -2**(n-1) <= sum(A) < 2**(n-1).
Wszystkie kombinacje elementów Aspełniają wszystkie powyższe warunki.

Oczywiście zdecydowałem się zlecić ten problem na zewnątrz!

Biorąc pod uwagę tablicę liczb całkowitych Ai dodatnią szerokość bitów całkowitych n, sprawdź, czy Aspełnia powyższe warunki.

Przypadki testowe

[0, 0, 0], 2: True
[0, 0, 0, 0], 2: False (violates #2)
[1, 2, 3, 4, 5], 8: True
[1, 2, 3, 4, 5], 2: False (violates all conditions)
[1, 2, 3, 4, 5], 5: True
[-3, 4, 1], 4: True
[10, 0, -10], 4: False (violates #1 and #4)
[27, -59, 20, 6, 10, 53, -21, 16], 8: False (violates #4)
[-34, 56, 41, -4, -14, -54, 30, 38], 16: True
[-38, -1, -11, 127, -35, -47, 28, 89, -8, -12, 77, 55, 75, 75, -80, -22], 7: False (violates #4)
[-123, -85, 6, 121, -5, 12, 52, 31, 64, 0, 6, 101, 128, -72, -123, 12], 12: True

Implementacja referencji (Python 3)

#!/usr/bin/env python3
from itertools import combinations
from ast import literal_eval


def check_sum(L, n):
  return -2**(n-1) <= sum(L) < 2**(n-1)


def check_len(L, n):
  return len(L) < 2**n


def check_elems(L, n):
  return all(-2**(n-1) <= a < 2**(n-1) for a in L)


A = literal_eval(input())
n = int(input())
OUTPUT_STR = "{}, {}: {}".format(A, n, "{}")

if not (check_elems(A, n) and check_len(A, n) and check_sum(A, n)):
  print(OUTPUT_STR.format(False))
  exit()

for k in range(1, len(A)):
  for b in combinations(A, k):
    if not check_sum(b, n):
      print(OUTPUT_STR.format(False))
      exit()

print(OUTPUT_STR.format(True))

Wypróbuj online!

— Mego
źródło

Piaskownica

— Mego

Czy musimy obsłużyć pustą listę?

— Pan Xcoder,

@ Mr.Xcoder Nie, wyjaśnię.

— Mego

7

Wolfram Language (Mathematica) , 40 bajtów

Max[x=2Tr/@Subsets@#,-x-1,Tr[1^#]]<2^#2&

Wypróbuj online!

Warunek 1 jest implikowany przez sprawdzenie warunku 3 dla wszystkich podzbiorów, w tym dla jednego elementu. Więc bierzemy maksimum

dwukrotność sumy każdego podzbioru,
jeden mniej niż dwukrotność ujemna sumy każdego podzbioru, oraz
długość całego zestawu

i sprawdź, czy to mniej niż 2^#2(gdzie #2jest wejście o szerokości bitu).

Kosztem zaledwie 6 więcej bajtów, możemy wymienić Subsets@#się GatherBy[#,Arg], co jest o wiele bardziej wydajny, ponieważ oblicza tylko dwóch najgorszych scenariuszy podzbiory: podzbiór wszystkich wartości nieujemnych, a podzbiór wszystkich wartości ujemnych. (Działa to, ponieważ Argma wartość 0pierwszego i πdrugiego).

— Misza Ławrow
źródło

3

Galaretka , 19 bajtów

ŒPS€;⁸L¤ḟ⁹’2*$ŒRṖ¤Ṇ

Wypróbuj online!

Wystarczy sprawdzić, czy mapped sum of powerset + length of setjest w wymaganym zakresie.

— Leaky Nun
źródło

1

Myślę, że (choć nie jestem pewien) można użyć ÆẸzamiast 2*$(niesprawdzonego)

— Pan Xcoder,

@ Mr.Xcoder To działa.

— user202729,

3

05AB1E , 13 12 11 bajtów

Zaoszczędzono 1 bajt dzięki Mr. Xcoder

æO·D±¹gMIo‹

Wypróbuj online!

Wyjaśnienie

æ             # powerset of first input
 O            # sum each subset
  ·           # multiply each element by 2
   D          # duplicate
    ±         # bitwise negation of each element in the copy
     ¹g       # push length of first input
       M      # get the maximum value on the stack
        Io    # push 2**<second input>
          ‹   # compare

— Emigna
źródło

@ Mr.Xcoder: O tak, dzięki! (Ciągle zapominam o ±)

— Emigna

2

JavaScript (ES6), 75 63 58 bajtów

a=>n=>!a.some(e=>(a.length|2*(e<0?l-=e:u+=e))>>n,u=0,l=-1)

Suma dowolnego podzbioru ależy między sumami elementów ujemnych i nieujemnych, więc sprawdzenie dwóch sum wystarcza na wszystko oprócz przypadku 2. Edycja: Zapisano 12 17 bajtów dzięki @Arnauld.

— Neil
źródło

O wiele lepsze niż moje naiwne podejście. :-) Można to skrócić do 61 bajtów

— Arnauld

W rzeczywistości możemy po prostu przetworzyć test w pętli na 56 bajtów .

— Arnauld,

Zhakowany ([-2, -1, -2]) (3)

— 14m2

@ l4m2 Good catch. Sugerowana poprawka (57 bajtów)

— Arnauld,

@Arnauld Problem w tym, że [-2, -2], 3powinien być prawdziwy, prawda?

— Neil,

1

Galaretka , 21 20 bajtów

»0,«0$S€~2¦Ḥ;LṀ<2*Ɠ¤

Wypróbuj online!

Rozwiązanie złożoności czasowej liniowej. Okazuje się, że przeceniłem złożoność czasu

w The Nineteenth Byte, 11.12.2017 13-15-03Z, autor: user202729

@NewSandboxedPosts Problem sumy podzbioru „Real” jest znacznie trudniejszy. Można to zrobić w czasie liniowo-rytmicznym ...

ponieważ teraz zdaję sobie sprawę, że sortowanie tablicy jest całkowicie niepotrzebne.

Wyjaśnienie:

»0,«0$S€~2¦Ḥ;LṀ<2*Ɠ¤    Main link. Example list: [-1, 0, 1]
»0                      Maximize with 0. Get [0, 0, 1]
  ,                     Pair with
   «0$                    minimize with 0. Get [-1, 0, 0]
      S€                Sum €ach. Get [1, -1]
        ~               Inverse
          ¦               at element
         2                2. (list[2] = ~list[2]) Get [-1, 2]
           Ḥ            Unhalve (double, ×2). Get [-2, 4]
            ;           Concatenate with
             L            Length (3). Get [-2, 4, 3]
              Ṁ         Maximum of the list (4).
               <   ¤    Still less than
                2         two
                 *        raise to the power of
                  Ɠ       eval(input())

— użytkownik202729
źródło

Wydaje się, że tak ~2¦może być ;~. EDYCJA: Gotowe.

— user202729,

@ user202729 Źle. Nadal ;~$będzie działać.

— user202729,

1

JavaScript (ES6), 114 bajtów

Pobiera dane wejściowe w składni curry (A)(n). Zwraca wartość logiczną.

A=>n=>!(A.reduce((a,x)=>[...a,...a.map(y=>[x,...y])],[[]]).some(a=>(s=eval(a.join`+`),s<0?~s:s)>>n-1)|A.length>>n)

Przypadki testowe

Pokaż fragment kodu

let f =

A=>n=>!(A.reduce((a,x)=>[...a,...a.map(y=>[x,...y])],[[]]).some(a=>(s=eval(a.join`+`),s<0?~s:s)>>n-1)|A.length>>n)

console.log('[Truthy]')
console.log(f([0, 0, 0])(2))
console.log(f([1, 2, 3, 4, 5])(8))
console.log(f([1, 2, 3, 4, 5])(5))
console.log(f([-3, 4, 1])(4))
console.log(f([-34, 56, 41, -4, -14, -54, 30, 38])(16))
console.log(f([-123, -85, 6, 121, -5, 12, 52, 31, 64, 0, 6, 101, 128, -72, -123, 12])(12))

console.log('[Falsy]')
console.log(f([0, 0, 0, 0])(2)) // violates #2
console.log(f([1, 2, 3, 4, 5])(2)) // violates all conditions
console.log(f([10, 0, -10])(4)) // violates #1 and #4
console.log(f([27, -59, 20, 6, 10, 53, -21, 16])(8)) // violates #4
console.log(f([-38, -1, -11, 127, -35, -47, 28, 89, -8, -12, 77, 55, 75, 75, -80, -22])(7)) // violates #4

Expand snippet

— Arnauld
źródło

1

Pyth , 20 bajtów

>EleS++KyMsMyQmt_dKl

Wypróbuj tutaj!

— Pan Xcoder
źródło

@ user202729 Poprosiłem OP i nie musimy obsługiwać pustej listy

— Pan Xcoder

1

Clojure, 121 117 bajtów

#(let[l(int(Math/pow 2(dec %2)))](every?(set(range(- l)l))(cons(count %)(for[i(vals(group-by pos? %))](apply + i)))))

Cóż, to było trochę głupie, dzielenie na wartości dodatnie i ujemne jest o wiele lepsze niż sortowanie. Oryginalne, ale zaskakująco niewiele dłużej:

#(let[l(int(Math/pow 2(dec %2)))S(sort %)R reductions](every?(set(range(- l)l))(concat[(count S)](R + S)(R +(into()S)))))

Działa to poprzez sprawdzanie sum prefiksu sekwencji w porządku rosnącym i malejącym, myślę, że nie jest konieczne generowanie wszystkich kombinacji elementów w A.

(into () S)jest tak samo jak (reverse S), ponieważ listy rosną z głowy. Nie mogłem wymyślić sposobu użycia conszamiast, concatgdy istnieją dwie listy consdo. : /

— NikoNyrh
źródło

1

Galaretka , 15 bajtów

ŒPS€Ḥ;~$;LṀl2<Ɠ

Wypróbuj online!

Wyjaśnienie

ŒPS€Ḥ;~$;LṀl2<Ɠ ~ Monadic full program.

ŒP              ~ Powerset.
  S€            ~ The sum of each subset.
    Ḥ           ~ Double (element-wise).
     ;~$        ~ Append the list of their bitwise complements.
        ;L      ~ Append the length of the first input.
          Ṁ     ~ And get the maximum.
           l2   ~ Base-2 logarithm.
             <Ɠ ~ Is smaller than the second input (from stdin)?

Zaoszczędzono 1 bajt dzięki caird coinheringaahing (odczytywanie drugiego wejścia z STDIN zamiast CLA).

— Pan Xcoder
źródło

@ user202729 Poprosiłem OP i nie musimy obsługiwać pustej listy

— Pan Xcoder

0

Łuska , 14 bajtów

≥Lḋ▲ṁ§eLöa→DΣṖ

Radzenie sobie z brutalną siłą poprzez zapętlanie wszystkich podlist, ponieważ podział na części dodatnią i ujemną zajmuje więcej bajtów. Wypróbuj online!

Wyjaśnienie

≥Lḋ▲ṁ§eLöa→DΣṖ  Implicit inputs, say A=[1,2,3,4,5] and n=5
             Ṗ  Powerset of A: [[],[1],[2],[1,2],..,[1,2,3,4,5]]
    ṁ           Map and concatenate:
                  Argument: a sublist, say S=[1,3,4]
            Σ     Sum: 8
           D      Double: 16
          →       Increment: 17
        öa        Absolute value: 17
     §eL          Pair with length of S: [3,17]
                Result is [0,1,1,3,1,5,2,7,..,5,31]
   ▲            Maximum: 31
  ḋ             Convert to binary: [1,1,1,1,1]
 L              Length: 5
≥               Is it at most n: 1

— Zgarb
źródło

0

Python 2 , 72 71 70 bajtów

def f(x,n):t=2*sum(k*(k<0)for k in x);max(2*sum(x)-t,~t,len(x))>>n>0>_

Wyjście odbywa się przez obecność / brak błędu .

Wypróbuj online!

— Dennis
źródło

Wariacja N-bitowa sumy częściowej

Przypadki testowe

Implementacja referencji (Python 3)

Wolfram Language (Mathematica) , 40 bajtów

Galaretka , 19 bajtów

05AB1E , 13 12 11 bajtów

JavaScript (ES6), 75 63 58 bajtów

Galaretka , 21 20 bajtów

JavaScript (ES6), 114 bajtów

Przypadki testowe

Pyth , 20 bajtów

Clojure, 121 117 bajtów

Galaretka , 15 bajtów

Wyjaśnienie

Łuska , 14 bajtów

Wyjaśnienie

Python 2 , 72 71 70 bajtów