fork download
  1. class Check {
  2. final static int TARGET_NUM = 100;
  3. final static int stacksize = 16;
  4. int[] numStack;
  5. int[] opStack;
  6. int[] numStack2;
  7. int[] opStack2;
  8. int numStackPoint, opStackPoint, numStack2Point, opStack2Point;
  9. Check() {
  10. numStack = new int[stacksize];
  11. opStack = new int[stacksize];
  12. numStack2 = new int[stacksize];
  13. opStack2 = new int[stacksize];
  14. }
  15. void CheckAndOutput(int[] seed) {
  16. boolean minusstartflag = false;
  17. numStackPoint = opStackPoint = numStack2Point = opStack2Point = 0;
  18. numStack[numStackPoint++] = 0;
  19.  
  20. /* step 1 */
  21. for (int i = 0; i < 9; i++) {
  22. switch (seed[i]) {
  23. case 0: /* concat */
  24. int t = numStack[--numStackPoint];
  25. if (!minusstartflag)
  26. numStack[numStackPoint++] = t * 10 + (10 - i - 1);
  27. else
  28. numStack[numStackPoint++] = t * 10 - (10 - i - 1);
  29. break;
  30. case 1: /* + */
  31. opStack2[opStack2Point++] = opStack[opStackPoint++] = 1;
  32. numStack2[numStack2Point++] = numStack[numStackPoint - 1];
  33. numStack[numStackPoint++] = 10 - i - 1;
  34. minusstartflag = false;
  35. break;
  36. case 2: /* - */
  37. if (i == 0) {
  38. minusstartflag = true;
  39. numStack[numStackPoint - 1] = -9;
  40. } else {
  41. opStack2[opStack2Point++] = opStack[opStackPoint++] = 2;
  42. numStack2[numStack2Point++] = numStack[numStackPoint - 1];
  43. numStack[numStackPoint++] = 10 - i - 1;
  44. minusstartflag = false;
  45. }
  46. break;
  47. }
  48. } /* for */
  49. numStack2[numStack2Point++] = numStack[numStackPoint - 1];
  50.  
  51. ReverseStack(numStack, numStackPoint);
  52. ReverseStack(opStack, opStackPoint);
  53.  
  54. /* step 2b */
  55. while (opStackPoint > 0) {
  56. switch (opStack[--opStackPoint]) {
  57. case 1: /* + */
  58. int t1 = numStack[--numStackPoint];
  59. int t2 = numStack[--numStackPoint];
  60. numStack[numStackPoint++] = t1 + t2;
  61. break;
  62. case 2: /* - */
  63. t1 = numStack[--numStackPoint];
  64. t2 = numStack[--numStackPoint];
  65. numStack[numStackPoint++] = t1 - t2;
  66. break;
  67. }
  68. }
  69. int answer = numStack[0];
  70.  
  71. /* step 3 */
  72. if (answer == TARGET_NUM) {
  73. int num_sp = 0, op_sp = 0;
  74. if (minusstartflag) {
  75. System.out.print('-');
  76. op_sp++;
  77. }
  78. while (num_sp < numStack2Point) {
  79. System.out.print(numStack2[num_sp++]);
  80. if (op_sp < opStack2Point)
  81. switch (opStack2[op_sp++]) {
  82. case 1:
  83. System.out.print('+'); break;
  84. case 2:
  85. System.out.print('-'); break;
  86. case 3:
  87. System.out.print('*'); break;
  88. case 4:
  89. System.out.print('/'); break;
  90. }
  91. } /* while */
  92. System.out.println(" = " + answer);
  93. } /* if TARGET_NUM */
  94. } /* method */
  95.  
  96. static void ReverseStack(int[] array, int n) { for (int i = 0; i < n - i - 1; i++) myswap(array, i, n - i - 1); }
  97. static void myswap(int[] array, int a, int b) { int t; t = array[a]; array[a] = array[b]; array[b] = t; }
  98. }
  99.  
  100. class Main {
  101. public static void main(String[] args) {
  102. Factory factory = new Factory();
  103. int[] seed;
  104. Check check = new Check();
  105. while (factory.getSeed(seed = new int[9])) {
  106. check.CheckAndOutput(seed);
  107. }
  108. }
  109. }
  110.  
  111. class Factory {
  112. static int[] seed;
  113. boolean stopflag;
  114.  
  115. Factory() {
  116. seed = new int[9];
  117. stopflag = false;
  118. for (int i = 0; i < 9; i++) seed[i] = 0;
  119. }
  120.  
  121. private boolean next() {
  122. int idx = 8;
  123. if (stopflag)
  124. return !stopflag;
  125. do {
  126. boolean cy = false;
  127. if (seed[idx]++ >= 2) {
  128. seed[idx] = 0;
  129. cy = true;
  130. }
  131. while (idx > 0 ) {
  132. --idx;
  133. if (cy == true)
  134. if (seed[idx]++ >= 2) {
  135. seed[idx] = 0;
  136. cy = true;
  137. } else {
  138. cy = false;
  139. }
  140. }
  141. if (cy == true)
  142. stopflag = true;
  143. } while (seed[0] != 0 && seed[0] != 2);
  144. return !stopflag;
  145. }
  146.  
  147. public boolean getSeed(int[] seed) {
  148. boolean flag;
  149. flag = this.next();
  150. for (int i = 0; i < 9; i++)
  151. seed[i] = this.seed[i];
  152. return flag;
  153. }
  154. }
  155. /* end */
  156.  
Success #stdin #stdout 0.08s 215680KB
stdin
Standard input is empty
stdout
98+7+6-5-4-3+2-1 = 100
98+7-6+5-4+3-2-1 = 100
98+7-6+5-4-3+2+1 = 100
98+7-6-5+4+3-2+1 = 100
98-76+54+3+21 = 100
98-7+6+5+4-3-2-1 = 100
98-7+6+5-4+3-2+1 = 100
98-7+6-5+4+3+2-1 = 100
98-7-6+5+4+3+2+1 = 100
98-7-6-5-4+3+21 = 100
9+8+76+5+4-3+2-1 = 100
9+8+76+5-4+3+2+1 = 100
9-8+76+54-32+1 = 100
9-8+76-5+4+3+21 = 100
9-8+7+65-4+32-1 = 100
-9+8+76+5-4+3+21 = 100
-9+8+7+65-4+32+1 = 100
-9-8+76-5+43+2+1 = 100