첫째 ¶
~cpp class AOI3nPlus1ProblemRunner: def getMaximumCycleLength(self, aFrom, aTo): max = 0 for i in range( aFrom, aTo + 1): cycleLength = self.getCycleLength(i) if max < cycleLength: max = cycleLength return max def getCycleLength( self, aStart ): n = aStart cycleLength = 1 while n is not 1: cycleLength = cycleLength + 1 if n % 2 is not 0: n = 3 * n + 1 else: n = n / 2 return cycleLength def run(self): numFrom = input("") numTo = input("") print self.getMaximumCycleLength(numFrom, numTo) ######################################################################### import unittest class AOI3nPlus1ProblemTestCase(unittest.TestCase): def setUp(self): self.runner = AOI3nPlus1ProblemRunner() def testGetMaximumCycleLength(self): self.assertEquals( 1, self.runner.getMaximumCycleLength( 1, 1 ) ) self.assertEquals( 20, self.runner.getMaximumCycleLength( 1, 10 ) ) self.assertEquals( 125, self.runner.getMaximumCycleLength( 100, 200 ) ) self.assertEquals( 89, self.runner.getMaximumCycleLength( 201, 210 ) ) self.assertEquals( 174, self.runner.getMaximumCycleLength( 900, 1000) ) def testGetCycleLength(self): self.assertEquals( 1, self.runner.getCycleLength(1) ) self.assertEquals( 5, self.runner.getCycleLength(16) ) self.assertEquals( 16, self.runner.getCycleLength(22) ) ######################################################################### if __name__ == '__main__': ## unittest.main() AOI3nPlus1ProblemRunner().run()
둘째 ¶
~cpp import psyco MAXIMUM = 10000 class AOI3nPlus1ProblemRunner: def __init__(self): self.cycleLens = {} def getMaximumCycleLen(self, aFrom, aTo): maximum = 0 for i in range( aFrom, aTo + 1): if self.getCycleLen(i) > maximum: maximum = self.getCycleLen(i) self.cycleLens[i] = maximum return maximum def getCycleLen( self, n ): if n not in self.cycleLens: self.storeCycleLen( n ) return self.getStoredCycleLen(n) def run(self): numFrom = input("") numTo = input("") print self.getMaximumCycleLen(numFrom, numTo) def storeCycleLen(self, aN): n = aN cycleLen = 1 while n is not 1: if n in self.cycleLens: cycleLen = cycleLen + self.cycleLens[n] - 1 break cycleLen += 1 if n % 2 is not 0: n = 3 * n + 1 else: n = n / 2 self.cycleLens[aN] = cycleLen def getStoredCycleLen(self, aN): if aN not in self.cycleLens: return 0 return self.cycleLens[aN] ######################################################################### import unittest class AOI3nPlus1ProblemTestCase(unittest.TestCase): def setUp(self): self.runner = AOI3nPlus1ProblemRunner() def testGetMaximumCycleLen(self): self.assertEquals( 1, self.runner.getMaximumCycleLen( 1, 1 ) ) self.assertEquals( 20, self.runner.getMaximumCycleLen( 1, 10 ) ) self.assertEquals( 125, self.runner.getMaximumCycleLen( 100, 200 ) ) self.assertEquals( 89, self.runner.getMaximumCycleLen( 201, 210 ) ) self.assertEquals( 174, self.runner.getMaximumCycleLen( 900, 1000) ) def testGetCycleLen(self): self.assertEquals( 1, self.runner.getCycleLen(1) ) self.assertEquals( 5, self.runner.getCycleLen(16) ) self.assertEquals( 16, self.runner.getCycleLen(22) ) def testStoreCycles(self): self.assertEquals( 0, self.runner.getStoredCycleLen(0) ) self.runner.storeCycleLen(22) self.assertEquals( 16, self.runner.getStoredCycleLen(22) ) def testTime(self): # goal = 999,999 in 4 sec self.runner.getMaximumCycleLen(1,MAXIMUM) ## self.runner.getCycleLen(MAXIMUM) self.runner.storeCycleLen(MAXIMUM) ######################################################################### if __name__ == '__main__': psyco.full() unittest.main(argv=('','-v')) ## AOI3nPlus1ProblemRunner().run()
셋째 ¶
~cpp # 45m after tuning # total = 3h 11m 11s import unittest TEST_MAX = 100000 MAX = 1000000 ##TEST_MAX = MAX - 1 storedCycleLens = [0] * MAX CUTOFF = 100 def preProcessing(): i = 1 cycleLen = 1 while i < MAX: storedCycleLens[i] = cycleLen cycleLen += 1 i *= 2 def getCycleLen(aN): n = aN result = 1 while n != 1: result += 1 if n % 2 != 0: result += 1 n = (3*n+1) / 2 else: n /= 2 if n < MAX and\ storedCycleLens[n] != 0: result += storedCycleLens[n] - 1 break ## if getStoredCycleLen(n) is not 0: ## return getStoredCycleLen(n) + result - 1 return result def storeCycleLen(aN): storedCycleLens[aN] = getCycleLen(aN) def getStoredCycleLen(aN): if aN < 0 or aN >= MAX: return 0 return storedCycleLens[aN] def getMaxCycleLen(aStart, aEnd): maximum = 0 interval = 1 if CUTOFF < aEnd - aStart: interval = 2 if aStart % 2 == 0: aStart -= 1 for n in range(aStart, aEnd+1, interval): cycleLen = getCycleLen(n) if maximum < cycleLen: maximum = cycleLen storedCycleLens[n] = cycleLen return maximum class MyTestCase(unittest.TestCase): def testGetCycleLen(self): tests = [(1,1), (9,20), (16,5), (MAX-1,259)] for n, expected in tests: self.assertEquals( expected, getCycleLen(n) ) for n in range(MAX-1000, MAX): getCycleLen(n) def testgetMaxCycleLen(self): tests = [(1,1,1), (1,16,20), (900,1000,174), (1,1000,179)] for start, end, expected in tests: self.assertEquals(expected, getMaxCycleLen( start, end ) ) def testStoreCycleLen(self): tests = [(1,1), (16,5), (MAX-1,259)] for n, expected in tests: storeCycleLen( n ) self.assertEquals( expected , getStoredCycleLen(n) ) def testTime(self): getMaxCycleLen(1, TEST_MAX) ## self.assertEquals(525, getMaxCycleLen(1, MAX)) if __name__ == '__main__': preProcessing() ## unittest.main() timeTest = MyTestCase("testTime") runner = unittest.TextTestRunner() runner.run(timeTest)
Thread ¶
절대 쉽지 않은 문제였다. 아직 수행시간이 턱없이 길다. 사전형 멤버를 이용해 계산했던 부분은 저장해두어 다시 쓰도록 하였다. 답답하다. PsyCo라는 모듈을 새롭게 알알게되었다. --Leonardong
셋째 코드에서 해본 새로운 시도는 다음과 같다.
셋째 코드에서 해본 새로운 시도는 다음과 같다.
- MAX(100000)개의 원소를 가진 리스트에 계산했던 CycleLength를 저장한다.
- 3n+1은 항상 짝수이므로 짝수 검사를 한 번 건너뛴다.
- 2의 제곱수들은 CycleLength를 예상할 수 있으므로 입력 받기 전에 미리 계산해둔다.
- CycleLength를 구하는 과정에서 n이 짝수일 때만 저장된 값이 있는지를 검사한다.
- 구하는 범위가 Cutoff보다 크면 시작하는 수가 홀수일 때 CycleLength가 클 것이므로 홀수부터 시작해서 짝수는 무시하고 구한다.
확신이 가지 않는 cutoff부분을 빼더라도 PsyCo를 쓰면 2초 안에 통과한다. 3시간 동안 10초 정도를 줄였는데, 10분만에 10초를 줄였다. 시간을 줄여야 하는데 정말 수가 안 떠오르면 PsyCo가 꽤 도움이 될 것이다. 남용은 조심해야겠다.--Leonardong