UVA 383 - Shipping Routes - Solution

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
class Graph{
    int V;
    list<int>*adj;
public:
    Graph(int V);
    ~Graph();
    void addEdge(int u, int v);
    int BFS(int s,int dest);
};
Graph::Graph(int V) //construtor
{
    this->V=V;
    adj=new list<int >[V];
}
Graph::~Graph() //destructor
{
    delete []adj;
}
void Graph::addEdge(int u,int v)
{
    adj[u].pb(v);
}
int Graph::BFS(int s,int dest)
{
    bool visited[V];
    int level[V];
    memset(visited,false,sizeof(visited));
    list<int>q;
    list<int>::iterator i;
    q.pb(s);
    visited[s]=true;
    level[s]=0;
    while (!q.empty())
    {
        s=q.front();
        q.pop_front();
        for (i=adj[s].begin();i!=adj[s].end();++i)
        {
            if (!visited[*i])
            {
                q.pb(*i);
                visited[*i]=true;
                level[*i]=level[s]+1;
                if (*i==dest) return level[*i];
            }
        }
    }
    return -1;
}
int main()
{
    int tc,c=1;
    scanf("%d",&tc);
    printf("SHIPPING ROUTES OUTPUT\n");
    while (tc--)
    {
        printf("\nDATA SET  %d\n\n",c++);
        int m,n,p;
        scanf("%d%d%d",&m,&n,&p);
        Graph g(m);
        map<string,int>mp;
        string s,s1;
        getchar();
        for (int i=0;i<m;i++)
        {
            cin>>s;
            mp[s]=i;
        }
        while (n--)
        {
            cin>>s>>s1;
            g.addEdge(mp[s],mp[s1]);
            g.addEdge(mp[s1],mp[s]);
        }
        
        while (p--)
        {
            int a;
            scanf("%d\n",&a);
            cin>>s>>s1;
            int l=g.BFS(mp[s],mp[s1]);
            if (l==-1) printf("NO SHIPMENT POSSIBLE\n");
            else printf("$%d\n",a*l*100);
        }
    }
    printf("\nEND OF OUTPUT\n");
    return 0;
}

Read More

UVA 10299 - Relatives Solution

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

int phi(int n)
{
    int res=n;
    for (int i=2;i*i<=n;i++)
    {
        if (n%i==0)
        {
            while (n%i==0) n/=i;
            res-=res/i;
        }
    }
    if (n>1) res-=res/n;
    return res;
}
int main ()
{
    int n;
    while (scanf("%d",&n)==1)
    {
        if (n==0) return 0;
        if (n==1) printf("0\n");
        else printf("%d\n",phi(n));
    }

    return 0;
}

Read More

Codeforces 697A - Pineapple Incident

#include<cstdio>
#include<cmath>
using namespace std;
int main()
{
    int t,s,x;
    scanf("%d%d%d",&t,&s,&x);
    if (x>=t &&( (x-t)%s==0 || (x-t-1!=0 && (x-t-1)%s==0))) printf("YES\n");
    else printf("NO\n");
    return 0;
}

Read More

Codeforces 689A - Mike and Cellphone

#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
    int n,l,r,u,d;
    l=r=u=d=0;
    scanf("%d",&n);
    getchar();
    char s[11];
    scanf("%s",s);
    for (int i=0;i<n;i++){
        int a=s[i]-'0';
        if (a==1 || a==4||a==7||a==0) l=1;
        if (a==3 || a==6||a==9||a==0) r=1;
        if (a==1 || a==2||a==3) u=1;
        if (a==7 || a==0||a==9) d=1;
    }
    if (l && r && u && d) printf("YES\n");
    else printf("NO\n");
    return 0;
}

Read More

Codeforces 688B - Lovely Palindromes

#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
    char s[100005];
    gets(s);
    printf("%s",s);
    for (int i=strlen(s)-1;i>-1;i--) printf("%c",s[i]);
    printf("\n");
    return 0;
}

Read More

Codeforces 698A - Vacations

#include<cstdio>
using namespace std;
int main()
{
    int n;
    scanf("%d",&n);
    int a[n];
    for (int i=0;i<n;i++)
        scanf("%d",&a[i]);
    int rest=0;
    int p=0;
    for (int i=0;i<n;i++)
    {
        if (a[i]==0){
            rest++;
            p=0;
        }
        else if (!p){
            p=a[i];
        }
        else if (p==3){
                p=a[i];
        }
        else if(p==2 && a[i]!=2 ){
            p=1;
        }
        else if(p==2 && a[i]==2 ){
            p=0;
            rest++;
        }
        else if(p==1 && a[i]!=1 ){
            p=2;
        }
        else if(p==1 && a[i]==1 ){
            p=0;
            rest++;
        }
    }
    printf("%d\n",rest);

    return 0;
}

Read More

Codeforces : 702A - Maximum Increase

#include<cstdio>
using namespace std;
int main()
{
    int n;
    scanf("%d",&n);
    int a[n];
    for (int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    int max=1,cur=1;
    for (int i=1;i<n;i++){
        if (a[i]>a[i-1]){
            cur++;
        }
        else{
            if (max<cur) max=cur;
            cur=1;
        }
    }
    if (max<cur) max=cur;
    printf("%d\n",max);
    return 0;
}

Read More