Cod sursa(job #1871)

Utilizator adyshorcont de teste adyshor Data 15 decembrie 2006 07:59:28
Problema Semne Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.68 kb
#include<stdio.h>
#include<stdlib.h>
#define M 100001

long S , S1 ,S2, k;
long s;
long a[M] , sume[M];
long n , i , j;
int semn,nr;
long sol[50001];
long ssol[50001];
int xsol[50001];
int main()
{
    freopen("semne.in","r",stdin);
    freopen("semne.out","w",stdout);
    scanf("%ld%ld",&n,&S);
    for (i = 1 ; i <= n ; i++)
    {
        scanf("%ld",&a[i]);
        sume[i] += sume[i-1] + a[i];
    }
    while(1)
    {
          s = 0;
          S1 = 0;
          S2 = 0;
          semn = 1;//1 - plus , -1 - minus
          sol[0] = 0;
          k = 0;
          int ind = 1;
          while (s<=n)
          {     
               while(1)
               {         
               k = rand()%n;   
               if (k!=0)
                  break;
               }
               sol[0]++;
               sol[sol[0]] = k;
               ssol[sol[0]] = ssol[sol[0]-1] + k;
               if (s+k >= n)
               {
                     
                     sol[sol[0]] = n - s;
                     ssol[sol[0]] = n;
                     s = n;
                     /*
                     for (i = 1 ; i <= sol[0] ;i++)
                         printf("%ld ",sol[i]);
                     printf("\n");
                     for (i = 1 ; i <= sol[0] ;i++)
                         printf("%ld ",ssol[i]);
                     printf("\n");
                     for (i = 1 ; i <= sol[0] ;i++)
                         printf("%ld ",sume[ssol[i]]);
                     printf("\n");
                     */
                     k = 0;
                     //s1 - , s2 +
                     S1 = sume[sol[1]];
                     S2 = -S1;
                     semn = -1;
                     for (i = 2 ; i <= sol[0] ; i++)
                     {
                         S1 += (sume[ssol[i]] - sume[ssol[i-1]])*semn;
                         S2 +=(-(sume[ssol[i]] - sume[ssol[i-1]]))*semn;
                         if (semn==-1)
                            semn = 1;
                         else
                             semn = -1;
                     }
                     /*
                     printf(" %ld",S2);
                     printf("\n");
                    */
                     if (S1 == S)
                     {
                     for (i = 1 ; i <= sol[0] ; i++)
                     {
                         for (j = 1 ; j <= sol[i] ; j++)
                         {
                             if (i%2==1)
                                             printf("+");
                             else
                                             printf("-");
                         }
                     }
                   //  printf("\n");
                                             
                     ind = 0; 
                     return 0;
                     }
                     if (S2 == S)
                     {
                     for (i = 1 ; i <= sol[0] ; i++)
                     {
                         for (j = 1 ; j <= sol[i] ; j++)
                         {
                             if (i%2==1)
                                             printf("-");
                             else
                                             printf("+");
                         }
                     }
                //     printf("\n");
                                             
                     ind = 0; 
                     return 0;
                     }
                     s = 0;
                     break;
               }
               s+=k;
          }
          if (ind==0)
             break;
    }
    return 0;
}