#include <stdio.h>
#include <stdlib.h>
/*
#define DEBUG
*/
#define PLUS 4
#define MINS 8
#define MULT 16
#define DIVD 32
#define NUM0 64
#define NUM1 128
#define NUM2 256
#define NUM3 512
#define NUM4 1024
#define NUM5 2048
#define NUM6 4096
#define NUM7 8192
#define NUM8 16384
#define NUM9 32768
#define EQAL 65536
struct solution {
int n;
unsigned int length;
};
struct stack {
struct solution s[1000000];
char solved[1000000];
unsigned int slen;
unsigned int enlargement;
};
void stack_init(struct stack *s)
{
int i;
for (i = 0; i < 1000000; i++){
s->solved[i] = 'u';
}
s->slen = 0;
s->enlargement = 0;
};
void stack_add(struct stack *s, int n, unsigned int length)
{
if (s->solved[n+500000] == 's') {
return;
}
s->solved[n+500000] = 's';
struct solution * f = &s->s[s->slen];
f->n = n;
f->length = length;
s->slen++;
};
int chartokey(char num)
{
switch (num) {
case '+': return PLUS; break;
case '-': return MINS; break;
case '*': return MULT; break;
case '/': return DIVD; break;
case '0': return NUM0; break;
case '1': return NUM1; break;
case '2': return NUM2; break;
case '3': return NUM3; break;
case '4': return NUM4; break;
case '5': return NUM5; break;
case '6': return NUM6; break;
case '7': return NUM7; break;
case '8': return NUM8; break;
case '9': return NUM9; break;
case '=': return EQAL; break;
default: return 0; break;
}
}
int havenum (int oper, int num)
{
if (num < 0) {
if (oper & MINS)
return 1 + havenum(oper, -num);
return 0;
}
if (oper & chartokey((num % 10) + '0')) {
unsigned int divnum = num/10;
if (divnum)
return 1 + havenum(oper, divnum);
return 1;
}
return 0;
}
int sol(int oper, struct stack *s, int stateb)
{
unsigned int i;
/*
#ifdef DEBUG
printf("%s %i \n",__func__, n);
#endif
*/
int mindepth = 2000000000;
for (i = 0; i<s->slen; i++) {
struct solution *solu;
solu = &s->s[i];
int state = solu->n;
unsigned int length = solu->length;
int depth = length + havenum(oper, state);
if (depth != 0)
if (depth < mindepth)
mindepth = depth;
}
if (mindepth != 2000000000) {
return 0;
}
return 1;
}
int solve(struct stack *s, char * keys, unsigned int skeys, int n)
{
int oper = 0;
unsigned int j;
for (j = 0; j< skeys; j++) {
oper|=chartokey(keys[j]);
}
if (n == 0)
stack_add(s, n, 0);
while (sol(oper, s, 0))
{
int i;
int snowlen = s->slen;
for (i = s->enlargement; i<snowlen; i++) {
struct solution *solu;
solu = &s->s[i];
int state = solu->n;
unsigned int length = solu->length;
int j;
for (j = 0; j < 9; j++) {
if (havenum(oper, j)) {
if (oper & PLUS) {
#ifdef DEBUG
printf("Adding %i %i with difficulty %u\n", state
-j
, j
, length
+2); #endif
stack_add(s, state-j, length+2);
}
if (oper & MINS) {
#ifdef DEBUG
printf("Adding %i %i with difficulty %u\n", state
+j
, j
, length
+2); #endif
stack_add(s, state+j, length+2);
}
if (oper & MULT) {
#ifdef DEBUG
printf("Adding %i %i with difficulty %u\n", state
/j
, j
, length
+2); #endif
stack_add(s, state/j, length+2);
}
if (oper & DIVD) {
#ifdef DEBUG
printf("Adding %i %i with difficulty %u\n", state
*j
, j
, length
+2); #endif
stack_add(s, state*j, length+2);
}
}
}
}
s->enlargement = 0;
}
#ifdef DEBUG
#endif
/*
#ifdef DEBUG
printf("%s %i \n",__func__, n);
#endif
*/
}
int main(void)
{
/*
#ifdef DEBUG
printf("%s \n",__func__);
#endif
*/
while (1) {
char keys[30];
keys[0] = 0;
unsigned int n;
scanf("%20s %u",&keys
, &n
); if (keys[0] == 0)
return 0;
/*
#ifdef DEBUG
printf("[%s]", keys);
#endif
*/
/*
#ifdef DEBUG
printf("%s \n",__func__);
#endif
*/
/*
#ifdef DEBUG
printf("%s \n",__func__);
#endif
*/
struct stack stek;
stack_init(&stek);
solve(&stek, keys, i, n);
#ifdef DEBUG
#endif
}
return 0;
}