document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. __author__ = \'charles\'
  2.  
  3. inputFile = "A-large-practice.in"
  4. outputFile = inputFile + ".out"
  5.  
  6. class ShopCredit(object):
  7.  
  8.     def __init__(self, credit, items):
  9.         self.credit = int(credit)
  10.         self.items = [int(y) for y in items.split(\' \')]
  11.  
  12.     def DisplayCase(self):
  13.         print "Case : Cred [" + str(self.credit) + "], items " + str(self.items)
  14.  
  15.     def solveCase(self):
  16.         #inverted index (dictionary of price to list position
  17.         priceIndex = {}
  18.         for n in range(0, len(self.items)):
  19.             p = self.items[n]
  20.  
  21.             if p in priceIndex.keys():
  22.                 priceIndex[int(p)].append(n)
  23.             else:
  24.                 priceIndex[int(p)] = [n]
  25.  
  26.  
  27.         # now iterate the list and try and find a match in the index
  28.         for n in range(0, len(self.items)):
  29.             if self.items[n] < self.credit:
  30.                 lookingFor = self.credit - self.items[n]
  31.                 if lookingFor in priceIndex.keys():
  32.                     for l in priceIndex[lookingFor]:
  33.                         if l > n:
  34.                             return (str(n + 1) + " " + str(l + 1))
  35.  
  36.  
  37. def extractTestCases(filename):
  38.  
  39.     with open(filename, \'r\') as f:
  40.         fileContents = (f.read().splitlines())
  41.         f.close()
  42.  
  43.     cases = []
  44.     for c in range(0,int(fileContents[0])):
  45.         caseIndex = c*3
  46.         cases.append(ShopCredit(fileContents[caseIndex+1], fileContents[caseIndex+3]))
  47.  
  48.     return cases
  49.  
  50.  
  51. def main():
  52.  
  53.     cases = extractTestCases(inputFile)
  54.  
  55.     with open(outputFile, "w") as w:
  56.         for n in range(0, len(cases)):
  57.             case = cases[n]
  58.             w.write("Case #" + str(n + 1) + ": " + case.solveCase() + "\\n")
  59.  
  60. if __name__ == "__main__":
  61.     main()
');