fork download
copy 
  1. class Rational {
  2.   public int num;
  3.   public int den;
  4.   Rational(int a, int b) { num = a; den = b; }
  5.   Rational add(Rational val) {
  6.     return reduce (new Rational(this.num * val.den + this.den * val.num, this.den * val.den));
  7.   }
  8.   Rational subtract(Rational val) {
  9.     return reduce(new Rational(this.num * val.den - this.den * val.num, this.den * val.den));
  10.   }
  11.   Rational multiply(Rational val) {
  12.     return reduce(new Rational(this.num * val.num, this.den * val.den));
  13.   }
  14.   Rational divide(Rational val) {
  15.     return reduce(new Rational(this.num * val.den, this.den * val.num));
  16.   }
  17.   boolean isZero() {
  18.     if (this.num == 0 && this.den != 0)
  19.       return true;
  20.     if (this.den == 0) {
  21.       System.err.println("denomination is zero !!(1)");
  22.       System.exit(1);
  23.     }
  24.     return false;
  25.   }
  26.   boolean equal(Rational val) {
  27.     if (this.subtract(val).isZero())
  28.       return true;
  29.     return false;
  30.   }
  31.   private static Rational reduce(Rational val) {
  32.     if (val.den == 0) {
  33.       System.err.println("denomination is zero !!(2)");
  34.       System.exit(1);
  35.     }
  36.     if (val.num == 0)
  37.       return new Rational(0, 1);
  38.     int n = gcd(val.num, val.den);
  39.     return new Rational(val.num / n, val.den / n);
  40.   }
  41.   private static int gcd(int a, int b) {
  42.     if (b == 0)
  43.       return a;
  44.     return gcd(b, a % b);
  45.   }
  46.   public String toString() {
  47.     return "(" + this.num + "/" + this.den + ")";
  48.   }
  49. }
  50.  
  51. class Check {
  52.   final static int TARGET_NUM = 100;
  53.   final static int stacksize = 16;
  54.   Rational[] numStack;
  55.   int[] opStack;
  56.   Rational[] numStack2;
  57.   int[] opStack2;
  58.   Rational[] numStack3;
  59.   int[] opStack3;
  60.   int numStackPoint, opStackPoint, numStack2Point, opStack2Point, numStack3Point, opStack3Point;
  61.   Check() {
  62.     numStack = new Rational[stacksize];
  63.     opStack = new int[stacksize];
  64.     numStack2 = new Rational[stacksize];    
  65.     opStack2 = new int[stacksize];
  66.     numStack3 = new Rational[stacksize];    
  67.     opStack3 = new int[stacksize];
  68.   }
  69.   void CheckAndOutput(int[] seed) {
  70.     boolean minusstartflag = false;
  71.     numStackPoint = opStackPoint = numStack2Point = opStack2Point = numStack3Point = opStack3Point = 0;
  72.     numStack[numStackPoint++] = new Rational(0, 1);
  73.  
  74.     /* step 1 */
  75.     for (int i = 0; i < 9; i++) {
  76.       switch (seed[i]) {
  77.       case 0: /* concat */
  78.         Rational t = numStack[--numStackPoint];
  79.         if (!minusstartflag)
  80.           /* t * 10 + (i + 1); */
  81.           numStack[numStackPoint++] = t.multiply(new Rational(10, 1)).add(new Rational(i, 1)).add(new Rational(1, 1));
  82.         else
  83.           /* t * 10 - (i + 1); */
  84.           numStack[numStackPoint++] = t.multiply(new Rational(10, 1)).subtract(new Rational(i, 1)).subtract(new Rational(1, 1));
  85.         break;
  86.       case 1: /* + */
  87.         opStack2[opStack2Point++] = opStack[opStackPoint++] = 1;
  88.         numStack2[numStack2Point++] = numStack[numStackPoint - 1];
  89.         /* i + 1 */
  90.         numStack[numStackPoint++] = new Rational(i + 1, 1);
  91.         minusstartflag = false;
  92.         break;
  93.       case 2: /* - */
  94.         if (i == 0) {
  95.           minusstartflag = true;
  96.           numStack[numStackPoint - 1] = new Rational(-1, 1);
  97.         } else {
  98.           opStack2[opStack2Point++] = opStack[opStackPoint++] = 2;
  99.           numStack2[numStack2Point++] = numStack[numStackPoint - 1];
  100.           numStack[numStackPoint++] = new Rational(i + 1, 1);
  101.           minusstartflag = false;
  102.         }
  103.         break;
  104.       case 3: /* * */
  105.         opStack2[opStack2Point++] = opStack[opStackPoint++] = 3;
  106.         numStack2[numStack2Point++] = numStack[numStackPoint - 1];
  107.         numStack[numStackPoint++] = new Rational(i + 1, 1);
  108.         minusstartflag = false;
  109.         break;
  110.       case 4: /* / */
  111.         opStack2[opStack2Point++] = opStack[opStackPoint++] = 4;
  112.         numStack2[numStack2Point++] = numStack[numStackPoint - 1];
  113.         numStack[numStackPoint++] = new Rational(i + 1, 1);
  114.         minusstartflag = false;
  115.       }
  116.     } /* for */
  117.     numStack2[numStack2Point++] = numStack[numStackPoint - 1];
  118.  
  119.     ReverseStack(numStack, numStackPoint);
  120.     ReverseStack(opStack, opStackPoint);
  121.  
  122.     /* step 2a */
  123.     while (opStackPoint > 0) {
  124.       switch (opStack[--opStackPoint]) {
  125.       case 3: /* * */
  126.         Rational t1 = numStack[--numStackPoint];
  127.         Rational t2 = numStack[--numStackPoint];
  128.         numStack[numStackPoint++] = t1.multiply(t2);
  129.         break;
  130.       case 4: /* / */
  131.         t1 = numStack[--numStackPoint];
  132.         t2 = numStack[--numStackPoint];
  133.         if (t1.isZero()) return;
  134.         numStack[numStackPoint++] = t1.divide(t2);
  135.         break;
  136.       case 1: /* + */
  137.         numStack3[numStack3Point++] = numStack[--numStackPoint];
  138.         opStack3[opStack3Point++] = opStack[opStackPoint];
  139.         break;
  140.       case 2: /* - */
  141.         numStack3[numStack3Point++] = numStack[--numStackPoint];
  142.         opStack3[opStack3Point++] = opStack[opStackPoint];
  143.         break;
  144.       }
  145.     } /* while */
  146.     numStack3[numStack3Point++] = numStack[--numStackPoint];
  147.  
  148.     ReverseStack(numStack3, numStack3Point);
  149.     ReverseStack(opStack3, opStack3Point);
  150.  
  151.     /* step 2b */
  152.     while (opStack3Point > 0) {
  153.       switch (opStack3[--opStack3Point]) {
  154.       case 1: /* + */
  155.         Rational t1 = numStack3[--numStack3Point];
  156.         Rational t2 = numStack3[--numStack3Point];
  157.         numStack3[numStack3Point++] = t1.add(t2);
  158.         break;
  159.       case 2: /* - */
  160.         t1 = numStack3[--numStack3Point];
  161.         t2 = numStack3[--numStack3Point];
  162.         numStack3[numStack3Point++] = t1.subtract(t2);
  163.         break;
  164.       }
  165.     }
  166.     Rational answer = numStack3[0];
  167.  
  168.     /* step 3 */
  169.     if (answer.equal(new Rational(TARGET_NUM, 1))) {
  170.       int num_sp = 0, op_sp = 0;
  171.       if (minusstartflag) {
  172.         System.out.print('-');
  173.         op_sp++;
  174.       }
  175.       while (num_sp < numStack2Point) {
  176.         System.out.print(numStack2[num_sp++].num);
  177.         if (op_sp < opStack2Point)
  178.           switch (opStack2[op_sp++]) {
  179.           case 1:
  180.             System.out.print('+'); break;
  181.           case 2:
  182.             System.out.print('-'); break;
  183.           case 3:
  184.             System.out.print('*'); break;
  185.           case 4:
  186.             System.out.print('/'); break;
  187.           }
  188.       } /* while */
  189.       System.out.println(" = " + TARGET_NUM);
  190.     } /* if TARGET_NUM */
  191.   } /* method */
  192.  
  193.   static void ReverseStack(Rational[] array, int n) { for (int i = 0; i < n - i - 1; i++) myswap(array, i, n - i - 1); }
  194.   static void ReverseStack(int[] array, int n) { for (int i = 0; i < n - i - 1; i++) myswap(array, i, n - i - 1); }
  195.   static void myswap(Rational[] array, int a, int b) { Rational t; t = array[a]; array[a] = array[b]; array[b] = t; }
  196.   static void myswap(int[] array, int a, int b) { int t; t = array[a]; array[a] = array[b]; array[b] = t; }
  197. }
  198.  
  199. class Main {
  200.   public static void main(String[] args) {
  201.     Factory factory = new Factory();
  202.     int[] seed;
  203.     Check check = new Check();
  204.     while (factory.getSeed(seed = new int[9])) {
  205.       check.CheckAndOutput(seed);
  206.     }
  207.   }
  208. }
  209.  
  210. class Factory {
  211.   static int[] seed;
  212.   boolean stopflag;
  213.  
  214.   Factory() {
  215.     seed  = new int[9];
  216.     stopflag = false;
  217.     for (int i = 0; i < 9; i++) seed[i] = 0;
  218.   }
  219.  
  220.   private boolean next() {
  221.     int idx = 8;
  222.     if (stopflag)
  223.       return !stopflag;
  224.     do {
  225.       boolean cy = false;
  226.       if (seed[idx]++ >= 4) {
  227.         seed[idx] = 0;
  228.         cy = true;
  229.       }
  230.       while (idx > 0 ) {
  231.         --idx;
  232.         if (cy == true)
  233.           if (seed[idx]++ >= 4) {
  234.             seed[idx] = 0;
  235.             cy = true;
  236.           } else {
  237.             cy = false;
  238.           }
  239.       }
  240.       if (cy == true)
  241.         stopflag = true;
  242.     } while (seed[0] != 0 && seed[0] != 2);
  243.     return !stopflag;
  244.   }
  245.  
  246.   public boolean getSeed(int[] seed) {
  247.     boolean flag;
  248.     flag = this.next();
  249.     for (int i = 0; i < 9; i++)
  250.       seed[i] = this.seed[i];
  251.     return flag;
  252.   }
  253. }
  254. /* end */
  255.  
Success #stdin #stdout 1.45s 216128KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
123+45-67+8-9 = 100
123+4-5+67-89 = 100
123+4*5-6*7+8-9 = 100
123-45-67+89 = 100
123-4-5-6-7+8-9 = 100
12+34+5*6+7+8+9 = 100
12+34-5+6*7+8+9 = 100
12+34-5-6+7*8+9 = 100
12+34-5-6-7+8*9 = 100
12+3+4+5-6-7+89 = 100
12+3+4-56/7+89 = 100
12+3-4+5+67+8+9 = 100
12+3*45+6*7-89 = 100
12+3*4+5+6+7*8+9 = 100
12+3*4+5+6-7+8*9 = 100
12+3*4-5-6+78+9 = 100
12-3+4*5+6+7*8+9 = 100
12-3+4*5+6-7+8*9 = 100
12-3-4+5-6+7+89 = 100
12-3-4+5*6+7*8+9 = 100
12-3-4+5*6-7+8*9 = 100
12*3-4+5-6+78-9 = 100
12*3-4-5-6+7+8*9 = 100
12*3-4*5+67+8+9 = 100
12/3+4*5-6-7+89 = 100
12/3+4*5*6-7-8-9 = 100
12/3+4*5*6*7/8-9 = 100
12/3/4+5*6+78-9 = 100
1+234-56-7-8*9 = 100
1+234*5*6/78+9 = 100
1+234*5/6-7-89 = 100
1+23-4+56+7+8+9 = 100
1+23-4+56/7+8*9 = 100
1+23-4+5+6+78-9 = 100
1+23-4-5+6+7+8*9 = 100
1+23*4+56/7+8-9 = 100
1+23*4+5-6+7-8+9 = 100
1+23*4-5+6+7+8-9 = 100
1+2+34-5+67-8+9 = 100
1+2+34*5+6-7-8*9 = 100
1+2+3+4+5+6+7+8*9 = 100
1+2+3-45+67+8*9 = 100
1+2+3-4+5+6+78+9 = 100
1+2+3-4*5+6*7+8*9 = 100
1+2+3*4-5-6+7+89 = 100
1+2+3*4*56/7-8+9 = 100
1+2+3*4*5/6+78+9 = 100
1+2-3*4+5*6+7+8*9 = 100
1+2-3*4-5+6*7+8*9 = 100
1+2*34-56+78+9 = 100
1+2*3+4+5+67+8+9 = 100
1+2*3+4*5-6+7+8*9 = 100
1+2*3-4+56/7+89 = 100
1+2*3-4-5+6+7+89 = 100
1+2*3*4*5/6+7+8*9 = 100
1-23+4*5+6+7+89 = 100
1-23-4+5*6+7+89 = 100
1-23-4-5+6*7+89 = 100
1-2+3+45+6+7*8-9 = 100
1-2+3*4+5+67+8+9 = 100
1-2+3*4*5+6*7+8-9 = 100
1-2+3*4*5-6+7*8-9 = 100
1-2-34+56+7+8*9 = 100
1-2-3+45+6*7+8+9 = 100
1-2-3+45-6+7*8+9 = 100
1-2-3+45-6-7+8*9 = 100
1-2-3+4*56/7+8*9 = 100
1-2-3+4*5+67+8+9 = 100
1-2*3+4*5+6+7+8*9 = 100
1-2*3-4+5*6+7+8*9 = 100
1-2*3-4-5+6*7+8*9 = 100
1*234+5-67-8*9 = 100
1*23+4+56/7*8+9 = 100
1*23+4+5+67-8+9 = 100
1*23-4+5-6-7+89 = 100
1*23-4-56/7+89 = 100
1*23*4-56/7/8+9 = 100
1*2+34+56+7-8+9 = 100
1*2+34+5+6*7+8+9 = 100
1*2+34+5-6+7*8+9 = 100
1*2+34+5-6-7+8*9 = 100
1*2+34-56/7+8*9 = 100
1*2+3+45+67-8-9 = 100
1*2+3+4*5+6+78-9 = 100
1*2+3-4+5*6+78-9 = 100
1*2+3*4+5-6+78+9 = 100
1*2-3+4+56/7+89 = 100
1*2-3+4-5+6+7+89 = 100
1*2-3+4*5-6+78+9 = 100
1*2*34+56-7-8-9 = 100
1*2*3+4+5+6+7+8*9 = 100
1*2*3-45+67+8*9 = 100
1*2*3-4+5+6+78+9 = 100
1*2*3-4*5+6*7+8*9 = 100
1*2*3*4+5+6+7*8+9 = 100
1*2*3*4+5+6-7+8*9 = 100
1*2*3*4-5-6+78+9 = 100
1*2/3+4*5/6+7+89 = 100
1/2*34-5+6-7+89 = 100
1/2*3/4*56+7+8*9 = 100
1/2/3*456+7+8+9 = 100
-123+45*6-7*8+9 = 100
-123-4+5*6*7+8+9 = 100
-12+34+5-6+7+8*9 = 100
-12+3*4*5+6*78/9 = 100
-12-3-4+5+6*7+8*9 = 100
-12*3-4*5+67+89 = 100
-12*3/4+5*6+7+8*9 = 100
-12*3/4-5+6*7+8*9 = 100
-12/3+45+6*7+8+9 = 100
-12/3+45-6+7*8+9 = 100
-12/3+45-6-7+8*9 = 100
-12/3+4*56/7+8*9 = 100
-12/3+4*5+67+8+9 = 100
-1+23+4+5/6*78+9 = 100
-1+23*4+56-7*8+9 = 100
-1+23*4+56/7-8+9 = 100
-1+23*4+56/7/8*9 = 100
-1+23*4+5-6-7+8+9 = 100
-1+23*4-56+7*8+9 = 100
-1+23*4-56-7+8*9 = 100
-1+23*4-56/7+8+9 = 100
-1+23*4-5+6+7-8+9 = 100
-1+23*4*56/7/8+9 = 100
-1+23*4/56*7*8+9 = 100
-1+2+34*5-6+7-8*9 = 100
-1+2+34*5-6-7*8-9 = 100
-1+2+3+4*5-6-7+89 = 100
-1+2+3+4*5*6-7-8-9 = 100
-1+2+3+4*5*6*7/8-9 = 100
-1+2-3+4+5+6+78+9 = 100
-1+2*3+45+67-8-9 = 100
-1+2*3+4*5+6+78-9 = 100
-1+2*3-4+5*6+78-9 = 100
-1+2*3*4+5*6+7*8-9 = 100
-1+2*3/4*56/7+89 = 100
-1+2/3*45+6+7*8+9 = 100
-1+2/3*45+6-7+8*9 = 100
-1+2/3*45*6-7-8*9 = 100
-1+2/3*45/6+7+89 = 100
-1+2/3/4*5*6+7+89 = 100
-1-23*4+5*6*7-8-9 = 100
-1-2+3*4*5+6*7-8+9 = 100
-1-2*3+4+56+7*8-9 = 100
-1-2*3*4+56+78-9 = 100
-1-2/3*45+6*7+89 = 100
-1*234+5*67+8-9 = 100
-1*23+4+5+6*7+8*9 = 100
-1*2+34+5-6+78-9 = 100
-1*2+34-5-6+7+8*9 = 100
-1*2+34*5-67+8-9 = 100
-1*2+3+4+5-6+7+89 = 100
-1*2+3+4+5*6+7*8+9 = 100
-1*2+3+4+5*6-7+8*9 = 100
-1*2+3-4+56+7*8-9 = 100
-1*2+3*4+5+6+7+8*9 = 100
-1*2-34+5+6*7+89 = 100
-1*2-3+4*5+6+7+8*9 = 100
-1*2-3-4+5*6+7+8*9 = 100
-1*2-3-4-5+6*7+8*9 = 100
-1/2-3+45/6+7+89 = 100
-1/2*34+5*6+78+9 = 100
https://ideone.com/f4jC9
language:
Java (12.0.1)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!