4 3 3 3
3 -1 2
-1 -1 -1
3 12 7
The first row contains some stupid numbers showing different things, because the solution of this problem is supposed to be written in C, but hey fuck C and it's stupid libraries ( this from a guy who makes a living like a professional C programmer - me ) The most important number from the first row is the second one which shows the time ticks the burglars have before the cops show up. The rest of the numbers say what's the array height and width (useless in python and in fact in C if you take the time to code is right).
Now the rules are simple. The burglars have the map so they know where the treasures are. Each treasure is represented by a positive number showing the amount of money the gain when they reach it. The cells with negative numbers does not contain treasures and they cost money to be dug. Each cell is dug for one tick time. The cops will come in K ticks of time where K is the second number in the first row. In order to get to a cell the burglars must dug out all the cell in it's column prior to it. The burglars may start from any column and stop digging within the column whenever they want.
Make a program that finds the maximum amount of money the burglars can gain without being caught from the cops.
He he, me lazy so code in python.
#!/usr/bin/env python
import os, sys
K = 0 # edinici vreme, broi kletki koito mogat da izkopaqt
def GetData(file=''):
f = open(file, 'r')
data = f.readlines()
f.close()
params = []
for i in data[0].split():
params.append(int(i))
data = data[1:data.__len__()]
array = []
for d in data:
array.append(d.split())
return (params, array)
class PreData:
def __init__(self, t=0, m=0):
self.time = t
self.money = m
def __repr__(self):
return 'Time: '+str(self.time)+' Money: '+str(self.money)
def __str__(self):
return 'Time: '+str(self.time)+' Money: '+str(self.money)
def GetPreData():
columns = []
tmpK = 0
tmpAward = 0
r = 0
c = 0
global K
((N,K,L,D), data) = GetData('input')
for c in xrange(0, L):
treasures = []
tmpC = PreData(0,0)
for r in xrange(0, D):
tmpC.time = tmpC.time + 1
tmpC.money = tmpC.money + int(data[r][c])
if int(data[r][c]) > 0:
if tmpC.time > int(K):
break
if tmpC.money > 0:
treasures.append(PreData(tmpC.time, tmpC.money))
tmpC.time = 0
tmpC.money = 0
columns.append(treasures)
return columns
maxMoney=0
def Recursion(cols=[], c=0, r=0, money=0, time=0):
global maxMoney
if c >= cols.__len__():
return
if r >= cols[c].__len__():
return
if (cols[c][r].time+time) > K:
return
cmoney = money + cols[c][r].money
ctime = time + cols[c][r].time
if maxMoney < cmoney:
maxMoney = cmoney
Recursion(cols, c + 1, r, cmoney , ctime )
Recursion(cols, c, r + 1, cmoney , ctime )
cols = GetPreData()
for i in range(0, cols.__len__()):
Recursion(cols, i, 0, 0, 0)
print maxMoney
Now test it!
serj@tokamak ~> cat input
4 3 3 3
3 -1 2
-1 -1 -1
3 12 7
serj@tokamak ~> ./stamen.py
10
Now test it again.
serj@tokamak ~> cat input; ./stamen.py
4 3 3 3
3 -1 24
-1 -1 -1
3 12 7
30
Yes it wErks! :-D
