Question

Вам дан набор целых чисел размера n (он может содержать одинаковые элементы). Вы должны найти поднабор чисел, где сумма чисел в поднаборе делится на n без остатка и вывести индексы этих чисел в наборе. Если такого набора не существует, вывести −1


Формат входных данных:


В первой строке входных данных находится единственное целое число n (1 6 n 6 106) — размер

набора целых чисел.

Во второй строке входных данных находится n целых чисел a1, a2,...,an(0 6 ai 6 109) — элементы данного вам набора целых чисел.


Формат выходных данных:


Если ответа не существует — выведите −1.

Иначе выведите две строки.

В первой строке выходных данных выведите размер поднабора ответа.

Во второй строке выведите индексы чисел в наборе, которые входят в ответ. Выводить индексы

в любом порядке. Индексы в ответе не должны повторяться.

Если есть несколько таких поднаборов, то выведите любой.


Python

Answer 1

Ответ:

Объяснение:

def subset_sum(n, arr):

   arr_sum = sum(arr)

   if arr_sum % n != 0:

       return -1

   target = arr_sum // n

   visited = [False] * n

   subset = []

   if find_subset(arr, visited, 0, n, 0, target, subset):

       return (len(subset), [i+1 for i in subset])

   else:

       return -1

def find_subset(arr, visited, curr_sum, n, index, target, subset):

   if curr_sum == target:

       return True

   if index == n:

       return False

   

   visited[index] = True

   subset.append(index)

   if find_subset(arr, visited, curr_sum + arr[index], n, index + 1, target, subset):

       return True

   subset.pop()

   visited[index] = False

   if find_subset(arr, visited, curr_sum, n, index + 1, target, subset):

       return True

   return False

n = int(input().strip())

arr = list(map(int, input().strip().split()))

result = subset_sum(n, arr)

if result == -1:

   print(-1)

else:

   print(result[0])

   print(*result[1])