Question

Problema #2712 Semne (pbinfo)

Cerința

Fie un număr n natural nenul, determinați un număr k și o combinație de semne + sau -(mai exact o succesiune x1,x2,…,xk
unde xi∈{−1,1}, astfel încat să aibă loc relația: n=x1⋅1^2+x2⋅2^2+…+xk⋅k^2

. Să se afișeze o succesiune de k semne + sau - care să îndeplinească relația de mai sus.
Date de intrare

Programul citește de la tastatură numărul n.
Date de ieșire

Programul va afișa pe ecran o succesiune de k semne + sau - care să îndeplinească relația.
Restricții și precizări

1 ≤ n ≤ 100

Exemplu 1:

Intrare

3

Ieșire

-+--+

Exemplu 2:

Intrare

2

Ieșire

---+

Answer 1

Solutia mea(100p):

Genereaza cam 2^16 modalitati de a combina + si - pana cand ajunge la n-ul citit. Solutia oficiala e mult mai eleganta.

#include <iostream>

using namespace std;

int gen(int k,int l){

int s = 0;

for(int i = 1; i <= l; i++){

 s += ((k&1) == 1 ? 1 : -1)*i*i;

 k>>=1;

}

return s;

}

void writebin(int x, int l){

   for(int i = 1; i <= l; i++){

 cout << ((x&1) ? '+' : '-');

       x>>=1;

   }

}

int main(){

int n;

   cin >> n;

   int s;

   bool f = false;

   for(int j = 1; j <= 15; j++){

       for(int k = 0; k < 1<<j; k++){

           s = gen(k, j);

           if(s==n){

               f = true;

           writebin(k,j);break;}

       }

       if(f)break;

   }

}