Блог

Постановка задачи:

Здесь проходят игры Содружества, и Питер Квилл, глава отдела организации матчей, представляет собой большую проблему. Учитывая список стран, которые будут участвовать в играх, он должен создать два пула для игр, причем каждая страна входит в любой из двух пулов. Однако из-за участившихся случаев коррупции и сговора между странами в играх на этот раз действует новое правило. Никакие две страны, разделяющие географическую границу, не будут храниться в одном пуле, чтобы поддерживать честную игру и разнообразие. Можете ли вы помочь Питеру решить, можно ли создать два пула в соответствии с правилами или нет для данного набора стран?

Формат ввода:

Первая строка содержит два целых числа через пробел n (количество стран) и m (количество пар стран, разделяющих географическую границу). Следующие m строк содержат два целых числа, разделенных пробелом, от 1 до n, представляющих две страны, которые имеют общие географические границы.

Формат вывода:
Если можно создать два пула, «да», в противном случае «нет»

Пример:

Ввод:

 5 5 
1 2 
1 3 
2 4 
3 4 
4 5  
 

Выходной сигнал:

 yes  
 

Объяснение:

Из приведенных входных данных ясно, что

1 имеет 2,3 в качестве соседей.

2 имеет 1,4 в качестве соседей.

3 имеет 1,4 в качестве соседей.

4 имеет 2,3,5 в качестве соседей.

5 имеет 4 в качестве соседа.

При небольшом наблюдении становится ясно, что могут быть сформированы два пула, т.е. (1,4) и . (2,3,5)

Я попытался из этой проблемы получить входные n данные and m и другие строки внутри списка, каждая из которых является независимым списком. Пока это результат, но я не знаю, как выполнить сравнение между списками и соседями.

Мне просто нужна идея рассуждения, а не решаемый код.

 n, m = [int(x) for x in input().split()]
countries=[]
neighbors=[]
for i in range (m):
    countries.append([int(x) for x in input().split()])
print (countries)

>>[[1, 2], [1, 3], [2, 4], [3, 4], [4, 5]]
 

Предположим, что ваш ввод представляет собой текстовый файл, вы можете прочитать его с помощью:

 m = []
with open('input.txt', 'r') as file:
    nm = list(map(int, file.readline().split()))
    for row in file:
        m.append([int(i) for i in row.split()])
 

В самом простом из сценариев, если количество стран больше, чем количество стран с соседями, то логически вы можете создать два пула, поскольку по крайней мере один из них наверняка сможет вместить один пул:

 if nm[0] > nm[1]:
    output = 'yes'
 

Если это не так (это не относится к вашему примеру), нам нужно будет управлять m . Конечно, есть несколько способов выполнить эту задачу, но я пойду путем создания словаря с соседними странами в качестве ключевых значений, заполнив пулы целевыми странами, если в этом списке нет соседей. Если мы можем заполнить все страны в любом из списков пула, вывод «да», в противном случае «нет»:

 # Get unique countries (we'll use them in the next line to identify all neighbors by country)
countries = set(sum(m, []))
# Get a dict with country and neighbors like in your provided explanation
country_neighbors = {c: [i if j==c else j for i,j in m if c in [i,j]] for c in countries}

# Create two empty lists
pool1,pool2 = [],[]
output = None

# Iterate through dictionary
for country,neighbors in country_neighbors.items():
    # Add country to first pool1 if there're not neighbors in the list
    if not any([neighbor in pool1 for neighbor in neighbors]):
        pool1.append(country)
    # If there's any country neighbors in pool1, try to place it in pool2
    elif not any([neighbor in pool2 for neighbor in neighbors]):
        pool2.append(country)
    # If no possible, then it's no possible to create two pools at all
    else:
        output = 'no'
        break

if output is None:
    output = 'yes'
 

Если вы хотите, вы можете обернуть его внутри функции, подобной этой:

 def check_pools(input_file):
    m = []
    with open(input_file, 'r') as file:
        nm = list(map(int, file.readline().split()))
        for row in file:
            m.append([int(i) for i in row.split()])
    if nm[0] > nm[1]:
        return 'yes'
    
    countries = set(sum(m, []))
    country_neighbors = {c: [i if j==c else j for i,j in m if c in [i,j]] for c in countries}
    
    pool1,pool2 = [],[]
    
    for country,neighbors in country_neighbors.items():
        if not any([neighbor in pool1 for neighbor in neighbors]):
            pool1.append(country)
        elif not any([neighbor in pool2 for neighbor in neighbors]):
            pool2.append(country)
        else:
            return 'no'
    return 'yes'