| jack's profilenash's spacePhotosBlogLists |  Tools  Help |
|
August 10 PKU_ACM_1727problem statement: http://acm.pku.edu.cn/JudgeOnline/problem?id=1727 my solution: (written in python) ####################################################################################################### def partition(Set, k): # return all possible partitions that partition 'Set' into k subsets. # 'Set' is a list having plain set element as its elements, e.g. [1, 2, 3, 4]. # Return a list (list_1), element of which is also a list (list_2) representing a possible partition. # element of list_2 is again a list (list_3) representing a subset of the partition list_2, # element of list_3 is plain set element. # For example, when 'Set' == [1, 2, 3, 4] # if k == 1, then return [[[1, 2, 3, 4]]] # if k == 2, then return [[[1], [2, 3, 4]], [[2], [1, 3, 4]], [[3], [1, 2, 4]], [[4], [1, 2, 3]], [[1, 2], [3, 4]], [[1, 3], [2, # 4]], [[1, 4], [2, 3]]] if k == 1: return [[Set]] elif len(Set) >= k: # only in this way partition is possible eln = Set[len(Set) - 1] # [eln] is a subset of the partition sub_1 = partition(Set[:-1], k - 1) # recursively call 'partition' for i in sub_1: i.append([eln]) # [eln] itself is not a subset of the partition sub_3 = [] if len(Set) - 1 >= k: # to guarantee 'partition(Set[:-1], k)' can be performed sub_2 = partition(Set[:-1], k) # recursively call 'partition', for every 'list_2' of 'sub_2', adjusting it by adding # element 'eln' to one of its 'list_3' generates a desired partition. for list_2 in sub_2: for list_3 in list_2: list_3_temp = list_3 + [eln] list_2_temp = [] for i in list_2: if i != list_3: list_2_temp.append(i) else: list_2_temp.append(list_3_temp) sub_3.append(list_2_temp) if len(sub_3) > 0: return sub_1 + sub_3 else: return sub_1 else: # 'k' > len(Set), the required partition is impossible, return with an error message. print('ERROR IN PARTITION(). trying to partition a set with less than k elements into k subsets, Impossible Mission!!!') exit def time_satisfied(coordinates): # 'coordinates' is a list, element of which is a list of length 2 representing a (event, time) pair # return the solution for 'case' == 1 # For example, if 'coordinates' == [[-1, 1], [3, 1], [4, 1], [6, 2]] # return -2. if len(coordinates) == 1: return coordinates[0][1] print('input coors is: ', coordinates) from math import cos, sin, pi, floor angle = pi / 4 rotation_matrix = [[cos(angle), sin(angle)], [-sin(angle), cos(angle)]] coordinates_2 = [[sum([rotation_matrix[i][j] * pair[j] for j in range(2)]) for i in range(2)] for pair in coordinates] for i in range(len(coordinates_2)): # assign index for each (event, time) pair coordinates_2[i] += [i] coordinates_2.sort() # sort the (event, time) pairs according to main diagonal of the original event, time coordinate system left_index = coordinates_2[0][2] # coordinates_2.sort(key = lambda x: x[1]) # sort the pairs according to second main diagonal of the original event, time cs. right_index = coordinates_2[0][2] # using the 'reverse_rotation_matrix' involes floating computing, therefore may not get the original exact integer coordinate, # and may comprimise the final compute of 'time'. # reverst_rotation_matrix = [[cos(-angle), sin(-angle)], [-sin(-angle), cos(-angle)]] # go back to the original coordinate system # left = [sum([reverst_rotation_matrix[i][j] * left[j] for j in range(2)]) for i in range(2)] # sright = [sum([reverst_rotation_matrix[i][j] * sright[j] for j in range(2)]) for i in range(2)] left = coordinates[left_index] right = coordinates[right_index] print('time_satisfied is: ', floor(left[1] - (right[0] - left[0] + left[1] - right[1]) / 2)) print('---------------------------------------') return floor(left[1] - (right[0] - left[0] + left[1] - right[1]) / 2) if __name__ == '__main__': # use test input of the problem statement to test. correct. coordinates = [[-1, 1], [3, 1], [4, 1], [6, 2]] Set_index = [0, 1, 2, 3] for i in range(4): time = -4000000 i += 1 partitions = partition(Set_index, i) for list_2 in partitions: time_2 = 4000000 for list_3 in list_2: coor = [] for j in list_3: coor.append(coordinates[j]) time_2 = min(time_2, time_satisfied(coor)) time = max(time, time_2) print('**************************************************************************') print('case number is: ', i) print('time_satisfied is: ', time) print('^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^') ###################################################################################################### any comment is welcome!  TrackbacksThe trackback URL for this entry is: http://daodan1664.spaces.live.com/blog/cns!16DE159894E564F1!363.trak Weblogs that reference this entry
|
|
|
