from time import time st=time() import sys input = lambda: sys.stdin.readline().rstrip() from math import log10,exp from copy import copy,deepcopy from random import randint,random,choice from bisect import bisect,bisect_left,insort MAX_OP=50 FIRST_PHASE=0.2 TIME_LIMIT=0.9 TARGET_NUM=5*10**17 # カード1のスコアだけ見ればいいのか # 奇数回目の操作でカード1以外を操作する # 偶数回目でカード1を操作する # カード1のスコアを計算 def calc_front():return abs(tempAB[0][0]-TARGET_NUM) def calc_back():return abs(tempAB[0][1]-TARGET_NUM) def calc_Score(cnt): V1=calc_front() V2=calc_front() temp=max(V1,V2) if temp==0:return 2000050-cnt return int(2000000-100000*log10(temp+1)) # 二枚のカードの表裏の平均値を返す def calc_ave(u,v): retf=(tempAB[u][0]+tempAB[v][0])//2 retb=(tempAB[u][1]+tempAB[v][1])//2 return retf,retb def rewrite(u,v): tempf,tempb=calc_ave(u,v) tempAB[u][0]=tempf tempAB[v][0]=tempf tempAB[u][1]=tempb tempAB[v][1]=tempb def Judge(N,AB,X,UV): def WrongAnswer(str): print("Wrong Answer (" + str + ")") sys.exit(0) # Step 1. テストケースの入力を受け取る A = [0] * (N + 1) B = [0] * (N + 1) for i in range(1, N+1): A[i], B[i] = AB[i-1] # Step 2. あなたの出力を受け取る if X < 0 or X > 50: WrongAnswer("X is out of range") U = [0] * (X + 1) V = [0] * (X + 1) for i in range(1, X+1): U[i], V[i] = UV[i-1] if U[i] == V[i]: WrongAnswer("U[i] and V[i] are same") elif U[i] < 1 or U[i] > N: WrongAnswer("U[i] is out of range") elif V[i] < 1 or V[i] > N: WrongAnswer("V[i] is out of range") # Step 3. シミュレーションを行う for i in range(1, X+1): avgA = (A[U[i]] + A[V[i]]) // 2 avgB = (B[U[i]] + B[V[i]]) // 2 A[U[i]] = avgA A[V[i]] = avgA B[U[i]] = avgB B[V[i]] = avgB # Step 4. 出力 ErrorA = abs(500000000000000000 - A[1]) ErrorB = abs(500000000000000000 - B[1]) Score = (int)(2000000.0 - 100000.0 * log10(1.0 * max(ErrorA, ErrorB) + 1.0)) if ErrorA == 0 and ErrorB == 0: Score = 2000050 - X print("Accepted!") print("Error of A[1] = " + str(ErrorA)) print("Error of B[1] = " + str(ErrorB)) print("Score = " + str(Score)) N=int(input()) AB=[list(map(int, input().split())) for _ in range(N)] NowScore=0 UV=[] while time()-st<=TIME_LIMIT: tempAB=deepcopy(AB) tempUV=[] preop=-1 opcnt=randint(0,MAX_OP) # 奇数回目は1にマッチさせるものを選ぶ # 偶数回目で1とマッチさせる for cnt in range(1,opcnt+1): if cnt&1: tarf=2*TARGET_NUM-tempAB[0][0] tarb=2*TARGET_NUM-tempAB[0][1] preScore=10**20 u,v=-1,-1 # 適当にu,vの平均を計算してaとマッチさせられるか考える for _ in range(20): tu=randint(1,N-1) tv=randint(1,N-1) while tu==tv:tv=randint(0,N-1) tf,tb=calc_ave(tu,tv) temp=abs(tf-tarf)+abs(tb-tarb) if tempNowScore: NowScore=tempScore UV=deepcopy(tempUV) # else: # T=(time()-st)/TIME_LIMIT # if exp((tempScore-NowScore)/T)>random(): # NowScore=tempScore # UV=deepcopy(tempUV) print(len(UV)) for u,v in UV:print(u,v)