#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 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;
int main()
{
//CIN;
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
string s;
while(cin>>s && s!="#")
{
if(next_permutation(all(s))) cout<<s<<endl;
else cout<<"No Successor"<<endl;
}
return 0;
}
Category UVa
UVa – 540 – Team Queue
#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 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 for0(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define forrev(i,n) for(int i=n-1; i>=0; i--)
#define forab(i,a,b) for(int i=a;i<=b;i++)
#define forba(i,b,a) for(int i=b;i>=a;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 acos(-1) //3.14159265358979323846264338328
#define valid(tx,ty) tx>=0 && tx<row && ty>=0 && ty<col
#define intlim 2147483648
#define MAX 100005
#define inf 100000008
/*------------------------------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;
deque<int> dq;
int ar[1000000];
int main()
{
//CIN;
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int n,k=0;
while(sf(n)==1 && n!=0)
{
k++;
for1(i,n)
{
int x,y;
sf(x);
for1(j,x)
{
sf(y);
ar[y]=i;
}
}
string s;
cout<<"Scenario #"<<k<<endl;
while(cin>>s && s!="STOP")
{
if(s=="ENQUEUE")
{
sf(n);
if(ar[n])
{
int c=0;
forrev(i,sz(dq))
{
if(ar[dq[i]]==ar[n])
{
dq.insert(dq.begin()+i+1,n);
c=1;
break;
}
}
if(!c) dq.pb(n);
}
else dq.pb(n);
}
else if(s=="DEQUEUE")
{
cout<<dq.front()<<endl;
dq.pop_front();
}
}
cout<<endl;
dq.clear();
ms(ar,0);
}
return 0;
}
SPOJ – PT07Y – Is it a tree
An undirected/directed graph is a tree if anyone know that any two of the following three properties are true:
1. It is connected
2. There are n – 1 edges, where n is the number of nodes
3. There are no cycles
It is better to check if all these three conditions are true, then that graph is surely a tree.
This problem also can be solved with BFS, but I used DFS because of smaller size of code n more simplyness than BFS.
Here, the source is not given so I have assumed the 1st node of the 1st given edge to be the source with the help of a variable x, you can assume any of the node.
#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 loopn(i,n) for(int i=1;i<n;i++)
#define loop1(i,n) for(int i=1;i<=n;i++)
#define loopi(i,n) for(int i=0;i<n-1;i++)
#define loopab(i,a,b) for(int i=a;i<=b;i++)
#define loopba(i,b,a) for(int i=b;i>=a;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<row && ty>=0 && ty<col
#define intlim 2147483648
#define MAX 1000000
#define inf 100000000
/*------------------------------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;
vector<int>g[MAX+1];
bool visited[MAX+1];
int c,d;
void dfs(int u)
{
visited[u]=1;
for(int i=0; i<g[u].size(); i++)
{
int v=g[u][i];
if(visited[v]) //Checking cycle/loop
{
d=1;
break;
}
else
{
c++; // Checking connected
dfs(v);
}
}
}
int main()
{
CIN;
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int node,edge;
cin>>node>>edge;
int x=0,src;
for(int i=0; i<edge; i++)
{
int from,to;
cin>>from>>to;
if(x==0) src=from;
x=1;
g[from].push_back(to);
}
c=1; // Either the graph is connected or not(Either each vertex is visited once or not)
d=0; // For checking cycle/loop
visited[src]=1;
dfs(src);
if(!d && c==node && edge==node-1) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
return 0;
}
UVa – 429 – Word Transformation
In this problem, since there is no mention of limit of input in a particular test case, so we have assumed the empty string to be the termination. That’s why we have used getline() for taking input instead of cin. Otherwise there is no way of returning to another test case taking only string by cin.
#include <bits/stdc++.h>
#define ms(a,b) memset(a,b,sizeof(a))
#define pb(a) push_back(a)
#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 loop0(i,n) for(int i=0;i<n;i++)
#define loop1(i,n) for(int i=1;i<=n;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 case(z,x) cout<<"Case "<<i<<": "<<x<<endl
#define case(z) cout<<"Case "<<z<<": "
#define PI 3.14159265358979323846264338328
#define valid(tx,ty) tx>=0 && tx<r && ty>=0 && ty<c
#define MAX 2000
/*----------------------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<string,vector<string>> mp;
bool check(string a, string b)
{
int cnt=0;
if(sz(a)!=sz(b)) return 0;
else
{
loop0(i,sz(a))
{
if(a[i]!=b[i]) cnt++;
if(cnt>1) return 0;
}
}
return cnt==1;
}
int bfs(string src, string dst)
{
map<string,int>dis;
map<string,bool>visited;
queue<string>Q;
Q.push(src);
dis[src]=0;
visited[src]=1;
while(!Q.empty())
{
string u=Q.front();
Q.pop();
if(u==dst) return dis[u];
loop0(i,sz(mp[u]))
{
string v=mp[u][i];
if(!visited[v])
{
dis[v]=dis[u]+1;
visited[v]=1;
Q.push(v);
}
}
}
}
int main()
{
// CIN;
// freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int t;
cin>>t;
for(int z=1; z<=t; z++)
{
string str;
vector<string>v;
while(cin>>str && str!="*") v.pb(str);
loop0(i,sz(v))
{
for(int j=i+1; j<sz(v); j++)
if(check(v[i],v[j]))
{
mp[v[i]].pb(v[j]);
mp[v[j]].pb(v[i]);
}
}
getchar();
string s1;
while(1)
{
getline(cin,s1);
if(s1=="") break;
bool x=0;
string s3,s4;
loop0(i,sz(s1))
{
if(s1[i]==' ')
{
x=1;
continue;
}
if(!x)
s3+=s1[i];
else
s4+=s1[i];
}
cout<<s3<<" "<<s4<<" "<<bfs(s3,s4)<<endl;
}
if(z!=t) cout<<endl;
mp.clear();
}
return 0;
}
UVa – 10008 – What’s Cryptanalysis
#include <bits/stdc++.h>
#define ms(a,b) memset(a,b,sizeof(a))
#define pb(a) push_back(a)
#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 loop0(i,n) for(int i=0;i<n;i++)
#define loop1(i,n) for(int i=1;i<=n;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 case(z,x) cout<<"Case "<<i<<": "<<x<<endl
#define case(z) cout<<"Case "<<z<<": "
#define PI 3.14159265358979323846264338328
#define valid(tx,ty) tx>=0 && tx<r && ty>=0 && ty<c
#define MAX 2000
/*----------------------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;
vector<pair<char,int> > v;
bool comp(pair<char,int> a,pair<char,int> b)
{
if(a.ss>b.ss) return 1;
else if(a.ss==b.ss)
{
if(a.ff<b.ff) return 1;
else return 0;
}
else return 0;
}
int main()
{
//CIN;
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int n;
cin>>n;
getchar();
loop0(i,n)
{
string s;
getline(cin,s);
char ch;
loop0(j,sz(s))
{
if((s[j]>='A' && s[j]<='Z') || (s[j]>='a' && s[j]<='z'))
{
ch=toupper(s[j]);
mp[ch]++;
}
}
}
stlloop(mp) v.pb(make_pair(it->ff,it->ss));
sort(all(v),comp);
loop0(i,sz(v)) cout<<v[i].ff<<" "<<v[i].ss<<endl;
return 0;
}
Fall out, Codes! 