Problème: http://nabetani.sakura.ne.jp/hena/orde11tredis/ Liens d'implémentation: http://qiita.com/Nabetani/items/10b2ccc28301e44e09e6
J'ai fait d'un nœud dans l'arbre une classe. Comme de nombreux nœuds avec la même valeur apparaissent, j'ai également créé une version avec cache.
E11.py(Pas de version de cache)
class Node:
def __init__(self, number):
self.number = number
self.children = [Node(i + 1)
for i in range(2, number // 2 + 1)
if number % i == 0]
def distances(self, number):
if number > self.number: return []
if number == self.number: return [0]
return [distance + 1
for child in self.children
for distance in child.distances(number)]
def distances_between(self, a, b):
distances_in_children = [distance
for child in self.children
for distance in child.distances_between(a, b)]
da, db = self.distances(a), self.distances(b)
distance_across_self = [min(da) + min(db)] if da and db else []
return distances_in_children + distance_across_self
def distance_between(self, a, b):
return min(self.distances_between(a, b))
def solve(data):
root, ab = data.split(':')
a, b = map(int, ab.split(','))
return str(Node(int(root)).distance_between(a, b))
def test(no, data, correct):
answer = solve(data)
result = "OK" if answer == correct else "NG"
print result, '%2d' % no, data, correct, '->', answer
if __name__ == '__main__':
test( 0, "50:6,3", "1" );
test( 1, "98:5,11", "4" );
test( 2, "1000:33,20", "7" );
test( 3, "514:9,18", "8" );
test( 4, "961:5,4", "3" );
test( 5, "1369:1369,3", "2" );
test( 6, "258:16,12", "5" );
test( 7, "235:13,3", "2" );
test( 8, "1096:19,17", "8" );
test( 9, "847:7,17", "6" );
test(10, "1932:3,5", "2" );
test(11, "2491:4,8", "3" );
test(12, "840:421,36", "2" );
test(13, "1430:37,111", "3" );
test(14, "496:17,9", "2" );
test(15, "891:6,10", "1" );
test(16, "1560:196,21", "2" );
test(17, "516:20,12", "5" );
test(18, "696:30,59", "2" );
test(19, "1760:5,441", "2" );
test(20, "1736:11,26", "5" );
test(21, "1518:17,34", "4" );
test(22, "806:63,16", "5" );
test(23, "1920:3,97", "2" );
test(24, "1150:13,22", "4" );
test(25, "920:116,5", "1" );
test(26, "2016:7,337", "2" );
test(27, "408:9,25", "2" );
test(28, "735:36,8", "2" );
test(29, "470:5,31", "2" );
test(30, "2100:12,351", "3" );
test(31, "870:36,10", "1" );
test(32, "1512:253,13", "2" );
test(33, "697:12,15", "3" );
test(34, "1224:5,14", "2" );
test(35, "986:125,17", "3" );
test(36, "864:12,13", "3" );
test(37, "500:21,51", "2" );
test(38, "819:33,21", "4" );
test(39, "594:55,3", "2" );
test(40, "638:17,24", "3" );
E11.py(Version avec cache)
class Node:
cache = {}
@staticmethod
def get(number):
if number in Node.cache: return Node.cache[number]
Node.cache[number] = node = Node(number)
return node
def __init__(self, number):
self.number = number
self.children = [Node.get(i + 1)
for i in range(2, number // 2 + 1)
if number % i == 0]
def distances(self, number):
if number > self.number: return []
if number == self.number: return [0]
return [distance + 1
for child in self.children
for distance in child.distances(number)]
def distances_between(self, a, b):
distances_in_children = [distance
for child in self.children
for distance in child.distances_between(a, b)]
da, db = self.distances(a), self.distances(b)
distance_across_self = [min(da) + min(db)] if da and db else []
return distances_in_children + distance_across_self
def distance_between(self, a, b):
return min(self.distances_between(a, b))
def solve(data):
number, ab = data.split(':')
a, b = map(int, ab.split(','))
return str(Node.get(int(number)).distance_between(a, b))
def test(no, data, correct):
answer = solve(data)
result = "OK" if answer == correct else "NG"
print result, '%2d' % no, data, correct, '->', answer
if __name__ == '__main__':
test( 0, "50:6,3", "1" );
test( 1, "98:5,11", "4" );
test( 2, "1000:33,20", "7" );
test( 3, "514:9,18", "8" );
test( 4, "961:5,4", "3" );
test( 5, "1369:1369,3", "2" );
test( 6, "258:16,12", "5" );
test( 7, "235:13,3", "2" );
test( 8, "1096:19,17", "8" );
test( 9, "847:7,17", "6" );
test(10, "1932:3,5", "2" );
test(11, "2491:4,8", "3" );
test(12, "840:421,36", "2" );
test(13, "1430:37,111", "3" );
test(14, "496:17,9", "2" );
test(15, "891:6,10", "1" );
test(16, "1560:196,21", "2" );
test(17, "516:20,12", "5" );
test(18, "696:30,59", "2" );
test(19, "1760:5,441", "2" );
test(20, "1736:11,26", "5" );
test(21, "1518:17,34", "4" );
test(22, "806:63,16", "5" );
test(23, "1920:3,97", "2" );
test(24, "1150:13,22", "4" );
test(25, "920:116,5", "1" );
test(26, "2016:7,337", "2" );
test(27, "408:9,25", "2" );
test(28, "735:36,8", "2" );
test(29, "470:5,31", "2" );
test(30, "2100:12,351", "3" );
test(31, "870:36,10", "1" );
test(32, "1512:253,13", "2" );
test(33, "697:12,15", "3" );
test(34, "1224:5,14", "2" );
test(35, "986:125,17", "3" );
test(36, "864:12,13", "3" );
test(37, "500:21,51", "2" );
test(38, "819:33,21", "4" );
test(39, "594:55,3", "2" );
test(40, "638:17,24", "3" );
Résultat d'exécution
$ python E11.py
OK 0 50:6,3 1 -> 1
OK 1 98:5,11 4 -> 4
OK 2 1000:33,20 7 -> 7
OK 3 514:9,18 8 -> 8
OK 4 961:5,4 3 -> 3
OK 5 1369:1369,3 2 -> 2
OK 6 258:16,12 5 -> 5
OK 7 235:13,3 2 -> 2
OK 8 1096:19,17 8 -> 8
OK 9 847:7,17 6 -> 6
OK 10 1932:3,5 2 -> 2
OK 11 2491:4,8 3 -> 3
OK 12 840:421,36 2 -> 2
OK 13 1430:37,111 3 -> 3
OK 14 496:17,9 2 -> 2
OK 15 891:6,10 1 -> 1
OK 16 1560:196,21 2 -> 2
OK 17 516:20,12 5 -> 5
OK 18 696:30,59 2 -> 2
OK 19 1760:5,441 2 -> 2
OK 20 1736:11,26 5 -> 5
OK 21 1518:17,34 4 -> 4
OK 22 806:63,16 5 -> 5
OK 23 1920:3,97 2 -> 2
OK 24 1150:13,22 4 -> 4
OK 25 920:116,5 1 -> 1
OK 26 2016:7,337 2 -> 2
OK 27 408:9,25 2 -> 2
OK 28 735:36,8 2 -> 2
OK 29 470:5,31 2 -> 2
OK 30 2100:12,351 3 -> 3
OK 31 870:36,10 1 -> 1
OK 32 1512:253,13 2 -> 2
OK 33 697:12,15 3 -> 3
OK 34 1224:5,14 2 -> 2
OK 35 986:125,17 3 -> 3
OK 36 864:12,13 3 -> 3
OK 37 500:21,51 2 -> 2
OK 38 819:33,21 4 -> 4
OK 39 594:55,3 2 -> 2
OK 40 638:17,24 3 -> 3
Recommended Posts