Три пирата делят свою добычу, в которую входят $n$ предметов разной ценности. Получится у вас помочь разделить добычу поровну?
- Входные данные: Первая строка содержит целое число $n$. Вторая строка содержит целые числа $v_1, v_2, \dotsc, v_n$, разделённые пробелами.
- Выходные данные: Вывести 1, если $v_1, v_2, \dotsc, v_n$ можно разделить на три поднабора с одинаковыми суммами; в противном случае — вывести 0.
- Ограничения: $1 \le n \le 20$, $1 \le v_i \le 30$ для всех $i$.
Пример 1
Ввод | Вывод |
---|---|
4 3 3 3 3 | 0 |
Пример 2
Ввод | Вывод |
---|---|
1 30 | 0 |
Пример 3
Ввод | Вывод |
---|---|
13 1 2 3 4 5 5 7 7 8 10 12 19 25 | 1 |
- $1+3+7+25=2+4+5+7+8+10=5+12+19$.
Рассмотрим решение задачи. Обозначим $v_1+v_2+\dotsb+v_i$ как $\operatorname{sum}(i)$. Разделить набор из $n$ предметов на три части возможно, только если их общая ценность делится на три. То есть $\operatorname{sum}(n)=3V$, где $V$ — это целое число. Так, нам необходимо разделить $n$ чисел на три части, где сумма чисел в каждой части равна $V$. Одна из этих частей содержит $n$-й трофей (с ценностью $v_n$). Если мы его уберём, то получим разделение первых $n-1$ трофеев на три части таким образом, что ценность двух из них будет равна $V$, а сумма оставшейся части — $V-v_n$.
Вместо разделения всех $n$ предметов, попробуем решить более мелкую задачу, состоящую в делении первых $i$ предметов на части с ценностью $s_1$, $s_2$ и $\operatorname{sum}(i)-s_1 - s_2$. Если такое разделение возможно, мы присваиваем $split(i,s_1,s_2)={\tt true}$ (в противном случае — ${\tt false}$) и отмечаем, что пираты могут разделить добычу честно, только если $split(n,V,V)={\tt true}$.
💡 Остановитесь и подумайте:
Учитывая первые пять предметов, $split(5,4,13)={\tt true}$. Найдите все значения $split(5,s_1,s_2)$, равные ${\tt true}$.
💡 Остановитесь и подумайте:
Представьте, что вы уже составили двоичный двумерный массив $split(i-1,s_1,s_2)$ для всевозможных значений $0 \le s_1 \le V$ и $0 \le s_2 \le V$. Сможете ли вы использовать этот массив, чтобы составить массив $split(i,s_1,s_2)$?
Предположим, что $split(i,s_1,s_2) = {\tt true}$. Тогда первые $i$ чисел можно разделить на три части таким образом, чтобы сумма чисел в первой части составляла $s_1$, а сумма чисел во второй части — $s_2$.
- $i$-й предмет принадлежит первой части. Тогда $v_i \le s_1$. Убрав его из первой части, мы разделим первые $i-1$ чисел на три части так, что сумма первых двух частей составит $s_1-v_i$ и $s_2$, то есть $split(i-1,s_1-v_i,s_2)={\tt true}$.
- $i$-й предмет принадлежит второй части. Как и в предыдущем случае, $v_i \le s_2$ и $split(i-1,s_1,s_2-v_i)={\tt true}$.
- $i$-й предмет принадлежит третьей части. Тогда $split(i-1,s_1,s_2)= {\tt true}$.
Так, значение $split(i,s_1,s_2)$ можно вычислить, посмотрев на $$ split(i-1,s_1-v_i,s_2),, split(i-1,s_1,s_2-v_i),, split(i-1,s_1,s_2). $$ Базовый случай для этого рекуррентного соотношения: $split(0,0,0)={\tt true}$ и $split(0,s_1,s_2)={\tt false}$, если $s_1+s_2>0$.
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]
Время выполнения составляет $O(nV^2)$.