Swad's Spot: August 2016

Monday, August 15, 2016

Uva 11933: Splitting Numbers

Problem Link:
[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=3084&mosmsg=Submission+received+with+ID+17843361]

Catagory :Basic Data structure, Bit manipulation

Strategy: Count the number of 1 in binary representation of input n. Take an integer ans=0.Suppose , we have kth 1 in n. If k is odd and in jth position of n, then put this 1 in jth position of ans.

n -> 6 -> 1(2nd 1) 1(1st 1) 0
ans -> 000
ans -> 01( 1st 1 of n in 2nd position) 0

then minus ans from n which is the 2nd output.

Code:

#include<bits/stdc++.h>
#define ll unsigned long long int
using namespace std;
ll n,n1,n2,ans2;
vector<ll>ans;
int main()
{
/*ifstream infile;
infile.open("A-large.in");
//freopen("output_file_name.out","w",stdout);
ofstream outfile;
outfile.open("output_file_name.out");*/
while(cin>>n)
{
if(!n)
break;
n1=1;
n2=0;
ll s=0;
while(n1<=n)
{ if((n & n1))
{ n2++;
if(n2 % 2)
s+=n1;}
n1=n1<<1;

}
cout<<s<<" "<<n-s<<endl;
}

}

Sunday, August 14, 2016

Uva 10260 : Soundex

Problem Link:
[https://uva.onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&page=show_problem&category=&problem=1201&mosmsg=Submission+received+with+ID+17837104]

Catagory:STL Data Structure,Map

Strategy: See Algorithmist
[http://www.algorithmist.com/index.php/UVa_10260]

Code:

#include<bits/stdc++.h>
#define ll unsigned long long int
using namespace std;
ll f[10000],n,m,o;
vector<ll>pr;
map<char,ll>p;

int main()
{
p['B']=p['F']=p['P']=p['V']=1;
p['C']=p['G']=p['J']=p['K']=p['Q']=p['S']=p['X']=p['Z']=2;
p['D']=p['T']=3;
p['L']=4;
p['M']=p['N']=5;
p['R']=6;
string s;
while(cin>>s)
{
ll i=0;

while(s[i])

{ if(p[s[i]] && (p[s[i]]!=p[s[i-1]]))
cout<<p[s[i]];
i++;
}
cout<<endl;
s.clear();
}

}

Uva 11825: A Minimum Land Price

Problem Link:
[https://uva.onlinejudge.org/external/118/11824.pdf]

Catagory: STL Algorithm.
Strategy: First, sort out the data in descending order. Then use (2*(Li)^t) Formula, where Li is the initial price of land and t is the year. Use Sort function with your own comparator and try to avoid pow function to avoid double type values.

Code:

#include<bits/stdc++.h>
#define ll unsigned long long int
using namespace std;
ll f[10000],n,m,o,s;
vector<ll>pr;

ll cmp (ll a,ll b)
{
return a>b;
}
ll power(ll x,ll y)
{
ll a=1;
while(y>0)
{
if(y%2)
a*=x;

x*=x;
y/=2;
}

return a;
}
int main()
{
cin>>n;

while(n--)
{ pr.clear();
while(cin>>m)
{
if(!m)
break;
pr.push_back(m);

}
sort(pr.begin(),pr.end(),cmp);

s=0,o=0;
for(ll i=0; i<pr.size(); i++)
{ //cout<<pr[i]<<" "<<power(pr[i],i+1)<<endl;
s+=2*power(pr[i],i+1);
if(s>5000000)
{cout<<"Too expensive"<<endl;
o=1;
break;
}
}
if(!o)
cout<<s<<endl;
}

}

Friday, August 12, 2016

Uva 11321: Sort! Sort!! and Sort!!!

Problem Link:
[https://uva.onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&page=show_problem&category=&problem=2296&mosmsg=Submission+received+with+ID+17829695]

Catagory: Sort,STL Algorithm

Reading Material: About how to create own comparator in stl sort function
[http://www.cplusplus.com/reference/algorithm/sort/]

Strategy: Just create own comparator according to the condition given in problem statement. Just Make sure that -x%y is -o, not o,

Code:

#include<bits/stdc++.h>
	#define ll unsigned long long int
	using namespace std;
	vector<int>o,e,d,nd;
	int n,p,q,m;
	bool cmp(int x, int y)
	{
	if(x%m>y%m)
	return false;
	else if(x%m<y%m)
	return true;

	if(x%2 && y%2)
	return x>y;
	else if(x%2==0 && y%2==0)
	return x<y;

	return x%2;
	}

	int main()
	{
	while(cin>>n>>m)
	{ d.clear();
	if(!n && !m)
	break;

	for(int i=1; i<=n; i++)
	{
	cin>>q;
	d.push_back(q);
	}
	cout<<n<<" "<<m<<endl;
	sort(d.begin(),d.end(),cmp);
	for(int i=0; i<d.size(); i++)
	cout<<d[i]<<endl;

	}

	cout<<n<<" "<<m<<endl;

	}

Uva 332: Rational Numbers from Repeating Fractions

Problem Link:
[https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=268&mosmsg=Submission+received+with+ID+17826944]

Catagory:Mathematics,GCD

Reading material; [http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=math_for_topcoders]

Strategy : First i found out the Denominator and Numerator according to the problem. Then i Calculate the GCD of the values. Then divided Denominator and Numerator by their GCD value. Plz make sure about the Presentation.

Code:

#include<bits/stdc++.h>
#define ll unsigned long long int
using namespace std;

int main()
{ ll p10[10]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
ll j,k,d,n,g,len,t=1;
double pw;
string p;
while(cin>>j)
{
if(j==-1)
break;
cin>>p;
len=p.length()-p.find(".")-1;
k=len-j;
if(j) //if ani repeating digit exist
d=p10[k+j]-p10[k];
else //if not
d=p10[k];

n=0;

for(ll i=2; i<p.length(); i++)
{
n=n*10 + (p[i]-'0');

}

if(j)
n=n-n/p10[j];

g=__gcd(n,d);
cout<<"Case "<<t<<": "<<(ll)n/g<<"/"<<(ll)d/g<<endl;
t++;
}

}

Thursday, August 11, 2016

Uva 10038: Jolly Jumpers

Problem Link:
[https://uva.onlinejudge.org/external/100/10038.pdf]
Catagory: Data Structure, Implementation;
Strategy: See Algorithmist
[http://www.algorithmist.com/index.php/UVa_10038]

Code:

#include<bits/stdc++.h>
#define ll long long int
using namespace std;

int main()
{
ll n;
while(cin>>n)
{
ll a[n],v[n];
set<ll>d;
for(int i=0; i<n; i++)
cin>>a[i];
for(int i=0; i<n-1; i++)
{ll p=abs(a[i+1]-a[i]);
if(p>0 && p<n)
d.insert(p);}

if(d.size()==n-1)
cout<<"Jolly"<<endl;
else
cout<<"Not jolly"<<endl;
}}

Swad's Spot