ARRAYSUB – subarrays

#include<stdio.h>
#include<queue>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll ar[1000006];
int main()
{
 deque<ll> dq;
 ll n,i,k;
 scanf("%lld",&n);
 for(i=1;i<=n;i++)
 scanf("%lld",&ar[i]);
 scanf("%lld",&k);
 for(i=1;i<=k;i++)
 {
 while(dq.empty()==false && ar[i]>=ar[dq.back()])
 dq.pop_back();
 dq.push_back(i);
 }
 for(i=k+1;i<=n;i++)
 {
 printf("%lld ",ar[dq.front()]);
 while(dq.empty()==false && ar[i]>=ar[dq.back()])
 dq.pop_back();
 while(dq.empty()==false && i-dq.front()>=k)
 dq.pop_front();
 dq.push_back(i);
 }
 printf("%lld",ar[dq.front()]);
 return 0;
}

SPOJ – AIBOHP – Aibohphobia

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
ll max(ll a,ll b)
{
 if(a>=b)
 return a;
 else
 return b;
}
ll dp[6103][6103];
int main()
{
 char ar[6103];
 char at[6103];
 ll t,i,j,n;
 scanf("%lld",&t);
 while(t--)
 {
 scanf("%s",ar);
 n=strlen(ar);
 reverse(ar,ar+n);
 for(i=0;i<n;i++)
 at[i]=ar[i];
 reverse(ar,ar+n);
 for(i=n;i>0;i--)
 {
 at[i]=at[i-1];
 ar[i]=ar[i-1];
 }
 for(i=0;i<=n;i++)
 dp[i][0]=0;
 for(i=0;i<=n;i++)
 dp[0][i]=0;
 for(i=1;i<=n;i++)
 {
 for(j=1;j<=n;j++)
 {
 if(ar[i]==at[j])
 dp[i][j]=1+dp[i-1][j-1];
 else
 dp[i][j]=max(dp[i-1][j],dp[i][j-1]); 
 }
 }
 ll ans=n-dp[n][n];
 printf("%lld\n",ans);
 }
 return 0;
 return 0;
 
}

SPOJ – ABCPATH

#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
typedef int ll;
ll n,m;
char ar[55][55];
ll dp[55][55];
ll drx[8]={1,1,0,-1,-1,-1,0,1};
ll dry[8]={0,1,1,1,0,-1,-1,-1};
ll dfs(ll a,ll b)
{
 ll i,j;
 ll x,y;
 if(dp[a][b]!=-1)
 return dp[a][b];
 else
 {
 dp[a][b]=1;
 for(i=0;i<8;i++)
 {
 x=a+drx[i];
 y=b+dry[i];
 if(x>=0 && y>=0 && x<n && y<m )
 if((ar[a][b]-'0')+1==(ar[x][y]-'0'))
 dp[a][b]=max(dp[a][b],1+dfs(x,y)); 
 }
 }
 return dp[a][b];
}
int main()
{
 ll i,j,ans,ans1=-1;
 ll q=1;
 while(scanf("%d%d",&n,&m) && (n!=0 || m!=0))
 {
 memset(dp,-1,sizeof(dp));
 ans1=0;
 for(i=0;i<n;i++)
 cin>> ar[i];
 for(i=0;i<n;i++)
 {
 for(j=0;j<m;j++)
 {
 if(ar[i][j]=='A')
 {
 ans=dfs(i,j);
 if(ans>ans1)
 ans1=ans;
 }
 }
 }
 printf("Case %d: %d\n",q++,ans1);
}
 return 0; 
}

SPOJ – ABCDEF

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long ll;
ll ar1[1000004];
ll ar2[1000004];
int main()
{
 ll ar[102];
 ll b=0,n,i;
 scanf("%lld",&n);
 for(i=0;i<n;i++)
 scanf("%lld",&ar[i]);
 ll j,k;
 for(i=0;i<n;i++)
 {
 for(j=0;j<n;j++)
 {
 for(k=0;k<n;k++)
 {
 ar1[b++]=(ar[i]*ar[j])+ar[k];
 }
 }
 }
 ll b1=0;
 for(i=0;i<n;i++)
 {
 for(j=0;j<n;j++)
 {
 for(k=0;k<n;k++)
 {
 if(ar[k]==0)
 continue;
 ar2[b1++]=(ar[i]+ar[j])*ar[k];
 }
 }
 }
 std::sort(ar1,ar1+b);
 std::sort(ar2,ar2+b1);
 ll count=0;
 ll o=0,t=0;
 for(i=0;i<b;i++)
 {
 ll k1=lower_bound(ar2,ar2+b1,ar1[i])-ar2;
 ll k2=upper_bound(ar2,ar2+b1,ar1[i])-ar2;
 count=count+k2-k1;
 }
 printf("%lld\n",count);
 return 0;
}

UVA – 12442 – Forwarding Emails

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<vector>
using namespace std;
typedef long long ll;
vector<ll> v[500004];
ll visit[500004];
ll d[500004];
ll dfs(ll n)
{
 visit[n]=1;
 ll i;
 ll ans=0;
 for(i=0;i<v[n].size();i++)
 {
 ll k=v[n][i];
 if(visit[k]==0)
 {
 ans=1+dfs(k);
 }
 }
 d[n]=ans;
 visit[n]=0;
 return ans;
}
int main()
{
 ll t,n,k,i,a,b;
 scanf("%lld",&t);
 ll s=1;
 while(t--)
 {
 ll max=-1;
 for(i=0;i<=50000;i++)
 v[i].clear();
 ll p;
 scanf("%lld",&n);
 for(i=0;i<n;i++)
 {
 scanf("%lld%lld",&a,&b);
 v[a].push_back(b);
 }
 memset(visit,0,sizeof(visit));
 for(i=0;i<=50000;i++)
 d[i]=-1;
 for(i=1;i<=n;i++)
 {
 if(d[i]==-1)
 {
 ll g=dfs(i);
 if(g>max)
 {
 max=g;
 p=i;
 }
 }
 }
 printf("Case %lld: %lld\n",s++,p);
 }
 return 0;
}

UVA – 10139 – Factovisors

#include<stdio.h>
typedef long long ll;
struct node{
 ll a,b;
};
ll g=0;
struct node ar[100000];
void prime(ll n)
{
 ll i;
 ll count;
 count=0;
 while(n%2==0)
 {
 n=n/2;
 count++;
 }
 if(count!=0)
 {
 ar[g].a=2;
 ar[g].b=count;
 g++;
 }
 for(i=3;i*i<=n;i=i+2)
 {
 count=0;
 while(n%i==0)
 {
 n=n/i;
 count++;
 }
 if(count!=0)
 {
 ar[g].a=i;
 ar[g].b=count;
 g++;
 }
 }
 count=0;
 if(n>1)
 {
 ar[g].a=n;
 ar[g].b=1;
 g++;
 }
}
ll get_power(ll n,ll p)
{
 ll ans=0;
 ll i;
 for(i=p;i<=n;i=i*p)
 {
 ans=ans+n/i;
 }
 return ans;
}
int main()
{
 ll n,m,i;
 ll p,k1,k2;
 while(scanf("%lld%lld",&n,&m)!=EOF)
 {
 g=0;
 prime(m);
 p=1;
 for(i=0;i<g;i++)
 {
 
 k1=get_power(n,ar[i].a);
 k2=ar[i].b;
 if(k1<k2)
 {
 p=2;
 break;
 }
 }
 if(p==2)
 {
 printf("%lld does not divide %lld!\n",m,n);
 continue;
 }
 printf("%lld divides %lld!\n",m,n);
 }
 return 0;
}

UVA – 10892 – LCM Cardinality

#include<stdio.h>
typedef long long ll;
ll prime(ll n)
{
 ll ans=1;
 ll count=0;
 while(n%2==0)
 {
 n=n/2;
 count++;
 }
 ans=ans*(2*count+1);
 count=0;
 ll i;
 for(i=3;i*i<=n;i++)
 {
 count=0;
 while(n%i==0)
 {
 count++;
 n=n/i;
 }
 ans=ans*(2*count+1);
 }
 if(n>1)
 ans=ans*3;
 return ans;
}
int main()
{
 ll n;
 while(scanf("%lld",&n) && n!=0)
 {
 ll k=prime(n);
 printf("%lld %lld\n",n,(k/2)+1);
 }
 return 0;
}

UVA – 10212 – The Last Non-zero Digit.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define mod 20000000
typedef long long ll;
int main()
{
 ll n,m,i,ans,j,k;
 while(scanf("%lld%lld",&n,&m)!=EOF)
 {
 ans=1;
 for(i=n,j=0;j<m;j++,i--)
 {
 ans=ans*i;
 while(ans%10==0)
 {
 ans=ans/10;
 }
 ans=ans%mod;
 }
 printf("%lld\n",ans%10);
 }
 return 0;
}

UVA – 11344 – The Huge One

#include<stdio.h>
#include<string.h>
typedef long long ll;
int main()
{
 ll t,n,i,x,p,a;
 ll r;
 char ar[10004];
 scanf("%lld",&t);
 while(t--)
 {
 p=1;
 scanf("%s",ar);
 n=strlen(ar);
 scanf("%lld",&x);
 while(x--)
 {
 scanf("%lld",&a);
 r=(ar[0]-'0')%a;
 for(i=1;i<n;i++)
 r=(r*10+ar[i]-'0')%a;
 if(r!=0)
 p=2; 
 }
 if(p==2)
 printf("%s - Simple.\n",ar);
 else
 printf("%s - Wonderful.\n",ar);
 }
 return 0;
}

UVA – 10127 – Ones

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
typedef long long ll;
int main()
{
 ll n;
 ll count;
 while(scanf("%lld",&n)!=EOF)
 {
 count=1;
 ll r=1;
 while(r%n!=0)
 {
 count++;
 r=(10*r+1)%n;
 }
 printf("%lld\n",count);
 }
 return 0;
}