from time import time start_time = time() import sys import io, os input = sys.stdin.readline #input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline import math import random random.seed(42) m = 50 TIME_LIMIT = 0.85 L = 5*10**17 start_temp = 10**14 end_temp = 1000 def move_element(lst, i, j): lst_ = lst.copy() element = lst_.pop(i) lst_.insert(j, element) return lst_ n = int(input()) A = [0]*n B = [0]*n for i in range(n): a, b = map(int, input().split()) A[i] = a B[i] = b ans = [] for i in range(m-1): u, v = random.sample(range(n), 2) ans.append((u, v)) v = random.randint(1, n-1) ans.append((0, v)) def calc_score(ans): Ac = A.copy() Bc = B.copy() for u, v in ans: x = (Ac[u]+Ac[v])//2 Ac[u], Ac[v] = x, x y = (Bc[u]+Bc[v])//2 Bc[u], Bc[v] = y, y v1 = abs(L-Ac[0]) v2 = abs(L-Bc[0]) cost = max(v1, v2) return cost cost = calc_score(ans) best_cost = cost best_ans = ans.copy() iter = 0 while True: iter += 1 now_time = time() if now_time - start_time > TIME_LIMIT: break neigh = neigh = random.randint(0, 1) if neigh == 0: # ランダムに1操作を選んで変更する i = random.randint(0, m-1) if i != m-1: idx = random.randint(0, 1) u = ans[i][idx] while True: v = random.randint(0, n-1) if v == u: continue break else: v = random.randint(1, n-1) u = 0 pre = ans[i] ans[i] = (u, v) new_cost = calc_score(ans) if new_cost <= best_cost: best_cost = new_cost best_ans = ans.copy() temp = start_temp+(end_temp-start_temp)*(now_time-start_time)/TIME_LIMIT if new_cost <= cost: prob = 1 else: #prob = math.exp((cost-new_cost)/temp) prob = 0 if prob > random.random(): cost = new_cost else: ans[i] = pre else: # ランダムに1操作の位置を変更する i = random.randint(0, m-2) j = random.randint(0, m-2) new_ans = move_element(ans, i, j) new_cost = calc_score(new_ans) if new_cost <= best_cost: best_cost = new_cost best_ans = ans.copy() temp = start_temp+(end_temp-start_temp)*(now_time-start_time)/TIME_LIMIT if new_cost <= cost: prob = 1 else: #prob = math.exp((cost-new_cost)/temp) prob = 0 if prob > random.random(): cost = new_cost ans = new_ans.copy() print(len(best_ans)) for i in range(len(best_ans)): u, v = best_ans[i] u, v = u+1, v+1 print(u, v) if cost != 0: score = (int)(2000000-100000*math.log10(best_cost+1)) else: score = 2000050-len(best_ans) print(cost, file=sys.stderr) print(iter, file=sys.stderr) print(score, file=sys.stderr)