M. N. Hasan: November 2015

27 November 2015

UVA 378- Intersecting Lines

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size) for(int i=0 ; i<size ; i++) cin>>array[i] ;
#define new_line pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647

int area(int x1,int y1,int x2,int y2,int x3,int y3)
{
return x1*y2-y1*x2+x2*y3-y2*x3+x3*y1-y3*x1;
}

int main()
{
int test ;
sc("%d",&test) ;
pf("INTERSECTING LINES OUTPUT\n") ;
while(test--)
{
int x1,y1,x2,y2,x3,y3,x4,y4 ;
cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4 ;

if( area(x1,y1,x2,y2,x3,y3)==0 && area(x1,y1,x2,y2,x4,y4)==0)
{
pf("LINE\n") ;
continue ;
}

int a1 = y2-y1 ;
int b1 = x1 -x2 ;
int c1 = y1*x2 - x1*y2 ;
int a2 = y4 -y3 ;
int b2 = x3 -x4 ;
int c2 = y3*x4 - x3*y4 ;
int m = (a1*b2 - b1*a2) ; /// condition to be parallel
if(m==0)
{
pf("NONE\n") ;
continue ;
}

double x = ((b1*c2 - b2*c1)*1.0) / ((a1*b2 - a2*b1)*1.0) ;
double y = ((c1*a2 - c2*a1)*1.0) / ((a1*b2 - a2*b1)*1.0) ;
pf("POINT %.2lf %.2lf\n",x,y) ;

}

pf("END OF OUTPUT\n") ;
return 0;
}

26 November 2015

uva 587- There's treasure everywhere!

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size) for(int i=0 ; i<size ; i++) cin>>array[i] ;
#define new_line pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647

int main()
{
char ch ;
string str ;
int d =0 ;
double x =0,y=0 ;
int cnt= 1 ;

while(cin>>ch)
{
if(ch>='0' && ch<='9')
d = d*10 + ch-'0' ;
else if(ch=='E' || ch=='N' || ch=='D' || ch=='S' || ch=='W')
{
str+=ch ;
if(str=="END")
break ;
}
else if(ch==',' || ch=='.')
{
if(str == "E")
x+=d ;
else if(str=="N")
y+=d ;
else if(str=="S")
y-=d ;
else if(str=="W")
x-=d ;
else if(str=="NE")
{
x = x + (d*cos(45*pi/180.0)) ;
y = y+ (d*sin(45*pi/180.0)) ;
}
else if(str=="NW")
{
x = x - (d*cos(45*pi/180.0)) ;
y = y+ (d*sin(45*pi/180.0)) ;
}
else if(str=="SW")
{
x = x - (d*cos(45*pi/180.0)) ;
y = y- (d*sin(45*pi/180.0)) ;
}
else if(str=="SE")
{
x = x + (d*cos(45*pi/180.0)) ;
y = y- (d*sin(45*pi/180.0)) ;
}

d= 0;
str = "" ;

if(ch=='.')
{
double dis = sqrt((x*x) + (y*y)) ;
pf("Map #%d\n",cnt++) ;
pf("The treasure is located at (%.3lf,%.3lf).\n",x,y) ;
pf("The distance to the treasure is %.3lf.\n\n",dis) ;
x=0 ;
y =0 ;
dis =0 ;
}
}
}
return 0;
}

23 November 2015

Lightoj 1141-Number Transformation

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size) for(int i=0 ; i<size ; i++) cin>>array[i] ;
#define new_line pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647
#define sz 1000+10

bool prime[100001] ;
vector<int> data ;
vector<int> prime_fact[100001] ;

void isPrime()
{
memset(prime,true,sizeof(prime)) ;

for(int i =2 ;i<=sz ; i++)
{
for(int j= 2*i ;j<=sz ;j+=i)
{
prime[j] =false ;
}
}

for(int i=2 ;i<=sz ;i++)
{
if(prime[i])
data.pb(i) ;
}
}

void fact()
{
for(int i=2 ;i<=sz ; i++)
{
for(int j=0 ;j<data.size() ; j++)
{
if(i%data[j]==0 && i>data[j])
prime_fact[i].pb(data[j]) ;
}
}
}

int dis[100001] ;

int bfs(int s, int t)
{
bool visited[100001] ;
memset(visited,false,sizeof(visited)) ;
queue<int>q ;
memset(dis,0,sizeof(dis)) ;

q.push(s) ;
dis[s] =0 ;
while(!q.empty())
{
int u = q.front() ;
q.pop() ;
if(u==t)
return dis[u] ;
for(int i=0 ;i<prime_fact[u].size() ; i++)
{
int v = u+ prime_fact[u][i] ;
if(visited[v]==false && v<=t)
{
visited[v] = true ;
q.push(v) ;
dis[v] = dis[u] +1 ;
}
}
}
return -1 ;

}
int main()
{
isPrime() ;
fact() ;
int test ;
cin>>test ;
int cnt =1 ;
while(test--)
{
int s ,t ;
cin>>s>>t ;
int ans = bfs(s,t) ;
pf("Case %d: %d\n",cnt++,ans) ;
}
return 0;
}

Lightoj 1214- Large Division

Let explain one input. a = -202202202202202202 and b =-101.Make partition of a such that the partition is divisible by b. Look 202 is divisible by 101 and next partition is also 202 which is also divisible by 101. Make the process continue till the end of a. There is one thing to beware which is range of a.

22 November 2015

Lightoj 1010-Knights in Chessboard

Though it is simple but has a twist when any dimension of the board is 2.Let a & b be the dimension of the board. It will be better if you 1st draw some board where a=2 and b may be an odd or even number greater than or equal to a . After that just calculate the number of knight with the condition which has been given in problem. If a!=2 & b!=2 then the calculation is quite easy.Just multiply a&b and take their ceil.

21 November 2015

Lightoj 1008- Fibsieve`s Fantabulous Birthday

This problem is quite easy. Look carefully that if we square root s and take it ceil n, then the abscissa or the ordinate will be equal to n. After that find k = m -n +1 which will help to determine that intersection number as like 1,3,7,13,21. When you will know the k ,check whether s is greater than or less then from k . if( s>k) x =n and y = m -s +1 and if(s<k) then y =n and x = s-a+1 where a is smallest number for that color.
The above process is when m is odd. If m is even the process is just reverse for x & y.
Beware about range of s

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size) for(int i=0 ; i<size ; i++) cin>>array[i] ;
#define new_line pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647

int main()
{
int test ;
ll cnt =1 ;
sc("%d",&test) ;

while(test--)
{
ll s ;
cin>>s ;
ll n = ceil(sqrt(s)) ;
ll m = n*n ;
ll x ,y ;
if(m&1)
{
ll k = m -n +1 ;
if(k==s)
x=y=n ;

else if(s>k){
x = n ;
y = m -s +1 ;
}

else if(s<k){
y =n ;
ll a = m - (2*n)+2 ;
x = s- a +1 ;
}

cout<<"Case "<<cnt++<<": "<<y<<" "<<x<<endl ; }
else
{
ll k = m -n +1 ;
if(k==s)
x=y=n ;

else if(s<k){
x =n ;
ll a = m - (2*n)+ 2 ;
y = s-a+1 ;
}

else if(s>k){
y =n ;
x =m-s+1 ;
}
cout<<"Case "<<cnt++<<": "<<y<<" "<<x<<endl ;
}
}
return 0;
}

Lightoj 1174- Commandos

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size) for(int i=0 ; i<size ; i++) cin>>array[i] ;
#define new_line pf("\n")
#define highest_int 2147483647
#define n_INF -99999999

vector<int> G[10001] ;
int dis1[10001] , dis2[10001] ;
int visited[10001] ;
int src ,des ,mx;

void reset(int n)
{
for(int i=0 ; i<=n ; i++)
{
G[i].clear() ;
visited[i] =0 ;
}
}

void bfs(int n , int dis[])
{
queue<int> q ;
visited[n] =1 ;
dis[n] =0 ;
q.push(n) ;

while(!q.empty())
{
int u = q.front() ;
q.pop() ;
for(int i=0 ; i<G[u].size() ; i++)
{
int v = G[u][i] ;
if(!visited[v])
{
visited[v] =1 ;
dis[v] = dis[u] +1 ;
q.push(v) ;

}
}
}
}

int main()
{
int test , cnt =1 ;
cin>>test ;
while(test--)
{
int node , edge ;
cin>>node>>edge ;
reset(node) ;

for(int i=0 ; i<edge ; i++)
{
int u ,v ;
cin>>u>>v ;
G[u].pb(v) ;
G[v].pb(u) ;
}

cin>>src>>des ;
mx = n_INF ;
memset(visited , 0 , sizeof(visited)) ;
bfs(src,dis1) ;
//mx = n_INF ;
memset(visited , 0 , sizeof(visited)) ;
bfs(des,dis2) ;
//mx = n_INF ;
for(int i=0 ; i<node ; i++)
{
mx = max(mx , dis1[i] + dis2[i]) ;
}
pf("Case %d: %d\n",cnt++,mx) ;
}
return 0;
}

20 November 2015

Lightoj 1019-Brush (V)

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size) for(int i=0 ; i<size ; i++) cin>>array[i] ;
#define new_line pf("\n")
#define highest_int 2147483647
#define INF 2000000

struct edge
{
int u ,w ;
bool operator < (const edge & p) const
{
return w>p.w ;
}
};

vector<int> G[10001] ;
vector<int> cost[1001];
int d[10001] ;

void res (int n)
{
for(int i=1 ; i<=n ; i++)
{
G[i].clear() ;
cost[i].clear() ;
d[i] = INF ;
}
}

int dijkstra(int n)
{
priority_queue<edge> q ;
edge e ;
e.u =1 ;
e.w =0 ;
d[1] =0 ;
q.push(e) ;

while(!q.empty())
{
edge top = q.top() ;
q.pop() ;
int u = top.u ;
if(u==n)
return d[n] ;

for(int i=0 ; i<G[u].size() ; i++)
{
int v = G[u][i] ;
int dis = cost[u][i] ;
if(d[u] + dis < d[v])
{
d[v] = dis + d[u] ;
e.u = v ;
e.w = d[v] ;
q.push(e) ;
}
}
}
return -1 ;
}

int main()
{
int test ;
cin>>test ;
int cnt =1 ;

while(test--)
{
int n ,m ;
cin>>n>>m ;

res(n) ;

for(int i=1 ; i<=m ; i++)
{
int u,v,w ;
cin>>u>>v>>w ;
cost[u].pb(w) ;
cost[v].pb(w) ;
G[u].pb(v) ;
G[v].pb(u) ;
}
int x = dijkstra(n) ;
if(x==-1)
pf("Case %d: Impossible\n",cnt++) ;
else
pf("Case %d: %d\n",cnt++,x) ;

}
return 0;
}

UVA 414 - Machined Surfaces

uva 12531- Hours and Minutes

19 November 2015

uva 579 Clock Hands

18 November 2015

uva 10377 ( graph)

#include<iostream>
#include<cstdio>
#include<map>
using namespace std ;

#define pf printf

int data[1001][1001] ;
char str[1001],ch ;
int r,c ,d;
int x , y;
map<int,char> mp ;

void travers()
{
while(cin>>ch)
{
if(ch=='Q')
break ;
else if(ch=='R')
{
d-- ;
if(d<0)
d =3 ;
}
else if(ch=='L')
{
d++ ;
if(d>3)
d =0 ;
}
else if(ch=='F')
{
if(d==0)
{
if(x-1>=1 && data[x-1][y])
{
x-- ;
}
}
else if(d==2)
{
if(x+1<=r && data[x+1][y])
x++ ;
}
else if(d==1)
{
if(y-1>=1 && data[x][y-1])
y-- ;
}
else if(d==3)
{
if(y+1<=c && data[x][y+1])
y++ ;
}
}
}

}

int main()
{
int test ;
cin>>test ;
while(test--)
{
mp[0] = 'N' ;
mp[1] = 'W' ;
mp[2] = 'S' ;
mp[3] = 'E' ;
cin>>r>>c ;
getchar() ;
for(int i=1 ; i<=r ; i++)
{
gets(str) ;
for(int j=0 ; j<c ; j++)
{
if(str[j]==' ')
data[i][j+1] = 1 ;
else
data[i][j+1]=0;
}
}
d =0 ;
cin>>x>>y ;

travers() ;
pf("%d %d %c\n",x,y,mp[d]) ;
if(test)
pf("\n") ;
}
}

uva 374

#include<iostream>
#include<cmath>
using namespace std;

int BigMod(long int b, int long p, int long m){
if(p == 0){
return 1;
}
if((p % 2) == 0){
return (BigMod(b,p/2,m)*BigMod(b,p/2,m)) % m;
}
return (BigMod(b,p-1,m)*(b%m)) % m;
}

int main(){
long int b,p,m;
while(cin >> b >> p >> m){
long int result = BigMod(b,p,m);
cout << result << endl;
}
return 0;
}

17 November 2015

uva 10165

It will be easy to solve the problem if you know about the Nim game.
"Nim has been mathematically solved for any number of initial heaps and objects, and there is an easily calculated way to determine which player will win and what winning moves are open to that player. In a game that starts with heaps of three, four, and five, the first player will win with optimal play, whether the misère or normal play convention is followed." - Wikipedia

The operation which is needed is XOR ( ^ ).

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size) for(int i=0 ; i<size ; i++) cin>>array[i] ;
#define new_line pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647

int main()
{
int n ;
while(sc("%d",&n)==1 && n)
{
int l=0 ;
int m ;
for(int i=0 ;i<n ;i++)
{
sc("%d",&m) ;
l = l^m ;
}
if(l!=0)
pf("Yes\n") ;
else
pf("No\n") ;

}

return 0;
}

uva 847

16 November 2015

uva 441

uva 113

#include<iostream>
#include<stdio.h>
#include<cmath>

using namespace std ;
int main()
{
double p,n ;

while(scanf("%lf %lf",&n,&p)==2)
{
double j = pow(p,1/n) ;
printf("%.0lf\n",j) ;
}
return 0 ;
}

uva 263

/***
Md. Namzul Hasan
Shahjalal University of Science & technology,sylhet.
hasan08sust@gmail.com
verdict: accepted
***/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<queue>
#include<algorithm>
#include<vector>
#include<cmath>
#include<cctype>
#include<sstream>
#include<stdlib.h>
#include<map>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))

string data ,niloy ;
queue <char> jak , nam;
char jaki[100000] ;
in t, m ,k, len, ln ;
char ch , j ;
ll n, x1, x2, mx= -1 , cnt ;
in cont1[11] , cont2[11] ;

void change()
{
MEM(cont1, 0);
MEM(cont2, 0);
while(n)
{
cont1[n%10]++ ;
cont2[n%10]++ ;
n = n/10 ;
}
x1 =x2 = 0 ;
for(in i=0 ; i<10 ; i++)
{
while(cont1[i]--)
{
x1 = (x1*10) + i ;
}
}
for(in i=9 ; i>=0 ; i--)
{
while(cont2[i]--)
{
x2 = (x2*10) + i ;
}
}
}

map<ll,in> ml ;
in main()
{
while(cin>>n && n)
{
pf("Original number was %lld\n",n) ;
ml.clear() ;
while(1)
{
change() ;
pf("%lld - %lld = %lld\n",x2,x1,x2-x1) ;
n = x2 -x1 ;
if (ml.count(n)) break;
ml[n] = 1;

}
printf("Chain length %d\n\n", ml.size() + 1);
}
return 0 ;
}

uva 11074

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size) for(int i=0 ; i<size ; i++) cin>>array[i] ;
#define new_line pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647

int main()
{
int cnt =1 ;
int s,t,n ;
while(sc("%d %d %d",&s,&t,&n)&&s &&t &&n)
{
pf("Case %d:\n",cnt++) ;
int g = (t*(n+1)) + (s*n) ;
for(int i=1 ; i<=t ; i++)
{
for(int j=1 ; j<=g ; j++)
pf("*") ;
pf("\n") ;
}

for(int i=1 ; i<=n ; i++)
{
int cnt1 =0 , cnt2 =0 ;

for(int j=1 ; j<=s ; j++)
{
int l =1 ;
for(int k =1 ; k<=g ; k++)
{
if(l==1)
{
pf("*") ;
cnt1++ ;
if(cnt1==t)
{
cnt1 =0 ;
l=0 ;
}
}
else if(l==0)
{
pf(".") ;
cnt2++ ;
if(cnt2==s)
{
cnt2=0 ;
l= 1 ;
}
}
}
pf("\n") ;
}

for(int a=1 ; a<=t ; a++)
{
for(int b=1 ; b<=g ; b++)
pf("*") ;
pf("\n") ;
}
}
pf("\n") ;
}
return 0;
}

uva 10776

/***
Md. Namzul Hasan
Shahjalal University of Science & Technology,Sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define load(array,size) for(int i=0 ; i<size ; i++) cin>>array[i] ;
#define new_line pf("\n")
#define clear_data(array) memset(array,0,sizeof(array))
#define highest_int 2147483647

string result ;
string str ;
int n ;
map<string,int> mp ;
int taken[40] = {0} ;

void backtrack(int pos)
{
if(result.size()==n)
{
if(!mp[result])
{
mp[result] =1 ;
cout<<result<<endl ;
}
}

for(int i =pos ; i<str.size() ; i++)
{
if(taken[i]==0)
{
if(!result.empty() && str[i]<result[result.size()-1])
continue ;

taken[i] =1 ;
result.pb(str[i]) ;
backtrack(i+1) ;
taken[i] =0 ;
result.erase(result.size()-1) ;
while(str[i]==str[i+1])
i++ ;
}

}
}
int main()
{
while(cin>>str>>n)
{
int ln =str.size() ;
sort(str.begin(),str.end()) ;
mp.clear() ;
memset(taken,0,sizeof(taken)) ;

backtrack(0) ;
}
}

uva 11059

04 November 2015

uva 11831 (DFS)

/***
Md. Namzul Hasan
Shahjalal University of Science & technology,sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define new_line pf("\n")

int row , col , n ;
char str[1001][1001] ;
char ins[50001],ch ;
int d,cnt ;

void travers(int x, int y)
{
cnt =0 ;
for(int i=0 ; i<n ; i++)
{
ch = ins[i] ;
if(ch=='F')
{
if(d==0) x-- ;
else if(d==1) y-- ;
else if(d==2) x++ ;
else if(d==3) y++ ;
if(str[x][y]=='#' || x<0 || x>=row || y<0 || y>=col)
{

if(d==0) x++ ;
else if(d==1) y++ ;
else if(d==2) x-- ;
else if(d==3) y-- ;
}
else if(str[x][y]=='*')
{
cnt++ ;
str[x][y] ='.' ;
}
}
else if(ch=='D')
{
d-- ;
if(d<0)
d= 3 ;
}
else if(ch=='E')
{
d++ ;
if(d>3)
d =0 ;
}

}
pf("%d\n",cnt) ;
}

int main()
{
int x, y ;
while(cin>>row>>col>>n &&row && col &&n)
{
getchar() ;
for(int i=0 ; i<row ; i++)
gets(str[i]) ;
for(int i=0 ; i<row ; i++)
{
for(int j=0 ; j<col ; j++)
{
if(str[i][j]=='N')
{
d=0 ;
x =i ;
y = j ;
break ;
}
else if(str[i][j]=='O')
{
d=1 ;
x =i ;
y = j ;
break ;
}
else if(str[i][j]=='S')
{
d=2 ;
x =i ;
y = j ;
break ;
}
else if(str[i][j]=='L')
{
d=3 ;
x =i ;
y = j ;
break ;
}
}
}
gets(ins) ;
travers(x,y) ;
}
return 0;
}

uva 10116

/***
Md. Namzul Hasan
Shahjalal University of Science & technology,sylhet.
hasan08sust@gmail.com
***/
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define new_line pf("\n")

int r ,c, n ;
char str[1001][1001],ch ;
int a,b ,l ;
int mat[1001][1001],k ;

void move_robot()
{
ch = str[a][b] ;
if(ch=='N') a-- ;
else if(ch=='W') b-- ;
else if(ch=='S') a++ ;
else if(ch=='E') b++ ;
}

int main()
{
while(cin>>r>>c>>n && r &&c &&n)
{
getchar() ;
l=0 ;
memset(mat,0 ,sizeof(mat)) ;

for(int i=0 ; i<r ; i++)
cin>>str[i] ;
b = n-1 ;
a =0 ;
mat[a][b] =1 ;
for( k=2 ; ; k++)
{
move_robot() ;
if(a<0 || a>=r || b<0 || b>=c)
{
l=1 ;
break ;
}
if(mat[a][b])
break ;
mat[a][b] = k ;
}
if(l==1)
{
pf("%d step(s) to exit\n",k-1) ;
}
else
pf("%d step(s) before a loop of %d step(s)\n",mat[a][b]-1 , k-mat[a][b]) ;

}
return 0;
}

uva 280 (BFS)

/***
Md. Namzul Hasan
Shahjalal University of Science & technology,sylhet.
hasan08sust@gmail.com
verdict: accepted
***/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<queue>
#include<algorithm>
#include<vector>
#include<cmath>
#include<cctype>
#include<sstream>
#include<stdlib.h>
#include<map>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))

vector<in>G[1001] ;
queue<in>q ;
in node , visited[1001] , level[1001],cnt,data[1001];
in a,b ,src,v, u ,test , m;

void BFS()
{
src = m-1 ;
q.push(src) ;
//visited[src] =1 ;
while(!q.empty())
{
u = q.front() ;
q.pop() ;
for(in j=0 ; j<G[u].size() ; j++)
{
v = G[u][j] ;
if(!visited[v])
{
visited[v] =1 ;
q.push(v) ;
}
}
}

cnt =0 ;
for(in k=0 ; k<node ; k++)
{
if(!visited[k])
cnt++ ;
}
pf("%d",cnt) ;
for(in k=0 ; k<node ; k++)
{
if(!visited[k])
pf(" %d",k+1) ;
}
pf("\n") ;
}

int main()
{
while(cin>>node && node)
{
for(in i=0 ; i<=node ; i++)
G[i].clear() ;

while(cin>>a && a)
{
while(cin>>b &&b)
{
G[a-1].push_back(b-1) ;
}
}

cin>>test ;
for(in i=0 ; i<test ; i++)
{
cin>>m ;
memset(visited , 0 , sizeof(visited)) ;
BFS() ;
}
}
return 0 ;
}

02 November 2015

uva 382

#include<iostream>
#include<stdio.h>
using namespace std ;
int main()
{
long int test ;
int x=0 ;
while(cin>>test)
{
if(test==0)
break ;
if(x!=1)
printf("PERFECTION OUTPUT\n");
x=1;
int a=0 ;
for(int i=1 ; i<=test/2 ; i++)
{
if(test%i==0)
a =a+i ;
}
if(a==test)
printf("%5d PERFECT\n",test) ;
else if(a<test)
printf("%5d DEFICIENT\n",test) ;
else if(a>test)
printf("%5d ABUNDANT\n",test) ;
}
printf("END OF OUTPUT\n") ;
return 0 ;
}

uva 371

/***
Md. Namzul Hasan
Shahjalal University of Sciency & technology,sylhet.
hasan08sust@gmail.com
verdict:
***/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<queue>
#include<algorithm>
#include<vector>
#include<cmath>
#include<sstream>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
int main()
{
vector<in> jak ;
ll m, n,i,k,p,v,count ;
while(cin>>m>>n && m&& n)
{
if(m>n)
swap(m,n) ;
p =0 ;
for(i =m ; i<=n;i++)
{
k = i ;
count =0 ;
while(1)
{
if(k%2!=0)
k = (3*k)+1 ;
else
k = k/2 ;
count++ ;
if(k==1)
break ;
}
if(p<count)
{
p = count ;
v = i ;
}
}
pf("Between %lld and %lld, %lld generates the longest sequence of %lld values.\n",m,n,v,p) ;
}
return 0 ;
}

uva 369

/***
Md. Namzul Hasan
Shahjalal University of Science & technology,sylhet.
hasan08sust@gmail.com
verdict: accepted
***/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<queue>
#include<algorithm>
#include<vector>
#include<cmath>
#include<cctype>
#include<sstream>
#include<stdlib.h>
#include<map>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
#define MEM(x,y) (memset((x),(y),sizeof(x)))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAX(x,y) ((x) > (y) ? (x) : (y))

long long nCr(long long n, long long r)
{
long long i,res=1;
if(n-r<r)
{
r=n-r;
}
for(i=1; i<=r; i++,n--)
{
res =(res*n)/i;

}
return res;
}

int main()
{
long long n,r,ans;
while(2==scanf("%lld%lld",&n,&r))
{
ans=1;
if(n==0 && r==0)
{
break;
}
ans=nCr(n,r);
printf("%lld things taken %lld at a time is %lld exactly.\n",n,r,ans);
}
return 0;
}

uva 272

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std ;
int main()
{
char ch ;
int count = 1 ;
while(scanf("%c",&ch)==1)
{
if(ch=='"')
{
if(count%2!=0)
{
printf("``") ;

}
else if(count%2==0)
{
printf("''") ;

}
count++ ;
}
else
printf("%c",ch) ;
}
return 0 ;
}

uva 264

/***
Md. Namzul Hasan
Shahjalal University of Sciency & technology,sylhet.
hasan08sust@gmail.com
verdict: accepted
***/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<queue>
#include<algorithm>
#include<vector>
#include<cmath>
#include<sstream>
using namespace std ;
typedef long long ll ;
typedef int in ;
typedef unsigned long long ull ;
const double pi = 2*acos(0) ;
#define maxi 40000
#define pf printf
#define sc scanf
#define pb push_back
int main()
{
in n ;
while(cin>>n)
{
in a=1 , b=1 , l=1 , m=0;
in count =1 ;
if(n==1)
{
pf("TERM %d IS %d/%d\n",n,a,b) ;
continue ;
}
while(1)
{
if(l==1)
{
b++ ;
l =0 ;
count++ ;
if(count==n)
{
m=1 ;
break ;
}

for(in i =1 ; ; i++)
{
a++ ;
b-- ;
// pf("%d /%d- ",a,b) ;
count++ ;
if(count==n)
{
m=1 ;
break ;
}
else if(b==1)
break ;
}
//cout<<endl ;
}
else if(l==0)
{
a++ ;
// pf("%d /%d ",a,b) ;
l=1 ;
count++ ;
if(count==n)
{
m=1 ;
break ;
}
for(in i=1 ;; i++)
{
a-- ;
b++ ;
// pf("%d /%d ",a,b) ;
count++ ;
if(count==n)
{
m=1 ;
break ;
}
else if(a==1)
break ;
}
//cout<<endl ;
}
if(m==1)
break ;
}
pf("TERM %d IS %d/%d\n",n,a,b) ;
}
return 0 ;
}