Source code for submission s952

ladybug.c

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. int allowed[256];
  6. int target;
  7. // dis, ope, val, state
  8. char visited[1100][5][1100][2];
  9. int q[100000000];
  10. int qpr, qpw;
  11.  
  12. #define OP_NA 0
  13. #define OP_PLUS 1
  14. #define OP_MINUS 2
  15. #define OP_MULT 3
  16. #define OP_DIV 4
  17. #define OP_EQ 5
  18. #define ST_N 0
  19. #define ST_O 1
  20. #define ST_S 2
  21.  
  22. int eval(int v, int op, int d)
  23. {
  24. 	if (op==OP_PLUS)
  25. 		return v+d;
  26. 	if (op==OP_MINUS)
  27. 		return v-d;
  28. 	if (op==OP_MULT)
  29. 		return v*d;
  30. 	if (op==OP_DIV && d==0) return 100000;
  31. 	if (op==OP_DIV)
  32. 		return v/d;
  33. 	return d;
  34. }
  35.  
  36. void qi(int disp, int oper, int val, int state, int dist, int button)
  37. {
  38. 	if (disp < 0 || disp > 999) return;
  39. 	if (button != 0 && !allowed[button]) return;
  40. 	if (state != ST_S) {
  41. 		if (visited[disp][oper][val][state])
  42. 			return;
  43. 		visited[disp][oper][val][state] = 1;
  44. 	}
  45. 	// visited ST_S !!
  46. //	printf("I %d %d %d %d %d\n", disp, oper, val, state, dist);
  47. 	q[qpw++] = disp;
  48. 	q[qpw++] = oper;
  49. 	q[qpw++] = val;
  50. 	q[qpw++] = state;
  51. 	q[qpw++] = dist;
  52. }
  53.  
  54. void qr(int *disp, int *oper, int *val, int *state, int *dist)
  55. {
  56. 	*disp = q[qpr++];
  57. 	*oper = q[qpr++];
  58. 	*val = q[qpr++];
  59. 	*state = q[qpr++];
  60. 	*dist = q[qpr++];
  61. //1	printf("R %d %d %d %d %d\n", *disp, *oper, *val, *state, *dist);
  62.  
  63. }
  64.  
  65. int main(int argc, char **argv)
  66. {
  67. 	int ch;
  68. 	int i;
  69. 	int disp, oper, val, state, dist;
  70. 	int disp2;
  71. 	while (1) {
  72. 		memset(allowed, 0, sizeof(allowed));
  73. 		while (1) {
  74. 			ch = getc(stdin);
  75. 			if (feof(stdin))
  76. 				return 0;
  77. 			if (ch == ' ') break;
  78. 			allowed[ch] = 1;
  79. 			//printf("allow %c\n", ch);
  80. 		}
  81. 		scanf("%d", &target);
  82. 		memset(visited, 0, sizeof(visited));
  83. 		qpr = qpw = 0;
  84. 		qi(0, OP_NA, 0, ST_S, 0, 0);
  85. 		for (i=0; i<10; i++)
  86. 			qi(i, OP_NA, 0, ST_N, 1, '0'+i);
  87. 		qi(0, OP_PLUS, 0, ST_O, 1, '+');
  88. 		qi(0, OP_MINUS, 0, ST_O, 1, '-');
  89. 		qi(0, OP_MULT, 0, ST_O, 1, '*');
  90. 		qi(0, OP_DIV, 0, ST_O, 1, '/');
  91. 		qi(0, OP_EQ, 0, ST_O, 1, '=');
  92. 		while (1) {
  93. 			qr(&disp, &oper, &val, &state, &dist);
  94. 			if (disp == target) {
  95. 				printf("%d\n", dist);
  96. 				break;
  97. 			}
  98. 			if (qpw <= qpr) {
  99. 				printf("impossible\n");
  100. 				break;
  101. 			}
  102. 			if (state == ST_N) {
  103. 				for (i=0; i<10; i++)
  104. 					qi(10*disp+i, oper, val, state, dist+1, '0'+i);
  105. 				disp2 = eval(val, oper, disp);
  106. 				qi(disp2, OP_PLUS, disp2, ST_O, dist+1, '+');
  107. 				qi(disp2, OP_MINUS, disp2, ST_O, dist+1, '-');
  108. 				qi(disp2, OP_MULT, disp2, ST_O, dist+1, '*');
  109. 				qi(disp2, OP_DIV, disp2, ST_O, dist+1, '/');
  110. 				qi(disp2, OP_EQ, disp2, ST_O, dist+1, '=');
  111. 			}
  112. 			if (state == ST_O) {
  113. 				for (i=0; i<10; i++)
  114. 					qi(i, oper, val, ST_N, dist+1, '0'+i);
  115. 				disp2 = eval(val, oper, disp);
  116. 				qi(disp2, OP_EQ, disp2, ST_O, dist+1, '=');
  117. 				qi(disp, OP_PLUS, disp, ST_O, dist+1, '+');
  118. 				qi(disp, OP_MINUS, disp, ST_O, dist+1, '-');
  119. 				qi(disp, OP_MULT, disp, ST_O, dist+1, '*');
  120. 				qi(disp, OP_DIV, disp, ST_O, dist+1, '/');
  121. 			}
  122. 		}
  123. 	}
  124. }
  125.