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