November 2014 – Page 2 – Live with passion

12502

Asif NaeemNovember 19, 2014

/**********12502**********/
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <math.h>

#define lld long long

using namespace std;


int main()
{
	int t;//a= 2/15 b=1/12

	double x,y,z;
	double extra,avg;
	cin>>t;

	while(t--)
	{
		cin>>x>>y>>z;

		avg=(x+y)/3;

		extra = x-avg;
		printf("%.0lf\n",(extra*z)/avg);
	}

	return 0;
}

/**********12502**********/

#include <iostream>

#include <string.h>

#include <stdio.h>

#include <math.h>

#define lld long long

using namespace std;

int main()

{

int t;//a= 2/15 b=1/12

double x,y,z;

double extra,avg;

cin>>t;

while(t--)

{

cin>>x>>y>>z;

avg=(x+y)/3;

extra = x-avg;

printf("%.0lf\n",(extra*z)/avg);

}

return 0;

}

12345

Asif NaeemNovember 19, 2014

#include <iostream>
#include <string.h>
#include <map>

using namespace std;


bool trace[1000005];
int a[50005];

int main()
{
	int n,q,res;
	char c;
	int idx,val;
	cin>>n>>q;

	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}

	while(q--)
	{
		cin>>c>>idx>>val;

		if(c=='M')
		{
			a[idx]=val;
		}
		else if(c=='Q')
		{
			res=0;
			for(int i=idx;i<val;i++)
			{
				if(trace[a[i]]==0)
				res++;

				trace[a[i]]=1;
			}

			for(int i=idx;i<val;i++)
				trace[a[i]]=0;

			cout<<res<<"\n";
		}
	}
}

#include <iostream>

#include <string.h>

#include <map>

using namespace std;

bool trace[1000005];

int a[50005];

int main()

{

int n,q,res;

char c;

int idx,val;

cin>>n>>q;

for(int i=0;i<n;i++)

{

cin>>a[i];

}

while(q--)

{

cin>>c>>idx>>val;

if(c=='M')

{

a[idx]=val;

}

else if(c=='Q')

{

res=0;

for(int i=idx;i<val;i++)

{

if(trace[a[i]]==0)

res++;

trace[a[i]]=1;

}

for(int i=idx;i<val;i++)

trace[a[i]]=0;

cout<<res<<"\n";

}

12554

Asif NaeemNovember 18, 2014

#include <iostream>
#include <string>

using namespace std;

string str[105];
string song[16]={"Happy", "birthday", "to", "you",
       "Happy", "birthday", "to", "you",
       "Happy", "birthday", "to", "Rujia",
       "Happy", "birthday", "to", "you",};
int main()
{
    int n;
    int i=0;
    cin>>n;
    int org = n;
    while(n--)
    {
       cin>>str[i++];
    }
    n=org;
    if(org<=16)
       {
          for(int j=0;j<16;j++)
          {
              cout<<str[j%i]<<": ";
              cout<<song[j]<<"\n";
          }
       }

    else
    {
          int Last;
          for(int j=0;j<i;j++)
          {
              cout<<str[j]<<": ";
              cout<<song[j%16]<<"\n";
              Last = j%16;//song[
          }
          if(Last!=15)
          {
             int l = 0;
             for(int k=Last+1;k<16;k++)
             {
                cout<<str[l++]<<": ";
                cout<<song[k]<<"\n";
             }
          }
    }

      // cin>>n;
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

string str[105];

string song[16]={"Happy", "birthday", "to", "you",

"Happy", "birthday", "to", "you",

"Happy", "birthday", "to", "Rujia",

"Happy", "birthday", "to", "you",};

int main()

{

int n;

int i=0;

cin>>n;

int org = n;

while(n--)

{

cin>>str[i++];

}

n=org;

if(org<=16)

{

for(int j=0;j<16;j++)

{

cout<<str[j%i]<<": ";

cout<<song[j]<<"\n";

}

else

{

int Last;

for(int j=0;j<i;j++)

{

cout<<str[j]<<": ";

cout<<song[j%16]<<"\n";

Last = j%16;//song[

}

if(Last!=15)

{

int l = 0;

for(int k=Last+1;k<16;k++)

{

cout<<str[l++]<<": ";

cout<<song[k]<<"\n";

}

// cin>>n;

return 0;

}

12527

Asif NaeemNovember 18, 2014

#include <stdio.h>
#include <iostream>
#include <math.h>
#include <string.h>
#include <time.h>

using namespace std;

int trace[5001];

int main()
{
	//clock_t t1,t2;
	//t1=clock();
	int cnt=0;
	int arr[10];
	for(int i=1;i<=5000;i++)
	{
		int tmp=i;
		trace[i]=cnt;
		memset(arr,0,sizeof(arr));

		while(tmp)
		{
			arr[tmp%10]++;
			if(arr[tmp%10]>1)
			{
				cnt++;
				trace[i]=cnt;
				break;
			}
			tmp/=10;
		}
	}

	int n,m;

	while(cin>>n>>m)
	{

		cout<<(m-n+1)-(trace[m] - trace[n-1])<<"\n";

	}
	//cout<<cnt<<"\n";
	/* t2=clock();
	 float diff ((float)t2-(float)t1);
    cout<<diff<<endl;
    */
	return 0;
}

#include <stdio.h>

#include <iostream>

#include <math.h>

#include <string.h>

#include <time.h>

using namespace std;

int trace[5001];

int main()

{

//clock_t t1,t2;

//t1=clock();

int cnt=0;

int arr[10];

for(int i=1;i<=5000;i++)

{

int tmp=i;

trace[i]=cnt;

memset(arr,0,sizeof(arr));

while(tmp)

{

arr[tmp%10]++;

if(arr[tmp%10]>1)

{

cnt++;

trace[i]=cnt;

break;

}

tmp/=10;

}

int n,m;

while(cin>>n>>m)

{

cout<<(m-n+1)-(trace[m] - trace[n-1])<<"\n";

}

//cout<<cnt<<"\n";

/* t2=clock();

float diff ((float)t2-(float)t1);

cout<<diff<<endl;

return 0;

}

Theory: from 0 to 99 there are 2*10^1=20 for each 0 to 9 digits. from 0 to 999 there are 3*10^2=300 for each 0 to 9 digits. so the foemulae is for 0 to n number of 9’s n*10^(n-1) for each 0 to 9 digits. And so, for upto 445 we can find total number

Continue Reading “12517” →

12532

Asif NaeemNovember 18, 2014

/*****Binary Index tree  12532******/
#include <stdio.h>
#include <iostream>
#include <string>
#include <string.h>
#include <math.h>

#define SZ 100005
#define ll long long

using namespace std;

int num[SZ];
int neg[SZ];
int zero[SZ];
int maxInd;

void update(int *arr,int ind,int val)
{
	while(ind<maxInd)
	{
		arr[ind]+=val;
		ind+=(ind & (-ind));
	}
}


int read(int *arr,int ind)
{
	int res =0;
	while(ind>0)
	{
		res+=arr[ind];
		ind-=(ind & (-ind));
	}
	return res;
}

int main()
{
	int a,n,k;
	string s;
	char ch;
	int valu,idx;
	while(cin>>n)
	{
		cin>>k;
		memset(zero,0,sizeof(zero));
		memset(neg,0,sizeof(neg));

		maxInd =n+1;
		for(int i=1;i<=n;i++)
		{
			cin>>a;
			if(a<0)
			{
				update(neg,i,1);
			}
			else if(a==0)
			{
				update(zero,i,1);
			}
			num[i]=a;
		}
		s="";
		//cout<<n<<" "<<k<<"\n";
		while(k--)
		{
			cin>>ch>>idx>>valu;

			if(ch=='C')
			{
				if(valu<0)
				{
					if(num[idx]==0)
					{
						update(zero,idx,-1);
						update(neg,idx,1);
					}
					else if(num[idx]>0)
					{
						update(neg,idx,1);
					}
				}
				else if(valu==0)
				{
					if(num[idx]>0)
					{
						update(zero,idx,1);
					}
					else if(num[idx]<0)
					{
						update(zero,idx,1);
						update(neg,idx,-1);
					}
				}
				else if(valu>0)
				{
					if(num[idx]==0)
					{
						update(zero,idx,-1);
					}
					else if(num[idx]<0)
					{
						update(neg,idx,-1);
					}
				}

				num[idx] = valu;
			}//end command type check

			else if(ch=='P')
			{
				int d,m;
				d = read(zero,valu) - read(zero,idx-1);
				m = read(neg,valu) - read(neg,idx-1);
				//cout<<"dm = "<<d<<" "<<m<<"\n";
				if(d>0)
				{
					s.append(1u,'0');
					//cout<<"0";
				}
				else if(m%2==1)
				{
					s.append(1u,'-');
					//cout<<"-";
				}
				else if(d==0 && (m%2)==0)
					s.append(1u,'+');
					//cout<<"+";

			}
		}
		cout<<s<<"\n";
	}

	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

/*****Binary Index tree 12532******/

#include <stdio.h>

#include <iostream>

#include <string>

#include <string.h>

#include <math.h>

#define SZ 100005

#define ll long long

using namespace std;

int num[SZ];

int neg[SZ];

int zero[SZ];

int maxInd;

void update(int *arr,int ind,int val)

{

while(ind<maxInd)

{

arr[ind]+=val;

ind+=(ind & (-ind));

}

int read(int *arr,int ind)

{

int res =0;

while(ind>0)

{

res+=arr[ind];

ind-=(ind & (-ind));

}

return res;

}

int main()

{

int a,n,k;

string s;

char ch;

int valu,idx;

while(cin>>n)

{

cin>>k;

memset(zero,0,sizeof(zero));

memset(neg,0,sizeof(neg));

maxInd =n+1;

for(int i=1;i<=n;i++)

{

cin>>a;

if(a<0)

{

update(neg,i,1);

}

else if(a==0)

{

update(zero,i,1);

}

num[i]=a;

}

s="";

//cout<<n<<" "<<k<<"\n";

while(k--)

{

cin>>ch>>idx>>valu;

if(ch=='C')

{

if(valu<0)

{

if(num[idx]==0)

{

update(zero,idx,-1);

update(neg,idx,1);

}

else if(num[idx]>0)

{

update(neg,idx,1);

}

else if(valu==0)

{

if(num[idx]>0)

{

update(zero,idx,1);

}

else if(num[idx]<0)

{

update(zero,idx,1);

update(neg,idx,-1);

}

else if(valu>0)

{

if(num[idx]==0)

{

update(zero,idx,-1);

}

else if(num[idx]<0)

{

update(neg,idx,-1);

}

num[idx] = valu;

}//end command type check

else if(ch=='P')

{

int d,m;

d = read(zero,valu) - read(zero,idx-1);

m = read(neg,valu) - read(neg,idx-1);

//cout<<"dm = "<<d<<" "<<m<<"\n";

if(d>0)

{

s.append(1u,'0');

//cout<<"0";

}

else if(m%2==1)

{

s.append(1u,'-');

//cout<<"-";

}

else if(d==0 && (m%2)==0)

s.append(1u,'+');

//cout<<"+";

}

cout<<s<<"\n";

}

return 0;

}

12541

Asif NaeemNovember 18, 2014

#include <iostream>
#include <sstream>
#include <stdio.h>
#include <string>
#include <math.h>


using namespace std;

int main()
{
    int n;
    double max_,min_;
    double day,month,yr;
    string s,name,young,old;
    stringstream ss;
    bool f=false;
    cin>>n;
    //getchar();
    while(n--)
    {
       cin>>name>>day>>month>>yr;
       yr+=((month/12)+(day/365));
       if(!f)
       {
          max_=yr;
          young = name;
          min_=yr;
          old = name;
          f=1;
       }
       else
       {
           if(yr>max_)
           {
              max_=yr;
              young = name;
           }
           if(yr<min_)
           {
              min_=yr;
              old = name;
           }
       }

    }

    cout<<young<<"\n"<<old<<"\n";
    //cin>>old;
    return 0;
}

#include <iostream>

#include <sstream>

#include <stdio.h>

#include <string>

#include <math.h>

using namespace std;

int main()

{

int n;

double max_,min_;

double day,month,yr;

string s,name,young,old;

stringstream ss;

bool f=false;

cin>>n;

//getchar();

while(n--)

{

cin>>name>>day>>month>>yr;

yr+=((month/12)+(day/365));

if(!f)

{

max_=yr;

young = name;

min_=yr;

old = name;

f=1;

}

else

{

if(yr>max_)

{

max_=yr;

young = name;

}

if(yr<min_)

{

min_=yr;

old = name;

}

cout<<young<<"\n"<<old<<"\n";

//cin>>old;

return 0;

}

12543

Asif NaeemNovember 17, 2014

#include <iostream>
#include <string>
#include <math.h>


using namespace std;

int main()
{
    string s,maxStr,a;
    int max_=0;
    int len=0;
    maxStr="";
    while(cin>>s)
    {
       if(s=="E-N-D")
       break;

       len=0;
       a="";
       for(int i=0;i<s.size();i++)
       {
         if((s[i]>='a' && s[i]<='z') || (s[i]>='A' && s[i]<='Z') || s[i]=='-')
         {
           len++;
           if(s[i]>='A' && s[i]<='Z')
           a.append(1u,s[i]+32);
           else
           a.append(1u,s[i]);
         }
       }

       if(len>max_)
       {
          max_=len;
          maxStr=a;
       }
    }
    cout<<maxStr<<"\n";
    return 0;
}

#include <iostream>

#include <string>

#include <math.h>

using namespace std;

int main()

{

string s,maxStr,a;

int max_=0;

int len=0;

maxStr="";

while(cin>>s)

{

if(s=="E-N-D")

break;

len=0;

a="";

for(int i=0;i<s.size();i++)

{

if((s[i]>='a' && s[i]<='z') || (s[i]>='A' && s[i]<='Z') || s[i]=='-')

{

len++;

if(s[i]>='A' && s[i]<='Z')

a.append(1u,s[i]+32);

else

a.append(1u,s[i]);

}

if(len>max_)

{

max_=len;

maxStr=a;

}

cout<<maxStr<<"\n";

return 0;

}

10780

Asif NaeemNovember 16, 2014

#include <iostream>
#include <cstring>
#include <math.h>
#include <stdio.h>
#include <vector>
#include <fstream>

#define ull  unsigned long long

using namespace std;


int factor[10001][1230];
int factorcount[10001][1230];
int prime[10001];
vector<int> v;
ull _MAX;

void primegenerator()
{
	double p=sqrt(10001);

	v.push_back(2);

	for(int i=3;i<p;i+=2)
	{
		if(prime[i]==0)
		for(int j=i*i;j<10001;j+=i)
			prime[j]=1;
	}

	for(int i=3;i<10001;i+=2)
	{
		if(prime[i]==0)
		v.push_back(i);
	}

}

void factorize()
{
	for(int i=2;i<10001;i++)
	{
		int tmp=i;
		int j=0;
		while(tmp>1)
		{
			if(tmp%v[j]==0)
			{
				factorcount[i][j]++;
				factor[i][j]++;
				tmp/=v[j];
				j=-1;

			}
			j++;
			if(j==v.size())
			break;
		}
		for(int k=0;k<1230;k++)
		factorcount[i][k]+=factorcount[i-1][k];

	}
}

int main()
{
	primegenerator();
	factorize();
	int t,m,n;
	int kase=0;
	cin>>t;
	while(t--)
	{
		cin>>m>>n;
		kase+=1;
		if(m<=1 || n<=0)
		{
			cout<<"Case "<<kase<<":\n";
			cout<<"Impossible to divide\n";
			continue;
		}
		int imposbl=0;
		double min_d=2e9;
		for(int i=0;i<1230;i++)
		{
			if(factor[m][i]>factorcount[n][i])
			{
				imposbl=1;
				break;
			}
			else if(factor[m][i] && factorcount[n][i] && factorcount[n][i]/factor[m][i] <min_d)
			{
                 min_d = factorcount[n][i]/factor[m][i];
			}
		}
		cout<<"Case "<<kase<<":\n";
		if(imposbl==1)
		{
           cout<<"Impossible to divide\n";
        }
		else
		{
            cout<<min_d<<"\n";
        }

	}


	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

#include <iostream>

#include <cstring>

#include <math.h>

#include <stdio.h>

#include <vector>

#include <fstream>

#define ull unsigned long long

using namespace std;

int factor[10001][1230];

int factorcount[10001][1230];

int prime[10001];

vector<int> v;

ull _MAX;

void primegenerator()

{

double p=sqrt(10001);

v.push_back(2);

for(int i=3;i<p;i+=2)

{

if(prime[i]==0)

for(int j=i*i;j<10001;j+=i)

prime[j]=1;

}

for(int i=3;i<10001;i+=2)

{

if(prime[i]==0)

v.push_back(i);

}

void factorize()

{

for(int i=2;i<10001;i++)

{

int tmp=i;

int j=0;

while(tmp>1)

{

if(tmp%v[j]==0)

{

factorcount[i][j]++;

factor[i][j]++;

tmp/=v[j];

j=-1;

}

j++;

if(j==v.size())

break;

}

for(int k=0;k<1230;k++)

factorcount[i][k]+=factorcount[i-1][k];

}

int main()

{

primegenerator();

factorize();

int t,m,n;

int kase=0;

cin>>t;

while(t--)

{

cin>>m>>n;

kase+=1;

if(m<=1 || n<=0)

{

cout<<"Case "<<kase<<":\n";

cout<<"Impossible to divide\n";

continue;

}

int imposbl=0;

double min_d=2e9;

for(int i=0;i<1230;i++)

{

if(factor[m][i]>factorcount[n][i])

{

imposbl=1;

break;

}

else if(factor[m][i] && factorcount[n][i] && factorcount[n][i]/factor[m][i] <min_d)

{

min_d = factorcount[n][i]/factor[m][i];

}

cout<<"Case "<<kase<<":\n";

if(imposbl==1)

{

cout<<"Impossible to divide\n";

}

else

{

cout<<min_d<<"\n";

}

return 0;

}

10308

Asif NaeemNovember 16, 2014

This is the problem to find the tree diameter.

#include <iostream>
#include <fstream>
#include <sstream>
#include <map>
#include <vector>
#include <string>
#include <queue>
#include <string.h>
#include <stdio.h>

#define ull unsigned long long
#define SZ 10002
#define FOR(i,a) for(int i=0;i<a;i++)

using namespace std;

vector<int> graph[SZ];
bool visit[SZ];
int distnce[SZ][SZ];
ull distnode[SZ];
ull max_dist=0;
int farthestnode;

void bfs(int u)
{
	int tmp;
	memset(visit,0,sizeof(visit));
	int next_node;
	max_dist=0;
	queue<int> q;
	q.push(u);
	distnode[u]=0;
	while(!q.empty())
	{
		tmp = q.front();
		q.pop();
		visit[tmp]=1;

		if(distnode[tmp]>max_dist)
		{
			max_dist=distnode[tmp];
			farthestnode = tmp;
		}
		for(int i=0;i<graph[tmp].size();i++)
		{
			next_node = graph[tmp][i];
			if(!visit[next_node])
			{
				distnode[next_node]=distnode[tmp]+distnce[tmp][next_node];
				q.push(next_node);
			}
		}

	}

}


int main()
{
	string s,s1;
	int from,dest,cost;
	stringstream ss;

	while(!cin.eof())
	{
		getline(cin,s);

		if(s=="")
		{
			cout<<0<<"\n";
			continue;
		}

		FOR(i,SZ)
		graph[i].clear();

		memset(distnce,0,sizeof(distnce));
		memset(distnode,0,sizeof(distnode));

		while(!cin.eof() && s.size()>0)
		{
			if(s=="")
			break;
			ss.clear();
			ss<<s;
			ss>>from>>dest>>cost;

			graph[from].push_back(dest);
			graph[dest].push_back(from);

			distnce[from][dest]=cost;
			distnce[dest][from]=cost;

			getline(cin,s);
		}

		bfs(1);
		bfs(farthestnode);

		cout<<max_dist<<"\n";

	}

	return 0;

}

100

101

102

103

104

105

106

107

#include <iostream>

#include <fstream>

#include <sstream>

#include <map>

#include <vector>

#include <string>

#include <queue>

#include <string.h>

#include <stdio.h>

#define ull unsigned long long

#define SZ 10002

#define FOR(i,a) for(int i=0;i<a;i++)

using namespace std;

vector<int> graph[SZ];

bool visit[SZ];

int distnce[SZ][SZ];

ull distnode[SZ];

ull max_dist=0;

int farthestnode;

void bfs(int u)

{

int tmp;

memset(visit,0,sizeof(visit));

int next_node;

max_dist=0;

queue<int> q;

q.push(u);

distnode[u]=0;

while(!q.empty())

{

tmp = q.front();

q.pop();

visit[tmp]=1;

if(distnode[tmp]>max_dist)

{

max_dist=distnode[tmp];

farthestnode = tmp;

}

for(int i=0;i<graph[tmp].size();i++)

{

next_node = graph[tmp][i];

if(!visit[next_node])

{

distnode[next_node]=distnode[tmp]+distnce[tmp][next_node];

q.push(next_node);

}

int main()

{

string s,s1;

int from,dest,cost;

stringstream ss;

while(!cin.eof())

{

getline(cin,s);

if(s=="")

{

cout<<0<<"\n";

continue;

}

FOR(i,SZ)

graph[i].clear();

memset(distnce,0,sizeof(distnce));

memset(distnode,0,sizeof(distnode));

while(!cin.eof() && s.size()>0)

{

if(s=="")

break;

ss.clear();

ss<<s;

ss>>from>>dest>>cost;

graph[from].push_back(dest);

graph[dest].push_back(from);

distnce[from][dest]=cost;

distnce[dest][from]=cost;

getline(cin,s);

}

bfs(1);

bfs(farthestnode);

cout<<max_dist<<"\n";

}

return 0;

}

Month: November 2014

12502

12345

12554

12527

12517

12532

12541

12543

10780

10308

Archives

Categories