#include #include #define rep(i,a,b) for(int i=a;i=a;i--) #define all(x) (x).begin(),(x).end() #define pb(x) push_back(x); templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b P; const int N = 45; const int M = 50; ll A[N],B[N]; void Input(){ int _n;cin >> _n; rep(i,0,N)cin >> A[i] >> B[i]; } struct Solution{ int X=0; vector u,v; P Simulate(){ ll a[N],b[N];rep(i,0,N)a[i]=A[i],b[i]=B[i]; rep(i,0,X){ ll tmp1=(a[u[i]]+a[v[i]])/2; ll tmp2=(b[u[i]]+b[v[i]])/2; a[u[i]]=tmp1;a[v[i]]=tmp1; b[u[i]]=tmp2;b[v[i]]=tmp2; } return P(a[0],b[0]); } lld CalcScore(){ P res=Simulate(); ll max_v=max(abs(BASE-res.first),abs(BASE-res.second)); return log10(max_v); } void Output(){ cout << X << endl; rep(i,0,X)cout << u[i]+1 << " " << v[i]+1 << endl; } }; Solution InitSolve(){ Solution res_sol; set st; st.insert(0); rep(i,0,M){ int x=random()%N; int y=random()%N; while(true){ if(x!=y&&(st.count(x)||st.count(y))){ break; } x=random()%N; y=random()%N; } res_sol.u.pb(x); res_sol.v.pb(y); res_sol.X++; st.insert(x); st.insert(y); } reverse(all(res_sol.u)); reverse(all(res_sol.v)); return res_sol; } Solution Suggest(Solution &sol){ Solution next_sol=sol; lld next_score=INF; int idx=random()%M; int pre_x=sol.u[idx]; int pre_y=sol.v[idx]; rep(x,0,N)rep(y,0,N){ if(x==y)continue; sol.u[idx]=x; sol.v[idx]=y; lld score=sol.CalcScore(); if(chmin(next_score,score)){ next_sol.u[idx]=x; next_sol.v[idx]=y; } } sol.u[idx]=pre_x; sol.v[idx]=pre_y; return next_sol; } Solution PartSuggest(Solution &sol){ Solution next_sol=sol; set idxs; int swap_size=random()%5+1; while(idxs.size() idxs_v;for(auto idx:idxs)idxs_v.pb(idx); sort(all(idxs_v));reverse(all(idxs_v)); for(auto idx:idxs_v){ int x=random()%N; int y=random()%N; while(true){ bool break_flag=true; if(x==y){ break_flag=false; } if(idx==M-1){ if(x!=0&&y!=0){ break_flag=false; } } if(break_flag){ break; } x=random()%N; y=random()%N; } next_sol.u[idx]=x; next_sol.v[idx]=y; } return next_sol; } Solution HillClimbing(Solution sol){ int cnt=0; Solution now_sol=sol; lld now_score=now_sol.CalcScore(); while((double)(clock()-start)/CLOCKS_PER_SECmax(next_v1,next_v2)){ // now_v1=next_v1; // now_v2=next_v2; // now_sol.u[idx]=next_x; // now_sol.v[idx]=next_y; // } // else{ // lld log_now_score = log10(max(now_v1,now_v2)); // lld log_next_score = log10(max(next_v1,next_v2)); // double prob = exp((log_next_score-log_now_score)/temp); // if(prob>lld(BigRandom()%INF)/INF){ // now_v1=next_v1; // now_v2=next_v2; // now_sol.u[idx]=next_x; // now_sol.v[idx]=next_y; // } // } // cnt++; if(cnt%100==0)cerr << cnt << " " << temp << endl; } cerr << "cnt: " << cnt << endl; return now_sol; } int main(void){ ios::sync_with_stdio(false); cin.tie(nullptr); Input(); Solution sol=InitSolve(); // P res=sol.Simulate(); Solution next_sol=HillClimbing(sol); // Solution next_sol=SimulatedAnnealing(sol); P next_score=next_sol.Simulate(); ll next_v1=abs(BASE-next_score.first); ll next_v2=abs(BASE-next_score.second); cerr << next_v1 << " " << next_v2 << endl; next_sol.Output(); // sol.Output(); return 0; }