Go to diff to previous submission
#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; }; #define STACK_MAX 100000 struct stack { struct solution s[STACK_MAX]; char solved[STACK_MAX]; unsigned int slen; unsigned int enlargement; }; void stack_init(struct stack *s) { int i; for (i = 0; i < STACK_MAX; i++){ s->solved[i] = 'u'; } s->slen = 0; s->enlargement = 0; }; void stack_add(struct stack *s, int n, unsigned int length) { if (s->slen >= STACK_MAX) return; if (s->solved[n+(STACK_MAX/2)] == 's') { return; } s->solved[n+(STACK_MAX/2)] = '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 = havenum(oper, state); #ifdef DEBUG #endif if (depth != 0) if (depth + length < mindepth) mindepth = depth + length; } 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 #endif stack_add(s, state-j, length+2); } if (oper & MINS) { #ifdef DEBUG #endif stack_add(s, state+j, length+2); } if (oper & MULT) { #ifdef DEBUG #endif stack_add(s, state/j, length+2); } if (oper & DIVD) { #ifdef DEBUG #endif stack_add(s, state*j, length+2); } } } } s->enlargement = snowlen; if (s->slen >= STACK_MAX) } #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; 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; }
--- c4.s1164.cteam073.ladybug.c.0.ladybug.c +++ c4.s1192.cteam073.ladybug.c.0.ladybug.c @@ -3,5 +3,5 @@ /* #define DEBUG -*/ +/**/ #define PLUS 4 @@ -26,7 +26,9 @@ }; +#define STACK_MAX 100000 + struct stack { - struct solution s[1000000]; - char solved[1000000]; + struct solution s[STACK_MAX]; + char solved[STACK_MAX]; unsigned int slen; unsigned int enlargement; @@ -37,5 +39,5 @@ { int i; - for (i = 0; i < 1000000; i++){ + for (i = 0; i < STACK_MAX; i++){ s->solved[i] = 'u'; } @@ -46,8 +48,9 @@ void stack_add(struct stack *s, int n, unsigned int length) { - if (s->solved[n+500000] == 's') { + if (s->slen >= STACK_MAX) return; + if (s->solved[n+(STACK_MAX/2)] == 's') { return; } - s->solved[n+500000] = 's'; + s->solved[n+(STACK_MAX/2)] = 's'; struct solution * f = &s->s[s->slen]; f->n = n; @@ -111,8 +114,11 @@ int state = solu->n; unsigned int length = solu->length; - int depth = length + havenum(oper, state); + int depth = havenum(oper, state); + #ifdef DEBUG + printf("[%i %u %i]", state, length, depth); + #endif if (depth != 0) - if (depth < mindepth) - mindepth = depth; + if (depth + length < mindepth) + mindepth = depth + length; } @@ -188,5 +194,8 @@ } - s->enlargement = 0; + s->enlargement = snowlen; + + if (s->slen >= STACK_MAX) + {printf("impossible\n");} }