__author__ = \'charles\'
inputFile = "A-large-practice.in"
outputFile = inputFile + ".out"
class ShopCredit(object):
def __init__(self, credit, items):
self.credit = int(credit)
self.items = [int(y) for y in items.split(\' \')]
def DisplayCase(self):
print "Case : Cred [" + str(self.credit) + "], items " + str(self.items)
def solveCase(self):
#inverted index (dictionary of price to list position
priceIndex = {}
for n in range(0, len(self.items)):
p = self.items[n]
if p in priceIndex.keys():
priceIndex[int(p)].append(n)
else:
priceIndex[int(p)] = [n]
# now iterate the list and try and find a match in the index
for n in range(0, len(self.items)):
if self.items[n] < self.credit:
lookingFor = self.credit - self.items[n]
if lookingFor in priceIndex.keys():
for l in priceIndex[lookingFor]:
if l > n:
return (str(n + 1) + " " + str(l + 1))
def extractTestCases(filename):
with open(filename, \'r\') as f:
fileContents = (f.read().splitlines())
f.close()
cases = []
for c in range(0,int(fileContents[0])):
caseIndex = c*3
cases.append(ShopCredit(fileContents[caseIndex+1], fileContents[caseIndex+3]))
return cases
def main():
cases = extractTestCases(inputFile)
with open(outputFile, "w") as w:
for n in range(0, len(cases)):
case = cases[n]
w.write("Case #" + str(n + 1) + ": " + case.solveCase() + "\\n")
if __name__ == "__main__":
main()