Три пирата делят свою добычу, в которую входят предметов разной ценности. Получится у вас помочь разделить добычу поровну?
- Входные данные: Первая строка содержит целое число . Вторая строка содержит целые числа , разделённые пробелами.
- Выходные данные: Вывести 1, если можно разделить на три поднабора с одинаковыми суммами; в противном случае — вывести 0.
- Ограничения: , для всех .
Пример 1
|
Ввод |
Вывод |
|
4 |
0 |
Пример 2
|
Ввод |
Вывод |
|
1 |
0 |
Пример 3
|
Ввод |
Вывод |
|
13 |
1 |
- .
Рассмотрим решение задачи. Обозначим как . Разделить набор из предметов на три части возможно, только если их общая ценность делится на три. То есть , где — это целое число. Так, нам необходимо разделить чисел на три части, где сумма чисел в каждой части равна . Одна из этих частей содержит -й трофей (с ценностью ). Если мы его уберём, то получим разделение первых трофеев на три части таким образом, что ценность двух из них будет равна , а сумма оставшейся части — .
Вместо разделения всех предметов, попробуем решить более мелкую задачу, состоящую в делении первых предметов на части с ценностью , и . Если такое разделение возможно, мы присваиваем (в противном случае — ) и отмечаем, что пираты могут разделить добычу честно, только если .
💡 Остановитесь и подумайте:
Учитывая первые пять предметов, . Найдите все значения , равные .
💡 Остановитесь и подумайте:
Представьте, что вы уже составили двоичный двумерный массив для всевозможных значений и . Сможете ли вы использовать этот массив, чтобы составить массив ?
Предположим, что . Тогда первые чисел можно разделить на три части таким образом, чтобы сумма чисел в первой части составляла , а сумма чисел во второй части — .
- -й предмет принадлежит первой части. Тогда . Убрав его из первой части, мы разделим первые чисел на три части так, что сумма первых двух частей составит и , то есть .
- -й предмет принадлежит второй части. Как и в предыдущем случае, и .
- -й предмет принадлежит третьей части. Тогда .
Так, значение можно вычислить, посмотрев на
Базовый случай для этого рекуррентного соотношения: и , если .
Split(v[1],…,v[n]):
if v[1] + … + v[n] не делится целочисленно на 3:
return false
V = (v[1] + … + v[n]) / 3
split = ... // массив размера (n+1) × (V+1) × (V+1)
// заполнить массив split значениями false
split[0][0][0] = true
for i from 1 to n:
for s1 from 0 to V:
for s2 from 0 to V:
split[i][s1][s2] = split[i−1][s1][s2]
if s1 >= v[i]:
split[i][s1][s2] = split[i][s1][s2] OR split[i - 1][s1 - v[i]][s2]
if s2 >= v[i]:
split[i][s1][s2] = split[i][s1][s2] OR split[i - 1][s1][s2 - v[i]]
return split[n][V][V]
Время выполнения составляет .