infoarena

Ma poate ajuta cineva va rog cu niste indicii pentru rezolvarea urmatoarei probleme:

Se da un numar natural n. Sa se insereze semnele + si - in expresia 1 ? 2 ? ... ? n astfel incat rezultatul obtinut prin evaluarea expresiei sa fie 0. Exemple: n=3 -> 1+2-3=0, n=4 -> 1-2-3+4=0, n->9 - imposibil. Indicatie: este nevoie de gasirea conditiei de existenta a solutiei si de o aranjare a semnelor (oricare, solutia nu este unica) care sa satisfaca enuntul.

Multumesc anticipat.

Fa un back care sa iti afiseze toate solutiile pt n de la 1 la 20 de exemplu si gaseste un pattern.

Hmm, am sa incerc si lucrul asta :). Sper sa fie ceva pattern iin secventele de semne +/-, ca m-am tot gandit azi la niste solutii si am zis ca poate nu am nevoie de back.

Ca sa existe solutie , ai nevoie ca suma lor sa fie divizibila cu 2.  n * (n + 1) / 2  se divide cu 2 inseamna ca n se divide cu 4 sau n + 1 se divide cu 4.
Daca n e divizibil cu 4 iei toate perechile i , n - i + 1 si le pui pe rand, alternativ, in multimea celor negative respectiv a celor pozitive.

1 2 3 4 5 6 7 8 :  (1, 8 ) (3, 6) cu plus , celelalte cu minus.

Daca n + 1 e divizibil cu 4 faci aceeasi chestie pentru primele n - 1 numere, si pe al n-lea il pui in multimea cu suma mai mica.

1 2 3 4 5 6 7

Alternativ, poti face knapsack in O(n ^ 3).

Mersi mult, am gasit si un pattern pe pare si impare:
pare: + - pana la n/2 si apoi - + pana la n
impare: ++- si ramai cu o secventa para unde aplici patternul de la pare :D

Sa nu uiti dupa ce gasesti un pattern cu back - sa il demonstrezi adevarat pt cazul general  :-'