between.rb

def f(n)
	
	
	l = []
	while (n != 1)
		
		n = n.even? ? n / 2 : n * 3 + 1
		l << n
	end
	return l
end

def slice(a, b, s1, s2)
	
	return (((1.0 - a) * s2) ** 2 - ((1.0 - b) * s2) ** 2) / 2 

end


def balance(l, x, y, rx, ry, dx, dy)
	
	s1 = l.size

	t = 0
	l.each { |z| t += z }


	s2 = Math.sqrt(2 * t)

	rc = (rx + ry) / 2

	a1 = slice(rx, rc, s1, s2)
	a2 = slice(rc, ry, s1, s2)


	t2 = 0
	(x...y).each { |i| t2 += l[i] }
	
#	p([t, t2, rx, ry, rc, fmt3(a1), fmt3(a2)])

#	p(t2)
	a3 = 0
	
	return (x...y).map \
	{ 
		|i| 
		a3 += l[i]
		t2 -= l[i]
		d1 = a3 - a1
		d2 = t2 - a2
		[[(d1 + dx).abs, (d2 + dy).abs].max, d1, d2, i, a3, t2]
	}.min
		
end

def maxdiff(l, xy)
	x, y = xy
	return ((x + 1)...y).map { |i| (l[i] - l[i - 1]).abs }.max
end

def fmt3(x)
	sprintf('%.3f', x).to_f
end

def branch(l, s)

	s = s.dup
	while (s != '')
		l = (s[0, 1] == '0') ? l[0] : l[1]
		s[0, 1] = ''
	end
	return nil if (l[0] >= l[1] - 1)
	return l
end


def at(b)
	rx = 0.0
	ry = 1.0
	
	b = b.dup
	while (b != '') 
		if (b[0, 1] == '0') then
			ry = (rx + ry) / 2
		else
			rx = (rx + ry) / 2
		end
		b[0, 1] = ''
	end
	return rx, ry
end

def walk(t, b)

	bm = ''
	t.each \
	{
		|x|
	
		b1 = ''
		b2 = b.dup
		l = []
		
		while (b2 != '') 
			break if (x[0].is_a?(Integer))
			l << x
			x = (b2[0, 1] == '0') ? x[0] : x[1]
			b1 += b2[0, 1]
			b2[0, 1] = ''
		end

		if (b2 == '') then
			if (x[0].is_a?(Integer)) then
				while (b1[-1, 1] == '1')
					b1[-1, 1] = '' 
					x = l.pop
				end
				return nil if (b1 == '')
				b1[-1, 1] = '1'
			end
			
			while (x[0].is_a?(Array))
				
				x = x[0]
				b1 += '0'
			end
		end
#		p(x)
		bm = [bm, b1].max
	}
	return bm
	
end

def adj(t, l2)
	

	bs = ['']

	while (!bs.empty?)
		
		b = bs.shift
		
		ex = ey = 0
		f = false
		z = (0...l2.size).map { |i| [i, branch(t[i], b)] }.select { |i, xy| xy != nil }
		z.sort_by { |i, xy| maxdiff(l2[i], xy) }.reverse.each \
		{
			|i, xy|
			
			l = l2[i]
			
			x, y = xy
			
			rx, ry = at(b)
					
			
			z = balance(l, x, y, rx, ry, ex, ey)

			c = z[3]
			dx = z[1]
			dy = z[2]
			ex += dx
			ey += dy
			
			xy2 = xy.dup
			xy[0] = [x, c + 1]
			xy[1] = [c + 1, y]
	#		p([xy2, '=>', xy, fmt3(dx), fmt3(dy), fmt3(ex), fmt3(ey)])
			f = true
		}
		
		if (f) then
	#		p([b, ex, ey])
			bs << b + '0'
			bs << b + '1'
		end

	end
		
end

def cut(b, t, l2)
	
	c = 0
	l2.each_with_index \
	{
		|l, i|
		x = t[i] 
		b2 = b.dup
		while (b2 != '')
			break if (x[0].is_a?(Integer))
			x = (b2[0, 1] == '0') ? x[0] : x[1]
			b2[0, 1] = ''
		end
		l2 = x.flatten
		x, y = l2[0], l2[-1]
		l[x...y].each { |z| c += z }
	}
	return c
	
end

def adv(t, l2)
	
	b = ''
	loop \
	{
		b = walk(t, b)
		break if (b.nil?)
		
		c = cut(b, t, l2)
		puts([b, c].join("\t"))
	}

end

def adv2(t, l2, w)
	
	i = 0
	loop \
	{
		b = sprintf("%0#{w}b", i)
		break if (b.length > w)
		puts([b, cut(b, t, l2)].join("\t"))
		i += 1
	}
	
end

x, y = ARGV.map { |z| z.to_i }

n = 3
l2 = []
t = []
x.times \
{
	l2 << f(n)
	t << [0, l2[-1].size]
	n += 2
}

adj(t, l2)

#adv(t, l2)

adv2(t, l2, y)