Pagini recente » Cod sursa (job #1497480) | Cod sursa (job #2907551) | Cod sursa (job #1505783) | Cod sursa (job #1682937) | Cod sursa (job #1652452)
#include<iostream>
#include<fstream>
#include<cstdlib>
using namespace std;
ifstream in("semne.in");
ofstream out("semne.out");
struct nr
{
long long val;
int poz;
};
const int N = 50005;
char ans[N+1];
nr v_adun[N];
nr v_scad[N];
int n,m;
long long s,s_crt;
void afis()
{
int i;
for(i=1; i<=n; ++i) cout<<v_adun[i].val<<" "; cout<<"\n";
for(i=1; i<=m; ++i) cout<<v_scad[i].val<<" "; cout<<"\n";
cout<<"\n";
}
int main()
{
srand(0);
int i,index;
in>>n>>s;
for(i=1; i<=n; ++i)
{
in>>v_adun[i].val;
v_adun[i].poz = i;
}
s_crt = 0;
for(i=1; i<=n; ++i) s_crt += v_adun[i].val;
///cout<<s_crt;
int pas=0;
///afis();
while(s_crt != s)
{
if(++pas>100) return 0;
///cout<<"s_crt = "<<s_crt<<"\n";
if(s_crt > s)
{
if(n!=0) index = (rand()*2)%n; /// Aleg un oricare element pozitiv
else index=1;
swap(v_adun[index], v_adun[n]); /// Il permut pe ultima pozitie
s_crt -= v_adun[n].val * 2; /// Actualizez suma
++m;
swap(v_scad[m], v_adun[n]); /// Mut elementul ales in celalalt vector
v_scad[m].val *= -1; /// Semnul sau se schimba
--n;
}
else // s_crt < s
{
/// Analog
if(m!=0) index = (rand()*2)%m;
else index=1;
swap(v_scad[index], v_scad[m]);
continue;
s_crt -= v_scad[m].val * 2;
++n;
swap(v_adun[n], v_scad[m]);
v_adun[n].val *= -1;
--m;
}
///afis();
}
return 0;
for(i=1; i<=n; ++i) ans[v_adun[i].poz] = '+';
for(i=1; i<=m; ++i) ans[v_scad[i].poz] = '-';
ans[n+m+1] = 0;
out<<(ans+1);
//for(i=1; i<=n+m; ++i) out<<ans[i];
//out<<"\n50000 0\n";
//for(i=1; i<=50000; ++i) out<<i<<" ";
return 0;
}