Sisoku.cpp

#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>

using namespace std;
#define EPS 1e-9


#define N 7

vector<int> formular;

string op[] = {
  " + ",
  " * ",
  " - ",
  " / ",
  " ** ",
  " rt ",
  " log ",
};

string numstring[] = {
  "0",
  "1",
  "2",
  "3",
  "4",
  "5",
  "6",
  "7",
  "8",
  "9",
  "10",
  "11",
  "12",
  "13",
};

double go(double a, double b, int x){
  switch(x){
  case 0:
    return a + b;

  case 1:
    return a * b;

  case 2:
    return a - b;

  case 3:
    if(b == 0)return 123456789;//random number
    return a / b;

  case 4:
    return pow(a, b);

  case 5:
    if(b == 0)return 12345676545;//random number
    return pow(a, 1/b);

  case 6:
    if(b <= 0)return 12345678765;//random number
    if(b == 1)return 12321314141;//random number
    return log(a) / log(b);
    
  }
}

double calc(){
  vector<double> stk;
  for(int i = 0;i < formular.size();i++){
    int tmp = formular[i];
    if(tmp > 0){
      stk.push_back(tmp);
    }
    else{
      double a = stk.back();stk.pop_back();
      double b = stk.back();stk.pop_back();
      stk.push_back(go(a, b, -tmp));
    }
  }
  return stk[0];
}

string toString(){
  vector<string> stk;
  for(int i = 0;i < formular.size();i++){
    int tmp = formular[i];
    if(tmp > 0){
      stk.push_back(numstring[tmp]);
    }
    else{
      string a = stk.back();stk.pop_back();
      string b = stk.back();stk.pop_back();
      stk.push_back("(" + a + op[-tmp] + b + ")");
    }
  }
  return stk[0];
}

void solve(vector<int> &nums, int x, double ans, int pos = 0){
  if(formular.size() == nums.size() * 2 - 1){
    double tmp = calc();
    if(abs(tmp - ans) < EPS){
      cout << toString() << endl;
    }
    return;
  }
  if(pos != nums.size()){
    formular.push_back(nums[pos]);
    solve(nums, x, ans, pos+1);
    formular.pop_back();
  }
  if((int)formular.size() < pos*2-1){
    formular.push_back(-(x % N));
    solve(nums, x / N, ans, pos);
    formular.pop_back();
  }
}

int main(){
  int n, num;
  double ans;
  vector<int> nums;
  cin >> n;
  for(int i = 0;i < n;i++){
    cin >> num;
    nums.push_back(num);
  }
  cin >> ans;
  sort(nums.begin(), nums.end());
  int pw = 1;
  for(int i = 0;i < n-1;i++)pw *= N;
  
  do{
    for(int i = 0;i < pw;i++){
      solve(nums, i, ans);
    }
  }while(next_permutation(nums.begin(), nums.end()));
  return 0;
}