Ideone.com

fork download

copy

#include <iostream>
#include <fstream>
#include <cstring>
#include <bitset>
using namespace std;
 
int lim = 1 << 16;
int mat[1 << 16];
//int arr[] = {-1,-4,0,1,4};
 
void swi(int &n) {
  if(n == 0) n = 1;
  if(n == 1) n = 0;
}
 
int soloUno(int x,int i) {
  x ^= (1 << i);
  return x;
}
 
bool potenciaDeDos(int n) {
  if(n == 0 or n == 1) return true;
  if(n % 2 != 0) return false;
  return potenciaDeDos(n >> 1);
}
 
int todos(int x,int i) {
  x ^= (1 << i);
  int aux = i - 1;
  if(aux >= 0) x ^= (1 << aux);
  aux = i - 4;
  if(aux >= 0) x ^= (1 << aux);
  aux = i + 1;
  if(aux < 16) x ^= (1 << aux);
  aux = i + 4;
  if(aux < 16) x ^= (1 << aux);
  return x;
}
 
int dp(int n) {
  if(n == 0) return 0;
  int &r = mat[n];
  if(potenciaDeDos(n)) r = 2;
  if(r == -1) {
    r = 100000;
    for(int i = 0; i < 16; ++i) {
      if(r == 1) return 1;
      r = min(r,min(2 + dp(soloUno(n,i)),1 + dp(todos(n,i))));
    }
  }
  return r;
}
 
int main() {
  //freopen("EcualizadorDJ.in","r",stdin);
  //freopen("EcualizadorDJ.out","w,",stdout);
  memset(mat,-1,sizeof mat);
  mat[0] = 0;
  //for(int i = 3; i < lim; ++i) dp(i);
  int T;
  cin >> T;
  string s,total;
  while(T--) {
    total = "";
    for(int i = 0; i < 4; ++i) {
      cin >> s;
      total += s;
    }
    bitset<20> bs(total);
    cout << total << endl;
    cout << dp(bs.to_ulong()) << endl;
  }
}

Success #stdin #stdout 0.07s 6060KB

stdin

copy

stdout

copy

1100100000000000
1
0100111001000000
1
1000000000000000
2
1100100000000001
3
1011101000000000
2
0010011101100111
6
1111001000010100
7
1001011001101001
4
1010011110100110
7
1101110101000100
6
0110110000010111
6
0011100101100011
7
1000111100100011
5
1100000101110101
4
0100111111100101
3
0110000011000100
8
0110110001000001
7
1110000100000100
6
0001101001011101
6
0101010110010100
100000
0110100110010110
8
0000011001100000
6
0110111111110110
4
0110011111111100
6
1110001111011101
5
1010110101101101
7
0000111110011111
6
1011110101001010
8
0101110110111001
8
1111111111111111
7
1011010001011010
8
1111110000111111
5
1010010110100101
5
0101101001011010
6
0100100011010110
3
1001000000001001
5
1011101000000000
2
0001010111111011
6
1111101101101101
7
1010110001010011
6
0100101001000000
3
1111101111011111
7
0110100101100000
2
1111110110111111
7
0100100001000000
5

https://ideone.com/8eruqZ

language:

C++ (gcc 8.3)

created:

visibility:

public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language