import sys input = lambda: sys.stdin.readline().rstrip() # sys.setrecursionlimit(10**7) # sys.set_int_max_str_digits(10**6) # import pypyjit # pypyjit.set_param('max_unroll_recursion=-1') def mp():return map(int,input().split()) def lmp():return list(map(int,input().split())) def lm1(LIST): return list(map(lambda x:x-1, LIST)) def mps(A):return [tuple(map(int, input().split())) for _ in range(A)] def stoi(LIST):return list(map(int,LIST)) def itos(LIST):return list(map(str,LIST)) def atoi(LIST): return [ord(i)-ord("a") for i in LIST] def Atoi(LIST): return [ord(i)-ord("A") for i in LIST] def LT(LIST,N): return LIST[bisect.bisect_left(LIST,N)-1] def LE(LIST,N): return LIST[bisect.bisect_right(LIST,N)-1] def GT(LIST,N): return LIST[bisect.bisect_right(LIST,N)] def GE(LIST,N): return LIST[bisect.bisect_left(LIST,N)] def bitA(X,A):return X & 1< best_score:break now_koho.append(nxt) koho = [] best_score = now_koho[0][0] for Score,A,B,Sosa in now_koho: heapq.heappush(koho, dc([Score, A, B, Sosa])) if len(Sosa) == max_limit:continue for i in range(n): for j in range(i+1,n): if Sosa and Sosa[-1] == [i,j]:continue ac = cc(A) bc = cc(B) sosac = cc(Sosa) if ac[i] == ac[j] and bc[i]==bc[j]:continue na,nb = (ac[i]+ac[j])/2, (bc[i]+bc[j])/2 ac[i],ac[j],bc[i],bc[j] = na,na,nb,nb hanei_a,hanei_b = (na+ac[0])/2, (nb+bc[0])/2 now_score = calc_score(hanei_a,hanei_b) sosac.append([i,j]) #if (A == ac and B == bc) or now_score > Score:continue heapq.heappush(koho,[now_score,ac,bc,sosac]) best_koho = heapq.heappop(koho) #best_koho[3] = remove_huyou(best_koho[3]) best_koho = hanei_0(*best_koho) return best_koho def main(): sosa_arr = [] global omote global ura while time.time()-start_time <= 0.85: pred_score,na,nb,sosa_arr = beam_search(omote,ura,sosa_arr) omote = na ura = nb output(sosa_arr) #print(calc_all_score(omote,ura,len(sosa_arr))) #na,nb,sosa_arr = greedy(omote,ura) main()