Ferry Loading III
python
a month ago
4.8 kB
9
Indexable
Never
''' 2 10 10 1st: 0 left: time 0 there's 1st car at left bank, then PICKS right: +10, NOW 10 right (1st: 10) 2nd: 10 left: time 10 there's 2nd car at left bank, then MOVES left: +10, NOW 20 left 3rd: 20 left: time 20 on left bank there are 2 cars 2nd, 3rd, then PICKS right: +10, NOW 30 right (2nd, 3rd: 30) 4th: 30 left: time 30 on left bank there's 4th car, then MOVES left:+10, NOW 40 left 5th: 40 left: time 40 PICKS 4th, 5th right:+10, NOW 50 right (4th,5th:50), there's 6th at left, then MOVES left:+10, NOW 60 left 6th: 50 left: 7th: 60 left: time 60 PICKS 6th, 7th right:+10, NOW 70 right (6th,7th:70), there's 8th at left, then MOVES left:+10, NOW 80 left 8th: 70 left: 9th: 80 left: time 80 PICKS 8th, 9th right:+10, NOW 90 right (8th,9th:90), there's 10th at left, then MOVES left:+10, NOW 100 left 10th: 90 left: time 100 PICKS 10th right:+10, NOW 110 right (10th:110) Expected output: 10 30 30 50 50 70 70 90 90 110 2 10 3 1st: 10 right 2nd: 25 left 3rd: 40 left time 0 no cars time 10 3rd at right, MOVES right:+10, NOW 20 right time 20 PICKS 1st left:+10, NOW 30 left (1st:30left), 30>25 then PICKS 2nd right:+10, NOW 40 right (2nd:40right) time 40>=40 then MOVES left:+10, NOW 50>=40 left, then PICKS 3rd right:+10, NOW 60 right (3rd:60right) Expected output: 30 40 60 ''' import queue class FerryStatus(object): def __init__(self, time, where): self.time = time self.where = where def __repr__(self): return f'({self.time}, {self.where})' class MyQueue(queue.Queue): def __repr__(self): items = list(self.queue) return f'{items}' def move(t, ferry, where): ferry.time += t ferry.where = where def oppositeBank(which_bank): if which_bank == 'left': return 'right' elif which_bank == 'right': return 'left' else: print('Input must be "left" or "right"') return which_bank def operate(ans, n, t, ferry, bank, where, opposite_bank): if not bank.empty() and bank.queue[0][1] <= ferry.time: # is there are cars arrive in this bank before current time (car_time < ferry.time) # we pick all cars that are suitable with time and capacity of ferry count = 1 while count <= n and not bank.empty() and bank.queue[0][1] <= ferry.time: car = bank.get() ans[car[0]] = ferry.time + t count += 1 move(t, ferry, oppositeBank(where)) elif not bank.empty() and bank.queue[0][1] > ferry.time: # The time when there's no cars in both 2 banks, we'll see car from which side comes first # if there's a car which comes to this bank first, then we update current time to the time that car arrives (top element from the queue) # or else, there's a car which comes to the opposite bank first, then we move ferry to the opposite bank # then update current time to the time the car arrives (top element from the queue) car_time_left = bank.queue[0][1] car_time_right = 10 ** 9 if not opposite_bank.empty(): car_time_right = opposite_bank.queue[0][1] if car_time_left < car_time_right: ferry.time = car_time_left else: move(t, ferry, oppositeBank(where)) if ferry.time < car_time_right: ferry.time = car_time_right else: # if this bank is empty, then move to the other move(t, ferry, oppositeBank(where)) def printAns(ans): for a in ans: print(a) def solve(): n, t, m = map(int, input().split()) left_bank = MyQueue() right_bank = MyQueue() ans = [0 for _ in range(m)] min_car_time_left = 10**9 min_car_time_right = 10**9 for i in range(m): car_time, which_bank = input().split() car_time = int(car_time) # we'll store (i: the order of the car, car_time: the time when the car arrives) tuples in 2 queues if which_bank == 'left': min_car_time_left = min(min_car_time_left, car_time) left_bank.put((i, car_time)) else: min_car_time_right = min(min_car_time_right, car_time) right_bank.put((i, car_time)) # class FerryStatus stores information about current time and which side the ferry's at ferry = FerryStatus(min(min_car_time_left, min_car_time_right), 'left') # we keep operate while there's at least 1 queue is not empty while (not left_bank.empty()) or (not right_bank.empty()): if ferry.where == 'left': operate(ans, n, t, ferry, left_bank, 'left', right_bank) else: operate(ans, n, t, ferry, right_bank, 'right', left_bank) return ans tc = int(input()) for i in range(tc): ans = solve() printAns(ans) if i != tc-1: print()