# Untitled

unknown
python
2 months ago
8.7 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:
find = 0
for i, boundary in enumerate(boundary_list):
if boundary>=distance:
D2Q[j1][j2] = i
find = 1
break
assert find
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]

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]

def get_delta_T_list(decrease_scale, weighted_decrease_scale, R_list, U_list, Q_list, A_list, B_list):
delta_T_list = [[-100000 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 maximum distance
max_distance = min(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 >= max_distance:
I = i
J = j
max_distance = total_distance
#best_delta_T = int(best_delta_T)
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]
#best_delta_T = int(best_delta_T)
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

#--------------------------------------------

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)

I, J, best_delta_T = distance_get_best_ij(delta_T_list, Dis_list)
assert I!=-1 and J!=-1 and best_delta_T>0
#print('I, J:', I, J)
#print('best_delta_T:', best_delta_T)

# 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
#print('ans_list:', ans_list)
#print('A_list:', A_list)
#print('B_list:', B_list)

# 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)

#print('delta_T_list')
#print(delta_T_list)

I, J, best_delta_T = naive_get_best_ij(delta_T_list)
#print('I, J:', I, J)
#print('best_delta_T:', best_delta_T)

# 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

#print('ans_list:', ans_list)
#print('A_list:', A_list)
#print('B_list:', B_list)

#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]