Problema número 469

Pesando patatas

Tiempo máximo: 1,000 sMemoria máxima: 4096 KiB
Balanza

Cuando antiguamente se utilizaban las balanzas de dos platos para pesar, los comerciantes llevaban una colección de pesas que colocaban junto con la mercancía en los platos hasta que la balanza quedaba equilibrada. De esta forma, averiguaban la cantidad exacta que estaban vendiendo y emitían el precio.

La colección de pesas exacta dependía de la destreza del vendedor. Hoy día, habituados como estamos a la base 2, es fácil entender que las pesas podrían tener pesos potencia de dos. En ese caso basta con colocar en un plato la mercancía y en el otro aquellas pesas cuyos bits estén a uno en la representación en binario del número.

Sin embargo si permitimos que mercancía y pesas compartan el mismo plato, las posibilidades se disparan. Por ejemplo, con una pesa de 1 Kg y otra de 100 gr, podremos averiguar si una colección de patatas pesa 900 gr. Basta con colocar en un platillo la pesa grande y en el otro la pesa pequeña y las patatas y mirar si la balanza queda equilibrada.

Una forma óptima (en cuanto a número de pesas distintas necesarias) para pesar es utilizar esta idea con pesas potencia de 3. Lo difícil es saber rápidamente cómo colocarlas…

Entrada

La entrada estará compuesta por varios casos de prueba, cada uno en una línea.

Cada caso de prueba será un único número que indicará la cantidad de patatas, en gramos, que queremos pesar. El peso no excederá los 109 gramos.

Salida

Para cada caso de prueba se escribirá, en una línea independiente, la configuración que debemos tener en la balanza.

La línea comenzará con los pesos (en orden creciente) de las pesas del platillo en el que no tenemos la mercancía, separados por espacio. A continuación le seguirán los caracteres ==X== simbolizando la parte central de la balanza. Después se indicarán, también en orden creciente y separados por un espacio, las pesas a colocar en el segundo platillo, seguidos de la palabra patatas.

Las pesas disponibles tienen siempre pesos en gramos potencia de tres, y tan altos como necesites. Pero sólo tienes una pesa de cada peso.

Entrada de ejemplo

1
8
79

Salida de ejemplo

1 ==X== patatas
9 ==X== 1 patatas
1 81 ==X== 3 patatas