逐次計算中に操作の順序を維持する

Question

私はKattisからプログラミングの問題をいくつかやっています。私が立ち往生している問題4 thoughtの一部があります。プログラムは操作を返すことになっている数、与えられ

（+、 - 、*または/）はその数を達成するために、4四つんばい間に必要。

例えば、入力

9 

は出力に

4 + 4 + 4/4 = 9 

をもたらすであろう私のソリューションは、（効率的な、しかし、簡単ではありません）上記の演算子を組み合わせて、見るためにすべての可能な方法を評価することです所望の結果を達成する組み合わせがあれば、私は以下の見た機能を書かれているこれを行うには

。それが評価される演算子である文字の配列（uo[3]、{+, /, *}ようになり）、および整数（expRes）として所望の結果を取り込みます。

bool check(char uo[3], int expRes) { 
    int res = 4; 
    for(int oPos = 2; oPos >= 0; oPos--) { 
     switch (uo[oPos]) { 
      case '+' : res += 4; break; 
      case '-' : res -= 4; break; 
      case '*' : res *= 4; break; 
      case '/' : res /= 4; break; 
     } 
    } 
    return res == expRes;  
} 

この「シーケンシャル」アプローチには、操作の順序に従わないという問題があります。 uo = {+, -, /} と expRes = 7で関数を呼び出す場合は、4 + 4 = 8,8-4 = 4,4/4 = 1なのでfalseを返します。 実際の答えは4 + 4 - = 7

4月4日には、あなたのいずれかが評価の操作の順序を次のように機能を書き換えるための方法を考えることはできますか？

ありがとうございます！

Answer 1

あなたはそれを見ると簡単な問題です。

あなたはすでにあなたの探索空間を知っている間に4つの4者と3つの演算子、で制限されています。したがって、1つの解決策は、O（n^3）= 4^3 = 64の全方程式である完全探索空間を生成することである。ここで、nは演算子の数である。これらの解に対する答えを<key, value>のペアとして保持し、テストケースの入力までの検索をO（1）にします。

賢明にお伝えください。

1. 完全な配列を生成し、キーとしてそれらを格納、値のペアは
2. は、キーが存在する場合は[はいシーケンスを印刷する場合、他の、テストケースから
3. チェックを入力してくださいシーケンスが存在しないことを印刷
4. ソリューションは、（そのほとんどが不完全である）、容易秒間にして計算することができます64×1000回の操作を、取るだろうと、通常、これらの競技は、コード形式で

を持っている時間制限超過エラーを回避する：

// C++ Syntax 
map<int, string> mp; 

void generateAll() { 
    // generate all equations 
} 

void main() { 
    generateAll(); 

    int n, t; scanf("%d", &t); 
    while (t--) { 
     scanf("%d", &n); 

     if (mp.find(n) != mp.end()) 
      // equation exists to the input 
     else 
      // equation doesn't exist for the input 
    } 
}