~cpp
import unittest
class WeightsAndMeasures:
def __init__(self):
self.dataList = []
self.stack = []
def inputEachData(self, weight, strength):
self.dataList.append([weight, strength, strength-weight])
return self.dataList
def putInStack(self, i):
self.stack.append(self.dataList[i][:])
return self.stack
def findNextDataIndex(self):
lastCapacity = self.stack[len(self.stack)-1][2]
nextDataIndex = -1
maxCapacity = 0
minWeight = 0
for each in self.dataList:
weight, capacity = each[0], each[2]
if not self.isInStack(weight) and
weight <= lastCapacity and capacity >= maxCapacity:
if capacity == maxCapacity and capacity != 0:
if weight < minWeight:
minWeight = weight
nextDataIndex = self.dataList.index(each)
continue
maxCapacity = capacity
minWeight = weight
nextDataIndex = self.dataList.index(each)
return nextDataIndex
def isInStack(self, aWeight):
for each in self.stack:
weight = each[0]
if weight == aWeight:
return True
return False
def computeCapacity(self):
end = len(self.stack) - 1
for each in self.stack:
if self.stack.index(each) < end:
each[2] -= self.stack[end][0]
return self.stack
def canStack(self):
for each in self.stack:
capacity = each[2]
if capacity <= 0:
return False
return True
def findMaxTurtle(self):
size = -1
for each in range(len(self.dataList)):
self.putInStack(each)
while True:
next = self.findNextDataIndex()
if self.isInStack(self.dataList[next][0]):
break
else:
self.putInStack(next)
self.computeCapacity()
if not self.canStack():
break
if len(self.stack) > size:
size = len(self.stack)
self.stack = []
return size
class WeightsAndMeasuresTestCase(unittest.TestCase):
def setUp(self):
self.wam = WeightsAndMeasures()
def testInputEachData(self):
self.assertEquals([[300, 1000, 700]], self.wam.inputEachData(300, 1000))
self.assertEquals([[300, 1000, 700],
[1000, 1200, 200]
], self.wam.inputEachData(1000, 1200))
self.assertEquals([[300, 1000, 700],
[1000, 1200, 200],
[200, 600, 400]
], self.wam.inputEachData(200, 600))
def testPutInStack(self):
self.wam.inputEachData(300, 1000)
self.wam.inputEachData(1000, 1200)
self.wam.inputEachData(200, 600)
self.assertEquals([[300, 1000, 700]], self.wam.putInStack(0))
def testFindNextDataIndex(self):
self.wam.inputEachData(300, 1000)
self.wam.inputEachData(1000, 1200)
self.wam.inputEachData(200, 600)
self.wam.putInStack(0)
self.wam.putInStack(0)
self.assertEquals(2, self.wam.findNextDataIndex())
def testNext(self):
self.wam.inputEachData(300, 1000)
self.wam.inputEachData(1000, 1200)
self.wam.inputEachData(200, 600)
self.wam.putInStack(0)
nextIndex = self.wam.findNextDataIndex()
self.assertEquals([[300, 1000, 700],
[200, 600, 400]
], self.wam.putInStack(nextIndex))
self.assertEquals([[300, 1000, 500],
[200, 600, 400],
], self.wam.computeCapacity())
self.assertEquals(True, self.wam.canStack())
def testOneData(self):
turtle = [(300, 1000), (1000, 1200), (200, 600), (100, 101)]
for data in turtle:
self.wam.inputEachData(data[0], data[1])
self.assertEquals(3, self.wam.findMaxTurtle())
def testOneData2(self):
turtle = [(500, 700), (200, 400), (1100, 1300), (5400, 7900),
(10, 20), (1, 10), (700, 9000), (100, 200)]
for data in turtle:
self.wam.inputEachData(data[0], data[1])
self.assertEquals(6, self.wam.findMaxTurtle())
def testOneData3(self):
turtle = [(10000, 60000), (20000, 70000), (9000, 59000),
(600, 90000), (800, 800), (900, 7000)]
for data in turtle:
self.wam.inputEachData(data[0], data[1])
self.assertEquals(6, self.wam.findMaxTurtle())
if __name__ == '__main__':
## unittest.main()
wam = WeightsAndMeasures()
while True:
data = raw_input()
if not data:
break
weight, strength = map(int, data.split())
wam.inputEachData(weight, strength)
print wam.findMaxTurtle()