Для небольшого ввода количество конфет невелико (до 15). Поиск всех возможных случаев будет состоять из 2 ^ 15 = 32768 возможностей, которые можно проверить в течение миллисекунды или около того. Но при наличии до 1000 конфет (большой ввод) число возможных комбинаций возрастает до 2 ^ 1000 = 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376. Теперь это число слишком велико, и даже если вы запустите программу в течение нескольких лет, вы не получите результат.
Есть несколько наблюдений, которые помогут создать эффективную программу для этого:
- Как указывал @Protostome, сумма, которую сумма Патрика на самом деле является операцией xor.
- Опять же, как указывал @Protostome, если это разрешимо, xor всех конфет будет 0. Причина такова: если возможно иметь одинаковую сумму xor в двух разделах, тогда берется xor обоих разделы будут
a xor a = 0.
- Если возможно разделить, то сумма xor всех конфет равна 0. Но если мы удалим одну конфету из набора целых конфет, она станет ненулевой. В частности,
.
c1 xor c2 xor ... xor ci-1 xor ci xor ci+1 xor ... xor cn = 0
=> c1 xor c2 xor ... xor ci-1 xor ci+1 xor ... xor cn = ci
То есть мы можем разделить набор на две части, вынув одну конфету из всего набора. Чтобы максимизировать арифметическую сумму левой половины, мы должны взять конфету с самым низким значением. Итак, арифметическая сумма конфет в верхней куче - это сумма всех конфет - значение самой низкой!
Поэтому имеем:
- Если xor всех конфет равен нулю, это разрешимо
- Если это разрешимо, сумма - это сумма всего списка - самое низкое значение.