Question

Часовой механизм К вам обратился владелец часовой мастерской, которая делает часы с прозрачным корпусом. В мастерской есть 1 проблема: дизайнеры придумывают то, как будут выглядят часы, но не задумываются о том, как шестеренки будут крутиться. Поэтому, когда дизайн получают мастера, им приходится проверять работоспособность нарисованного дизайнерами механизма – проверять не заклинит ли механизм от сцепки двух крутящихся в одном направлении шестеренок. Напишите программу, которая будет делать эту работу за мастеров. Входные данные: Первая строка содержит количество шестеренок NN (число от 1 до 1000 включительно). Вторая строка содержит количество связей между шестеренками MM (число от 0 до 1000 включительно), которые сцеплены между собой (если одна из них крутится по часовой стрелке, вторая должна крутиться против часовой и наоборот). Далее идет ММ строк с парами чисел, являющихся номерами сцепленных между собой шестеренок (нумерация начинается с 1). Выходные данные: Программа должна вывести одно из 2 слов: ‘good’, если механизм работоспособен или ‘bad’, если механизм заклинит. Sample Input: 4 4 1 2 2 3 3 4 4 1 Sample Output: good Напишите программу. Тестируется через stdin → stdout Time Limit: 15 секунд Memory Limit: 256 MB

Answer 1

Ответ:

gears_count = int(input())

connections_count = int(input())

connections = []

for i in range(connections_count):

   inp = input()

   connections = connections + [[int(inp.split()[0]), int(inp.split()[1])]]

def get_connections_of_gear(gear=1, connections_arr=[[0]]):

   gear_connections = 0

   if connections_arr:

       for i in range(connections_count * 2):

           if connections_arr[i // 2][i % 2] == gear:

               gear_connections += 1

   return gear_connections

def is_valid():

   if gears_count < 3 or connections_count < 3:

       return "good"

   elif gears_count % 2 == 0:

       gears = 0

       for i in range(gears_count):

           if get_connections_of_gear(i, connections) > 2:

               gears += 1

       if gears % 2 == 0:

           return "good"

   elif not gears_count % 2 == 0:

       gears = 0

       for i in range(gears_count):

           if get_connections_of_gear(i, connections) > 2:

               gears += 1

       if not gears % 2 == 0:

           return "good"

   return "bad"

print(is_valid())

Объяснение:

8 из 11

Answer 2

Вот решение на языке Python:

pythonCopy code
def check_mechanism(N, M, connections):
    # Создаем пустой граф
    graph = [[] for _ in range(N + 1)]

    # Добавляем связи между шестеренками в граф
    for i in range(M):
        gear1, gear2 = connections[i]
        graph[gear1].append(gear2)
        graph[gear2].append(gear1)

    # Используем обход в глубину (DFS) для проверки работоспособности механизма
    def dfs(node, direction):
        visited[node] = True

        for neighbor in graph[node]:
            if not visited[neighbor]:
                # Меняем направление вращения соседней шестеренки
                if direction == 'clockwise':
                    dfs(neighbor, 'counterclockwise')
                else:
                    dfs(neighbor, 'clockwise')
            elif visited[neighbor] and directions[neighbor] == direction:
                return False

        return True

    # Инициализируем массивы для отслеживания посещенных вершин и направлений вращения
    visited = [False] * (N + 1)
    directions = [''] * (N + 1)

    # Проверяем каждую шестеренку на работоспособность механизма
    for i in range(1, N + 1):
        if not visited[i]:
            if not dfs(i, 'clockwise'):
                return 'bad'

    return 'good'


# Считываем входные данные
N = int(input())
M = int(input())
connections = []
for _ in range(M):
    connection = tuple(map(int, input().split()))
    connections.append(connection)

# Проверяем механизм и выводим результат
result = check_mechanism(N, M, connections)
print(result)

Программа считывает количество шестеренок N, количество связей M, а затем считывает пары номеров сцепленных шестеренок connections. Затем вызывается функция check_mechanism, которая проверяет работоспособность механизма и возвращает результат.

Программа использует обход в глубину (DFS) для проверки работоспособности механизма. Она создает граф, где вершины представляют шестеренки, а ребра - связи между ними. Затем она выполняет обход в глубину, проверяя, что соседние шестеренки вращаются в противоположных направлениях. Если в процессе обхода обнаруживается противоречие, то механизм считается "bad" (заклинившим), иначе - "good" (работоспособным).

Надеюсь, это поможет!