UVA 706 LC-Display

#include<iostream>
#include<string>
#include<cstring>
#include<sstream>
#include<cctype>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<stack>
#include<fstream>
#include<cstdlib>
#include<iomanip>
#include<vector>
#include<map>
#include<set>
using namespace std;

char a[1000][1000];

void one(int s, int pos)
{
    int m,i,j,x,y,p,q;
    x=s+2;
    y=2*s+3;
    m=(y+1)/2;
    p=(x*(pos-1))+pos;
    q=p+x-1;
    for(i=2; i<y; i++)
        if(i!=m)
            a[i][q]='|';
}
void two(int s, int pos)
{
    int m,i,j,x,y,p,q;
    x=s+2;
    y=2*s+3;
    m=(y+1)/2;
    p=(x*(pos-1))+pos;
    q=p+x-1;
    for(i=2; i<m; i++)
        a[i][q]='|';
    for(i=m+1; i<y; i++)
        a[i][p]='|';
    for(j=p+1; j<q; j++)
    {
        a[1][j]='-';
        a[m][j]='-';
        a[y][j]='-';
    }
}
void three(int s, int pos)
{
    int m,i,j,x,y,p,q;
    x=s+2;
    y=2*s+3;
    m=(y+1)/2;
    p=(x*(pos-1))+pos;
    q=p+x-1;
    for(i=2; i<y; i++)
        if(i!=m)
            a[i][q]='|';
    for(j=p+1; j<q; j++)
    {
        a[1][j]='-';
        a[m][j]='-';
        a[y][j]='-';
    }
}
void four(int s, int pos)
{
    int m,i,j,x,y,p,q;
    x=s+2;
    y=2*s+3;
    m=(y+1)/2;
    p=(x*(pos-1))+pos;
    q=p+x-1;
    for(i=2; i<m; i++)
        a[i][p]='|';
    for(i=2; i<y; i++)
        if(i!=m)
            a[i][q]='|';
    for(j=p+1; j<q; j++)
        a[m][j]='-';
}
void five(int s, int pos)
{
    int m,i,j,x,y,p,q;
    x=s+2;
    y=2*s+3;
    m=(y+1)/2;
    p=(x*(pos-1))+pos;
    q=p+x-1;
    for(i=2; i<m; i++)
        a[i][p]='|';
    for(i=m+1; i<y; i++)
        if(i!=m)
            a[i][q]='|';
    for(j=p+1; j<q; j++)
    {
        a[1][j]='-';
        a[m][j]='-';
        a[y][j]='-';
    }
}
void six(int s, int pos)
{
    int m,i,j,x,y,p,q;
    x=s+2;
    y=2*s+3;
    m=(y+1)/2;
    p=(x*(pos-1))+pos;
    q=p+x-1;
    for(i=2; i<y; i++)
        if(i!=m)
            a[i][p]='|';
    for(i=m+1; i<y; i++)
        a[i][q]='|';
    for(j=p+1; j<q; j++)
    {
        a[1][j]='-';
        a[m][j]='-';
        a[y][j]='-';
    }
}
void seven(int s, int pos)
{
    int m,i,j,x,y,p,q;
    x=s+2;
    y=2*s+3;
    m=(y+1)/2;
    p=(x*(pos-1))+pos;
    q=p+x-1;
    for(i=2; i<y; i++)
        if(i!=m)
            a[i][q]='|';
    for(j=p+1; j<q; j++)
        a[1][j]='-';
}
void eight(int s, int pos)
{
    int m,i,j,x,y,p,q;
    x=s+2;
    y=2*s+3;
    m=(y+1)/2;
    p=(x*(pos-1))+pos;
    q=p+x-1;
    for(i=2; i<y; i++)
        if(i!=m)
        {
            a[i][p]='|';
            a[i][q]='|';
        }
    for(j=p+1; j<q; j++)
    {
        a[1][j]='-';
        a[m][j]='-';
        a[y][j]='-';
    }
}
void nine(int s, int pos)
{
    int m,i,j,x,y,p,q;
    x=s+2;
    y=2*s+3;
    m=(y+1)/2;
    p=(x*(pos-1))+pos;
    q=p+x-1;
    for(i=2; i<y; i++)
        if(i!=m)
            a[i][q]='|';
    for(i=2; i<m; i++)
        a[i][p]='|';
    for(j=p+1; j<q; j++)
    {
        a[1][j]='-';
        a[m][j]='-';
        a[y][j]='-'
                ;
    }
}
void zero(int s, int pos)
{
    int m,i,j,x,y,p,q;
    x=s+2;
    y=2*s+3;
    m=(y+1)/2;
    p=(x*(pos-1))+pos;
    q=p+x-1;
    for(i=2; i<y; i++)
        if(i!=m)
        {
            a[i][p]='|';
            a[i][q]='|';
        }
    for(j=p+1; j<q; j++)
    {
        a[1][j]='-';
        a[y][j]='-';
    }
}

int main()
{
    int x,y,i,k,s,f,j,l;
    string n;
    while(cin>>s>>n)
    {
        stringstream nt(n);
        nt>>l;
        if(s==0 && l==0)
            return 0;
        x=s+2;
        y=2*s+3;
        f=(n.length()*x)+n.length()-1;
        for(i=1; i<=y; i++)
            for(j=1; j<=f; j++)
                a[i][j]=' ';
        for(k=0; k<n.length(); k++)
        {
            if(n[k]-'0'==1)
                one(s,k+1);
            else if(n[k]-'0'==2)
                two(s,k+1);
            else if(n[k]-'0'==3)
                three(s,k+1);
            else if(n[k]-'0'==4)
                four(s,k+1);
            else if(n[k]-'0'==5)
                five(s,k+1);
            else if(n[k]-'0'==6)
                six(s,k+1);
            else if(n[k]-'0'==7)
                seven(s,k+1);
            else if(n[k]-'0'==8)
                eight(s,k+1);
            else if(n[k]-'0'==9)
                nine(s,k+1);
            else if(n[k]-'0'==0)
                zero(s,k+1);
        }
        for(i=1; i<=y; i++)
        {
            for(j=1; j<=f; j++)
                cout<<a[i][j];
            cout<<endl;
        }
        cout<<endl;
    }
    return 0;
}

UVA 13244 - Space Happiness

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long num,t,sum=0;
    cin>>t;
    while(t--)
    {
        cin>>num;
        for(long long i=1; i<=num; i++)
        {

            if(i%2!=0)
            {
                if(i==num)
                    sum+=i;
                else
                    sum+=2*i;
            }
        }
        cout<<sum<<endl;
        sum=0;
    }
    return 0;
}

UVA 13130 - Cacho

#include <cstdio>

int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int a1, a2, a3, a4, a5;
        scanf("%d %d %d %d %d", &a1, &a2, &a3, &a4, &a5);
        puts(
            (a1 == 1 && a2 == 2 && a3 == 3 && a4 == 4 && a5 == 5 ||
             a1 == 2 && a2 == 3 && a3 == 4 && a4 == 5 && a5 == 6) ? "Y" : "N");
    }
    return 0;
}

UVA 11839 - Optical Reader

#include<stdio.h>
int main()
{
    char ans[5]={'A','B','C','D','E'};
    int t,i,x,pos,a;
    while(scanf("%d",&t) &&t!=0)
    {
        while(t--)
        {
            x=0;
            for(i=0;i<5;i++)
            {
                scanf("%d",&a);
                if(a<=127) {x++;pos=i;}
            }
            if(x>1||x==0) printf("*\n");
            else printf("%c\n",ans[pos]);
        }
    }
    return 0;
}

Dijkstra: Shortest Reach 2 (Hackerrank)

একটা সোর্স থেকে অন্য সকল নোডের মিনিমাম দুরুত্ত বের করে
INPUT:
1
4 4
1 2 24
1 4 20
3 1 3
4 3 12
1

OUTPUT:
24 3 15

#include<bits/stdc++.h>
using namespace std;
#define wl(n) while(n--)
#define fl(i,a,b) for(i=a; i<b; i++)
#define rev(i,a,b) for(i=a; i>=b; i--)
#define scan(n) scanf("%d", &n)
#define scans(s) scanf("%s", s)
#define scanc(c) scanf("%c", &c)
#define scanp(f) scanf("%f", &f)
#define print(n) printf("%d\n", n)
#define prints(s) printf("%s\n", s)
#define printc(c) printf("%c\n", c)
#define printp(f) printf("%f\n", f)
#define nline printf("\n")
#define mclr(strn) strn.clear()
#define ignr cin.ignore()
#define MOD 1000000007
#define ll long long int
#define u64 unsigned long long int
#define PB push_back
#define SZ size
#define MP make_pair
int dist[3005];
bool vis[3005];
std::vector<int> adj[3003];
int mat[3005][3005];
queue<pair<int,int> > pro;
int n, e;
int main()
{
    int i, j;
    int cases;
    scan(cases);
    wl(cases)
    {
        cin>>n>>e;
        fl(i,0,n+1)
        {
            adj[i].clear();
            vis[i]=0;
            dist[i]=0;
            dist[i]=INT_MAX;
        }
        fl(i,0,n+1)
        fl(j,0,n+1)
        mat[i][j]=INT_MAX;
        fl(i,0,e)
        {
            int x, y;
            cin>>x>>y;
            adj[x].PB(y);
            adj[y].PB(x);
            int val;
            cin>>val;
            mat[x][y]=mat[y][x]=min(val,mat[x][y]);
        }
        int ini;
        cin>>ini;
        int node=ini;
        dist[node]=0;
        vis[node]=1;
        fl(i,0,n-1)
        {
            int this_dist=INT_MAX;
            fl(j,1,n+1)
            {
                if(!vis[j] && dist[j]<this_dist)
                {
                    this_dist=dist[j];
                    node=j;
                }
            }
            vis[node]=1;
            int limit=adj[node].SZ();
            fl(j,0,limit)
            {
                if(!vis[adj[node][j]] && dist[node]+mat[node][adj[node][j]]<dist[adj[node][j]])
                {
                    dist[adj[node][j]]=dist[node]+mat[node][adj[node][j]];
                }
            }
        }
        fl(i,1,n+1)
        {
            if(i==ini)
                continue;
            if(dist[i]==INT_MAX)
                cout<<-1;
            else
                cout<<dist[i];
            cout<<" ";
        }
        cout<<endl;
    }
    return 0;
}

UVA 10025 - The ? 1 ? 2 ? ... ? n = k problem

///...................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
main()
{
    timesave;
    long ts,cs=1;
    cin>>ts;
    while(ts--)
    {
        ll n,sum=0,x,i;
        cin>>n;
        if(cs>1)
            cout<<endl;
        cs=2;
        n=abs(n);
        for(i=1;; i++)
        {
            sum+=i;
            if(sum>=n)
            {
                x=sum-n;
                if(x%2==0)
                {
                    break;
                }
            }
        }
        cout<<i<<endl;
    }
}

Graph Minimum distance

Problem Link: https://toph.co/p/road-minister-techboy

এখানে বলা হয়েছে যে ১ হল রুট
১ থেকে আমার সব নোডে যাওয়া লাগবে তাহলে মিনিমাম কত ডিস্ট্যান্স লাগবে?
এক নোড থেকে অন্য টায় যেতে এবং ব্যাক আসতে হলে দুইটা ডিস্ট্যান্স ই যোগ করা লাগবে


INPUT:
2
3
1 2 3
2 3 4
3
1 2 3
1 3 3

OUPUT:
Case 1: 7
Case 2: 9

প্রথম টার জন্য ৩+৪=৭
আর ২য় টার জন্য ১->২=৩,২->১=৩,১->৩=৩ মোট হবে ৩+৩+৩=৯

#include<bits/stdc++.h>
using namespace std;
#define LL long long
vector<LL>graph[10003], cost[10003];
bool visited[10003];
int level[10003];
LL node, temp;

void DFS(LL u, LL sum)
{
    visited[u] = true;
    if(sum>temp)
    {
        temp = sum;
        node = u;
    }
    for(int i=0; i<graph[u].size(); i++)
    {
        LL v = graph[u][i];
        if(!visited[v])
        {
            level[v] = level[u] + 1;
            DFS(v, sum+cost[u][i]);
        }
    }
    return;
}

LL DFS2(LL u)
{
    visited[u] = true;
    if(u==1)
    {
        return 0;
    }
    LL sum = 0;
    for(int i=0; i<graph[u].size(); i++)
    {
        LL v = graph[u][i];
        if(!visited[v] && level[v]<level[u])
        {
            sum = sum + cost[u][i] + DFS2(v);
        }
    }
    return sum;
}
int main()
{
    int test;
    scanf("%d", &test);
    for(int i=1; i<=test; i++)
    {
        for(int i=0; i<=10000; i++)
        {
            graph[i].clear();
            cost[i].clear();
            level[i] = 0;
        }
        LL n, e, u, v, w;
        scanf("%lld", &n);
        LL ans = 0;
        for(int i=1; i<n; i++)
        {
            scanf("%lld %lld %lld", &u, &v, &w);
            graph[u].push_back(v);
            graph[v].push_back(u);
            cost[u].push_back(w);
            cost[v].push_back(w);
            ans = ans + 2*w;
        }
        memset(visited,false,sizeof(visited));
        node = 0;
        temp = 0;
        level[1] = 1;
        DFS(1, 0);
        memset(visited,false,sizeof(visited));
        LL bad = DFS2(node);
        printf("Case %d: %lld\n",i,ans - bad);
    }
    return 0;
}

UVA 10539 - Almost Prime Numbers { Important }

Almost prime numbers are the non-prime numbers which are divisible by only a single prime number. In this problem your job is to write a program which finds out the number of almost prime numbers within a certain range.
Limit:   Low and high (0 < low ≤ high < 10^12).
Input:
3
1 10
1 20
1 5
Output:
3
4
1

Secuence:-  4 8 9 16 25 27 32 49 64 81..........................

From 1 to 10 ans is 4,8,9
So output 3
From 1 to 20 ans is 4,8,9,16
So output 4
From 1 to 5 ans is 4
So output 1

#include<stdio.h>
#include<math.h>
#include<vector>
#include<algorithm>
#include<set>
#define sz 1000001
using namespace std;
vector<int>prime;
vector<long long int>ans;
bool flag[1000001];
int prsz;
void sieve(void)
{
    int i,j,add;
    flag[0]=flag[1]=1;
    prime.push_back(2);
    for(i=4; i<sz; i+=2)
        flag[i]=1;
    for(i=3; i<sz; i+=2)
    {
        if(!flag[i])
        {
            prime.push_back(i);
            if(sz/i>=i)
            {
                add=i*2;
                for(j=i*i; j<sz; j+=add)
                    flag[j]=1;
            }
        }
    }
}
int main()
{
    sieve();
    long long int i,k,szp,j;
    szp=prime.size();
    for(i=0; i<sz; i++)
    {
        if(!flag[i])
            for(j=i*i; j<1000000000001; j*=i)
                ans.push_back(j);
    }
    sort(ans.begin(),ans.end());
    int tst,count,ansz;
    ansz=ans.size();
    long long x,y;
    scanf("%d",&tst);
    while(tst--)
    {
        count=0;
        scanf("%lld %lld",&x,&y);
        i=0;
        while(ans[i]<x)
            i++;
        for(; i<ansz && ans[i]<=y; i++)
            count++;
        printf("%d\n",count);
    }
    return 0;
}

SPOJ QTREE2 - Query on a tree II

Dist দিলে a,b এর মধ্যে Distance বের করতে হবে 

আর kth দিলে a থেকে b যেতে  kth তম নোড কোনটা?  

• DIST a b : ask for the distance between node a and node b
  or
• KTH a b k : ask for the k-th node on the path from node a to node b

1

6
1 2 1
2 4 1
2 5 2
1 3 1
3 6 2
DIST 4 6
KTH 4 6 4
DONE

Output:
5
3

#include <iostream>
#include <cstdio>
#include <cstring>
#define N 10005
using namespace std;
struct edge
{
    int to,next,w;
} e[N<<1];
int head[N],cnt;
void add(int u,int v,int w)
{
    e[++cnt]=(edge)
    {
        v,head[u],w
    };
    head[u]=cnt;
}
int n;
int deep[N],dis[N],p[N][30];
void dfs(int x,int fa)
{
    deep[x]=deep[fa]+1;
    p[x][0]=fa;
    for(int i=0; p[x][i]; i++)
        p[x][i+1]=p[p[x][i]][i];
    for(int i=head[x]; i; i=e[i].next)
    {
        int to=e[i].to;
        if(to==fa)
            continue;
        dis[to]=dis[x]+e[i].w;
        dfs(to,x);
    }
}
int lca(int a,int b)
{
    if(deep[a]<deep[b])
        swap(a,b);
    for(int j=14; j>=0; j--)
        if(deep[a]-(1<<j)>=deep[b])
            a=p[a][j];
    if(a==b)
        return a;
    for(int j=14; j>=0; j--)
        if(p[a][j]&&p[a][j]!=p[b][j])
        {
            a=p[a][j];
            b=p[b][j];
        }
    return p[a][0];
}
int get(int u,int d)
{
    for(int j=14; j>=0; j--)
        if(deep[u]-(1<<j)>=d)
            u=p[u][j];
    return u;
}
int main()
{
int t;
    cin>>t;
    while(t--)
    {
        memset(head,0,sizeof head);
        memset(p,0,sizeof p);
        cnt=0;
        cin>>n;
        for(int i=1; i<n; i++)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);
            add(v,u,w);
        }
        dfs(1,0);
        char op[100];
        while(1)
        {
            scanf("%s",op);
            if(op[1]=='O')
                break;
            if(op[1]=='I')
            {
                int u,v;
                scanf("%d%d",&u,&v);
                printf("%d\n",dis[u]+dis[v]-2*dis[lca(u,v)]);
            }
            else
            {
                int u,v,k;
                scanf("%d%d%d",&u,&v,&k);
                int fa=lca(u,v),d;
                if(deep[u]-deep[fa]<k)
                {
                    d=deep[fa]+k-(deep[u]-deep[fa]+1);
                    u=v;
                }
                else
                    d=deep[u]-k+1;
                printf("%d\n",get(u,d));
            }
        }
    }
}

Bigmod in iteraive way (1 <= A, B <= 1000000000000000000, 1 < M < 1000000000).

#include<bits/stdc++.h>
using namespace std;


long long Power(long long BaSe,long long PoWeR,long long MoD){
    //if BaSe zero
    BaSe%=MoD;
    long long ret=1;
    while(PoWeR>0){
        if(PoWeR&1) ret=(ret*BaSe)%MoD;
        PoWeR>>=1;
        BaSe=(BaSe*BaSe)%MoD;
    }
    if(ret==0) return MoD;
    return ret;
}


main(){
    int Case;
    scanf("%d",&Case);
    while(Case--){
        long long a,b,m;
        scanf("%lld %lld %lld",&a,&b,&m);
        printf("%lld\n",Power(a,b,m));
    }
    return 0;
}

Russian Peasunt Theorem

#include<bits/stdc++.h>
using namespace std;

///pre-processing
#define     gcd(a, b)       __gcd(a,b)
#define     lcm(a, b)       (a * b) / gcd(a, b)
#define     loop(i, n)      for(int i=0;i<n;i++)
#define     all(x)          x.begin(),x.end()
#define     mem(a, x)       memset(a,x,sizeof a)
#define     endl            '\n'
#define     ss              second
#define     ff              first
#define     TN              typename

///input functions
int Int(){int x;scanf("%d",&x);return x;}
long long Long(){long long x;scanf("%lld",&x);return x;}
double Double(){double x;scanf("%lf",&x);return x;}

///input functions shorting
#define Int Int()
#define Long Long()
#define Double Double()
#define Float Float()
const int N = (int) 1e5 + 5;
unsigned long long peasant(unsigned long long a, unsigned long long b, unsigned long long MOD){
    unsigned long long res = 0;
    while(b){
        if(b & 1){res += (a % MOD), res %= MOD;}
        a <<= 1;
        a %= MOD;
        b >>= 1;
    }
    return res;
}
unsigned long long bigMod (unsigned long long base, unsigned long long power, unsigned long long MOD){
    long long res = 1;
    while (power){
        if (power & 1){
            res = peasant(res, base, MOD) % MOD;
        }
        base = peasant(base, base, MOD) % MOD;
        power = power >> 1;
    }
    return res;
}
int main()
{
    int t, cs = 0;
    cin>>t;
    while(t--){
       /// printf("Case %d: ", ++cs);
        unsigned long long a, b, c;
        cin >> a >> b >> c;
        cout << bigMod(a, b, c) <<endl;
    }
    return 0;
}

print ( a^b ) mod m (a and b both will be integer numbers of at most 10^5 digits.)

There will be multiple test cases in each input file . Each line of the input file will contain three integer numbers a , band m (1 ≤ m ≤ 1.5*109).

a and b both will be integer numbers of at most 105 digits.

For each case, print ( ab ) mod m in a new line.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100005
ll bigmod(ll b, ll p, ll m)
{
    ll res = 1%m, k = b%m;
    while(p)
    {
        if(p&1)
            res = (res*k)%m;
        k = (k*k)%m;
        p = p>>1LL;
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string a,b;
    ll m;
    while(cin>>a>>b>>m)
    {
        if(a=="0" && b=="0" && m==0)
            break;

        ll base = 0;
        for(int i=0; i<a.size(); i++)
        {
            int d = a[i]-'0';
            base = ((base*10)+d)%m;
        }

        ll ans = 1;
        for(int i=0; i<b.size(); i++)
        {
            int d = b[i]-'0';
            ans = (bigmod(ans,10,m) * bigmod(base,d,m))%m;
        }
        cout << ans << endl;
    }
    return 0;
}

UPDATE(L,R,v)
You should add v to all Ai where L ≤ i ≤ R

QUERY(L,R,v)

You should output the frequency of the number v in the range from Lth to Rth index in the array.

INPUT:

1
5 5
1 2 3 4 5
2 3 4 3
1 3 4 -2
2 3 4 3
1 4 4 -1
2 3 4 1

OUTPUT:

Case 1:
1
0
2

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define vin vector<int>
#define vll vector<long long>
#define pii pair<int,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define pq priority_queue
#define all(x) x.begin(),x.end()
#define mod 1000000007
#define cone __builtin_popcount
#define conel __builtin_popcountll
typedef vector<vector<ll> > matrixl;
typedef vector<vector<int> > matrix;
#define N 100009
#define SN 2000
#define L (100000/SN)+2

int a[N],c[L][2*N],lz[L];

void upd(int l,int r,int v)
{
    int lc = l/SN;
    int rc = r/SN;
    if(lc==rc)
    {
        for(int i=l;i<=r;i++)
        {
            //cout<<"T "<<i<<endl;
            c[lc][a[i]]--;
            a[i]+=v;
            c[lc][a[i]]++;
        }
        return;
    }
    for(int i=l;i<(lc+1)*SN;i++)
    {
        c[lc][a[i]]--;
        a[i]+=v;
        c[lc][a[i]]++;
    }
    for(int i = lc+1;i<rc;i++) lz[i]+=v;
    for(int i=rc*SN;i<=r;i++)
    {
        c[rc][a[i]]--;
        a[i]+=v;
        c[rc][a[i]]++;
    }
}

int qry(int l,int r,int v)
{
    int res = 0;
    int lc = l/SN;
    int rc = r/SN;
    if(lc==rc)
    {
        for(int i=l;i<=r;i++) if(a[i]+lz[lc]==v) res++;
        return res;
    }
    for(int i=l;i<(lc+1)*SN;i++)
    {
        if(a[i]+lz[lc]==v) res++;
    }
    for(int i=lc+1;i<rc;i++)
    {
        res+=c[i][v-lz[i]];
    }
    for(int i=rc*SN;i<=r;i++)
    {
        if(a[i]+lz[rc]==v) res++;
    }
    return res;
}

int main()
{
    int n,q,t,tp,x,y,v,test = 0;
    scanf("%d",&t);
    while(t--)
    {
        printf("Case %d:\n",++test);
        memset(c,0,sizeof(c));
        memset(lz,0,sizeof(lz));
        scanf("%d%d",&n,&q);
        for(int i=0; i<n; i++)
        {
            scanf("%d",&a[i]);
            c[i/SN][a[i]]++;
        }
        while(q--)
        {
            scanf("%d%d%d%d",&tp,&x,&y,&v);
            if(tp==1)
            {
                upd(x-1,y-1,v);
            }
            else
            {
                printf("%d\n",qry(x-1,y-1,v));
            }
            //for(int i=0;i<n;i++) cout<<a[i]<<" ";
            //cout<<endl;
        }
    }
}

UVA 10099 - The Tourist Guide

#include <climits>
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
#define MAXN 100
#define INF INT_MAX
#define NINF INT_MIN
int d[MAXN][MAXN]; // d[i][j] = distance from i node to j node
int floyd(int n)
{
    for(int k=0; k<n; k++)
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
            {
                d[i][j]=max(d[i][j],min(d[i][k],d[k][j]));
            }

    return 0;
}
int main()
{
    int n,e,i,j,u,v,w,cs=0; // n=number of nodes,e=number of edges
    while(scanf("%d %d",&n,&e))
    {
        if(n==0&&e==0)
            break;
        for(i=0; i<n; i++) //node number begins from 0 to n-1
            for(j=0; j<n; j++)
                d[i][j]=NINF;
        for(i=0; i<e; i++)
        {
            scanf("%d %d %d",&u,&v,&w);
            u--;
            v--;
            d[u][v]=d[v][u]=w; //if graph is bidirectional
        }
        floyd(n);
        scanf("%d %d %d",&u,&v,&w);
        u--;
        v--;
        printf("Scenario #%d\n",++cs);
        //cout<<d[0][6]<<endl;
        int trip=ceil((float)w/(d[u][v]-1));
        printf("Minimum Number of Trips = %d\n\n",trip);
    }
    return 0;
}

UVA 10078 - The Art Gallery

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <bitset>
#include <sstream>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include<stdio.h>
#include <stdlib.h>
#include<string.h>
using namespace std;
bool isConvex(int n,int x[], int y[])
{
    int pos=0,neg =0;
    for(int i = 0; i < n; i++)
    {
        int prev = (i + n -1) % n, next = (i  + 1) % n;
        int pv = (x[next] - x[i]) * (y[prev] - y[i]) - (x[prev] - x[i])*(y[next] - y[i]);

        if(pv > 0)
            pos++;
        else
        {
            if(pv < 0)
                neg++;
        }
    }
    return (pos == 0) || (neg == 0);
}

int main()
{
    int N,a,b;
    while(cin>>N)
    {
        if(N==0)
            break;
        int x[N], y[N];
        for(int i = 0; i < N; i++)
        {
            cin>>a>>b;
            x[i] = a;
            y[i] = b;
        }
        if(isConvex(N,x,y))
            cout<<"No"<<endl;
        else
            cout<<"Yes"<<endl;
    }
    return 0;
}

UVA 465 - Overflow

#include<stdio.h>
int main()
{
    double a, b;
    int INF = 2147483647;
    char op, s[2000];
    while(gets(s))
    {
        printf("%s\n", s);
        sscanf(s, "%lf %c %lf", &a, &op, &b);
        if(a > INF)
            puts("first number too big");
        if(b > INF)
            puts("second number too big");
        if(op == '+' && a+b > INF)
            puts("result too big");
        if(op == '*' && a*b > INF)
            puts("result too big");
    }
    return 0;
}

UVA 10600 - ACM Contest and Blackout (First Minimum spanning tree AND Second Minimum spanning tree)

First Minimum spanning tree
Second Minimum spanning tree


2
5 8        ///5 holo node 8 holo edge
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66

OUTPUT :110 121

9 14     ///9 holo node 14 holo edge
1 2 4
1 8 8
2 8 11
3 2 8
8 9 7
8 7 1
7 9 6
9 3 2
3 4 7
3 6 4
7 6 2
4 6 14
4 5 9
5 6 10


Output 37 37


///...................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++)
#define sz 103
#define inf 1<<29
/*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
struct edge
{
    int f,t,c;
    edge(int a,int b,int co)
    {
        f=a;
        t=b;
        c=co;
    }
};

vector<edge>vec;
int n,e,ans2,edgetaken[sz],etl;
int comp(edge a,edge b)
{
    return a.c<b.c;
}
int par[sz];
int set_find(int a)
{
    if(a==par[a])
        return a;
    return(par[a]=set_find(par[a]));
}
void link(int x,int y)
{
    if(x>y)
        par[x]=y;
    else par[y]=x;
}
int  mst(void)
{
    int i=0,j,x,y,sum=0,cnt=0;
    etl=0;
    sort(vec.begin(),vec.end(),comp);
    for(i=0; i<e && cnt<n-1; i++)
    {
        x=set_find(vec[i].f);
        y=set_find(vec[i].t);

        if(x!=y)
        {
            link(x,y);
            sum+=vec[i].c;
            edgetaken[etl++]=i;
            cnt++;
        }
    }
    return sum;
}
void ini(void)
{
    for(int i=1; i<=n; i++)
        par[i]=i;
}

int main()
{
//   freopen("in.txt","r",stdin);

    int t,i,j,f,c,tst,cs,cnt,ans1,an2,x,y,miin;
    scanf("%d",&tst);
    for(cs=1; cs<=tst; cs++)
    {
        scanf("%d %d",&n,&e);
        ini();
        vec.clear();
        memset(edgetaken,0,sizeof edgetaken);
        for(j=0; j<e; j++)
        {
            scanf("%d %d %d",&f,&t,&c);
            vec.push_back(edge(f,t,c));
        }

        ans1=mst();

        //2nd mst
        miin= inf;
        for(i=0; i<etl; i++)
        {
            ini();
            cnt=0;
            ans2=0;
            for(j=0; j<e && cnt<n-1; j++)
            {
                //     printf("i %d j %d\n",i,j);
                if(edgetaken[i]!=j)
                {
                    x=set_find(vec[j].f);
                    y=set_find(vec[j].t);
                    //       printf("f %d t %d c %d\n",vec[j].f,vec[j].t,vec[j].c);
                    if(x!=y)
                    {
                        cnt++;
                        link(x,y);
                        ans2+=vec[j].c;
                    }
                }
            }
            //   printf("ans %d\n",ans2);
            if(cnt==n-1 && miin>ans2)
                miin=ans2;
        }
        printf("%d %d\n",ans1,miin);
    }
    return 0;
}

UVA 10036 - Divisibility

///...................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 n,k,arr[10000+5];
int dp[100+5][10000+5];
vector<long>v1;
vector<long>v2;
bool func(int sum, int position)
{
    bool check=false;
    sum=((sum%k)+k)%k;
    if(position==n)
    {
        if(sum==0)
            return true;
        else
            return false;
    }
    if(dp[sum][position]!=-1)
        return dp[sum][position];
    check=check | func(sum+arr[position],position+1);
    check=check | func(sum-arr[position],position+1);
    v1.push_back(sum);
    v2.push_back(position);
    return dp[sum][position]=check;
}
int main()
{
    long tc,i;
    cin>>tc;
    memset(dp,-1,sizeof(dp));
    while(tc--)
    {
        v1.clear();
        v2.clear();
        cin>>n>>k;
        for(i=0; i<n; i++)
            cin>>arr[i];
        bool ans=func(arr[0],1);
        if(ans)
            cout<<"Divisible"<<endl;
        else
            cout<<"Not divisible"<<endl;
        long l=v1.size();
        for(i=0; i<l; i++)
            dp[v1[i]][v2[i]]=-1;

    }
    return 0;
}

UVA 10183 - How Many Fibs?

#include<bits/stdc++.h>
#define pi acos(-1.0)
#define E 2.71828182845904523536
using namespace std;

struct BI
{
    char Digits[110];
    int LastDigit;
};

void addBI(BI & a, BI & b, BI& c)
{
    for (int i=0; i<110; i++) c.Digits[i] = 0;
    int carry=0;
    c.LastDigit = max(a.LastDigit, b.LastDigit);
    for (int i=0; i<=c.LastDigit; i++)   {       c.Digits[i] = (a.Digits[i] + b.Digits[i] + carry)%10;       carry = (a.Digits[i] + b.Digits[i] + carry)/10;     }   if (carry) c.Digits[++c.LastDigit] = carry;     return; } int compBI(BI &a, BI&b) {     if (a.LastDigit != b.LastDigit) return a.LastDigit > b.LastDigit;

    for (int i=a.LastDigit; i >=0; i--) if (a.Digits[i] != b.Digits[i]) return a.Digits[i] > b.Digits[i];

    return -1;
}
int howManyFibs(BI &small, BI &big)
{
    BI *a,*b,*c;
    a = new BI;
    b = new BI;
    c = new BI;

    for (int i=0; i<110; i++) a->Digits[i] = b->Digits[i] = 0;
    a->Digits[0] = 1; b->Digits[0] = 1;
    a->LastDigit = 0; b->LastDigit = 0;

    int nFibs=0;
    bool reached=false;
    while(1)
    {

        if(compBI(*b,small) && compBI(*b, big) < 1)nFibs++;      else if (compBI(*b, big) == 1) break;       addBI(*a,*b,*c);        swap(b,c);      swap(a,c);  }   return nFibs; } int main() {    string a,b;     BI large, small;    while(1)    {       cin >> a >> b;

        if (a == "0" && b == "0") return 0;
        small.LastDigit = a.size() - 1;
        for (int i=small.LastDigit, j=0; i>=0; i--, j++)small.Digits[i] = a[j] - '0';
        large.LastDigit = b.size() - 1;
        for (int i=large.LastDigit, j=0; i>=0; i--, j++)large.Digits[i] = b[j] - '0';
        cout << howManyFibs(small,large) << endl;

    }
    return 0;
}