Skip to content

Instantly share code, notes, and snippets.

@peienwu
Created May 20, 2022 09:45
Show Gist options
  • Save peienwu/5ead95bfcb358434efd029bd338507e7 to your computer and use it in GitHub Desktop.
Save peienwu/5ead95bfcb358434efd029bd338507e7 to your computer and use it in GitHub Desktop.
#include <bits/stdc++.h>
#define ld long double
#define int long long int
#define IOS ios::sync_with_stdio(0),cout.tie(0)
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;
bool table[8][8];
int n = 3,test[40],timer = 0;
int tp[30];
const ld full = pow(2,n*n);
fstream f;
set<int> st;
bitset<16> sss;
bool set_table(int s){
memset(table,0,sizeof(table));
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
if(s % 2 == 1){
table[i][j] = 1;
for(int p = max(i-1,(int)1);p <= min(i+1,n);p++){
for(int q = max(j-1,(int)1);q <= min(j+1,n);q++){
table[p][q] = 1;
}
}
}
s = s >> 1;
}
}
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
if(!table[i][j])return 0;
}
}
return 1;
}
int times(int s){
int ans = 0;
for(int i = 1;i <= (n*n);i++){
if(s % 2)ans++;
s = s >> 1;
}
return ans;
}
void print(int s){
for(int i = 1;i <= (n*n);i++){
cout<<s%2<<" ";
s = s >> 1;
if(i % 4 == 0)cout<<endl;
}
cout<<endl;
}
void dfs(int s,int id,bool pass){
timer++;
if(timer % 100000 == 0){
cout<<"Processing: "<<(ld)timer / full<<endl;
}
if(id > (n*n))return;
if(pass == 1 || set_table(s)){
if(pass == 0 && set_table(s)){
tp[times(s)] += 1;
//print(s);
// sss = s;
// cout<<sss<<endl;
// cout<<times(s)<<endl;
// cout<<endl;
}
st.insert(s);
// sss = s;
// cout<<sss<<endl;
dfs((s|(1<<id)),id+1,1);
dfs((s),id+1,1);
return;
}
dfs((s|(1<<id)),id+1,0);
dfs((s),id+1,0);
return;
}
signed main(){
IOS;
memset(table,0,sizeof(table));
memset(tp,0,sizeof(tp));
dfs(0,0,0);
int total[100];memset(total,0,sizeof(total));
cout<<st.size()<<endl;
for(auto it = st.begin();it != st.end();it++){
total[times(*it)] += 1;
}
for(int i = 1;i <= (n*n);i++)cout<<total[i]<<" ";
cout<<endl;
for(int i = 1;i <= (n*n);i++)cout<<i<<" ";
cout<<endl<<endl;
int temp = 0;
for(int i = 1;i <= (n*n);i++){
cout<<tp[i]<<" ";temp+=tp[i];
}
cout<<endl;
ld posi = 0.0;
for(int i = 1;i <= (n*n);i++){
posi += i * ((ld)tp[i] / temp);
}
cout<<posi<<endl;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment