#include <bits/stdc++.h>
#define pf printf
#define sf(a) scanf("%d",&a)
#define sfl(a) scanf("%lld",&a)
#define sff(a,b) scanf("%d %d",&a,&b)
#define sffl(a,b) scanf("%lld %lld",&a,&b)
#define sfff(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define sffff(a,b,c,d) scanf("%d %d %d %d",&a,&b,&c,&d)
#define sffffl(a,b,c,d) scanf("%lld %lld %lld %lld",&a,&b,&c,&d)
#define sfffff(a,b,c,d,e) scanf("%d %d %d %d %d",&a,&b,&c,&d,&e)
#define sfffffl(a,b,c,d,e) scanf("%lld %lld %lld %lld %lld",&a,&b,&c,&d,&e)
#define sfc(a) scanf("%c",&a)
#define ms(a,b) memset(a,b,sizeof(a))
#define pb(a) push_back(a)
#define pbp(a,b) push_back({a,b})
#define db double
#define ft float
#define ll long long
#define ull unsigned long long
#define ff first
#define ss second
#define sz(x) x.size()
#define qu queue
#define pqu priority_queue
#define vc vector
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define all(x) x.begin(),x.end()
#define CIN ios_base::sync_with_stdio(0); cin.tie(0)
#define max3(a, b, c) max(a, b) > max(b, c) ? max(a, b) : max(b, c)
#define min3(a, b, c) min(a, b) < min(b, c) ? min(a, b) : min(b, c)
#define loop0(i,n) for(int i=0;i<n;i++)
#define loop1(i,n) for(int i=1;i<=n;i++)
#define loopab(i,a,b) for(int i=a;i<=b;i++)
#define REV(i,n) for(i=n; i>=0; i--)
#define stlloop(x) for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) ((a)*((b)/gcd(a,b)))
#define case1(z) cout<<"Case "<<z<<": "
#define case2(z) printf("Case %d: ",z)
#define PI 3.14159265358979323846264338328
#define valid(tx,ty) tx>=0 && tx<r && ty>=0 && ty<c
#define intlim 2147483648
#define MAX 1000000
#define inf 10000000
/*------------------------------Graph Moves----------------------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
//const int fx[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
//const int fy[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
/*---------------------------------------------------------------------*/
using namespace std;
map<char,int> mp;
int main()
{
//CIN;
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
char ch;
int i;
for(ch='a',i=1; ch<='z'; ch++,i++)
{
mp[ch]=i;
}
string s1,s2;
while(getline(cin,s1))
{
getline(cin,s2);
int sum1=0;
loop0(i,sz(s1))
{
if((s1[i]>='a' && s1[i]<='z') || (s1[i]>='A' && s1[i]<='Z'))
{
s1[i]=tolower(s1[i]);
sum1+=mp[s1[i]];
}
}
while(sum1>9)
{
int x=sum1;
sum1=0;
while(x!=0)
{
sum1+=x%10;
x=x/10;
}
}
int sum2=0;
loop0(i,sz(s2))
{
if((s2[i]>='a' && s2[i]<='z') || (s2[i]>='A' && s2[i]<='Z'))
{
s2[i]=tolower(s2[i]);
sum2+=mp[s2[i]];
}
}
while(sum2>9)
{
int x=sum2;
sum2=0;
while(x!=0)
{
sum2+=x%10;
x=x/10;
}
}
if(sum1==0 && sum2==0) pf("\n");
else
{
int maxi=max(sum1,sum2);
int mini=min(sum1,sum2);
db ans=((db)mini/(db)maxi)*100.0;
pf("%.2f %\n",ans);
}
}
return 0;
}
Category Number Theory
UVa – 10394 – Twin Primes
#include <bits/stdc++.h>
#define pf printf
#define sf(a) scanf("%d",&a)
#define sfl(a) scanf("%lld",&a)
#define sff(a,b) scanf("%d %d",&a,&b)
#define sffl(a,b) scanf("%lld %lld",&a,&b)
#define sfff(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define sffff(a,b,c,d) scanf("%d %d %d %d",&a,&b,&c,&d)
#define sffffl(a,b,c,d) scanf("%lld %lld %lld %lld",&a,&b,&c,&d)
#define sfffff(a,b,c,d,e) scanf("%d %d %d %d %d",&a,&b,&c,&d,&e)
#define sfffffl(a,b,c,d,e) scanf("%lld %lld %lld %lld %lld",&a,&b,&c,&d,&e)
#define ms(a,b) memset(a,b,sizeof(a))
#define pb(a) push_back(a)
#define pbp(a,b) push_back({a,b})
#define db double
#define ft float
#define ll long long
#define ull unsigned long long
#define ff first
#define ss second
#define sz(x) x.size()
#define qu queue
#define pqu priority_queue
#define vc vector
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define all(x) x.begin(),x.end()
#define CIN ios_base::sync_with_stdio(0); cin.tie(0)
#define max3(a, b, c) max(a, b) > max(b, c) ? max(a, b) : max(b, c)
#define min3(a, b, c) min(a, b) < min(b, c) ? min(a, b) : min(b, c)
#define loop0(i,n) for(int i=0;i<n;i++)
#define loop1(i,n) for(int i=1;i<=n;i++)
#define loopab(i,a,b) for(int i=a;i<=b;i++)
#define stlloop(x) for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) ((a)*((b)/gcd(a,b)))
#define case1(z) cout<<"Case "<<z<<": "
#define case2(z) printf("Case %d: ",z)
#define PI 3.14159265358979323846264338328
#define valid(tx,ty) tx>=0 && tx<r && ty>=0 && ty<c
#define intlim 2147483648
#define MAX 20000000
#define inf 10000000
/*------------------------------Graph Moves----------------------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
//const int fx[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
//const int fy[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
/*---------------------------------------------------------------------*/
using namespace std;
bool p[MAX+2];
vector<int>prime;
void sieve()
{
p[0]=p[1]=1;
int root=sqrt(MAX);
for(int i=2; i<=root; i++)
{
if(p[i]==0)
{
for(int j=i*i; j<=MAX; j+=i)
{
p[j]=1;
if(i%2==1) j+=i;
}
}
}
for(int i=2;i<=MAX;i++)
{
if(p[i]==0) prime.push_back(i);
}
}
vector<pair<int,int> > v;
void twin_prime()
{
for(int i=1;i<sz(prime);i++)
{
if(prime[i]-prime[i-1]==2)
{
v.pbp(prime[i-1],prime[i]);
}
}
}
int main()
{
//CIN;
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
sieve();
twin_prime();
int n;
while(sf(n)==1)
{
pf("(%d, %d)\n",v[n-1].ff,v[n-1].ss);
}
return 0;
}
UVa – 10235 – Simply emirp
Note:
Here, if after reversing the number the number is equal to n , then the number is prime. But it didn’t seem logical to me after reading the problem statement.
#include <bits/stdc++.h>
using namespace std;
bool p[1000000];
vector<long long>prime;
void sieve()
{
p[0]=p[1]=1;
for(long long i=2; i<1000000;)
{
prime.push_back(i);
for(long long j=i*i; j<1000000; j+=i)
p[j]=1;
for(++i;; i++)
{
if(!p[i]) break;
}
}
}
int main()
{
long long a,n,c,i,rvrs,d;
sieve();
while(cin>>n)
{
a=0;
c=0;
for(i=0; i<prime.size(); i++)
{
if(n==prime[i])
{
a=1;
d=n;
rvrs=0;
while(d!=0)
{
rvrs=rvrs*10;
rvrs=rvrs+(d%10);
d=d/10;
}
break;
}
}
if(a==1)
{
if(rvrs==n)
{
cout<<n<<" is prime."<<endl;
}
else
{
for(i=0; i<prime.size(); i++)
{
if(rvrs==prime[i])
{
c=1;
cout<<n<<" is emirp."<<endl;
break;
}
}
if(c==0)
{
cout<<n<<" is prime."<<endl;
}
}
}
else
{
cout<<n<<" is not prime."<<endl;
}
}
return 0;
}
UVa – 583 – Prime Factors
#include <bits/stdc++.h>
#define pf printf
#define sf(a) scanf("%d",&a)
#define sfl(a) scanf("%intd",&a)
#define sff(a,b) scanf("%d %d",&a,&b)
#define sffl(a,b) scanf("%intd %intd",&a,&b)
#define sfff(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c) scanf("%intd %intd %intd",&a,&b,&c)
#define sffff(a,b,c,d) scanf("%d %d %d %d",&a,&b,&c,&d)
#define sffffl(a,b,c,d) scanf("%intd %intd %intd %intd",&a,&b,&c,&d)
#define sfffff(a,b,c,d,e) scanf("%d %d %d %d %d",&a,&b,&c,&d,&e)
#define sfffffl(a,b,c,d,e) scanf("%intd %intd %intd %intd %intd",&a,&b,&c,&d,&e)
#define ms(a,b) memset(a,b,sizeof(a))
#define pb(a) push_back(a)
#define pbp(a,b) push_back({a,b})
#define db double
#define ft float
#define ll long long
#define uint unsigned long long
#define ff first
#define ss second
#define sz(x) x.size()
#define qu queue
#define pqu priority_queue
#define vc vector
#define vi vector<int>
#define vint vector<long long>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define aint(x) x.begin(),x.end()
#define CIN ios_base::sync_with_stdio(0); cin.tie(0)
#define max3(a, b, c) max(a, b) > max(b, c) ? max(a, b) : max(b, c)
#define min3(a, b, c) min(a, b) < min(b, c) ? min(a, b) : min(b, c)
#define loop0(i,n) for(int i=0;i<n;i++)
#define loop1(i,n) for(int i=1;i<=n;i++)
#define loopab(i,a,b) for(int i=a;i<=b;i++)
#define stintoop(x) for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) ((a)*((b)/gcd(a,b)))
#define case1(z) cout<<"Case "<<z<<": "
#define case2(z) printf("Case %d: ",z)
#define PI 3.14159265358979323846264338328
#define valid(tx,ty) tx>=0 && tx<r && ty>=0 && ty<c
#define intlim 2147483648
#define MAX 46340
#define inf 10000000
/*------------------------------Graph Moves----------------------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
//const int fx[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
//const int fy[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
/*---------------------------------------------------------------------*/
using namespace std;
bool p[MAX+2];
vector<int>prime;
void sieve()
{
p[0]=p[1]=1;
int root=sqrt(MAX);
for(int i=2; i<=root; i++)
{
if(p[i]==0)
{
for(int j=i*i; j<=MAX; j+=i)
{
p[j]=1;
if(i%2==1) j+=i;
}
}
}
for(int i=2; i<=MAX; i++)
{
if(p[i]==0) prime.push_back(i);
}
}
int main()
{
//CIN;
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
sieve();
int i,d,n,c;
while(sf(n)==1 && n!=0)
{
if(n==0)
{
break;
}
pf("%d =",n);
d=0;
c=0;
if(n<0)
{
pf(" -1");
d=1;
}
n=abs(n);
int root=sqrt(n);
for(i=0; i<prime.size() && prime[i]<=root; i++)
{
if(n%prime[i]==0)
{
while(n%prime[i]==0)
{
c++;
n/=prime[i];
if(d==1) pf(" x %d",prime[i]);
else if(c>1 && d==0) pf(" x %d",prime[i]);
else pf(" %d",prime[i]);
}
}
}
if(c==0 && d==0 && n>1)
{
pf(" %d",n);
}
else if((c>=1 || d==1) && n>1)
{
pf(" x %d",n);
}
pf("\n");
}
return 0;
}
UVa – 406 – Prime Cuts
Note:
Alternative approach: Binary Ssearch
#include <bits/stdc++.h>
#define pf printf
#define sf(a) scanf("%d",&a)
#define sfl(a) scanf("%lld",&a)
#define sff(a,b) scanf("%d %d",&a,&b)
#define sffl(a,b) scanf("%lld %lld",&a,&b)
#define sfff(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define sffff(a,b,c,d) scanf("%d %d %d %d",&a,&b,&c,&d)
#define sffffl(a,b,c,d) scanf("%lld %lld %lld %lld",&a,&b,&c,&d)
#define sfffff(a,b,c,d,e) scanf("%d %d %d %d %d",&a,&b,&c,&d,&e)
#define sfffffl(a,b,c,d,e) scanf("%lld %lld %lld %lld %lld",&a,&b,&c,&d,&e)
#define ms(a,b) memset(a,b,sizeof(a))
#define pb(a) push_back(a)
#define pbp(a,b) push_back({a,b})
#define db double
#define ft float
#define ll long long
#define ull unsigned long long
#define ff first
#define ss second
#define sz(x) x.size()
#define qu queue
#define pqu priority_queue
#define vc vector
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define all(x) x.begin(),x.end()
#define CIN ios_base::sync_with_stdio(0); cin.tie(0)
#define max3(a, b, c) max(a, b) > max(b, c) ? max(a, b) : max(b, c)
#define min3(a, b, c) min(a, b) < min(b, c) ? min(a, b) : min(b, c)
#define loop0(i,n) for(int i=0;i<n;i++)
#define loop1(i,n) for(int i=1;i<=n;i++)
#define loopab(i,a,b) for(int i=a;i<=b;i++)
#define stlloop(x) for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) ((a)*((b)/gcd(a,b)))
#define case1(z) cout<<"Case "<<z<<": "
#define case2(z) printf("Case %d: ",z)
#define PI 3.14159265358979323846264338328
#define valid(tx,ty) tx>=0 && tx<r && ty>=0 && ty<c
#define intlim 2147483648
#define MAX 1002
#define inf 10000000
/*------------------------------Graph Moves----------------------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
//const int fx[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
//const int fy[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
/*---------------------------------------------------------------------*/
using namespace std;
bool p[MAX+2];
vector<int>prime;
void sieve(int n)
{
p[0]=1;
int root=sqrt(n);
for(int i=2; i<=root; i++)
{
if(p[i]==0)
{
for(int j=i*i; j<=n; j+=i)
{
p[j]=1;
if(i%2==1) j+=i;
}
}
}
for(int i=1; i<=n; i++)
{
if(p[i]==0) prime.push_back(i);
}
}
int main()
{
//CIN;
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int n,c;
while(cin>>n>>c)
{
ms(p,0);
sieve(n);
pf("%d %d:",n,c);
int a;
if(sz(prime)%2==0) a=c*2;
else a=c*2-1;
int s,lim;
if(sz(prime)>a) s=(sz(prime)-a)/2;
else s=0;
if(sz(prime)>a) lim=s+a;
else lim=sz(prime);
for(int i=s; i<lim; i++)
{
pf(" %d",prime[i]);
}
pf("\n\n");
prime.clear();
}
return 0;
}
Fall out, Codes! 