Problem:


Problem A: Ohgas' Fortune

The Ohgas are a prestigious family based on Hachioji.  The head of the family,
Mr. Nemochi Ohga, a famous wealthy man, wishes to increase his fortune
by depositing his money to an operation company. You are asked to help
Mr. Ohga maximize his profit by operating the given money during a specified
period.

From a given list of possible operations, 
you choose an operation to deposit the given fund to. 
You commit on the single operation throughout the period and
deposit all the fund to it.

Each operation specifies an annual interest rate, whether the interest
is simple or compound, and an annual operation charge.

An annual operation charge is a constant 
not depending on the balance of the fund.

The amount of interest is calculated at the end of every year, by
multiplying the balance of the fund under operation by the annual
interest rate, and then rounding off its fractional part. For compound
interest, it is added to the balance of the fund under operation, and
thus becomes a subject of interest for the following years.  For
simple interest, on the other hand, it is saved somewhere else and
does not enter the balance of the fund under operation (i.e. it is
not a subject of interest in the following years).

An operation charge is then subtracted from the balance of the fund
under operation.  You may assume here that you can always pay the
operation charge (i.e. the balance of the fund under operation is
never less than the operation charge).

The amount of money you obtain after the specified years of operation
is called ``the final amount of fund.''  For simple interest, it is
the sum of the balance of the fund under operation at the end of the
final year, plus the amount of interest accumulated throughout the
period. For compound interest, it is simply the balance of the fund
under operation at the end of the final year.

Operation companies use C, C++, Java, etc., to perform their
calculations, so they pay a special attention to their interest
rates. That is, in these companies, an interest rate is always an
integral multiple of 0.0001220703125 and between 0.0001220703125 and
0.125 (inclusive).  0.0001220703125 is a decimal representation of
1/8192. Thus, interest rates' being its multiples means that they can
be represented with no errors under the double-precision binary
representation of floating-point numbers.

For example, if you operate 1000000 JPY for five years with an annual,
compound interest rate of 0.03125 (3.125 %) and an annual operation charge of 3000 JPY, the balance changes as
follows.

The balance of the fund under operation
(at the beginning of year)
Interest
The balance of the fund under operation (at the end of year)

AB = A &times; 0.03125 (and rounding off fractions)
A + B - 3000

1000000312501028250

1028250321321057382

1057382330431087425

1087425339821118407

1118407349501150357

After the five years of operation, the final amount of fund is 1150357 JPY.

If the interest is simple with all other parameters being equal, 
it looks like:

The balance of the fund under operation (at the beginning of year)
Interest
The balance of the fund under operation (at the end of year)
Cumulative interest 

AB = A &times; 0.03125 (and rounding off fractions)A - 3000

10000003125099700031250

9970003115699400062406

9940003106299100093468

99100030968988000124436

98800030875985000155311

In this case the final amount of fund is the total of the fund under
operation, 985000 JPY, and the cumulative interests, 155311 JPY, which
is 1140311 JPY.

Input

The input consists of datasets. The entire input looks like:

the number of datasets (=m) 

1st dataset                 

2nd dataset                 

...                                

m-th dataset                

The number of datasets, m, is no more than 100.
Each dataset is formatted as follows.

the initial amount of the fund for operation  

the number of years of operation              

the number of available operations (=n)       

operation 1                                   

operation 2                                   

...                                                  

operation n                                   

The initial amount of the fund for operation, the number of years of operation, 
and the number of available operations are all positive integers.
The first is no more than 100000000, the second no more than 10, and 
the third no more than 100.

Each ``operation'' is formatted as follows.

simple-or-compound annual-interest-rate annual-operation-charge

where simple-or-compound is a single character of either '0' or '1', 
with '0' indicating
simple interest and '1' compound. annual-interest-rate is represented
by a decimal fraction and is an integral multiple of 1/8192.
annual-operation-charge is an integer not exceeding 100000.

Output

For each dataset, print a line having a decimal integer indicating the
final amount of fund for the best operation. The best operation is the
one that yields the maximum final amount among the available
operations. Each line should not have any character other than 
this number.

You may assume the final balance never exceeds 1000000000.
You may also assume that at least one operation has the final amount of the
fund no less than the initial amount of the fund.

Sample Input

4
1000000
5
2
0 0.03125 3000
1 0.03125 3000
6620000
7
2
0 0.0732421875 42307
1 0.0740966796875 40942
39677000
4
4
0 0.0709228515625 30754
1 0.00634765625 26165
0 0.03662109375 79468
0 0.0679931640625 10932
10585000
6
4
1 0.0054931640625 59759
1 0.12353515625 56464
0 0.0496826171875 98193
0 0.0887451171875 78966

Output for the Sample Input

1150357
10559683
50796918
20829397



Sample input:
4
1000000
5
2
0 0.03125 3000
1 0.03125 3000
6620000
7
2
0 0.0732421875 42307
1 0.0740966796875 40942
39677000
4
4
0 0.0709228515625 30754
1 0.00634765625 26165
0 0.03662109375 79468
0 0.0679931640625 10932
10585000
6
4
1 0.0054931640625 59759
1 0.12353515625 56464
0 0.0496826171875 98193
0 0.0887451171875 78966


Sample output:
1150357
10559683
50796918
20829397

Submission status: Accepted

Solution code:
m = int(input())
for _ in range(m):
    s = int(input())
    y = int(input())
    n = int(input())
    a = 0
    for _d in range(n):
        t, p, b = map(float, input().split())
        tem = 0
        ts = s
        if t:
            for _y in range(y):
                ts += int(ts * p)
                ts -= b
            a = max(a, ts)
        else:
            tp = 0
            for _y in range(y):
                tp += int(ts * p)
                ts -= b
            a = max(a, ts + tp)
    print(int(a))

Submission status: Accepted

Solution code:
# AOJ 1135: Ohgas' Fortune
# Python3 2018.7.14 bal4u

for cno in range(int(input())):
	a0, y, n = int(input()), int(input()), int(input())
	ans = 0
	for i in range(n):
		buf = list(input().split())
		k, r, f = int(buf[0]), float(buf[1]), int(buf[2])
		a = a0
		if k:
			for j in range(y):
				b = (int)(a*r)
				a += b-f
		else:
			c = 0
			for j in range(y):
				b = (int)(a*r)
				a -= f
				c += b
			a += c
		ans = max(ans, a)
	print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

for _ in range(int(readline())):
    a = int(readline())
    y = int(readline())
    n = int(readline())
    ans = a
    for _ in range(n):
        t, rate, fee = [f(x) for f, x in zip((int, float, int), readline().split())]
        if t == 1:
            res = a
            for _ in range(y):
                res = res + int(res * rate) - fee
        else:
            res = a
            r = 0
            for _ in range(y):
                r += int(res * rate)
                res = res - fee
            res += r
        ans = max(ans, res)
    print(ans)

Submission status: Accepted

Solution code:
M = int(input())

def tanri(a,y,nenri,tax):
    w = 0
    for i in range(y):
        w += int(a * nenri)
        a -= tax
    return a+w
def fukuri(a, y, nenri, tax):
    for i in range(y):
        a += int(a * nenri) - tax 
    return a

for i in range(M):
    A = int(input())
    Y = int(input())
    N = int(input())
    max_ = 0
    for i in range(N):
        t, nenri, tax = list(map(float,input().split()))
        max_ = max(max_, tanri(A,Y,nenri,tax) if t == 0 else fukuri(A,Y,nenri,tax))

    print(int(max_))

Submission status: Accepted

Solution code:
trial = int(input())
for t in range(trial):
    money = int(input())
    year = int(input())
    cond = int(input())
    answer = 0
    
    for c in range(cond):
        initial = money
        bank = [float(n) for n in input().split(" ")]
        if bank[0] == 0:
            interest = 0
            for y in range(year):
                interest += int(initial * bank[1])
                initial -= bank[2]
            else:
                #print(interest + initial)
                if answer < interest + initial:
                    answer = int(interest + initial)
        else:
            for y in range(year):
                initial = initial + int(initial * bank[1] )
                initial -= bank[2]
            else:
                #print(initial)
                if answer < initial:
                    answer = int(initial)
    else:
        print(answer)

Submission status: Accepted

Solution code:
def co(a):
    global y,c,d
    for _ in range(y):a+=int(a*c)-d
    return int(a)

def i(a):
    global y,c,d
    b=0
    for _ in range(y):
        b+=int(a*c)
        a-=d
    return int(a+b)

for _ in range(int(input())):
    m=0
    a=int(input());y=int(input())
    for _ in range(int(input())):
        b,c,d=map(float,input().split())
        m=max(m,co(a) if b==1 else i(a))
    print(m)

Submission status: Accepted

Solution code:
def c(a):
    global y,r,d
    for _ in range(y):a+=int(a*r)-d
    return a

def s(a):
    global y,r,d
    b=0
    for _ in range(y):
        b+=int(a*r)
        a-=d
    return a+b

for _ in range(int(input())):
    m=0
    a=int(input());y=int(input())
    for _ in range(int(input())):
        b,r,d=map(float,input().split())
        m=max(m,c(a) if b==1 else s(a))
    print(int(m))

Submission status: Accepted

Solution code:
import sys

n = int(raw_input())
for i in xrange(n):
        im = int(raw_input())
        y = int(raw_input())
        n = int(raw_input())
        fm = 0
        for j in xrange(n):
                w, ir, c = raw_input().split()
                w, ir, c = int(w), float(ir), int(c)
                if w == 1:
                        m = im
                        for k in xrange(y):
                                m += int(m * ir)
                                m -= c
                                #print >> sys.stderr, m
                        if m > fm: fm = m
                else:
                        tmp = 0
                        m = im
                        for k in xrange(y):
                                tmp += int(m * ir)
                                m -= c
                                #print >> sys.stderr, m
                                #print >> sys.stderr, tmp
                        if m+tmp > fm: fm = m+tmp
        #print >> sys.stderr, fm
        print fm

Submission status: Accepted

Solution code:
import sys


def simple(money, rate, charge, year):
    temp = 0
    for i in xrange(year):
        temp += int(money * rate)
        money -= charge
    return money + temp

def compound(money, rate, charge, year):
    temp = 0
    for i in xrange(year):
        money += int(money * rate)
        money -= charge
    return money + temp

m = int(sys.stdin.readline())
for z in xrange(m):
    money = int(sys.stdin.readline())
    year = int(sys.stdin.readline())
    n = int(sys.stdin.readline())
    result = []
    for i in xrange(n):
        simple_or_compound, rate, charge = sys.stdin.readline().split()
        simple_or_compound = int(simple_or_compound)
        rate = float(rate)
        charge = int(charge)
        if simple_or_compound == 0:
            result.append(simple(money, rate, charge, year))
        else:
            result.append(compound(money, rate, charge, year))
    result.sort()
    print result[-1]

Submission status: Accepted

Solution code:
def simple(init,year,rate,fee):
    accum=0
    for i in range(year):
        accum+=int(init*rate)
        init-=fee
    return init+accum

def compound(init,year,rate,fee):
    for i in range(year):
        init+=int(init*rate-fee)
    return init

m=input()
for i in range(m):
    init=input()
    year=input()
    n=input()
    L=[map(float,raw_input().split()) for i in range(n)]
    maxInt=0
    for data in L:
        if data[0]==0:
            maxInt=max(maxInt,simple(init,year,data[1],data[2]))
        else:
            maxInt=max(maxInt,compound(init,year,data[1],data[2]))
    print int(maxInt)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

'''

'''

def func():
    '''

    '''

    m = int(raw_input())
    
    for num in range(m):
        init = int(raw_input())
        years = int(raw_input())
        n = int(raw_input())

        answer = 0
        for ope_num in range(n):
            operation, interest, fee = map(float, raw_input().split())
            operation = int(operation)
            if operation == 0:
                a = init
                b = 0
                for year in range(years):
                    b += (int)(a * interest)
                    a -= fee
                    #print a, b
                res = int(a + b)
            if operation == 1:
                a = init
                for year in range(years):
                    a = (int)(a * (1.0 + interest))
                    a -= fee
                    #print a
                res = int(a)

            if answer < res:
                answer = res

        print answer

    return None

if __name__ == '__main__':
    func()

Submission status: Accepted

Solution code:
for _ in range(input()):
	asset = ans = input()
	year = input()
	n = input()
	for i in range(n):
		plan,rate,cost = map(float,raw_input().split())
		if plan == 0.0:
			ans = max(ans,sum(int(rate*(asset - y*cost)) for y in range(year)) + asset - year*cost)
		else:
			cur = asset
			for y in range(year):
				cur = int(cur*(1 + rate) - cost)
			ans = max(ans,cur)
	print int(ans)

Submission status: Accepted

Solution code:
def hukuri(y, m, p, t) :
    for i in range(y) :
        m += int(m * p) - t
    return m

def tanri(y, m, p, t) :
    risoku = 0
    for i in range(y) :
        risoku += int(m * p)
        m -= t
    return m+risoku
    
M = int(input())
for i in range(M) :
    m = int(input())
    y = int(input())
    N = int(input())
    ans = []
    for j in range(N) :
        s, p, t = input().split()
        if s == '0' :
            ans.append(tanri(y, m, float(p), int(t)))
        elif s == '1' :
            ans.append(hukuri(y, m, float(p), int(t)))
    print(max(ans))

Submission status: Accepted

Solution code:
def tanri(a, y, r, c):
    o = 0
    for i in range(y):
        o += int((a-i*c)*r)
    o += a-y*c
    return o


def fukuri(a, y, r, c):
    o = a
    for i in range(y):
        o = int(o*(1+r))-c
    return o


m = int(input())
for _ in range(m):
    a = int(input())
    y = int(input())
    n = int(input())
    b = []
    for i in range(n):
        t,r,c = input().split()
        r = float(r)
        c = int(c)
        if t == '0':
            b.append(tanri(a, y, r, c))
        else:
            b.append(fukuri(a, y, r, c))
    print(max(b))

Submission status: Accepted

Solution code:
def tanri(money, year, ritu, cost):
	temp = int(year*(money+cost)*ritu)
	temp -= (ritu * cost*year*(year-1))//2
	return temp

def tanri_a(m,y,r,c):
	temp = m
	ans = 0
	for _ in range(y):
		ans += int(temp*r)
		temp -= c
	return ans + temp

def hukuri(m, y, r, c):
	temp = (m-c/r)*((1+r)**(y-1))
	return int(temp)

def hukuri_a(m, y, r, c):
	temp = m
	for i in range(y):
		temp = temp + int(temp*r) - c
	return int(temp)

def main(init_money):
	year = int(input())
	n = int(input())
	ans = 0
	for _ in range(n):
		temp = input().split()
		w, ritsu, cost = int(temp[0]), float(temp[1]), int(temp[2])
		# if w == 0: temp = tanri(init_money, year, ritsu, cost)
		# else: temp = hukuri(init_money, year, ritsu, cost)
		if w == 0: temp2 = tanri_a(init_money, year, ritsu, cost)
		else: temp2 = hukuri_a(init_money, year, ritsu, cost)
		ans = max(ans, temp2)
		# print(f"temp: {temp}, temp2: {temp2}, diff: {temp-temp2}")
	print(ans)
	return
		
n = int(input())
for _ in range(n):
	main(int(input()))

Submission status: Accepted

Solution code:
m = int(input())
for _ in range(m):
  fund = int(input())
  year = int(input())
  n = int(input())
  ans = fund
  for i in range(n):
    t, rate, fee = map(float, input().split())
    if t:
      a = fund
      b = 0
      for j in range(year):
        b = int(a*rate)
        a = a+b-fee
      ans = max(ans, a)
    else:
      a = fund
      b = 0
      for j in range(year):
        b+= int(a*rate)
        a = a-fee
      ans = max(ans, a+b)
  print(int(ans))