In [1]:
# SAMPLE INPUT:
#
# 10 3 3
In [2]:
# function to check if X will achieve repayment
def goodX(x,n,k,m):
y,r = divmod(n,x) # y is first payment amount
if y<=m:
return False # K*M<N, so loan can't be paid for this value of x
xdays = min(r//y,k) # days that this y value is valid for this value of x, set to k if longer than k
xdays = max(xdays,1) # make sure xdays is at least 1
g = y*xdays # paid off g, initialize g at end of xdays worth of payments
days = xdays # num days payments have been made, initialize after xdays payments
while g<n and days<k:
# if remaining amount can be paid off with minimum payments, return True
if (k-days)*m >= n-g:
return True
y,r = divmod(n-g,x)
if y<m:
if g+(k-days)*m >= n:
return True # this condition should have been caught above
else:
return False # min payments are not going to cut it
# y is non-increasing...
# bail if the current level y is insufficient to pay the remaining balance
if y*(k-days) < n-g:
return False
xdays = min(r//y,k) # compute number of days this value of y is will remain unchanged
xdays = max(xdays,1) # make sure xdays is at least 1 and no more than K
days += xdays
g += y*xdays
if g >= n:
return True
else:
return False
In [3]:
fin = open ('loan.in', 'r')
fout = open ('loan.out', 'w')
# N = TOTAL
# K = DAYS
# M = MIN DAILY
# M*K < N
N,K,M = map(int, fin.readline().split())
print(N,K,M)
# binary search
p1 = 1
p2 = N
while(p1 < p2):
mid = (p1+p2+1)//2
if( goodX(mid,N,K,M) ):
p1 = mid
else:
p2 = mid-1
print(p1)
fout.write(str(p1)+"\n")
fout.close()
