bunch26.rb

def f1(n)
	n = (n * 3 + 1) / 2 while (n.odd?)
	n /= 2 while (n.even?)
	return n
end

def sum(l)
	t = 0
	l.each { |x| t += x }
	return t
end



def smooth(n)
	

	n1 = n
	l = []

	500.times { l << [n, n2 = f1(n), n2 - n]; n += 2 }

	seen = {1=>nil}
	y = t2 = m = 0
	l1 = []
	begin
		j = (0...l.size).min_by { |x| l[x][2] }
		
		if (l[j][2] >= 0) then
			z = l.delete_at(j)
			
			if (!seen.member?(z[1])) then
				seen[z[1]] = nil
				l << [z[1], n2 = f1(z[1]), n2 - z[1]]
			end
		else
		
			l2 = (0...l.size).select { |x| l[x][2] < 0 }.sort_by { |x| l[x][2] }.reverse
			tn = sum(l2.map { |x| l[x][2] })
			
			j = (0...l.size).select { |x| l[x][2] + tn < 0 }.max_by { |x| l[x][2] }
			
			
			tp = l[j][2]

			i = 0
			begin
				if (tp + (tn - l[l2[i]][2]) < 0) then
					tn -= l[l2[i]][2]
					l2.delete_at(i)
					next
				end
				i += 1
			end while (i < l2.size)

			l2 << j
			l2.sort.reverse.each \
			{
				|x|
				z = l.delete_at(x)
				next if (seen.member?(z[1]))
				seen[z[1]] = nil
				l << [z[1], n2 = f1(z[1]), n2 - z[1]]
			}
			
		end
		
		t = sum(l.map { |x| x[0] })
		m += 1 if (t > t2)
		t2 = t
#		puts([y, t, l.size, l.select { |x| x[0] >= n1 }.size, m.to_f / (y + 1)].join("\t"))
		l1 << t
		y += 1
	end while (!l.select { |x| x[0] >= n1 }.empty?)
	return l1
end

def mx(a, b)
	a.nil? ? b : [a, b].max
end

def mn(a, b)
	a.nil? ? b : [a, b].min
end

def nonmono(l)
	
	mn = nil
	r = nil
	l.each_with_index \
	{
		|d, i|
		d1 = d.abs
		mn = mn(mn, [d1, i])
		r = mx(r, i - mn[1])
	}
	return r

end

def dense(n)
 
        s = n.to_s(2)
        c = 0
        s.length.times \
        {
                |i|
                c += s[i, 1].to_i
        }
        return c.to_f / s.length
 
end

def widthdiff(x, y)
        x.to_s(2).length - y.to_s(2).length
 
end

def widthratio(x, y)
        x.to_s(2).length.to_f / y.to_s(2).length
end

def f(n, w)
 
        n1 = n
        c = 0
	l = [n]
	cg = nil
	
        while (n != 1)
		n = f1(n)

		l << n
                c += 1
	
		cg = c if (cg.nil? && n < n1)

		break if (!cg.nil? && w != 'c')
        end
	cm = (0...l.size).max_by { |x| l[x] }
	
        return {'cm' => cm,
		'cg' => cg.nil? ? 0 : cg, 
		'm' => l[cm].to_s(2).length,
		'w' => widthdiff(l[cm], n1),
		'r' => widthratio(l[cm], n1),
		'c' => l.size,
		'd' => (0.5 - dense(n1)).abs}
 
end

def long(m, w)
 
	return {'n' => rand(2 ** m) | 1 } if (w == 'z')
		
        l = [{'n' => 1, 'p' => 0}.merge(f(1, w))]
        t = 0
	e = 2000
	
        loop \
        {
                l = l.sort_by { |x| [x[w], -x['d']] }.reverse
 
                x = l.delete_at(rand([l.size, 20].min))
 
                p2 = x['p'] + 1
                n2 = x['n'] + 2 ** p2
 
 
                x1 = x.dup
                x1['p'] = p2
                l << x1
 
                x2 = {'n' => n2, 'p' => p2}.merge(f(n2, w))
                l << x2
                t += 1
 
		w2 = w
		if (w == 'r') then
			z = l.sort_by { |x| x['n'] }.reverse[0...100].max_by { |x| x['r'] }
			w2 = 's'
		else
			z = l.max_by { |x| x[w] }
		end
		z.merge!({ 't' => t, 's' => t.to_f / e })
		
                return z if (z[w2] >= m)
		
                return if (t >= e)
        }
 
end

def test(p, k, m)
	r = p[k]
	a, b, c = r
	
	return if (c && m >= 1.0)
	
	x = a + m * (b - a)
	z = long(x, k)
	$c1 += 1
	return if (z.nil?)
	$c2 += 1
	
	n = z['n']
	return if ($a.member?(n))
	$c3 += 1
	
	$a[n] = nil
	
	$stderr.puts([$c1, $c2, $c3, k, r2(m), r2(x), z['s'], n.to_s(2)].inspect)
	puts(nonmono(smooth(n)))
	$stdout.flush
end

def r2(x)
	sprintf("%.2f", x).to_f
end

p = {'w' => [0, 80, false],
	'p' => [0, 350, false],
	'c' => [0, 550, false],
	'm' => [0, 300, false],
	'cg' => [0, 140, false],
	'cm' => [0, 50, false],
	'r' => [0.0, 1.0, true],
	'z' => [0, 1000, true],
	}

p.keys.each \
{
	|k|
	$a = {}
	$c1 = $c2 = $c3 = 0
	100.times \
	{
		|w|
		test(p, k, w / 100.0)
	}
}