#sys.stdout = open(os.devnull, 'w') T = int(fin.readline())
def bribe(rs, s, e): if not rs: return 0 if s >= e: return 0 center = (s + e) / 2.0 closest = e + 2 for i in rs: if abs(center - i) < abs(center - closest): closest = i
left = [a for a in rs if a < closest] right = [a for a in rs if a > closest] print s, e, closest, e - s, left, right return (e - s) + bribe(left, s, closest - 1) + bribe(right, closest + 1, e)
solutions = {} def dynamic_bribe(rs, s, e, space): if not rs: return "", 0 if s >= e: return '', 0 s0 = 1 e0 = e - s + 1 rs0 = [a - s + 1 for a in rs]
key = str(e0) + ':' + (',').join(str(a) for a in rs0) keystr = str(s) + '~' + str(e) + ':' + (',').join(str(a) for a in rs) solution = solutions.get(key) if solution: #print space, s, e, rs, solution, "key:" + key #return '\n' + space + '<' + keystr + '_' + str(solution) + '>\n', solution return '', solution else: candidate = sys.maxint way = "" for r in rs: left = [a for a in rs if a < r] right = [a for a in rs if a > r] left_way, lc = dynamic_bribe(left, s, r-1, space + ' ') right_way, rc = dynamic_bribe(right, r+1, e, space + ' ') cc = (e - s) + lc + rc if cc < candidate: candidate = cc way = '\n' + space + '<' + keystr + '_' + str(cc) + ',' + left_way + ',' + right_way + '>\n' solution = candidate solutions[key] = solution #print space, s, e, rs, solution #return way, solution return '', solution
#print dynamic_bribe([3], 1, 8, '') def solve(P, Q, rs): a = bribe(rs, 1, P) #print '' #if a != b: # print "DIFFERENT", a, b, a > b return a
def dynamic_solve(P, Q, rs): way, b = dynamic_bribe(rs, 1, P, '') print way return b
cases = [15]
for i in range(T): #if i > 3: # break solutions = {} P, Q = map(int, fin.readline().split()) rsline = fin.readline() rs = map(int, rsline.split())
#if i in cases: if True: print P, Q, rs #answer = solve(P, Q, rs) #line = "Case #%d: %s" % (i+1, str(answer)) #print line + '; ' + rsline + '\n' #f1out.write(line + '\n') answer2 = dynamic_solve(P, Q, rs) line2 = "Case #%d: %s" % (i+1, str(answer2)) print line2 + '; ' + rsline + '\n' fout.write(line2 + '\n')
RECENT COMMENT