Allen Turing The Great Mathemacian

Life of Sir Allen Turing

Program to find last digit of n’th Fibonnaci Number

/*

It takes a while before it is noticeable. In fact, the series is just 60 numbers long and then it repeats the same sequence again and again all the way through the Fibonacci series – for ever. The series of final digits repeats with a cycle length of 60 (Refer this for explanations of this result).
So, instead of calculating the Fibonacci number again and again, pre-compute the units digit of first 60 Fibonacci number and store it in an array and use that array values for further calculations.

Link: Program to find last digit of n’th Fibonnaci Number

*/


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

#define sf scanf
#define pf printf

LL f[65] = {0};

LL fib(LL n)
{
    f[0] = 0;
    f[1] = 1;

    for (LL i = 2; i <= n; i++)
    {
        f[i] = (f[i-1] + f[i-2])%10;
    }

    return f[n];
}

LL findLastDigit(LL n)
{
    fib(60);

    return f[n%60];
}

int main()
{
    int t , tc=0;
    LL n;
    sf("%d", &t);
    while(t--)
    {
        memset(f , 0 , sizeof f);

        sf("%lld", &n);

        pf("Case %d: %lld is the last digit.\n", ++tc, findLastDigit(n));
    }

    return 0;
}

ACM ICPC Preliminary 2016 Team Practice Contest A.Multiplication Queries

Problem Link: A - Multiplication Queries 

//Next Codeforces Round #354 (Div. 2)
#include<bits/stdc++.h>

//#include<cstdio>
//#include<iostream>
//#include<algorithm>
//#include<vector>
//#include<cstring>
//#include<cmath>
//#include<map>

using namespace std;

#define fast ios_base::sync_with_stdio(false)
#define bfast cin.tie(0)
#define outs(x) cout << x << " "
#define outn(x) cout << x << "\n"
#define sf scanf
#define pf printf
#define nl puts("")
//#define i64 long long
#define high 50005

typedef long long LL;
typedef vector<int>vii;
typedef vector<LL>vll;

LL ar[high], br[high];
LL tree[high * 3] , m;

LL multiple(LL a, LL b , LL c)
{
    if(!b) return 0;

    LL x = multiple(a , b/2, c)%c;

    if(!(b&1))
    {
        return ((x%c) + (x%c))%c;
    }

    else
    {
        return ((a%c) + (x%c)+(x%c))%c;
    }
}

LL bigmod(LL a, LL b , LL c)
{
    if(!b) return 1;

    LL x = bigmod(a , b/2, c)%c;

    if(!(b&1))
    {
        return multiple(x , x , c);
    }

    else
    {
        return (multiple(a%c, multiple(x , x , c)%c , c))%c;
    }
}

void build(LL node, LL b , LL e)
{
    if(b == e)
    {
        tree[node] = br[b];
        return;
    }

    LL Left = node * 2;
    LL Right = (node * 2)+1;
    LL mid = (b + e) / 2;

    build(Left , b , mid);
    build(Right, mid+1, e);

    tree[node] = (tree[Left]%m * tree[Right]%m)%m;
}

LL query(LL node, LL b , LL e, LL i, LL j)
{
    if(i > e or j < b) return 1;

    if(b >= i and e <= j)
    {
        //cout << tree[node] << "; ";
        return tree[node];
    }

    LL Left = node * 2;
    LL Right = (node * 2) + 1;
    LL mid = (b + e) / 2;

    LL pek = query(Left, b , mid, i , j);
    LL pdui = query(Right, mid+1, e , i , j);

    //cout << pek << " " << pdui << "; ";

    return (pek%m * pdui%m)%m;
}

int main()
{
    fast;
    int t , tc=0;
    LL n , q , k , i , l , r, tmp=1 , p;
    //cin >> t;
    sf("%d", &t);
    while(t--)
    {
        //cin >> n >> q >> k >> m;
        //ans.clear();
        sf("%lld %lld %lld %lld", &n, &q, &k ,&m);

        for(i=1; i<=n; i++)
        {
            //cin >> ar[i];
            sf("%lld", &ar[i]);
        }

        br[0] = 1;

        for(i=1; i<=n; i++)
        {
            br[i] = bigmod(ar[i] , k , m);

            //br[i]= (br[i]%m * br[i-1]%m)%m;
        }

        build(1 , 1 , n);

        //for(i=1; i<=n; i++) cerr << tree[i] << " ";

        pf("Case %d:\n", ++tc);

        while(q--)
        {
            sf("%lld %lld", &l, &r);

            LL ans = query(1, 1, n, l , r);
            pf("%lld\n", ans%m);
        }

      }

    return 0;
}
 

LightOJ ACM ICPC Preliminary 2016 Team Practice Contest G. Chocolates

Problem Link: G.Chocolates


//Next Codeforces Round #354 (Div. 2)
#include<bits/stdc++.h>

//#include<cstdio>
//#include<iostream>
//#include<algorithm>
//#include<vector>
//#include<cstring>
//#include<cmath>
//#include<map>

using namespace std;

#define fast ios_base::sync_with_stdio(false)
#define bfast cin.tie(0)
#define outs(x) cout << x << " "
#define outn(x) cout << x << "\n"
#define sf scanf
#define pf printf
#define nl puts("")
//#define i64 long long

typedef long long LL;
typedef vector<int>vii;
typedef vector<LL>vll;

vll v;

int main()
{
    int t;
    LL k , m , n , i , sum=0 , x , ans=0 , tmp;
    sf("%d", &t);
    while(t--)
    {
        v.clear();

        sf("%lld %lld %lld", &k, &m , &n);

        for(i=0; i<k; i++)
        {
            sf("%lld", &x);
            v.push_back(x);
        }

        sort(v.rbegin(), v.rend()); //for(i=0; i<k; i++) cerr << v[i] << " ";

        sum = ans = 1;

        for(i=1; i<k; i++)
        {
            if(v[i-1] == v[i])
            {
                ans+=sum;
            }

            else
            {
                sum+=(m * (v[i-1] - v[i]));
                ans+=sum;
            }
        }

        //cerr << ans << "\n";

        if(ans > n)
        {
            pf("impossible\n");
        }

        else
        {
            tmp = (n - ans) / k;

            pf("%lld\n", (tmp * k) + ans);
        }
    }

    return 0;
}

Extended Euclid

#include<bits/stdc++.h>

using namespace std;

typedef pair<int, int>pii;

pii EGCD(int a, int b)
{
    if(!b)
    {
        return pii(1, 0);
    }

    else
    {
        pii d = EGCD(b, a%b);

        return pii(d.second, d.first - (a / b) * d.second);
    }
}

int main()
{
    int a, b;

    while(cin >> a >> b)
    {
        pii ans = EGCD(a,b);

        cout << ans.first << " " << ans.second << "\n";
    }

    return 0;
}

Binary Search Lower Bound and Upper Bound

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

int ar[N+5];

int lowerBound(int itm , int sz)
{
    int lo=0, hi=sz-1 , mid;

    while(lo <= hi)
    {
        mid = (lo + hi) / 2 ;

        if(ar[mid] == itm)
        {
            hi = mid-1;
        }

        else if(ar[mid] > itm)
        {
            hi = mid-1 ;
        }

        else if(ar[mid] < itm)
        {
            lo = mid+1;
        }
    }

    return lo;
}

int upperBound(int itm, int sz)
{
    int lo=0, hi=sz-1, mid;

    while(lo <= hi)
    {
        mid = (lo+hi) / 2;

        if(ar[mid] == itm)
        {
            lo = mid+1;
        }

        else if(ar[mid] > itm)
        {
            hi = mid - 1;
        }

        else if(ar[mid] < itm)
        {
            lo = mid+1;
        }
    }

    return lo;
}

int main()
{
    int n;

    cout << "Take array size: ";

    while(cin >> n)
    {
        int i;

        for(i=0;i<n;i++)
        {
            cin >> ar[i];
        }

        int q;
        cout << "Number of Query: ";
        cin >> q;

        while(q--)
        {
            int x;
            cin >> x;

            int lw,up;

            lw = lowerBound(x,n);

            cout << "index = " << lw << " value = " << ar[lw] << "\n";

            up = upperBound(x, n);

            cout << "index = " << up << " value = " << ar[up] << "\n";
        }

        cout << "Take array size: ";
    }

    return 0;
}

Upcomming_Eid_Ul_AZHA_Programmming_Contest Problem B. Even Digits

Link: Problem B - Even Digits Problem Link
AC Code Link: Problem B - Even Digits AC Code Link

//#include<cstdio>
//#include<iostream>
//#include<algorithm>
//#include<vector>
//#include<cstring>
//#include<cmath>
//#include<map>
#include<bits/stdc++.h>
using namespace std;

#define fast ios_base::sync_with_stdio(false)
#define outs(x) cout << x << " "
#define outn(x) cout << x << "\n"
#define sf scanf
#define pf printf
#define high 10000

typedef long long LL;
typedef vector<int>vii;
typedef vector<LL>vll;

int main()
{
    fast;
    int t, tc=0;
    LL n, quotiant=0;
    string ans="";
    cin >> t;
    while(t--)
    {
        ans="";
        cin >> n;

        cout << "Case " << ++tc << ": ";

        if(n==1)
        {
            outn("0");
            continue;
        }

        quotiant = n-1;

        while(quotiant > 0)
        {
            ans+=((quotiant % 5) * 2) + 48;

            quotiant = quotiant / 5;
        }

        reverse(ans.begin(), ans.end());
        outn(ans);
    }

    return 0;
}