#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')
Qualification Round. Code Jam will start with a qualification round on Friday, April 10, 2015 at 23:00 UTC (4:00 PM PT) and run for 27 hours, ending on Sunday, April 12, 2015 at 2:00 UTC (Saturday, April 11, 2015 at 7:00pm PT). In the Qualification Round, you must log in to the Contest website to attempt to solve a number of problems within the 27-hour period. If you earn a minimum number of points during the qualification round, which will be displayed on the Contest website, you will advance to Round 1 of Code Jam.
QR은 절대평가. 쉽다고 한다.
Round 1. Code Jam Round 1 is conducted online and is offered in three sub-rounds at the times specified at https://code.google.com/codejam/schedule.html from Saturday, April 18, 2015 (Friday, April 17th PST) to Sunday, May 10, 2015. If you advanced to Code Jam Round 1, you can participate in any or all of the sub-rounds by logging into the Contest website to solve a number of problems until you qualify for Code Jam Round 2. However, once you qualify for Code Jam Round 2, you may not participate in any later sub-rounds of Code Jam Round 1. You will advance to Code Jam Round 2 if you are one of the top-scoring 1000 contestants from one of the sub-rounds in Code Jam Round 1. You will be notified by email after the end of each sub-round if you are one of the 3000 contestants advancing to Code Jam Round 2.
If you advanced to Code Jam Round 1, you can participate in any or all of the sub-rounds by logging into the Contest website to solve a number of problems until you qualify for Code Jam Round 2. However, once you qualify for Code Jam Round 2, you may not participate in any later sub-rounds of Code Jam Round 1.
RECENT COMMENT