์ฒซ์งธ ¶
~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