Как алгоритм использовать для решения задачи?

Question

не могу понять как решить следующую задачу:

На вход программа получает две строки. В первой находится список целых чисел, разделенных пробелом. Во второй строке программа получает натуральное число group_size. Программа должна определить, можно ли полученный список разделить на группы размера group_size так, чтобы в каждой группе все элементы были одинаковы. На выходе программа должна вывести True или False. Пример входных данных: 0 6 4 4 5 4 5 5 6 5 2 5 5 0 1 3 1 7 7 6 2 1 2 5 0 0 1 6 6 2 Выходные данные: False

Вот я начал так решать:

string='3 2 2 3 3 3 1 4 4 3 2 1 3 4 2 4'
lst=string.split()
lst.sort(reverse=False) #1122223333334444
print(lst)
group=int(2)
print(group)
ind=0
lstgr=[]
#print(type(lstgr))
for i, item in enumerate(lst):
    lst[i]=int(item) #11 22 22 33 33 33 44 44
    for j in range(0,group):
        lstgr.append(lst[i])
    #print(i,lst[i],ind)

отсортировал список, но не понимаю, как можно разделить на необходимые группы и сравнить их? можете подсказать?

Answer 1

Это можно сделать так:

string = '0 6 4 4 5 4 5 5 6 5 2 5 5 0 1 3 1 7 7 6 2 1 2 5 0 0 1 6 6 2' # входная строка
group_size = 2 # по сколько группируем

numbers = string.split() # преобразуем в список

for num in set(numbers):
    c = numbers.count(num) # сколько раз число встречается в списке
    if c%group_size: # если кол-во появлений в списке не кратно размеру группы - задача невыполнима
        print(False)
        break
else:
    # сюда программа доходит, если проверила все числа и все прошли проверку кол-ва вхождений
    print(True)

Answer 2

collections.Counter считает одинаковые элементы. После проверяется что все счётчики делятся на размер группы:

import collections


c = collections.Counter(input().split())
size = int(input())
print(all(s % size == 0 for s in c.values()))

$ echo -e "3 2 2 3 3 3 1 4 4 3 2 1 3 4 2 4\n2" | python groups.py
True
$ echo -e "0 6 4 4 5 4 5 5 6 5 2 5 5 0 1 3 1 7 7 6 2 1 2 5 0 0 1 6 6\n2" | python groups.py
False

БЛОГ НА HUSL

Как алгоритм использовать для решения задачи?

Ответы (2 шт):