Problema número 136

Encadenando trolls

Tiempo máximo: 1,000-5,000 sMemoria máxima: 4096 KiB
-Y antes que amanezca cambiará al este − dijo Legolas − Pero descansad, si tenéis que hacerlo. Mas no abandonéis toda esperanza. Del día de mañana nada sabemos aún. La solución se encuentra a menudo a la salida del sol*.
Troll encadenado

Tras la caída de Sauron, algunos de los hobbits más jóvenes de La Comarca han decidido establecer rutas de comunicación con las demás razas. En algunas de las ocasiones que han tenido que atravesar el Bosque de los Trolls en su camino a las Montañas Nubladas, se han visto obligados a huir de esta desagradable especie. Por ello han tenido la idea de encadenarlos a todos, pero no han reunido el valor suficiente para hacerlo.

Sin embargo, y gracias a la amistad que une a determinadas familias con los enanos, han conseguido que éstos les ayuden. El primer paso es construir las pesadas cadenas que usarán para inmovilizar a los indeseables trolls. Los herreros de Aglarond son conocidos por su gran destreza, por lo que se encargarán de fabricarlas. Naturalmente, cada eslabón tiene que ser lo suficiente grande y robusto como para que soporte las embestidas de los enormes trolls. El problema es que los hobbits no son precisamente una raza que se caracterice por su fuerza, por lo que cada uno puede sólo transportar unos cuantos eslabones. Los enanos son mucho más fuertes, pero tendrán que transportar sus pesadas herramientas hasta el lugar donde se encadenará a los trolls, por lo que, en la práctica, cada enano sólo podrá cargar con el doble de eslabones que un hobbit.

Cada vez que se fabrica una cadena, deben decidir cómo se transporta. Si la cadena es lo suficientemente ligera como para que pueda ser transportada por un único individuo (ya sea hobbit o enano), se traslada tal cual. En caso contrario, habrá que partirla.

Sorprendentemente, han llegado a la conclusión de que trocearán la cadena en la misma proporción que sus fuerzas, es decir, haciendo una parte el doble de larga que la otra. Si la división no es exacta, los eslabones que sobren quedarán en el fragmento más grande. Ocurre en ocasiones que alguno de los fragmentos resultantes (¡o ambos!) sigue siendo demasiado pesado incluso para los enanos, por lo que repiten el proceso con él. Al final, una cadena puede terminar troceada en un montón de segmentos, cada uno con un número de eslabones diferente.

A ninguna de las razas les molesta que el reparto del trabajo no sea equitativo, por lo que cualquiera de los dos segmentos de la cadena (sea el largo o el corto) será transportado por el primer individuo que pueda con ella.

Entrada

La entrada estará compuesta por una serie de casos de prueba. Cada uno consistirá en dos números enteros no negativos. El primero indicará la fuerza de los hobbits, dando el número de eslabones que son capaces de llevar. El segundo indicará el tamaño (en número de eslabones) de la cadena que hay que transportar.

La entrada acabará cuando el primer número sea cero.

Salida

Para cada caso de prueba, se indicará el número de eslabones que hay que romper para construir los segmentos. Naturalmente, esos eslabones que se abren deben también ser transportados con alguno de los segmentos.

Entrada de ejemplo

10 8
5 10
1 3
1 4
0 0

Salida de ejemplo

0
0
1
2
1Capitulo II del Libro Tercero. Las dos torres. El Señor de los Anillos. (J.R.R. Tolkien)