Cho đa giác n đỉnh, n trục lật, n điểm quay. Thực hiện chuỗi phép quay (loại 1) và lật (loại 2) theo danh sách đầu vào. Thêm một phép biến đổi để đưa đa giác về trạng thái ban đầu.
Ví dụ: n=6, input_list=[[1,2],[1,4],[2,3],[2,5],[1,6]] → phép cần thêm là (1,4).
Giải thuật
- Theo dõi vị trí (position) và trạng thái lật (decision_var).
- Duyệt danh sách:
- Nếu quay (1): position += k.
- Nếu lật (2): position = k - position; decision_var = not decision_var.
- position %= n.
- Nếu decision_var=True: trả về (2, position) (lật).
- Ngược lại: trả về (1, n - position) (quay).
Ví dụ mã Python
def solve(n, input_list):
decision_var = False
position = 0
for item in input_list:
x, y = item[0], item[1]
if x == 1:
position += y
else:
position = y - position
decision_var = not decision_var
position %= n
if decision_var:
return (2, position)
else:
return (1, n - position)
print(solve(6, [[1, 2], [1, 4], [2, 3], [2, 5], [1, 6]])) # Output: (1, 4)
Đầu vào
6, [[1, 2], [1, 4], [2, 3], [2, 5], [1, 6]]
Đầu ra
(1, 4)