foo-and-exams-4

Foo was not amongst the most brilliant students of his class. So, he has some pending exams to clear. As the exams are approaching, this time he vowed to pass in all of them. This will only happen if he is not under stress. Foo's stress can be calculated using a simple function called Foo_function which depends upon the time for which Foo studies continuously .

Foo_funtion is defined as follows:

F(t)=A(t^3)+B(t^2)+C*(t)+D, F(t) ≤ 10^18

where A,B,C,D belong to the set of prime numbers.
t is the time in minutes for which foo studies continuously.

As foo is not very good at solving cubic equations, he seeks your help to find out the maximum number of minutes for which he can study continuously without taking stress. Help him find t such that F(t+1) > K, and F(t) ≤ K, where K is the maximum stress Foo can bear. 

Input:

The first line of the input contains a single integer T denoting the number of test cases.
each test case consists of a single line containing 5 space seperated positive numbers a, b, c, d, K.

Output:

for each test case, output a single integer t denoting the maximum time for which foo can study continuously without taking stress.

Constraints:

1 ≤ T ≤ 10^4 
 A, B, C, D belong to a set of prime numbers such that F(t) would never exceed 10^18
t ≥ 0 
 1 ≤ K ≤ 10^18

SAMPLE INPUT
2
2 2 2 2 10
2 3 5 7 1000

SAMPLE OUTPUT
1
7

Explanation

In the 1st test case for t = 2 foo will be under stress because F(2)=30 > K, therefore he can study for a maximum time of 1 minute without having stress.

In the 2nd test case for t = 8 foo will be under stess because F(8)=1263 > K, therefore he can study for a maximum time of  7 minutes continuously without having stress.

Source: hackerearth | Difficulty: EASY
Tags: Sorting

Data structures

Implementation


Solutions:
'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
import sys
import math

def binary():
	sys.stdin.readline()
	line = sys.stdin.readline()
	while line:
		a, b, c, d, k = [int(x) for x in line.strip().split(" ")]
		
		func = lambda x: a * math.pow(x, 3) + b * math.pow(x, 2) + c * x + d
		upper = k
		lower = 0

		while True:
		    i = (upper + lower) / 2
		    if func(i) == k or upper - lower <= 1:
		        break
		    elif func(i) > k:
		        upper = i
		    elif func(i) < k:
		        lower = i

		print(lower)
		line = sys.stdin.readline()
	

binary()


t = int(input())
def calculate(a,b,c,d,k,beg,end):
	if d >= k:
		return 0
	temp = 0
	while end >= beg :
		mid = (beg+end)/2
		temp = a*(mid**3) + b*(mid**2) + c*(mid) +d
		if temp <= k and (a*((mid+1)**3) + b*((mid+1)**2) + c*(mid+1) +d) > k :
			return mid
		if temp >  k :
			end = mid -1
		else :
			beg = mid + 1
while t:
	t-=1
	a,b,c,d,k = list(map(int, input().split()))
	print(calculate(a,b,c,d,k,0,k))


t = int(input())
def calculate(a,b,c,d,k,beg,end):
	# calculate value of t
	temp = 0
	if d >= k:
		return 0
	while end >= beg :
		mid = (beg+end)/2
		temp = a*(mid**3) + b*(mid**2) + c*(mid) +d
		if temp <= k and (a*((mid+1)**3) + b*((mid+1)**2) + c*(mid+1) +d) > k :
			return mid
		if temp >  k :
			end = mid -1
		else :
			beg = mid + 1

while t:
	t-=1
	a,b,c,d,k = list(map(int, input().split()))
	print(calculate(a,b,c,d,k,0,k))


t = int(input())
while t>0:
	a,b,c,d,k = [int(i) for i in input().split()]
	f = lambda t:a*(t**3)+b*(t**2)+c*t + d
	ans = 0
	r = k
	l = 0

	while l<r:
		mid = (l+r)//2
	#	print "mid",mid
	#	print l,r
		search_item = f(mid)
	#	print search_item
		if search_item == k:
			ans = mid
			break
		elif search_item < k:
			ans = mid
			l = mid+1
		elif search_item > k:
			r = mid
		
	print(ans)
	t-=1


#https://www.hackerearth.com/practice/algorithms/searching/binary-search/practice-problems/algorithm/foo-and-exams-4/

def func(A, B, C, D, t):
	return A*pow(t, 3) + B*pow(t, 2) + C*t + D

def do_recurr(A, B, C, D, st, t, K):
	stress_t = func(A, B, C, D, t)
	stress_t1 = func(A, B, C, D, t+1)
	#print stress_t, stress_t1, t
	if (stress_t <= K and stress_t1 > K) or t == 0:
		return t
	elif stress_t < K: #can take more stress
		return do_recurr(A, B, C, D, t, (t+t*2)/2, K)
	else: #needs lower stress
		return do_recurr(A, B, C, D, st, (st+t)/2, K)

if __name__ == "__main__":
	T = int(input())
	while(T):
		in_arr = input().split()
		A = int(in_arr[0])
		B = int(in_arr[1])
		C = int(in_arr[2])
		D = int(in_arr[3])
		K = int(in_arr[4])
		T -= 1
		#select a random t
		t = K
		print(do_recurr(A, B, C, D, 0, t, K))


n=eval(input())
import math
for i in range(n):
	z=input().split()
	a=int(z[0])
	b=int(z[1])
	c=int(z[2])
	d=int(z[3])
	k=int(z[4])
	if (d>=k):
		print(0)
	if d<k:	
		n=(k/a)**(1.0/3.0)
		n=int(n)
		flag=0
		while(flag==0):
			if a*(n**3)+b*(n**2)+(c*n)+d <= k and a*((n+1)**3)+b*((n+1)**2)+(c*(n+1))+d >k :
				flag=1
				break
			n=n-1
		print(n)	


import math
for i in range(int(input())):
	list=list(map(int,input().split()))
	t=(list[4]/list[0])**(1.0/3)

	t=math.ceil(t)
	t=int(t)


	time = list[0] * (t ** 3) + list[1] * (t ** 2) + list[2] * (t ** 1) + list[3]
	while time > list[4] :
		t -= 1
		time = list[0] * (t ** 3) + list[1] * (t ** 2) + list[2] * (t ** 1) + list[3]
	if t>=0:
		print(t)
	else:
		print(0)




def userfunction(arr,t):
	return arr[0]*t**3+arr[1]*t**2+arr[2]*t+arr[3]#A(t^3)+B(t^2)+C*(t)+D, F(t)<=10^18

def binarySearch(arr,left,right,val):
	first = left
	last = right    
	while first<=last:
		midpoint = (first + last)//2
		temp = userfunction(arr,midpoint)
		if (temp<=val and (midpoint==last or userfunction(arr,midpoint+1))>val):
			return midpoint    
		if temp > val:
			last = midpoint-1
			if(last==0):
				return 0
		elif temp < val:           
			first = midpoint+1            
	return midpoint

lower=1
upper=1000000
  
if __name__ == "__main__":
	testcases = eval(input())
	
	for caseNr in range(1, testcases+1):
		arr = [ int(i) for i in input().split(' ')]
		print(binarySearch(arr,lower,upper,arr[4]))


def userfunction(arr,t):
	return arr[0]*t**3+arr[1]*t**2+arr[2]*t+arr[3]#A(t^3)+B(t^2)+C*(t)+D, F(t)<=10^18

def binarySearch(arr,left,right,val):
	first = left
	last = right    
	while first<=last:
		midpoint = (first + last)//2
		temp = userfunction(arr,midpoint)
		if (temp<=val and (midpoint==last or userfunction(arr,midpoint+1))>val):
			return midpoint    
		if temp > val:
			last = midpoint-1
			if(last==0):
				return 0
		elif temp < val:           
			first = midpoint+1            
	return midpoint

lower=1
upper=1000000
  
if __name__ == "__main__":
	testcases = eval(input())
	
	for caseNr in range(1, testcases+1):
		arr = [ int(i) for i in input().split(' ')]
		print(binarySearch(arr,lower,upper,arr[4]))


def userfunction(arr,t):
	return arr[0]*t**3+arr[1]*t**2+arr[2]*t+arr[3]#A(t^3)+B(t^2)+C*(t)+D, F(t)<=10^18

def binarySearch(arr,left,right,val):
	first = left
	last = right    
	while first<=last:
		midpoint = (first + last)//2
		temp = userfunction(arr,midpoint)
		if (temp<=val and (midpoint==last or userfunction(arr,midpoint+1))>val):
			return midpoint    
		if temp > val:
			last = midpoint-1
			if(last==0):
				return 0
		elif temp < val:           
			first = midpoint+1            
	return midpoint

lower=1
upper=1000000
  
if __name__ == "__main__":
	testcases = eval(input())
	
	for caseNr in range(1, testcases+1):
		arr = [ int(i) for i in input().split(' ')]
		print(binarySearch(arr,lower,upper,arr[4]))


n=eval(input())
import math
for i in range(n):
	z=input().split()
	a=int(z[0])
	b=int(z[1])
	c=int(z[2])
	d=int(z[3])
	k=int(z[4])
	if (d>=k):
		print(0)
	if d<k:	
		n=(k/a)**(1.0/3.0)
		n=int(n)
		flag=0
		while(flag==0):
			if a*(n**3)+b*(n**2)+(c*n)+d <= k and a*((n+1)**3)+b*((n+1)**2)+(c*(n+1))+d >k :
				flag=1
				break
			n=n-1
		print(n)	


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
T = int(input())
cases = []
results = [0]*T
test = None

for i in range(T):
	test = input()
	cases.append([int(y) for y in test.split(" ")])
	
def eval_cubic_equ(A,t):
	return A[0]*t**3+A[1]*t**2+A[2]*t+A[3] <= A[4]

def binary_search(a,b,case):
	mid = (a+b)/2
	final_val = None
	if b - a > 1:
		if eval_cubic_equ(case,mid):
			return binary_search(mid,b,case)
		else:
			return binary_search(a,mid,case)
	else:
		return a
	
def calc_max_time(case):
	t = 1
	count = 60
	found = False
	while(count > 0 and found == False):
		if eval_cubic_equ(case,t):
			t = t*2
		else:
			t_final = binary_search(t/2,t,case)
			found = True
		count+=1
	return t_final

for case in cases:
	print(calc_max_time(case))


def userfunction(arr,t):
	return arr[0]*t**3+arr[1]*t**2+arr[2]*t+arr[3]#A(t^3)+B(t^2)+C*(t)+D, F(t)<=10^18

def binarySearch(arr,left,right,val):
	first = left
	last = right    
	while first<=last:
		midpoint = (first + last)//2
		temp = userfunction(arr,midpoint)
		if (temp<=val and (midpoint==last or userfunction(arr,midpoint+1))>val):
			return midpoint    
		if temp > val:
			last = midpoint-1
			if(last==0):
				return 0
		elif temp < val:           
			first = midpoint+1            
	return midpoint

lower=1
upper=1000000
  
if __name__ == "__main__":
	testcases = eval(input())
	
	for caseNr in range(1, testcases+1):
		arr = [ int(i) for i in input().split(' ')]
		print(binarySearch(arr,lower,upper,arr[4]))


def foo(a,b,c,d,t):
	return a*(t**3)+b*(t**2)+c*t+d
	
test_cases=int(input())
for t in range(test_cases):
	items=input().split(" ")
	a,b,c,d,k=[int(item) for item in items]
	t_current=0
	gap=100
	t_prev=0
	while True:
		if k <= foo(a,b,c,d,t_current):
			break
		else:
			t_prev=t_current
			t_current+=gap
	for pointer in range(t_prev,t_current+1):
		if k <= foo(a,b,c,d,pointer):
			break
		pointer+=1
	if pointer==0:
		print(pointer)
	else:
		print(pointer-1)


n=eval(input())
import math
for i in range(n):
	z=input().split()
	a=int(z[0])
	b=int(z[1])
	c=int(z[2])
	d=int(z[3])
	k=int(z[4])
	if (d>=k):
		print(0)
	if d<k:	
		n=(k/a)**(1.0/3.0)
		n=int(n)
		flag=0
		while(flag==0):
			if a*(n**3)+b*(n**2)+(c*n)+d <= k and a*((n+1)**3)+b*((n+1)**2)+(c*(n+1))+d >k :
				flag=1
				break
			n=n-1
		print(n)	


n=eval(input())
import string
import math
for i in range(n):
	z=input()
	z=string.split(z)
	a=int(z[0])
	b=int(z[1])
	c=int(z[2])
	d=int(z[3])
	k=int(z[4])
	if (d>=k):
		print(0)
	if d<k:	
		n=(k/a)**(1.0/3.0)
		n=int(n)
		flag=0
		while(flag==0):
			if a*(n**3)+b*(n**2)+(c*n)+d <= k and a*((n+1)**3)+b*((n+1)**2)+(c*(n+1))+d >k :
				flag=1
				break
			n=n-1
		print(n)	
	


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''

def cubicFunc(A, B, C, D, t):
	#print A, B, C, D, t, A*(pow(t,3)) + B*(pow(t,2)) + C*t + D
	return A*(pow(t,3)) + B*(pow(t,2)) + C*t + D
	
	
def binarySearch(A,B,C,D, K):
    lowIndex = 1
    highIndex = 2*lowIndex + 1
    
    lowFunc = cubicFunc(A, B, C, D, lowIndex)
    highFunc = cubicFunc(A, B, C, D, highIndex)
    while highFunc < K:
    	highIndex = 2*highIndex + 1
    	highFunc = cubicFunc(A, B, C, D, highIndex)
    	
    while highIndex > lowIndex:
        index = (highIndex + lowIndex) / 2
        sub = cubicFunc(A, B, C, D, index)
        if cubicFunc(A, B, C, D, lowIndex) == K:
            return [lowIndex, lowIndex]
        elif sub == K:
            return [index, index]
        elif cubicFunc(A, B, C, D, highIndex) == K:
            return [highIndex, highIndex]
        elif sub > K:
            if highIndex == index:
                return sorted([highIndex, lowIndex])
            highIndex = index
        else:
            if lowIndex == index:
                return sorted([highIndex, lowIndex])
            lowIndex = index
    return sorted([highIndex-1, lowIndex-1])
	

	
T = int(input())
import math

for i in range(T):
	params = list(map(int, input().strip().split(' ')))
	A = params[0]
	B = params[1]
	C = params[2]
	D = params[3]
	K = params[4]
	
	#timeArray = range(1, int((K/2) ** (1. / 3)) + 2)
	#print timeArray
	#timeArray2 = [cubicFunc(A, B, C, D, x) for x in timeArray]
	#print timeArray2
	print((binarySearch(A, B, C, D, K)[0]))
	#mini = min(range(len(timeArray2)), key=lambda i: abs(timeArray2[i]-K))
	#


def userfunction(arr,t):
	return arr[0]*t**3+arr[1]*t**2+arr[2]*t+arr[3]#A(t^3)+B(t^2)+C*(t)+D, F(t)<=10^18

def binarySearch(arr,left,right,val):
	first = left
	last = right    
	while first<=last:
		midpoint = (first + last)//2
		temp = userfunction(arr,midpoint)
		if (temp<=val and (midpoint==last or userfunction(arr,midpoint+1)>val)):
			return midpoint    
		if temp > val:
			last = midpoint-1
			if(last==0):
				return 0
		elif temp < val:           
			first = midpoint+1            
	return midpoint

lower=1
upper=1000000
  
if __name__ == "__main__":
	testcases = eval(input())
	
	for caseNr in range(1, testcases+1):
		arr = [ int(i) for i in input().split(' ')]
		print(binarySearch(arr,lower,upper,arr[4]))


def userfunction(arr,t):
	return arr[0]*t**3+arr[1]*t**2+arr[2]*t+arr[3]#A(t^3)+B(t^2)+C*(t)+D, F(t)<=10^18

def binarySearch(arr,left,right,val):
	first = left
	last = right    
	while first<=last:
		midpoint = (first + last)//2
		temp = userfunction(arr,midpoint)
		if (temp<=val and (midpoint==last or userfunction(arr,midpoint+1))>val):
			return midpoint    
		if temp > val:
			last = midpoint-1
			if(last==0):
				return 0
		elif temp < val:           
			first = midpoint+1            
	return midpoint

lower=1
upper=1000000
  
if __name__ == "__main__":
	testcases = eval(input())
	
	for caseNr in range(1, testcases+1):
		arr = [ int(i) for i in input().split(' ')]
		print(binarySearch(arr,lower,upper,arr[4]))


def calc(a, b, c, d, k):
	beg = 0
	end = k
	if d >= k:
		return 0
	tmp1 , tmp2 = 0, 0
	while end >= beg:
		mid =  (beg  + end) / 2
		tmp1 = a*(mid**3) + b*(mid**2) + c*(mid) + d
		tmp2 = a*((mid + 1)**3) + b*((mid + 1)**2) + c*((mid) + 1) +d
		if tmp1 <= k and tmp2 > k:
			return mid
		if tmp1 > k:
			end = mid - 1
		else:
			beg = mid + 1
			
for _ in range(eval(input())):
	a, b, c, d, k = list(map(int, input().split()))
	print(calc(a, b, c, d, k))