Skip to content

Instantly share code, notes, and snippets.

@jackhftang
Created October 30, 2020 12:12
Show Gist options
  • Save jackhftang/b765c168f369e88dbc1e601d5b18d2d0 to your computer and use it in GitHub Desktop.
Save jackhftang/b765c168f369e88dbc1e601d5b18d2d0 to your computer and use it in GitHub Desktop.
you are a zoo keeper, You wanna keep animals to be healthy (not overweight) so you apply a diet plan.
Problem:
An animal has intial weight S at the start, For every day, you can choose to lose weight (a[i]) or have food (b[i]) or , but you have to make sure every day animal doesnt exceed T (target weight)
for N days plan, how many possbile combinations can have
condition
・1 ≦ N ≦ 35
・1 ≦ Ai, Bi ≦ 1,000,000,000 (1 ≦ i ≦ N)
・(sum of A_i) < S ≦ T ≦ 1,000,000,000
sample in
2 10 20
5 6
3 10
out: 3
sample in
8 300 400
9 39
48 38
21 10
14 45
32 20
32 48
9 7
19 16
out: 194
from bisect import bisect_right
# input
input_line = input()
[n, s, t] = [int(x) for x in input_line.split()]
vs = []
for _ in range(n):
input_line = input()
vs.append([int(x) for x in input_line.split()])
def solve(vs, w):
n = len(vs)
g = n // 2
# table
ps = [0]
for i in range(g):
[a,b] = vs[n-i-1]
ps = [max(0,v-a) for v in ps] + [v+b for v in ps]
ps.sort()
# dp
def run(i, w):
if w < 0:
return 0
if i == n - g:
return bisect_right(ps, w)
return run(i+1, w+vs[i][0]) + run(i+1, w-vs[i][1])
return run(0,w)
print(solve(vs,t-s))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment