Sometimes it requires GPU to compute huge amount of operation... like O(2^100)..? Nah, you'll use better algorithm, O(2^50) seems fair huh? - __readfsqword
MAX_N = 100
RAND_MAX = 10 ** 200 # You can't even solve with knapsack method
from random import randrange
for n in range(1, MAX_N + 1):
print(f"Stage {n}")
arr = [ randrange(0, RAND_MAX) for _ in range(n) ]
counts = randrange(0, n + 1)
used = set()
while True:
idx = randrange(0, n)
used.add(idx)
if len(used) >= counts:
break
s = 0
for idx in used:
s += arr[idx]
for a in arr:
print(a, end=' ')
print(s)
answer = list(map(int, input().split()))
user_sum = 0
for i in answer:
user_sum += arr[i]
Another knapsack question, although the question states that it is exponential in time, we use a lattice reduction method that solves it in polynomial time
To do this, we refer to this paper
Exploit
from pwn import *
load(flatter.sage)
def solve(arr,s):
M = identity_matrix(QQ, len(arr))
M = M.augment(vector(arr))
M = M.stack(vector([-1/2 for _ in range(len(arr))] + [-s]))
try:
M1= flatter(M)
row = M1[0][:-1]
ans=[]
for cnt,i in enumerate(row):
if i==1:
ans.append(cnt)
return ans
except:
M1 = M.LLL()
for row in M.LLL():
for row in (row, -row):
if row[-1] == 0:
subset = [i for i, x in enumerate(row[:-1]) if x+1/2==1]
return subset
r.close()
r = remote("35.224.11.111",32054)
r.sendline("0")
r.recv()
r.recvline()
for i in range(99):
arr=r.recvuntil(b"\n")[:-1].decode()
arr = arr.split(" ")
arr = [int(i) for i in arr]
s= arr[-1]
arr = arr[:-1]
ans=solve(arr,s)
a1=str(ans)[1:-1].replace(','," ")
r.sendline(a1)
r.recvline()
b'DEAD{T00_B1g_Number_Causes_Pr0blem...}\n'
To speed up the lattice reduction for large lattices, we use . Unfortunately, flatter doesn't work for very short lattices so we use sage's built in LLL method as a fallback and the knapsack solve code from