#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair P; /*const ll INF=1e18; struct edge {int to; ll cap; int rev;} ; vector G[202]; int level[202]; int iter[202]; void add_edge(int from, int to, ll cap){ edge e; e.to=to, e.cap=cap, e.rev=G[to].size(); G[from].push_back(e); e.to=from, e.cap=0, e.rev=G[from].size()-1; G[to].push_back(e); } void bfs(int s){ memset(level, -1, sizeof(level)); queue que; level[s]=0; que.push(s); while(!que.empty()){ int v=que.front(); que.pop(); for(int i=0; i0 && level[e.to]<0){ level[e.to]=level[v]+1; que.push(e.to); } } } } ll dfs(int v, int t, ll f){ if(v==t) return f; for(int &i=iter[v]; i0 && level[v]0){ e.cap-=d; G[e.to][e.rev].cap+=d; return d; } } } return 0; } ll max_flow(int s, int t){ ll flow=0; while(1){ bfs(s); if(level[t]<0) return flow; memset(iter, 0, sizeof(iter)); ll f; while((f=dfs(s, t, INF))>0){ flow+=f; } } }*/ int p[90]={5,35,25,16,15,0,24,14,3,4,6,7,17,18,27,26,11,1,2,12,32,9,28,19,29,36,33,22,23,13,8,43,45,42,39,44,54,64,31,34,37,55,65,53,52,56,66,76,10,57,46,47,67,77,62,68,78,63,69,21,38,58,59,73,75,60,50,74,30,20,48,49,81,82,83,84,88,61,40,41,85,86,87,79,89,80,70,71,72,51}; int q[90]={0,50,60,80,81,82,83,84,85,86,10,70,61,71,72,73,74,75,76,77,20,1,2,3,4,5,6,7,87,78,30,11,12,13,14,15,16,17,8,88,40,21,22,23,24,25,26,27,18,9,31,41,32,33,34,35,36,37,28,19,51,42,52,43,44,45,46,47,38,29,62,53,63,54,64,55,56,57,48,39,65,66,67,58,68,49,59,69,79,89}; int num[510][504]; int main() { for(int i=0; i<10; i++) for(int j=0; j<9; j++) num[i][j]=j*10+i; for(int i=0; i<500/10; i++){ for(int x=0; x<10; x++){ for(int y=0; y<9; y++){ int x1=q[y*10+x]%10, y1=q[y*10+x]/10; num[(i+1)*10+x1][y1]=num[i*10+x][y]; } } for(int j=0; j<504/9-1; j++){ for(int x=0; x<10; x++){ for(int y=0; y<9; y++){ int x1=p[y*10+x]%10, y1=p[y*10+x]/10; num[i*10+x1][(j+1)*9+y1]=num[i*10+x][j*9+y]; } } } } int n; cin>>n; vector v[90]; for(int i=0; i>x>>y; x--; y--; v[num[x][y]].push_back(i); } for(int i=0; i<90; i++){ if(v[i].size()>=(n+89)/90){ cout<=100) add_edge(j*10+i, l*10+k+90, 1); } } } } max_flow(s, t); for(int i=0; i<90; i++){ for(auto e:G[i]){ if(e.to==s) continue; if(e.cap==0){ p[i]=e.to-90; } } } for(int i=0; i<202; i++){ G[i].clear(); level[i]=iter[i]=0; } for(int i=0; i<90; i++){ add_edge(s, i, 1), add_edge(i+90, t, 1); } for(int i=0; i<10; i++){ for(int j=0; j<9; j++){ for(int k=0; k<10; k++){ for(int l=0; l<9; l++){ int d=(i-10-k)*(i-10-k)+(l-j)*(l-j); if(d>=100) add_edge(j*10+i, l*10+k+90, 1); } } } } max_flow(s, t); for(int i=0; i<90; i++){ for(auto e:G[i]){ if(e.to==s) continue; if(e.cap==0){ q[i]=e.to-90; } } }*/ return 0; }