120 lines
3.2 KiB
Python
120 lines
3.2 KiB
Python
def process_inputs(inputs):
|
|
lines = inputs.split('\n')
|
|
lines = iter(lines)
|
|
|
|
testcases_num = int(next(lines))
|
|
testcases = []
|
|
|
|
for i in range(testcases_num):
|
|
line = next(lines)
|
|
# numbers = [int(i) for i in line.split(' ')]
|
|
# target_pos_x, target_pos_y, time_limit = [int(i) for i in line.split(' ')]
|
|
target_pos, time_limit = line.split(' ')
|
|
time_limit = int(time_limit)
|
|
target_pos_x, target_pos_y = [int(i) for i in target_pos.split(',')]
|
|
|
|
|
|
|
|
testcase = {
|
|
# 'sequence': numbers,
|
|
'target_pos_x': target_pos_x,
|
|
'target_pos_y': target_pos_y,
|
|
'time_limit': time_limit,
|
|
}
|
|
testcases.append(testcase)
|
|
|
|
return testcases
|
|
|
|
|
|
|
|
|
|
def solve(testcases):
|
|
res = ''
|
|
for i, testcase in enumerate(testcases):
|
|
print('Solving testcase #', i + 1)
|
|
|
|
res += process_testcase(**testcase)
|
|
|
|
return res
|
|
|
|
|
|
|
|
def process_testcase(target_pos_x, target_pos_y, time_limit):
|
|
res_x = process_testcase_1d(target_pos_x, time_limit)
|
|
res_y = process_testcase_1d(target_pos_y, time_limit)
|
|
return res_x + res_y + "\n"
|
|
|
|
def process_testcase_1d(target_pos, time_limit) -> str:
|
|
# edge cases
|
|
if target_pos == 0:
|
|
return "0 0\n"
|
|
elif target_pos == 1:
|
|
return "0 5 0\n"
|
|
elif target_pos == -1:
|
|
return "0 -5 0\n"
|
|
|
|
sequence = []
|
|
|
|
distance_to_travel = abs(target_pos)
|
|
|
|
slowest_pace = 5
|
|
# max_acceleration_time = slowest_pace - 1
|
|
# max_acceleration_sequence_time = max_acceleration_time * 2
|
|
acceleration_windows = distance_to_travel - 1
|
|
max_accel = min(acceleration_windows / 2, slowest_pace - 1)
|
|
# floor to int
|
|
max_accel = int(max_accel)
|
|
|
|
min_reachable_pace = slowest_pace - max_accel
|
|
|
|
startup_seq = list(range(slowest_pace, min_reachable_pace - 1, -1))
|
|
end_seq = list(range(min_reachable_pace + 1, slowest_pace + 1))
|
|
distance_covered = len(startup_seq) + len(end_seq)
|
|
mid_seq = [min_reachable_pace] * (distance_to_travel - distance_covered)
|
|
sequence = startup_seq + mid_seq + end_seq
|
|
|
|
|
|
|
|
if target_pos < 0:
|
|
sequence = [-s for s in sequence]
|
|
# insert 0 at back and at start
|
|
sequence = [0] + sequence + [0]
|
|
|
|
# verify_testcase(sequence, target_pos, time_limit)
|
|
|
|
sequence_str = ' '.join([str(s) for s in sequence])
|
|
return sequence_str + '\n'
|
|
|
|
|
|
def verify_testcase(sequence, target_pos, time_limit):
|
|
positives = []
|
|
negatives = []
|
|
all_abs = []
|
|
zeroes_count = 0
|
|
for num in sequence:
|
|
all_abs.append(abs(num))
|
|
if num > 0:
|
|
positives.append(num)
|
|
elif num < 0:
|
|
negatives.append(num)
|
|
else:
|
|
zeroes_count += 1
|
|
|
|
final_position = len(positives) - len(negatives)
|
|
total_time = sum(all_abs) + zeroes_count
|
|
assert final_position == target_pos
|
|
assert total_time < time_limit
|
|
|
|
# Verify gradual stepup / stepdown
|
|
# except 0 - 5 and 5 - 0 transitions
|
|
for i in range(1, len(sequence)):
|
|
speed1 = abs(sequence[i - 1])
|
|
speed2 = abs(sequence[i])
|
|
if speed1 == 0:
|
|
speed1 = 6
|
|
if speed2 == 0:
|
|
speed2 = 6
|
|
|
|
diff = abs(speed1 - speed2)
|
|
assert diff <= 1
|