Programming Problems!!!

Saturday, April 4, 2015

11466 - Largest Prime Divisor (UVa)

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
#define MAX 10001000
#define size 1000000
typedef long long ll;
ll prime[size], status[MAX];
ll factor[150];
ll p, d;

void siv()
{
ll n;
ll i, j;
n=MAX;
ll sq= sqrt(n);
for(i=3; i<=sq; i+=2)
{
if(status[i]==0)
{
for(j=i*i; j<=n; j+=(i+i))
{
status[j]=1;
}
}
}
prime[0]=2;
p=1;
for(i=3; i<=n; i+=2)
{
if(status[i]==0)
{
prime[p++] = i;
}
}
}

void primeFactor(ll n)
{
ll i, j, temp;
ll sq = ll(sqrt(n));
d=0;
temp =0;
for(i=0; prime[i]<=sq; i++)
{
while(n%prime[i]==0)
{
if(temp !=prime[i])
factor[d++] = prime[i];

n /= prime[i];
temp = prime[i];
}
}
if(n>1)
{
factor[d++] = n;
}
}
int main()
{
siv();
ll n;
while(cin >> n)
{
if(n==0) break;
if(n<0) n*=-1;
primeFactor(n);
if(d<2)
{
cout << "-1" << endl;
}
else
{
cout << factor[d-1] << endl;
}
}
return 0;
}

Friday, April 3, 2015

10699 - Count the factors (UVa)

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
#define MAX 10000
#define size 1500

int prime[size], status[MAX];
int factor[200];
int p;

void siv()
{
int n, i, j;
n=MAX;
int sq= sqrt(n);
for(i=3; i<=sq; i+=2)
{
if(status[i]==0)
{
for(j=i*i; j<=n; j+=(i+i))
{
status[j]=1;
}
}
}
prime[0]=2;
p=1;
for(i=3; i<=n; i+=2)
{
if(status[i]==0)
{
prime[p++] = i;
}
}
}

void primeFactor(int n)
{
int i, j, d;
int sq= sqrt(n);
d=0;
int temp =0;
for(i=0; prime[i]<=sq; i++)
{
while(n%prime[i]==0)
{
if(temp !=prime[i])
factor[d++] = prime[i];

n /= prime[i];
temp = prime[i];
}
}
if(n>1)
{
factor[d++] = n;
}
printf("%d",d);
}

int main()
{
siv();
int n;
while(cin >> n)
{
if(n==0)
break;
else
{
printf("%d : ", n);
primeFactor(n);
}
printf("\n");
}
return 0;
}

583 - Prime Factors (UVa)

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
#define MAX 50000
#define size 5500
typedef long long ll;
int prime[size], status[MAX];
int factor[200];
int p, d;

void siv()
{
int n, i, j;
n=MAX;
int sq= sqrt(n);
for(i=3; i<=sq; i+=2)
{
if(status[i]==0)
{
for(j=i*i; j<=n; j+=(i+i))
{
status[j]=1;
}
}
}
prime[0]=2;
p=1;
for(i=3; i<=n; i+=2)
{
if(status[i]==0)
{
prime[p++] = i;
}
}
}

void primeFactor(int n)
{
int i, j;
int sq= sqrt(n);
d=0;
for(i=0; prime[i]<=sq; i++)
{
while(n%prime[i]==0)
{
factor[d++] = prime[i];
n /= prime[i];
}
}
if(n>1)
{
factor[d++] = n;
}
}

int main()
{
siv();
ll n, c;
while(cin >> n)
{
if(n==0)
break;
if(n<0)
{
n *=(-1);
printf("-%lld = -1 x ", n);
primeFactor(n);
for(c=0 ; c<d ; c++)
{
if(c==d-1)
{
printf("%d", factor[c]);
}
else
{
printf("%d x ", factor[c]);
}
}
}
else
{
printf("%lld = ", n);
primeFactor(n);
for(c=0 ; c<d ; c++)
{
if(c==d-1)
{
printf("%d", factor[c]);
}
else
{
printf("%d x ", factor[c]);
}
}
}
printf("\n");
}
return 0;
}

467A - George and Accommodation (Codeforces)

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define pf printf
#define sf scanf

int main()
{
int n, p, q, count;
sf("%d", &n);
count = 0;
while(n--)
{
sf("%d%d", &p, &q);
if((q-p)>=2)
count++;
}
pf("%d\n", count);
return 0;
}

469A - I Wanna Be the Guy (Codeforces)

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define pf printf
#define sf scanf
#define size 105
int p_arr[size], q_arr[size], test[size];

int main()
{
int n, p, q, t=0, i, count;
sf("%d", &n);
sf("%d", &p);
for(i=1; i<=p; i++)
{
sf("%d", &p_arr[i]);
t = p_arr[i];
test[t] = 1;
}
sf("%d", &q);
for(i=1; i<=q; i++)
{
sf("%d", &q_arr[i]);
t = q_arr[i];
test[t] = 1;
}
count = 0;
for(t=1; t<=n; t++)
{
if(test[t]==1)
{
count++;
}
}
if(count==n)
{
pf("I become the guy.\n");
}
else
{
pf("Oh, my keyboard!\n");
}
return 0;
}

471A. MUH and Sticks (Codeforces)

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define pf printf
#define sf scanf
#define size 10
int a[size];

int main()
{
int i;
for(i=0; i<6; i++)
{
sf("%d", &a[i]);
}
sort(a, a+6);
i=0;

if((a[i]==a[i+1] && a[i]==a[i+2] && a[i]==a[i+3] && a[i+4]==a[i+5])||
(a[i]==a[i+1] && a[i+2]==a[i+3] && a[i+2]==a[i+4] && a[i+2]==a[i+5])||
(a[i+1]==a[i+2] && a[i+1]==a[i+3] && a[i+1]==a[i+4] && a[i]==a[i+5]))
{
pf("Elephant\n");
}

else if((a[i]==a[i+1] && a[i]==a[i+2] && a[i]==a[i+3] && a[i+4]<a[i+5])||
(a[i]<a[i+1] && a[i+2]==a[i+3] && a[i+2]==a[i+4] && a[i+2]==a[i+5]) ||
(a[i+1]==a[i+2] && a[i+1]==a[i+3] && a[i+1]==a[i+4] && a[i]<a[i+5]))
{
pf("Bear\n");
}

else
{
pf("Alien\n");
}
return 0;
}

476A - Dreamoon and Stairs (Codeforces)

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define pf printf
#define sf scanf

int main()
{
int n, m, temp=0, move;
while(sf("%d%d", &n, &m)==2)
{
if(n<m)
pf("-1\n");
if(n==m)
pf("%d\n", n);
else
{
if(n%2==0)
{
temp = n/2;
}
else
{
temp = (n-1)/2;
temp += 1;
}
move = 0;
while(temp!=n)
{
if(temp%m==0)
{
move = temp;
pf("%d\n", move);
break;
}
else
{
temp++;
}
}
}
}
return 0;
}