蟻本練習問題(反転)
反転
問題訳
20個のビット列が与えられる。1つを反転させると両隣のビットも反転される。
全てを0にするのに必要な反転の最小回数は?
解法
最初のビットを反転するかを決めると、全部決まるので2通り
メモ
配列を初期化するのと最初の反転をカウントするのを忘れていた。
コード
#include<stdio.h> #include<iostream> #include<string> #include<vector> #include<map> #include<set> #include<list> #include<queue> #include<deque> #include<algorithm> #include<utility> #include<memory> #include<cmath> #include<stack> #define ALL(g) (g).begin(),(g).end() #define REP(i, x, n) for(int i = x; i < n; i++) #define rep(i,n) REP(i,0,n) #define EXIST(s,e) ((s).find(e)!=(s).end()) #define pb push_back #define DEBUG false using namespace std; typedef long long ll; typedef pair<int,int> P; const int mod=1e9+7,INF=1<<30; const double EPS=1e-12,PI=3.1415926535897932384626; const ll LINF=1LL<<60; const int MAX_N=100005; int a[22],c[22]; int main(){ rep(i,20) cin >> a[i] ; rep(i,20) c[i]=a[i]; int ans=INF; rep(j,2){ int cnt=0; rep(i,20) a[i]=c[i]; if(j){ a[0]^=1; a[1]^=1; cnt++; } rep(i,19){ if(a[i]==1){ a[i]^=1; a[i+1]^=1; a[i+2]^=1; cnt++; } } if(a[19]==0) ans=min(ans,cnt); } cout << ans << endl; return 0; }
問題訳
5x6のマスがあり、1マスを反転させると隣接4マスも反転するようなパズルがある。
パズルの答えを示せ。(最小回数でなくとも良い)
解法
1行目を決めるとパタパタ決まる。
メモ
またも配列の初期化ミスってしんどいことに…
コード
#include<stdio.h> #include<iostream> #include<string> #include<vector> #include<map> #include<set> #include<list> #include<queue> #include<deque> #include<algorithm> #include<utility> #include<memory> #include<cmath> #define ALL(g) (g).begin(),(g).end() #define REP(i, x, n) for(int i = x; i < n; i++) #define rep(i,n) REP(i,0,n) #define EXIST(s,e) ((s).find(e)!=(s).end()) #define pb push_back #define DEBUG false using namespace std; typedef long long ll; typedef pair<int,int> P; const int mod=1e9+7,INF=1<<30; const double EPS=1e-12,PI=3.1415926535897932384626; const ll LINF=1LL<<60; const int MAX_N=1002,MAX_K=102; int a[5][7],c[5][7],ans[5][7]; int dx[5]={0,-1,0,1,0}; int dy[5]={0,0,1,0,-1}; void rev(int i,int j){ rep(k,5){ if((i+dy[k]>=0 &&i+dy[k]<5)&&(j+dx[k]>=0 && j+dx[k]<6)){ c[i+dy[k]][j+dx[k]]^=1; } } } void calc(){ rep(i,5) rep(j,6) scanf("%d",&a[i][j]); bool ok=false; rep(i,1<<6){ rep(j,5) rep(k,6) c[j][k]=a[j][k]; rep(j,5) rep(k,6) ans[j][k]=0; rep(j,6){ ans[0][j]=(i>>j)&1; if(ans[0][j]){ rev(0,j); } } REP(j,1,5){ rep(k,6){ if(c[j-1][k]){ rev(j,k); ans[j][k]=1; } } } ok=true; rep(k,6){ if(c[4][k]) ok=false; } if(DEBUG){ cout << "cnt" << i << endl; rep(k,5){ rep(j,5) cout << ans[k][j] << " " ; cout << ans[k][5] << endl; } cout << "--------" << endl; rep(k,5){ rep(j,5) cout << c[k][j] << " " ; cout << c[k][5] << endl; } cout << endl; } if(ok) break; } if(ok){ rep(i,5){ rep(j,5) cout << ans[i][j] << " " ; cout << ans[i][5] << endl; } } } int main(){ int n; cin >> n ; rep(i,n){ cout << "PUZZLE #" << i+1 << endl; calc(); } return 0; }