AtCoder ABC 079 C - Train Ticket でWA

Question

AtCoder ABC 079 C - Train Ticket でWA

AtCoder ABC 079 C - Train Ticketにて、WA(不正解）となってしまう（コードテストはうまくいく）ため質問します。
以下の実装コードではどのように間違っているのでしょうか。
※愚直にifで試すのではなくbit全探索をしたい。

問題：https://atcoder.jp/contests/abc079/tasks/abc079_c

実装コード

#include <bits/stdc++.h>
using namespace std;

int main() {
  vector<int> ticket(4);

  for(int i = 0; i < 4; i++){
    cin >> ticket[i];
  }

  for(int bit = 0; bit < (1 << 3); bit++){
    int ans = 0;

    for(int idx = 0; idx < 3; idx++){
      if(bit & (1 << idx)) ans += ticket[idx + 1];

      else ans -= ticket[idx + 1];
    }

    if(ans == 7){
      cout << ticket[0];

      for(int idx = 0; idx < 3; idx++){
        if(bit & (1 << idx)) cout << '+';
        else cout << '-';

        cout << ticket[idx + 1];
      }

      cout << "=7" << endl;

    }
  }
}

#修正後

#include <bits/stdc++.h>
using namespace std;

int main() {
  int abcd;
  cin >> abcd;
  vector<int> ticket(4);

  for(int i = 3; i > -1; i--){
    ticket[i] = (abcd%10); // 1桁取り出していく
    abcd /= 10;
  }

  for(int bit = 0; bit < (1 << 3); bit++){
    int ans = ticket[0];

    for(int idx = 0; idx < 3; idx++){
      if(bit & (1 << idx)) ans += ticket[idx + 1];

      else ans -= ticket[idx + 1];
    }

    if(ans == 7){
      cout << ticket[0];

      for(int idx = 0; idx < 3; idx++){
        if(bit & (1 << idx)) cout << '+';
        else cout << '-';

        cout << ticket[idx + 1];
      }

      cout << "=7" << endl;

    }
  }
}

Answer 1

すべての場合の計算結果を表にしておけば速いのではないかな、と思って書いてみました。

#include <stdio.h>

#define D(a,b,c,d) a+b+c+d,a+b+c-d,a+b-c+d,a+b-c-d,\
                   a-b+c+d,a-b+c-d,a-b-c+d,a-b-c-d
#define C(a,b,c) D(a,b,c,0),D(a,b,c,1),D(a,b,c,2),D(a,b,c,3),D(a,b,c,4),\
                 D(a,b,c,5),D(a,b,c,6),D(a,b,c,7),D(a,b,c,8),D(a,b,c,9) 
#define B(a,b) C(a,b,0),C(a,b,1),C(a,b,2),C(a,b,3),C(a,b,4),\
               C(a,b,5),C(a,b,6),C(a,b,7),C(a,b,8),C(a,b,9) 
#define A(a) B(a,0),B(a,1),B(a,2),B(a,3),B(a,4),\
             B(a,5),B(a,6),B(a,7),B(a,8),B(a,9) 

int t[80000] = { A(0),A(1),A(2),A(3),A(4),A(5),A(6),A(7),A(8),A(9) };

void print(int i, const int *s)
{
	static const char *fmt[8] = {
		"%d+%d+%d+%d=7\n", "%d+%d+%d-%d=7\n", "%d+%d-%d+%d=7\n", "%d+%d-%d-%d=7\n",
		"%d-%d+%d+%d=7\n", "%d-%d+%d-%d=7\n", "%d-%d-%d+%d=7\n", "%d-%d-%d-%d=7\n"
	};
	printf(fmt[i], s[0], s[1], s[2], s[3]);
}

int main(void)
{
	int s[4];
	scanf("%1d%1d%1d%1d", s, s+1, s+2, s+3);
	int n = (s[0]*1000 + s[1]*100 + s[2]*10 + s[3]) * 8;
	for (int i = 0; i < 8; i++)
        if (t[n + i] == 7) { print(i, s); break; }
}

Answer 2

以下の実装コードではどのように間違っているのでしょうか。

入力が 1222 の場合、それが ticket[0] に入り、
ticket[1]～ticket[3] への入力待ちとなります。

計算の方は、ticket[0] の値が使用されず、
ticket[1]～ticket[3] の値だけで計算しています。

Comments

[kei0105]

入力部分を
```
int abcd;
cin >> abcd;
vector<int> ticket(4);

for(int i = 3; i > -1; i--){
ticket[i] = (abcd%10); // 1桁取り出していく
abcd /= 10;
}
```
計算部分にticket[0]を挿入
```
int ans = ticket[0];
```

以上のように変更しましたがテストケースによってはうまく行きませんでした。
どのように問題でしょうか。

[kazuma-s]

答えが複数存在する場合に全部出力しているからではありませんか？