Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
Grundy Number
#include<bits/stdc++.h> using namespace std; #define ll long long int ll a[100005]; ll pow2[20]; ll pow16[5]; ll G[66000]; ll check(ll mat[][4],ll i,ll j,ll l, ll k) { for(int m1=i;m1<=j;m1++) for(int n1=l;n1<=k;n1++) if(mat[m1][n1]==0) return 0; return 1; } ll grundy(ll N) { if(G[N]!=-1) return G[N]; set<ll> S; ll mat[4][4]={0}; ll count=15; for(int m1=3;m1>=0;m1--) { for(int n1=3;n1>=0;n1--) { if(N>=pow2[count]) { mat[m1][n1]=1; N=N-pow2[count]; } count--; } } for(int i=0;i<3;i++) { for(int j=i;j<3;j++) { for(int l=0;l<3;l++) { for(int k=l;k<3;k++) { if(check(mat,i,j,l,k)) { S.insert((pow16[k+1]-pow16[l])*(pow2[j+1]-pow2[i])); //S.insert(grundy((pow16[k+1]-pow16[l])*(pow2[j+1]-pow2[i]))); } } } } } count=0; for(set<ll>::iterator it=S.begin();it!=S.end();it++) { cout<<*it<<endl; /* if(*it!=count) return G[N]=count; count++;*/ } return G[N]=count; } void pre() { pow2[0]=1; pow16[0]=1; pow16[1]=16; pow16[2]=256; pow16[3]=4096; pow16[4]=65536; for(int i=1;i<20;i++) pow2[i]=pow2[i-1]*2; memset(G,-1,sizeof(G)); G[0]=0; G[pow2[4]-1]=grundy(pow2[4]-1); } int main() { pre(); for(int i=0;i<pow2[4];i++) cout<<i<<" "<<G[i]<<endl; ll t; cin>>t; while(t--) { ll n,m; cin>>n>>m; for(int i=0;i<n;i++) { ll num=0,c=0; for(int j=0;j<4;j++) { string s; cin>>s; if(j!=5) { for(int l=0;l<s.size();l++) { if(s[l]=='1') num+=pow2[c]; c++; } } } a[i]=num; cout<<a[i]<<endl; } } }
run
|
edit
|
history
|
help
0
multimap
5
sample1
MatrixVectorConversion
Continuous Sub Set with given sum
Jilebi Nimki
Value equal to index value
char
ThreadPool
PriorQ2