UVA 571 Jugs

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("%lld %lld",&a,&b)
#define sf3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("%lld %lld",a,b)
#define pf3(a,b,c) printf("%lld %lld %lld",a,b,c)
#define nl printf("\n")
#define   timesave              ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define pb push_back
#define MPI map<int,int>mp;
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
/*primes in range 1 - n
1 - 100(1e2) -> 25 pimes
1 - 1000(1e3) -> 168 primes
1 - 10000(1e4) -> 1229 primes
1 - 100000(1e5) -> 9592 primes
1 - 1000000(1e6) -> 78498 primes
1 - 10000000(1e7) -> 664579 primes
large primes ->
104729 1299709 15485863 179424673 2147483647 32416190071 112272535095293 48112959837082048697
*/
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
//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
long pre[1005][1005][4],vis[1005][1005];
struct NODE
{
    long a,b;
};
NODE node,node1;
queue<NODE>q;
long ca,cb,n,k;
void call(long num)
{
    if(vis[node1.a][node1.b]==0)
    {
        vis[node1.a][node1.b]=1;
        pre[node1.a][node1.b][0]=num;
        pre[node1.a][node1.b][1]=node.a;
        pre[node1.a][node1.b][2]=node.b;
        q.push(node1);
    }
}
void print(long aa,long bb)
{
    if(aa==0&&bb==0)
        return;
    print(pre[aa][bb][1],pre[aa][bb][2]);
    k=pre[aa][bb][0];
    if(k==1)
    {
        cout<<"fill A"<<endl;
    }
    else if(k==2)
    {
        cout<<"fill B"<<endl;
    }
    else if(k==3)
    {
        cout<<"empty A"<<endl;
    }
    else if(k==4)
    {
        cout<<"empty B"<<endl;
    }
    else if(k==5)
    {
        cout<<"pour A B"<<endl;
    }
    else if(k==6)
    {
        cout<<"pour B A"<<endl;
    }
}
main()
{
    timesave;
    while(cin>>ca>>cb>>n)
    {
        memset(vis,0,sizeof(vis));
        node.a=0;
        node.b=0;
        vis[0][0]=1;
        q.push(node);
        while(!q.empty())
        {
            node=q.front();
            q.pop();
            if(node.b==n)
                break;
            node1.a=ca;
            node1.b=node.b;
            call(1);
            node1.a=node.a;
            node1.b=cb;
            call(2);
            node1.a=0;
            node1.b=node.b;
            call(3);
            node1.a=node.a;
            node1.b=0;
            call(4);
            k=min(cb-node.b,node.a);
            node1.a=node.a-k;
            node1.b=node.b+k;
            call(5);
            k=min(ca-node.a,node.b);
            node1.a=node.a+k;
            node1.b=node.b-k;
            call(6);
        }
        print(node.a,node.b);
        cout<<"success"<<endl;
        while(!q.empty())
            q.pop();
    }
}

Maximum length of the longest street in the city by using BFS

How to find maximum  length of the longest street in the city by using BFS

Problem link:  https://www.spoj.com/problems/BENEFACT/

Input:
1
6
1 2 3
2 3 4
2 6 2
6 4 6
6 5 5

Output:
12

Explanation:
6+2+4=12
At first start bfs from 1 and find the longest city from 1
And again start with bfs from this longest city and find the longest length
So we need two bfs search.

1st Code:

///...................SUBHASHIS MOLLICK...................///
///.....DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING....///
///.............ISLAMIC UNIVERSITY,BANGLADESH.............///
///....................SESSION-(14-15)....................///
#include<bits/stdc++.h>
using namespace std;
#define sf(a) scanf("%lld",&a)
#define sf2(a,b) scanf("lld%lld",&a,&b)
#define sf3(a,b,c) scanf("lld%lld%lld",&a,&b,&c)
#define pf(a) printf("%lld",a)
#define pf2(a,b) printf("lld%lld",a,b)
#define pf3(a,b,c) printf("lld%lld%lld",a,b,c)
#define nl printf("\n")
#define ll long long
#define pb push_back
#define MPI map<int,int>mp
#define fr(i,n) for(i=0;i<n;i++)
#define fr1(i,n) for(i=1;i<=n;i++)
#define frl(i,a,b) for(i=a;i<=b;i++)
//freopen("Input.txt","r",stdin);
//freopen("Output.txt","w",stdout);
vector<long>vec[50005],cost[50005];
long vis[50005];
long bfs(long source)
{
    queue<long>q;
    memset(vis,0,sizeof(vis));
    long dist[50005]= {0},boroman=0,mx=0;
    dist[source]=0;
    vis[50005]=1;
    q.push(source);
    long i;
    while(!q.empty())
    {
        long u=q.front();
        if(mx<dist[u])
        {
            mx=dist[u];
            boroman=u;
        }
        for(i=0; i<vec[u].size(); i++)
        {
            long v=vec[u][i];
            if(vis[v]==0)
            {
                dist[v]=dist[u]+cost[u][i];
                vis[v]=1;
                q.push(v);
            }
        }
        q.pop();
    }
    return boroman;
}
long bfss(long source)
{
    memset(vis,0,sizeof(vis));
    queue<long>q;
    long dist[50005]= {0},i,mx=0;
    q.push(source);
    vis[source]=1;
    dist[source]=0;
    while(!q.empty())
    {
        long u=q.front();
        vis[u]=1;
        if(mx<dist[u])
        {
            mx=dist[u];
        }
        for(i=0; i<vec[u].size(); i++)
        {
            long v=vec[u][i];
            if(vis[v]==0)
            {
                dist[v]=dist[u]+cost[u][i];
                // mx=max(mx,dist[v]);
                vis[v]=1;
                q.push(v);
            }
        }
        q.pop();
    }
    return mx;
}
main()
{
    long ts;
    cin>>ts;
    while(ts--)
    {
        long n,u,v,d,i;
        cin>>n;
        for(i=1; i<n; i++)
        {
            cin>>u>>v>>d;
            vec[u].push_back(v);
            vec[v].push_back(u);
            cost[u].push_back(d);
            cost[v].push_back(d);
        }
        long boro=bfs(1);
        cout<<bfss(boro)<<endl;
        for(i=0; i<=50005; i++)
        {
            vec[i].clear();
            cost[i].clear();
            vis[i]=0;
        }
    }

}

2nd Code:

#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<cctype>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#include<sstream>
using namespace std;
#define pb push_back
#define pi 3.141592653589793238462643383

int dist[50001];
int visited[50001];
int n;
struct node
{
    int i,d;
};
typedef struct node node;
vector<node> v[50001];
int bfs(int start){
    queue<int> q;
    q.push(start);
    int i,j;
    for(i=0;i<=n;i++){
        visited[i]=0;
        dist[i]=0;
    }
    visited[start]=1;
    while(!q.empty()){
        int temp = q.front();
        q.pop();
        for(i=0;i<v[temp].size();i++){
            if(visited[v[temp][i].i]==0){
                visited[v[temp][i].i]=1;
                dist[v[temp][i].i]+=dist[temp]+v[temp][i].d;
                q.push(v[temp][i].i);
            }
        }
    }
    return int(max_element(dist+1,dist+n+1)-dist);
}
int main()
{
 int i,j,t,u1,v1,d;
 node temp;
 scanf("%d",&t);
 while(t>0){
        scanf("%d",&n);
        for(i=1;i<=n;i++)
            v[i].clear();
        for(i=1;i<=n-1;i++){
                scanf("%d%d%d",&u1,&v1,&d);
                temp.i =  v1;
                temp.d = d;
                v[u1].pb(temp);
                temp.i = u1;
                v[v1].pb(temp);
        }
        int start = bfs(1);
        cout<<start<<endl;
        int ans = bfs(start);
        printf("%d\n",dist[ans]);
        t--;
    }
}

UVA 11988 - Broken Keyboard

#include <cstdio>
#include <list>
#include <cstring>
using namespace std;
int main()
{
    char line[100001];
    while (scanf("%s", line) != EOF)
    {
        list<char> l;
        int len = strlen(line);
        list<char>::iterator it = l.begin();
        for (int i = 0; i < len; i++)
        {
            if (line[i] == '[')
            {
                it = l.begin();
            }
            else if (line[i] == ']')
            {
                it = l.end();
            }
            else
            {
                l.insert(it, line[i]);
            }   
        }
        for (it = l.begin(); it != l.end(); it++)
        {
            printf("%c", *it);
        }
        printf("\n");
    }
    return 0;
}

Find the number of continuous sequence of numbers such that their sum is zero.

Find the number of continuous sequence of numbers such that their sum is zero.

For example if the sequence is- 5, 2, -2, 5, -5, 9

There are 3 such sequences

2, -2= (2+-2)=0

5, -5=(5+-5)=0

2, -2, 5, -5=(2+-2+5+-5)=0

so ans is 3;

Problem link:   https://www.spoj.com/problems/CRAN02/\

Hints:

At first we need to comulative sum of the array then sort the sum array and find a pair of same digit.then calculate n*(n+1)/2 and add with result;

Example: 5,2,-2,5,-5,9

Commulative sum array={5,7,5,10,5,14} and add 0 in position 0

So the array is={0,5,7,5,10,5,14} now sort the array.

So the array is={0,5,5,5,7,10,14}

the find pair of same digit 1st pair is 5,5 and 2nd is 5,5 so 2 pairs and (2*(2+1))/2; so the result is (2*3)/2=3

Source Code:

#include<stdio.h>

#include<stdlib.h>

#include<algorithm>

#include<bits/stdc++.h>

using namespace std;

unsigned long long int a[10000100]= {0},b[10000100]= {0},c[10000100]= {0};

int main()

{

    unsigned long long int i,j,k,l=0,n,m,sum=0,r,sum1=0,p,t;

    scanf("%llu",&n);

    for(i=0; i<n; i++)

    {

        scanf("%llu",&m);

        sum=0;

        sum1=0;

        for(j=0; j<m; j++)

        {

            scanf("%llu",&a[j]);

            sum=sum+a[j];

            b[j+1]=sum;

        }

        sort(b,b+m+1);

        l=0;

        for(p=0; p<m; p++)

        {

            if(b[p]==b[p+1])

            {

                c[l]++;

            }

            else

            {

                l++;

            }

        }

        for(r=0; r<=l; r++)

        {

            sum1=sum1+(c[r]*(c[r]+1)/2);

        }

        memset(c,0,sizeof(c));

        printf("%llu\n",sum1);

    }

    return 0;

}

Big numbers multiplication mod by big number (10000000000007)

#include<bits/stdc++.h>
#define clr(x)      memset(x,0,sizeof(x))
#define fr(i,x)     for(long long i=0;i<x;i++)
#define ll          long long
#define pi          3.14159265358979323846
using namespace std;

long long bigmul ( long long a, long long b, long long c ) {
    if ( b == 0 ) return 0;
    if ( b & 1 ) {
        return ( a + bigmul ( a, b - 1, c ) ) % c;
    }
    else {
        return ( 2 * bigmul ( a, b / 2, c ) ) % c;
    }
}

int main()
{
    ll a,b;
    ll m=10000000000007;
    while(cin>>a>>b)
    {
        ll x1=bigmul(a,b,m);
        cout<<"X = "<<x1<<endl;
    }
    return 0;
}