Untitled
unknown
python
a year ago
8.2 kB
1
Indexable
Never
# define some functions
def get_D2Q(Dis_list, boundary_list):
m = len(Dis_list)
D2Q = [[0 for j2 in range(m)] for j1 in range(m)]
for j1 in range(m):
for j2 in range(m):
distance = Dis_list[j1][j2]
if distance>boundary_list[-1]:
D2Q[j1][j2] = 4
else:
for i, boundary in enumerate(boundary_list):
if boundary>=distance:
D2Q[j1][j2] = i
break
return D2Q
def get_Q_past2current(decrease_scale_row, Q_list):
total_Q = 0
for Q_index in range(4):
total_Q += decrease_scale_row[Q_index] * Q_list[Q_index]
return total_Q
def get_QR_current2past(weighted_decrease_scale_row, Q_list):
total_QR = 0
for Q_index in range(4):
total_QR += weighted_decrease_scale_row[Q_index] * Q_list[Q_index]
return total_QR
def get_delta_T_list(decrease_scale, weighted_decrease_scale, R_list, U_list, Q_list, A_list, B_list):
delta_T_list = [[-1000 for j in range(m)] for i in range(n)]
for i in range(n):
# check if car of type i still remains
if A_list[i]<=0:
continue
for j in range(m):
# check if stop j still can be filled with new cars
if B_list[j]<=0:
continue
# calculate delta_T
total_Q_past_cars_to_current_car = get_Q_past2current(decrease_scale[j], Q_list)
total_QR_current_car_to_past_cars = get_QR_current2past(weighted_decrease_scale[j], Q_list)
delta_T = 24 * R_list[i] * (U_list[i][j] - total_Q_past_cars_to_current_car) - total_QR_current_car_to_past_cars
# fill into delta_T_list
delta_T_list[i][j] = delta_T
#print(delta_T_list)
return delta_T_list
def distance_get_best_ij(delta_T_list, Dis_list):
# get each stop's total distance
total_distance_list = [0] * m
for j in range(m):
total_distance_list[j] = sum(Dis_list[j])
# find best_delta_T
best_delta_T = 0
I, J = -1, -1
for i in range(len(delta_T_list)):
for j in range(len(delta_T_list[0])):
if delta_T_list[i][j] > best_delta_T:
I = i
J = j
best_delta_T = delta_T_list[i][j]
if I==-1 and J==-1:
return I, J, best_delta_T
# traverse again to get combination with best_delta_T and minimum distance
min_distance = max(total_distance_list)
I, J = -1, -1
for i in range(len(delta_T_list)):
for j in range(len(delta_T_list[0])):
if delta_T_list[i][j] == best_delta_T:
total_distance = total_distance_list[j]
if total_distance < min_distance:
I = i
J = j
min_distance = total_distance
return I, J, best_delta_T
def naive_get_best_ij(delta_T_list):
best_delta_T = 0
I, J = -1, -1
for i in range(len(delta_T_list)):
for j in range(len(delta_T_list[0])):
if delta_T_list[i][j] > best_delta_T:
I = i
J = j
best_delta_T = delta_T_list[i][j]
return I, J, best_delta_T
def update_decrease_scale(decrease_scale, J, D2Q):
for j in range(m):
# consider > 1000
if D2Q[J][j]==4:
continue
decrease_scale[j][D2Q[J][j]] += 1
return decrease_scale
def update_weighted_decrease_scale(weighted_decrease_scale, I, J, D2Q, R_list):
R = R_list[I]
for j in range(m):
# consider > 1000
if D2Q[J][j]==4:
continue
weighted_decrease_scale[j][D2Q[J][j]] += 24 * R
return weighted_decrease_scale
def update_ans_list(ans_list, I, J):
ans_list[I][J] += 1
return ans_list
#--------------------------------------------
# read input
n = 2
m = 3
Q_list = [0.1, 0.05, 0.03, 0.01]
R_list = [50, 70]
A_list = [10, 5]
B_list = [10, 8, 7]
U_list = [[0.9, 0.8, 0.7],
[0.7, 0.85, 0.75]]
Dis_list = [[0, 350, 800],
[350, 0, 450],
[800, 450, 0]]
# [[5,3,1], [1,3,1]] -> 3091.2
# sample input:
'''
2 3 0.01 0.05 0.03 0.01
50 70
10 5
10 8 7
0.9 0.8 0.7
0.7 0.85 0.75
0 350 800
350 0 450
800 450 0
'''
# input lines
n, m, *Q_list = input().split(' ')
n, m = int(n), int(m)
Q_list = [float(q) for q in Q_list]
R_list = input().split(' ')
R_list = [int(R) for R in R_list]
A_list = input().split(' ')
A_list = [int(A) for A in A_list]
B_list = input().split(' ')
B_list = [int(B) for B in B_list]
U_list = []
for i in range(n):
U_row = input().split(' ')
U_row = [float(U) for U in U_row]
U_list.append(U_row)
Dis_list = []
for j in range(m):
Dis_row = input().split(' ')
Dis_row = [int(Dis) for Dis in Dis_row]
Dis_list.append(Dis_row)
'''
print('input check:')
print(n)
print(m)
print(Q_list)
print(R_list)
print(A_list)
print(B_list)
print(U_list)
print(Dis_list)
print('done ###################################3')
'''
#--------------------------------------------------
# init ans_list
ans_list = [[0 for j in range(m)] for i in range(n)]
# init boundary_list
boundary_list = [0, 300, 500, 1000]
# init decrease_scale
decrease_scale = [[0 for j in range(4)] for i in range(m)]
weighted_decrease_scale = [[0 for j in range(4)] for i in range(m)]
# get D2Q
D2Q = get_D2Q(Dis_list, boundary_list)
# init T (target)
T = 0
# put 1st car
# delta_T_list[n][m]
delta_T_list = get_delta_T_list(decrease_scale, weighted_decrease_scale, R_list, U_list, Q_list, A_list, B_list)
# get the best i, j for the new car (considering distance)
I, J, best_delta_T = distance_get_best_ij(delta_T_list, Dis_list)
# if I, J == -1 break (best_delta_T occurs when we do not put into new car)
if I!=-1 and J!=-1:
# update decrease_scale
decrease_scale = update_decrease_scale(decrease_scale, J, D2Q)
# update weighted_decrease_scale
weighted_decrease_scale = update_weighted_decrease_scale(weighted_decrease_scale, I, J, D2Q, R_list)
# update ans_list
ans_list = update_ans_list(ans_list, I, J)
# update T
T += best_delta_T
# update A_list and B_list
A_list[I] -= 1
B_list[J] -= 1
# put 2nd to Ath car
while sum(A_list)>0 and sum(B_list)>0:
# get delta_T_list
delta_T_list = get_delta_T_list(decrease_scale, weighted_decrease_scale, R_list, U_list, Q_list, A_list, B_list)
# get the best i, j for the new car
I, J, best_delta_T = naive_get_best_ij(delta_T_list)
# if I, J == -1 break (best_delta_T occurs when we do not put into new car)
if I==-1 or J==-1:
break
# update decrease_scale
decrease_scale = update_decrease_scale(decrease_scale, J, D2Q)
# update weighted_decrease_scale
weighted_decrease_scale = update_weighted_decrease_scale(weighted_decrease_scale, I, J, D2Q, R_list)
# update ans_list
ans_list = update_ans_list(ans_list, I, J)
# update T
T += best_delta_T
# update A_list and B_list
A_list[I] -= 1
B_list[J] -= 1
# output answer
#print('ans_list:\n', ans_list)
#print('revenue:', T)
# output lines
for i in range(n):
output_string = ''
for j in range(m):
output_string += str(ans_list[i][j])
output_string += ','
print(output_string[:-1])
# -------------------------------------------------------
# verification function
def get_total_T(ans_list, R_list, U_list, Q_list, D2Q):
total_T = 0
for i in range(n):
for j in range(m):
# get adjusted_utility (= utility - total_Q + Q_list[0])
total_Q = 0
for j2 in range(m):
for i2 in range(n):
if D2Q[j][j2]==4:
continue
total_Q += Q_list[D2Q[j][j2]] * ans_list[i2][j2]
adjusted_utility = U_list[i][j] - total_Q + Q_list[0]
# get T
total_T += 24 * R_list[i] * adjusted_utility * ans_list[i][j]
return total_T
# ---------------------------------------------------
ref_T = get_total_T(ans_list, R_list, U_list, Q_list, D2Q)
#print('ref revenue:', ref_T)