ABC079-C Train Ticket(Atcoder精進記録)
Atcoder Beginner Contest 079-C
〇問題
・0以上9以下の4つの整数の間に ’+’ か ’-’ を入れて計算式を作り、その値が 7 になるものを出力。
〇方針
・8通り全部試すほうが早いが、あえてbit探索を使う。
#include <stdio.h> #include <stdlib.h> int main(){ int A[4],i; char s[4]; scanf("%s",s); for(i=0;i<4;i++){ A[i] = s[i] - '0'; } int j,sum; char op[3]; for(i=0;i<8;i++){ sum = A[0]; for(j=0;j<3;j++){ if( i & ( 1 << j ) ){ op[j] = '+'; sum += A[j+1]; }else{ op[j] = '-'; sum -= A[j+1]; } } if( sum == 7 ){ break; } } for(i=0;i<3;i++){ printf("%d%c",A[i],op[i]); } printf("%d=7\n",A[3]); return 0; }
〇所感
・bit探索は理解したはず。
〇参考記事
・AtCoder 版!蟻本 (初級編) (問題の選択)