For her next karate demonstration, Ada will break some bricks.
Ada stacked three bricks on top of each other. Initially, their widths (from top to bottom) are $W_1, W_2, W_3$.
Ada's strength is $S$. Whenever she hits a stack of bricks, consider the largest $k \ge 0$ such that the sum of widths of the topmost $k$ bricks does not exceed $S$; the topmost $k$ bricks break and are removed from the stack. Before each hit, Ada may also decide to reverse the current stack of bricks, with no cost.
Find the minimum number of hits Ada needs in order to break all bricks if she performs the reversals optimally. You are not required to minimise the number of reversals.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains four space-separated integers $S$, $W_1$, $W_2$ and $W_3$.

-----Output-----
For each test case, print a single line containing one integer ― the minimum required number of hits.

-----Constraints-----
- $1 \le T \le 64$
- $1 \le S \le 8$
- $1 \le W_i \le 2$ for each valid $i$
- it is guaranteed that Ada can break all bricks

-----Subtasks-----
Subtask #1 (50 points): $W_1 = W_2 = W_3$
Subtask #2 (50 points): original constraints

-----Example Input-----
3
3 1 2 2
2 1 1 1
3 2 2 1

-----Example Output-----
2
2
2

-----Explanation-----
Example case 1: Ada can reverse the stack and then hit it two times. Before the first hit, the widths of bricks in the stack (from top to bottom) are $(2,2,1)$. After the first hit, the topmost brick breaks and the stack becomes $(2,1)$. The second hit breaks both remaining bricks.
In this particular case, it is also possible to hit the stack two times without reversing. Before the first hit, it is $(1, 2, 2)$. The first hit breaks the two bricks at the top (so the stack becomes $(2)$) and the second hit breaks the last brick.

Difficulty: EASY
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
import math
for i in range(int(input())):
	(k, w1, w2, w3) = map(int, input().split())
	s = w1 + w2 + w3
	if k >= s:
		print(1)
	elif k >= w1 + w2 or k >= w2 + w3:
		print(2)
	else:
		print(3)


tc = int(input())
for _ in range(tc):
	arr = [int(x) for x in input().split(' ')]
	if arr[3] + arr[2] + arr[1] <= arr[0]:
		print(1)
	elif arr[3] < arr[1]:
		if arr[3] + arr[2] <= arr[0]:
			print(2)
		else:
			print(3)
	elif arr[1] + arr[2] <= arr[0]:
		print(2)
	else:
		print(3)


for i in range(int(input())):
	(s, w1, w2, w3) = list(map(int, input().split()))
	if s >= w1 + w2 + w3:
		print(1)
	elif s >= w1 + w2 or s >= w2 + w3:
		print(2)
	else:
		print(3)


T = int(input())
for tc in range(T):
	(s, w1, w2, w3) = map(int, input().split(' '))
	fsum = w1 + w2
	rsum = w3 + w2
	wsum = w1 + w2 + w3
	if wsum <= s:
		print(1)
	elif fsum <= s or rsum <= s:
		print(2)
	else:
		print(3)


for i in range(int(input())):
	(s, a, b, c) = map(int, input().split())
	if a + b + c <= s:
		print(1)
	elif a + b <= s or b + c <= s:
		print(2)
	else:
		print(3)


for _ in range(int(input())):
	(s, w1, w2, w3) = map(int, input().split())
	if w1 + w2 + w3 <= s:
		print(1)
	elif w1 + w2 <= s:
		print(2)
	elif w2 + w3 <= s:
		print(2)
	else:
		print(3)


t = int(input())
for _ in range(t):
	(p, w1, w2, w3) = map(int, input().split())
	if p >= w1 + w2 + w3:
		print(1)
	elif p >= w1 + w2 or p >= w2 + w3:
		print(2)
	elif p >= w3 or p >= w1:
		print(3)


for _ in range(int(input())):
	L = list(map(int, input().split()))
	S = L[0]
	W = L[1:]
	c = 0
	if W[0] + W[1] <= S:
		if W[0] + W[1] + W[2] <= S:
			print(1)
		else:
			print(2)
	elif W[2] + W[1] <= S:
		print(2)
	else:
		print(3)


def brkbs(s, w1, w2, w3):
	w = [w1, w2, w3]
	c = 0
	while len(w) > 0:
		ans = []
		for i in range(len(w)):
			if w[i] > s:
				return c
			ans.append(w[i])
			sum_ans = sum(ans)
			if sum_ans > s:
				c += 1
				ans.pop()
				for elem in ans:
					w.remove(elem)
				break
		else:
			return c + 1
	return c
for _ in range(int(input())):
	(s, w1, w2, w3) = map(int, input().split())
	print(brkbs(s, w1, w2, w3))


cases = int(input())
for case in range(cases):
	(ss, w1, w2, w3) = map(int, input().split())
	width = w1 + w2 + w3
	hits = 0
	if width > ss:
		if ss >= w1 + w2 or ss >= w2 + w3:
			hits = 2
		else:
			hits = 3
	else:
		hits = 1
	print(hits)


for tc in range(int(input())):
	(s, w1, w2, w3) = map(int, input().split())
	rev = 0
	bricksleft = 3
	bricks = 0
	if w1 < w3:
		firstbrick = w1
		lastbrick = w3
		rev = 0
	else:
		firstbrick = w3
		lastbrick = w1
		rev = 1
	hit = 1
	if firstbrick > s:
		bricks = 0
	else:
		bricks = 1
	if firstbrick + w2 <= s:
		bricks = 2
	if firstbrick + w2 + lastbrick <= s:
		bricks = 3
	bricksleft = bricksleft - bricks
	if bricksleft > 0:
		bricks = 0
		hit = 2
		if w2 <= s:
			bricks = 1
		if w2 + lastbrick <= s:
			bricks = 2
		bricksleft = bricksleft - bricks
	if bricksleft > 0:
		bricks = 0
		hit = 3
		if lastbrick <= s:
			bricks = 1
		bricksleft = bricksleft - bricks
	print(hit)


for _ in range(int(input())):
	(a, b, c, d) = map(int, input().split())
	print(1 if d + b + c <= a else 2 if b + c <= a or c + d <= a else 3)


import math
t = int(input())
while t > 0:
	(s, a, b, c) = map(int, input().split())
	if s >= a + b + c:
		print('1')
	elif s >= a + b or s >= b + c:
		print('2')
	else:
		print('3')
	t -= 1


t = int(input())
for i in range(t):
	(s, w1, w2, w3) = map(int, input().split())
	ans = 0
	if s >= w1 + w2 + w3:
		ans += 1
	elif s >= w1 + w2:
		ans += 1
		if s >= w3:
			ans += 1
	elif s >= w1:
		ans += 1
		if s >= w2 + w3:
			ans += 1
		elif s >= w2:
			ans += 1
			if s >= w3:
				ans += 1
	print(ans)


for _ in range(int(input())):
	(s1, w1, w2, w3) = map(int, input().split())
	l = [w1, w2, w3]
	o = 0
	p = 0
	s = s1
	while p < 3:
		s = s - l[p]
		if s == 0:
			o = o + 1
			s = s1
		elif s < 0:
			s = s1
			o = o + 1
			continue
		elif p == 2:
			o = o + 1
		p = p + 1
	print(o)


test = int(input())
for i in range(test):
	(a, w1, w2, w3) = map(int, input().split())
	if w1 + w2 + w3 <= a:
		print('1')
	elif w2 + w3 <= a or w1 + w2 <= a:
		print('2')
	else:
		print('3')


for ms in range(int(input())):
	(h, a1, a2, a3) = map(int, input().split())
	if a1 + a2 + a3 <= h:
		print(1)
	elif a1 + a2 <= h or a2 + a3 <= h:
		print(2)
	else:
		print(3)


for _ in range(int(input())):
	list_a = list(map(int, input().split()))
	s = list_a[0]
	list_a = list_a[1:]
	sum = 0
	count = 1
	for char in list_a:
		sum += char
		if sum <= s:
			continue
		elif sum > s:
			count += 1
			sum = char
	print(count)


def solve():
	(S, W1, W2, W3) = map(int, input().split())
	print(1 if S >= W1 + W2 + W3 else 2 if S >= W1 + W2 or S >= W2 + W3 else 3)
for _ in range(int(input())):
	solve()


t = int(input())
while t:
	l = list(map(int, input().split()))
	s = l[0]
	l.remove(l[0])
	if l[0] + l[1] + l[2] <= s:
		print(1)
	elif l[0] + l[1] <= s or l[1] + l[2] <= s:
		print(2)
	else:
		print(3)
	t -= 1


try:
	T = int(input())
	for t in range(T):
		w = list(map(int, input().split()))
		s = w.pop(0)
		c = 0
		while len(w) > 0:
			r = s
			c += 1
			if w[0] > w[-1]:
				while len(w) > 0 and r >= w[0]:
					r -= w[0]
					w.pop(0)
			else:
				while len(w) > 0 and r >= w[-1]:
					r -= w[-1]
					w.pop(-1)
		print(c)
except:
	pass


for i in range(int(input())):
	(a, b, c, d) = map(int, input().split())
	q = b + c + d
	if a >= q:
		print(1)
	elif b + c > a and c + d > a:
		print(3)
	else:
		print(2)


t = int(input())
for i in range(t):
	(s, W1, W2, W3) = map(int, input().split())
	c = W1 + W2 + W3
	if s >= c:
		print('1')
	elif W1 + W2 <= s or W2 + W3 <= s:
		print('2')
	else:
		print('3')


for case in range(int(input())):
	(a, b, c, d) = map(int, input().split())
	w = b + c + d
	k = 0
	if w > a:
		if a >= b + c or a >= c + d:
			k = 2
		else:
			k = 3
	else:
		k = 1
	print(k)


for _ in range(int(input())):
	l = list(map(int, input().split()))
	if l[0] >= sum(l[1:]):
		print(1)
	elif l[0] >= sum(l[1:3]) or l[0] >= sum(l[2:4]):
		print(2)
	else:
		print(3)


t = int(input())
for i in range(t):
	(n, w1, w2, w3) = map(int, input().split())
	if n >= w1 + w2 + w3:
		print(1)
	elif n >= w1 + w2 or n >= w2 + w3:
		print(2)
	else:
		print(3)


for _ in range(int(input())):
	n = list(map(int, input().split()))
	s = n[0]
	w = n[1:]
	c = 0
	for i in range(3):
		if sum(w) <= s:
			c = c + 1
			break
		elif sum(w[:2]) <= s:
			w = w[2:]
			c = c + 1
		else:
			w = w[1:]
			c += 1
	print(c)


t = int(input())
for _ in range(t):
	(s, w1, w2, w3) = [int(x) for x in input().split()]
	if w1 + w2 + w3 <= s:
		print(1)
	elif w1 + w2 <= s or w3 + w2 <= s:
		print(2)
	else:
		print(3)


t = int(input())
for _ in range(t):
	(s, *w) = map(int, input().split())
	if sum(w) <= s:
		print('1')
	elif w[0] + w[1] <= s and w[2] <= s or (w[2] + w[1] <= s and w[0] <= s):
		print('2')
	else:
		print('3')


t = int(input())
for tc in range(t):
	(s, w1, w2, w3) = map(int, input().split())
	if s >= w1 + w2 + w3:
		print('1')
	elif s >= w1 + w2 or s >= w2 + w3:
		print('2')
	else:
		print('3')


def solve(s, a, b, c):
	if s >= a + b + c:
		return 1
	if s >= a + b:
		return 2
	if s >= b + c:
		return 2
	return 3

def main():
	t = int(input())
	for _ in range(t):
		line = input().strip()
		(s, a, b, c) = [int(x) for x in line.split(' ')]
		print(solve(s, a, b, c))
main()


for _ in range(int(input())):
	(S, W1, W2, W3) = (int(i) for i in input().split(' '))
	if W1 + W2 + W3 <= S:
		print(1)
	elif S >= W1 + W2 or S >= W2 + W3:
		print(2)
	else:
		print(3)


for _ in range(int(input())):
	(p, w1, w2, w3) = map(int, input().split())
	count = 0
	sum = 0
	if p >= w1 + w2 + w3:
		print(1)
	elif p >= w1 + w2 and p >= w3:
		print(2)
	elif p >= w3 + w2 and p >= w1:
		print(2)
	else:
		print(3)


for i in range(int(input())):
	(s, w1, w2, w3) = map(int, input().split())
	c = 0
	sum = w1 + w2 + w3
	if w1 < w3:
		tmp = w3
		w3 = w1
		w1 = tmp
	if w1 + w2 + w3 <= s:
		print('1')
	elif w1 + w2 <= s:
		print('2')
	elif w1 <= s:
		c = c + 1
	if c == 1:
		if w2 + w3 <= s:
			print('2')
		elif w2 + w3 > s:
			print('3')


a = int(input(''))
for i in range(a):
	(s, w1, w2, w3) = [int(x) for x in input('').split()]
	if w1 + w2 + w3 <= s:
		print(1)
	elif w1 + w2 <= s or w2 + w3 <= s:
		print(2)
	else:
		print(3)


t = int(input())
for i in range(0, t):
	(a, x, y, z) = list(map(int, input().split()))
	p = x + y + z
	print('1' if a >= p else '2' if x + y <= a or y + z <= a else '3')


def main():
	for _ in range(int(input())):
		(s, w1, w2, w3) = map(int, input().split(' '))
		if s >= w1 + w2 + w3:
			print('1')
		elif s >= w1 + w2 or s >= w2 + w3:
			print('2')
		elif s >= w3 or s >= w1:
			print('3')
main()


for h in range(int(input())):
	(s, w1, w2, w3) = map(int, input().split())
	sum1 = w1 + w2 + w3
	if s >= sum1:
		print(1)
	elif s >= w1 + w2 or s >= w3 + w2:
		print(2)
	else:
		print(3)


a = int(input())
while a != 0:
	(S, x, y, z) = input().split(' ')
	x = int(x)
	y = int(y)
	z = int(z)
	S = int(S)
	count = 0
	if x + y + z <= S:
		count = 1
	elif x + y <= S and z <= S or (y + z <= S and x <= S):
		count = 2
	else:
		count = 3
	print(count)
	a -= 1


for i in range(int(input())):
	(a, x, y, z) = list(map(int, input().split()))
	b = x + y + z
	print('1' if a >= b else '2' if x + y <= a or y + z <= a else '3')


for _ in range(int(input())):
	a = list(map(int, input().split()))
	s = a.pop(0)
	sm = sum(a)
	ans = 0
	while sm > 0:
		a1 = a[::-1]
		(s1, i) = (0, 0)
		while s1 < s and i < len(a):
			s1 += a[i]
			i += 1
		if s1 > s:
			i -= 1
			s1 -= a[i]
		(s2, i1) = (0, 0)
		while s2 < s and i1 < len(a):
			s2 += a1[i1]
			i1 += 1
		if s2 > s:
			i1 -= 1
			s2 -= a[i1]
		if i1 > i:
			sm -= s2
			a = a1[i1:][::-1]
		else:
			sm -= s1
			a = a[i:]
		ans += 1
	print(ans)


for _ in range(int(input())):
	arr = list(map(int, input().split()))
	s = arr[0]
	arr = arr[1:]
	if sum(arr) <= s:
		print(1)
	elif min(sum(arr) - arr[0], sum(arr) - arr[-1]) <= s:
		print(2)
	else:
		print(3)


def hits(l, s):
	if sum(l) <= s:
		return 1
	elif l[0] + l[1] <= s or l[1] + l[2] <= s:
		return 2
	else:
		return 3
for _ in range(int(input())):
	(s, w1, w2, w3) = map(int, input().split())
	wl = [w1, w2, w3]
	print(hits(wl, s))