Source code for submission s1192

Go to diff to previous submission

ladybug.c

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. /*
  4. #define DEBUG
  5. /**/
  6.  
  7. #define PLUS 4
  8. #define MINS 8
  9. #define MULT 16
  10. #define DIVD 32
  11. #define NUM0 64
  12. #define NUM1 128
  13. #define NUM2 256
  14. #define NUM3 512
  15. #define NUM4 1024
  16. #define NUM5 2048
  17. #define NUM6 4096
  18. #define NUM7 8192
  19. #define NUM8 16384
  20. #define NUM9 32768
  21. #define EQAL 65536
  22.  
  23. struct solution {
  24. int n;
  25. unsigned int length;
  26. };
  27.  
  28. #define STACK_MAX 100000
  29.  
  30. struct stack {
  31. struct solution s[STACK_MAX];
  32. char solved[STACK_MAX];
  33. unsigned int slen;
  34. unsigned int enlargement;
  35. };
  36.  
  37.  
  38. void stack_init(struct stack *s)
  39. {
  40. int i;
  41. for (i = 0; i < STACK_MAX; i++){
  42. s->solved[i] = 'u';
  43. }
  44. s->slen = 0;
  45. s->enlargement = 0;
  46. };
  47.  
  48. void stack_add(struct stack *s, int n, unsigned int length)
  49. {
  50. if (s->slen >= STACK_MAX) return;
  51. if (s->solved[n+(STACK_MAX/2)] == 's') {
  52. return;
  53. }
  54. s->solved[n+(STACK_MAX/2)] = 's';
  55. struct solution * f = &s->s[s->slen];
  56. f->n = n;
  57. f->length = length;
  58. s->slen++;
  59. };
  60.  
  61. int chartokey(char num)
  62. {
  63. switch (num) {
  64. case '+': return PLUS; break;
  65. case '-': return MINS; break;
  66. case '*': return MULT; break;
  67. case '/': return DIVD; break;
  68. case '0': return NUM0; break;
  69. case '1': return NUM1; break;
  70. case '2': return NUM2; break;
  71. case '3': return NUM3; break;
  72. case '4': return NUM4; break;
  73. case '5': return NUM5; break;
  74. case '6': return NUM6; break;
  75. case '7': return NUM7; break;
  76. case '8': return NUM8; break;
  77. case '9': return NUM9; break;
  78. case '=': return EQAL; break;
  79. default: return 0; break;
  80. }
  81. }
  82.  
  83. int havenum (int oper, int num)
  84. {
  85. if (num < 0) {
  86. if (oper & MINS)
  87. return 1 + havenum(oper, -num);
  88. return 0;
  89. }
  90. if (oper & chartokey((num % 10) + '0')) {
  91. unsigned int divnum = num/10;
  92. if (divnum)
  93. return 1 + havenum(oper, divnum);
  94. return 1;
  95. }
  96. return 0;
  97. }
  98.  
  99.  
  100. int sol(int oper, struct stack *s, int stateb)
  101. {
  102. unsigned int i;
  103.  
  104. /*
  105. #ifdef DEBUG
  106. printf("%s %i \n",__func__, n);
  107. #endif
  108. */
  109.  
  110. int mindepth = 2000000000;
  111. for (i = 0; i<s->slen; i++) {
  112. struct solution *solu;
  113. solu = &s->s[i];
  114. int state = solu->n;
  115. unsigned int length = solu->length;
  116. int depth = havenum(oper, state);
  117. #ifdef DEBUG
  118. printf("[%i %u %i]", state, length, depth);
  119. #endif
  120. if (depth != 0)
  121. if (depth + length < mindepth)
  122. mindepth = depth + length;
  123.  
  124. }
  125. if (mindepth != 2000000000) {
  126. printf("%i\n", mindepth);
  127. return 0;
  128. }
  129.  
  130.  
  131.  
  132. return 1;
  133. }
  134.  
  135. int solve(struct stack *s, char * keys, unsigned int skeys, int n)
  136. {
  137.  
  138.  
  139. int oper = 0;
  140. unsigned int j;
  141. for (j = 0; j< skeys; j++) {
  142. oper|=chartokey(keys[j]);
  143.  
  144.  
  145. }
  146.  
  147. if (n == 0)
  148. {printf("0\n"); return;}
  149.  
  150. stack_add(s, n, 0);
  151.  
  152. while (sol(oper, s, 0))
  153. {
  154.  
  155. int i;
  156. int snowlen = s->slen;
  157. for (i = s->enlargement; i<snowlen; i++) {
  158. struct solution *solu;
  159. solu = &s->s[i];
  160. int state = solu->n;
  161. unsigned int length = solu->length;
  162. int j;
  163. for (j = 0; j < 9; j++) {
  164. if (havenum(oper, j)) {
  165.  
  166.  
  167. if (oper & PLUS) {
  168. #ifdef DEBUG
  169. printf("Adding %i %i with difficulty %u\n", state-j, j, length+2);
  170. #endif
  171. stack_add(s, state-j, length+2);
  172. }
  173. if (oper & MINS) {
  174. #ifdef DEBUG
  175. printf("Adding %i %i with difficulty %u\n", state+j, j, length+2);
  176. #endif
  177. stack_add(s, state+j, length+2);
  178. }
  179. if (oper & MULT) {
  180. #ifdef DEBUG
  181. printf("Adding %i %i with difficulty %u\n", state/j, j, length+2);
  182. #endif
  183. stack_add(s, state/j, length+2);
  184. }
  185. if (oper & DIVD) {
  186. #ifdef DEBUG
  187. printf("Adding %i %i with difficulty %u\n", state*j, j, length+2);
  188. #endif
  189. stack_add(s, state*j, length+2);
  190. }
  191.  
  192. }
  193. }
  194.  
  195. }
  196. s->enlargement = snowlen;
  197.  
  198. if (s->slen >= STACK_MAX)
  199. {printf("impossible\n");}
  200.  
  201. }
  202. #ifdef DEBUG
  203. printf("konec\n");
  204. #endif
  205. /*
  206. #ifdef DEBUG
  207. printf("%s %i \n",__func__, n);
  208. #endif
  209. */
  210.  
  211.  
  212.  
  213. }
  214.  
  215. int main(void)
  216. {
  217. /*
  218. #ifdef DEBUG
  219. printf("%s \n",__func__);
  220. #endif
  221. */
  222. while (1) {
  223.  
  224.  
  225. char keys[30];
  226. keys[0] = 0;
  227. unsigned int n;
  228. scanf("%20s %u",&keys, &n);
  229. if (keys[0] == 0)
  230. return 0;
  231.  
  232.  
  233. /*
  234.  
  235. #ifdef DEBUG
  236. printf("[%s]", keys);
  237. #endif
  238. */
  239. int i = strlen(keys);
  240.  
  241.  
  242. /*
  243. #ifdef DEBUG
  244. printf("%s \n",__func__);
  245. #endif
  246. */
  247. /*
  248. #ifdef DEBUG
  249. printf("%s \n",__func__);
  250. #endif
  251. */
  252. struct stack stek;
  253. stack_init(&stek);
  254.  
  255.  
  256. solve(&stek, keys, i, n);
  257.  
  258. #ifdef DEBUG
  259. printf("---------\n\n\n");
  260. #endif
  261.  
  262.  
  263.  
  264.  
  265. }
  266. return 0;
  267. }
  268.  

Diff to submission s1164

ladybug.c

--- 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");}
 
                 }