from time import time st=time() import sys input = lambda: sys.stdin.readline().rstrip() from math import log10 from copy import copy,deepcopy from random import randint,random,choice from bisect import bisect,bisect_left,insort MAX_OP=50 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 rewrite(u,v): tempf=(tempAB[u][0]+tempAB[v][0])//2 tempAB[u][0]=tempf tempAB[v][0]=tempf tempb=(tempAB[u][1]+tempAB[v][1])//2 tempAB[u][1]=tempb tempAB[v][1]=tempb def Judge(N,AB,X,UV): def WrongAnswer(str): print("Wrong Answer (" + str + ")") 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=[] premove=-1 preop=-1 while time()-st<=TIME_LIMIT: tempAB=deepcopy(AB) tempUV=[] pretempScore=0 opcnt=randint(0,MAX_OP) for cnt in range(1,opcnt+1): # 各カード表裏について値を記録する F_set=[] B_set=[] for i in range(1,N): a,b=tempAB[i] insort(F_set,(a,i)) insort(B_set,(b,i)) if cnt&1: F,B=tempAB[0] # 表裏を適当に書き換える k=randint(0,1) preop=k if k: while 1: a,u=choice(F_set) t=calc_front() bk=bisect_left(F_set,(2*t-a,0)) if bk>=N-1:bk=N-2 b,v=F_set[bk] if u!=v:break rewrite(u,v) else: while 1: c,u=choice(B_set) t=calc_back() dk=bisect_left(B_set,(2*t-c,0)) if dk>=N-1:dk=N-2 d,v=B_set[dk] if u!=v:break rewrite(u,v) tempUV.append((u+1,v+1)) else: k=randint(0,1) if k: a=tempAB[0][0] bk=bisect_left(F_set,(2*TARGET_NUM-a,0)) if bk>=N-1:bk=N-2 b,v=F_set[bk] rewrite(0,v) else: c=tempAB[0][1] dk=bisect_left(B_set,(2*TARGET_NUM-c,0)) if dk>=N-1:dk=N-2 d,v=B_set[dk] rewrite(0,v) tempUV.append((1,v+1)) tempScore=calc_Score(cnt) if tempScore>NowScore: NowScore=tempScore UV=deepcopy(tempUV) print(len(UV)) for u,v in UV:print(u,v) Judge(N,AB,len(UV),UV)