1
""" 归并排序中的merge操作，并统计跨越两段的逆序数 """
2
def merge_and_count(num_list, start, mid, end):
3
    temp_list = []
4
    left, right = start, mid + 1
5
    result = 0
6
    
7
    while left < mid + 1 and right < end:
8
        if num_list[left] <= num_list[right]:
9
            temp_list.append(num_list[left])
10
            left += 1
11
        else:
12
            temp_list.append(num_list[right])
13
            right += 1
14
            result += mid + 1 - left
15
            
16
    while left < mid + 1:
17
        temp_list.append(num_list[left])
18
        left += 1
19
    while right < end:
20
        temp_list.append(num_list[right])
21
        right += 1
22
 
23
    for i in range(len(temp_list)):
24
        num_list[start + i] = temp_list[i]
25
    
26
    return result
27
 
28
""" 归并排序num_list[start : end]，并统计该段的逆序数 """
29
def merge_sort_and_count(num_list, start, end):
30
    result = 0
31
    if start + 1 >= end:
32
        return result
33
    
34
    mid = (start + end - 1) // 2
35
    
36
    result += merge_sort_and_count(num_list, start, mid + 1)
37
    result += merge_sort_and_count(num_list, mid + 1, end)
38
    result += merge_and_count(num_list, start, mid, end)
39
    return result
40
    
41
    
42
if __name__ == "__main__":
43
    while True:
44
        n = int(input())
45
        if n == 0:
46
            break
47
        num_list = list(map(int, input().split()))
48
        result = merge_sort_and_count(num_list, 0, n)
49
        print(result)

1
from collections import deque
2
 
3
a, b, t = map(int, input().split())
4
 
5
def fill(state, jug):
6
    x, y = state
7
    if jug == 0:
8
        return (a, y), "FILL(1)"
9
    else:
10
        return (x, b), "FILL(2)"
11
 
12
def drop(state, jug):
13
    x, y = state
14
    if jug == 0:
15
        return (0, y), "DROP(1)"
16
    else:
17
        return (x, 0), "DROP(2)"
18
 
19
def pour(state, direction):
20
    x, y = state
21
    if direction == 0:  
22
        amount = min(x, b - y)
23
        return (x - amount, y + amount), "POUR(1,2)"
24
    else:        
25
        amount = min(y, a - x)
26
        return (x + amount, y - amount), "POUR(2,1)"
27
 
28
def bfs():
29
    visited = set((0, 0))
30
    queue = deque([( (0, 0), [] )]) 
31
    
32
    while queue:
33
        state, path = queue.popleft()  
34
        if state[0] == t or state[1] == t:
35
            print(len(path))
36
            for step in path:
37
                print(step)
38
            return True
39
        
40
        for operation in [fill, drop, pour]:
41
            for arg in [0, 1]:
42
                try:
43
                    new_state, action = operation(state, arg)
44
                    if new_state not in visited:
45
                        new_path = path.copy()
46
                        new_path.append(action)
47
                        queue.append( (new_state, new_path) )
48
                        visited.add(new_state)
49
                except:  
50
                    continue
51
    return False
52
 
53
result = bfs()
54
if not result:
55
    print("impossible")

1
from collections import deque
2
 
3
def find_shortest_path(maze):
4
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
5
    
6
    queue = deque([(0, 0)])
7
    visited = {(0, 0)}
8
    parent = {(0, 0): None}
9
    
10
    while queue:
11
        r, c = queue.popleft()
12
        
13
        if (r, c) == (4, 4):
14
            path = []
15
            current = (4, 4)
16
            while current is not None:
17
                path.append(current)
18
                current = parent[current]
19
            return path[::-1]
20
        
21
        for dr, dc in directions:
22
            nr, nc = r + dr, c + dc
23
            if (0 <= nr < 5 and 0 <= nc < 5 and 
24
                maze[nr][nc] == 0 and (nr, nc) not in visited):
25
                visited.add((nr, nc))
26
                queue.append((nr, nc))
27
                parent[(nr, nc)] = (r, c)
28
    
29
    return []
30
 
31
maze = []
32
for _ in range(5):
33
    row = list(map(int, input().split()))
34
    maze.append(row)
35
 
36
path = find_shortest_path(maze)
37
 
38
for r, c in path:
39
    print(f"({r}, {c})")