Tamflexの貯蔵庫

やる気のない備忘録

テンパズル

テンパズル - Wikipedia

数式 | Aizu Online Judge
においては除算が含まれなかったが, 除算も含めて計算できるものを作成した.
まず除算について, すべて整数なので計算結果は0除算の時を除き有理数になることが保証される.したがってpairで分母分子を保存しておけば除算が誤差なく計算できる.
立式の規則について, 数列を2分割したのち,それぞれ可能な数式と値の組み合わせをmapによって保存し, 2分割したものの間で四則演算を行っている. 分割は再帰的に行っている. そして全部探索し終わったあとに条件に一致するものを表示させている. イメージしたのは算術式におけるインストラクションと評価文脈で, 分割のやり方によってこれらを表現しているつもり.
なお空間, 時間ともに計算量はO(n^2*n!)のためせいぜい5あたりが限界っぽい.

sample input

※4つの数を使って10を作るとき

4 10
3 4 7 8

sample output

((3-(7/4))*8)
(8*(3-(7/4)))
end

source

#include <bits/stdc++.h>

#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

typedef long long ll;
typedef pair<ll,ll> Pll;

map<string, Pll> generate(vector<ll> v)
{
  map<string, Pll> T;
  if(v.size() == 1)
  {
    if(v[0] < 0) T["("+to_string(v[0])+")"] = make_pair(v[0],1);
    else T[to_string(v[0])] = make_pair(v[0],1);
    return T;
  }
  else
  {
    REP(i,v.size()-1)
    {
      vector<ll> a,b;
      map<string, Pll>  s,t;
      FOR(j,0,i) a.push_back(v[j]);
      FOR(j,i+1,v.size()-1) b.push_back(v[j]);
      s = generate(a);
      t = generate(b);
      for(auto m : s) for(auto n : t)
      {
        ll n1 = m.second.first;
        ll d1 = m.second.second;
        ll n2 = n.second.first;
        ll d2 = n.second.second;
        T["("+m.first+"*"+n.first+")"] = make_pair(n1*n2,d1*d2);
        T["("+m.first+"/"+n.first+")"] = make_pair(n1*d2,d1*n2);
        T["("+m.first+"+"+n.first+")"] = make_pair(n1*d2+n2*d1,d1*d2);
        T["("+m.first+"-"+n.first+")"] = make_pair(n1*d2-n2*d1,d1*d2);
      }
    }
    return T;
  }
}

void solve(vector<ll> v, ll f)
{
  do
  {
    map<string, Pll> T = generate(v);
    for(auto a : T) if(a.second.second != 0 && a.second.first == f * a.second.second)
      printf("%s\n",a.first.c_str());
  } while(next_permutation(v.begin(),v.end()));
  printf("end\n\n");
}

int main()
{
  ll n = 0, f = 0, i = 0;
  cin >> n >> f;
  vector<ll> a(n);
  while(cin >> a[i])
  {
    i=(i+1)%n;
    if(i == 0)
    {
      sort(a.begin(),a.end());
      solve(a,f);
    }
  }
  return 0;
}