Problem: http://nabetani.sakura.ne.jp/hena/orde11tredis/ Implementation links: http://qiita.com/Nabetani/items/10b2ccc28301e44e09e6
First, implement ruby.
def each_item(n, list)
yield( list )
(2..(n/2)).each do |x|
next unless n % x==0
each_item( x+1, list+[x+1] ){ |y| yield(y) }
end
end
def dist(a,b)
a.size+b.size - 2*(0..Float::INFINITY).find{ |x| a[x] != b[x] }
end
def impl( root, a, b )
as=[]
bs=[]
each_item(root,[root]){ |x|
as<<x if x.last==a
bs<<x if x.last==b
}
as.inject(Float::INFINITY) do |d0, ai|
bs.inject(d0) do |d1, bi|
d1=[d1, dist(ai,bi)].min
end
end
end
def solve( src )
impl( *src.split(/\D+/).map(&:to_i) ).to_s
end
DATA.map{ |line|
num, src, expected = line.split( /\s+/ )
actual = solve( src )
ok = actual==expected
puts [ num, ( ok ? "ok" : "**NG**" ), src, actual, expected ].join( " " )
ok
}.all?.tap{ |x| p( x ? "all okay!" : "something wrong!!" ) }
__END__
0 50:6,3 1
1 98:5,11 4
2 1000:33,20 7
To find the divisor, omit O (n).
The strategy. You can find the distance by comparing the list from the route to yourself.
I don't like the area around ʻeach_item, but it can't be helped. I'm not used to defining my own method of yield` or block arguments yet.
so. I ported this to python below:
import re
def each_item(n,list) :
yield( list )
for x in range( 2, n//2+1 ) :
if n % x == 0 :
for item in each_item( x+1, list + [x+1] ):
yield(item)
def dist(a,b):
n=0
while n<len(a) and n<len(b) and a[n]==b[n]:
n+=1
return len(a) + len(b) - 2*n
def impl( root, a, b ) :
a_s=[]
b_s=[]
for item in each_item(root, [root]) :
if item[-1]==a:
a_s.append( item )
if item[-1]==b:
b_s.append( item )
d=1e100
for a in a_s:
for b in b_s:
d = min( d, dist(a,b) )
return d
def solve( src ):
root, a, b = [ int(x) for x in re.split( "\\D", src ) ]
return "%d" % ( impl( root, a, b ) )
def test( src, expected ):
actual = solve( src )
ok= ( actual==expected )
print( "%s : %s -> %s ( %s )" % ( ("ok" if ok else "**NG**"), src, actual, expected ) )
test( "50:6,3", "1" )
test( "98:5,11", "4" )
test( "1000:33,20", "7" )
I was confused about using python yield for the first time in my life, but it felt the same.
Recommended Posts