Thursday, October 5, 2017

0-1 BFS 2D .cpp File


#include<bits/stdc++.h>
#define DIST(x1,x2, y1, y2) (((x1-x2)*(x1-x2))+((y1-y2)*(y1-y2)))
#define CLR(a) a.clear()
#define VCLR(a, n) for(int i=0; i<=n+3; i++) a[i].clear()
#define SIZE(a) a.size()
#define ERASE(a, b) memset(a, b, sizeof a)
#define PB(a, b) a.push_back(b)
#define PB2(a,i,b) a[i].push_back(b)
#define LL long long
#define DBG cout<<"I Am Here"<<endl
#define DBGA(a) cout<<a<<endl
#define DBGI(b,a) cout<<b<<' '<<a<<endl
#define DBGL(i,s,e,b) or(int i=s; i<=e; i++) cout<<b<<endl
#define INF 1e9
#define II(a) scanf("%I64d", &a)
#define PP(a) printf("%I64d", a)
#define si(a) scanf("%d", &a)
#define pii pair<int,int>
#define pii2 pair<int, pii>
#define MAX 1000
#define MAXN 100007
#define logbase(a, b) ( log10(a)/log10(b) )
#define DIR(f,s,R,C) (f>=0 && f<R && s>=0 && s<C)
#define DIR1(f,s,R,C) (f>=1 && f<=R && s>=1 && s<=C)
#define CASE(i) printf("Case %d:", i);


using namespace std;

int level[1005][1005];
char grid[1005][1005];

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int m, n;

int BFS()
{
    int ans = 0;
    for(int i=0; i<m; i++) for(int j=0; j<n; j++) level[i][j] = INT_MAX;
    deque<pii>q;
    q.push_front(pii(0,0));
    level[0][0] = 1;

    while(!q.empty())
    {
        pii top = q.front();

        q.pop_front();
        if(top.first==m-1 && top.second==n-1) break;

        for(int i=0; i<4; i++)
        {
            int u = top.first + dx[i];
            int v = top.second + dy[i];

            if(u>=0 && v>=0 && u<m && v<n)
            {
             //   cout<<endl<<u<<' '<<v<<' '<<top.first<<' '<<top.second;
                if(grid[u][v]==grid[top.first][top.second] && level[u][v]>level[top.first][top.second])
                {

                    level[u][v] = level[top.first][top.second];
                    q.push_front(pii(u,v));
                }
                else if(level[u][v]>level[top.first][top.second]+1)
                {
                    level[u][v] = level[top.first][top.second] + 1;
                    q.push_back(pii(u,v));
                }
            }
        }
    }
    ans = level[m-1][n-1] - 1;

    return ans;
}

int main()
{
    int test;
    scanf("%d", &test);A
    for(int caseno=1; caseno<=test; caseno++)
    {
        scanf("%d %d", &m, &n);
        for(int i=0; i<m; i++)
        {
            scanf("%s", grid[i]);
        }
       // CASE(caseno);
       // printf(" ");
        printf("%d\n", BFS());
    }
}

0-1 Knapsack code .cpp file


#include<bits/stdc++.h>
#define DIST(x1,x2, y1, y2) (((x1-x2)*(x1-x2))+((y1-y2)*(y1-y2)))
#define DIST3D(x1,x2, y1, y2, z1, z2) (((x1-x2)*(x1-x2))+((y1-y2)*(y1-y2)) + ((z1-z2)*(z1-z2)))
#define CLR(a) a.clear()
#define VCLR(a, n) for(int i=0; i<=n+3; i++) a[i].clear()
#define SIZE(a) a.size()
#define ERASE(a, b) memset(a, b, sizeof a)
#define PB(a, b) a.push_back(b)
#define PB2(a,i,b) a[i].push_back(b)
#define LL long long
#define ULL unsigned long long
#define DBG cout<<"I Am Here"<<endl
#define DBGA(a) cout<<a<<endl
#define DBGI(b,a) cout<<b<<' '<<a<<endl
#define DBGL(i,s,e,b) or(int i=s; i<=e; i++) cout<<b<<endl
#define INF 1e9
#define INV 1e-6
#define sll(a) scanf("%I64d", &a)
#define pll(a) printf("%I64d\n", a)
#define si(a) scanf("%d", &a)
#define pii pair<int,int>
#define MAX 100006
#define CASE(i) printf("Case %d: ", i);
#define CSH(i) printf("Case #%d: ", i);
#define PI acos(-1)
#define piis pair<int, string>
#define fast1 ios_base::sync_with_stdio(false);
#define fast2 cin.tie(0)


LL MOD = 1000000007;

using namespace std;

LL bigmod(LL b, LL p, LL m)
{
    if(p==0)  return 1;
    if(p%2==0)
    {
        LL x = bigmod(b,p/2,m);
        return (x%m * x%m)%m;
    }
    else return ((b%m)*bigmod(b,p-1,m)%m)%m;
}


LL MODINVERSE(LL a)
{
    return bigmod(a, MOD-2, MOD);
}

int N, CAP;
int arr[100], cost[100];
int dp[100][10000];

int solve(int i, int wt)
{
    if(i==N+1) return 0;
    if(dp[i][wt]!=-1)  return dp[i][wt];
    int cost1 = 0, cost2 = 0;
    if(wt + arr[i]<=CAP)
        cost1 = cost[i] + solve(i+1, wt + arr[i]);
    cost2 = solve(i+1, wt);
   // cout<<cost1<<' '<<cost2<<endl;
    dp[i][wt] = max(cost1, cost2);
    return dp[i][wt];
}

int main()
{
    scanf("%d %d", &N, &CAP);
    for(int i=1; i<=N; i++){
        scanf("%d %d", &arr[i], &cost[i]);
    }
    memset(dp, -1, sizeof dp);
    printf("Maximal Cost: %d\n", solve(1,0));
}

/// KnapSack Item Printing Code: http://pastebin.ubuntu.com/22396978/ ///
/// KnapSack Item Printing Code: http://pastebin.ubuntu.com/22418770/ ///

Contest Template-02

Contest Template-02

///    Md.ASADUZZAMAN
///    Dept of ICT
///    MBSTU
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long

#define fr(i,a,b) for(int i=(a);i<(b);i++)
#define rfr(i,a,b) for(int i=(b-1);i>=(a);i--)
#define freach(i, c) for( __typeof( (c).begin() ) i = (c).begin(); i != (c).end(); ++i )
#define rep(i,n) for(int i=0;i<(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define forit(it, s) for(__typeof(s.begin()) it = s.begin(); it != s.end(); it++)


#define PINF INT_MAX
#define MINF INT_MIN
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define mset(a,c) memset(a,c,sizeof a)
#define clr(a) memset(a,0,sizeof a)
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pcc pair<char,char>
#define pic pair<int,char>
#define pci pair<char,int>
#define psi pair<sting,int>
#define pis pair<int,string>
#define ff first
#define ss second
#define vs vector<string>
#define vi vector<int>
#define vll vector<long long>
#define vpi vector<pair<int,int> >
#define vpl vector<pair<long long,long long> >


#define qi  queue<int>
#define ql  queue<long>
#define qll queue<long long>
#define PQ priority_queue

#define mpii map<int,int>
#define mpsi map<string,int>
#define mpci map<char,int>
#define mpll map<long long,long long>

#define stl set<ll>
#define sts set<string>
/// Bug
#define bug(x) cout<<#x<<": "<<x<<endl
#define bug1(x,y) cout<<#x<<": "<<x<<"  |  "<<#y<<": "<<y<<endl
#define bug2(x,y,z) cout<<#x<<": "<<x<<"  |  "<<#y<<": "<<y<<"  |  "<<#z<<": "<<z<<endl
#define bug3(w,x,y,z) cout<<#w<<": "<<w<<"  |  "<<#x<<": "<<x<<"  |  "<<#y<<": "<<y<<"  |  "<<#z<<": "<<z<<endl
/// Trigonometry
#define pi acos(-1.0)
#define rad(x) (((1.0 * x * pi) / 180.0))
#define deg(x) (((x * 180.0) / (1.0 * pi)))
#define sinr(x) (sin(rad(x)))
#define cosr(x) (cos(rad(x)))
#define tanr(x) (tan(rad(x)))
#define asind(x) (deg((asin(x))))
#define acosd(x) (deg((acos(x))))
#define atand(x) (deg((atan(x))))

///Bit

#define setbiton(x, i) (x |= (1 << i))
#define setbitoff(x, i) (x &= (~(1 << i)))
#define togglebit(x, i) (x ^= (1 << i))
#define checkbiton(x,i)   ((x &(1 << i))!=0)
#define ispow2 (x!=0 && (x&(x-1))==0)
#define countbit(x) __builtin_popcountll((ll)x)
#define countlead(x) __builtin_clzll((ll)x)  ///give wrong ans for zero (0)
#define counttrail(x) __builtin_ctzll((ll)x)  ///give wrong ans for zero (0)
/// Search
#define LB(a,x) (lower_bound(all(a),x)-a.begin()) //  first element in the range [first,last) which does not compare less than val.
#define UB(a,x) (upper_bound(all(a),x)-a.begin()) //  first element in the range [first,last) which compares greater than val.
#define bin_sa(a,n,x) (binary_search(a, a+n,x))
#define bin_sv(v,x) (binary_search(v.begin(), v.end(),x))

/// Algorithm
#define Unique(store) store.resize(unique(store.begin(),store.end())-store.begin())
#define mxe(a,n) (*max_element(a,a+n))
#define mxv(v)   (*max_element(v.begin(), v.end()))
#define mne(a,n) (*min_element(a,a+n))
#define mnv(v)   (*min_element(v.begin(), v.end()))
#define SUM(a,n) (accumulate(a,a+n,0))
#define SUMv(v)   (accumulate(v.begin(), v.end(), 0))
#define occurx(v,x) (count(v.begin(), v.end(),x))
#define findx(v,x)  (find(v.begin(), v.end(),x))
#define swap(a,b)  a^=b^=a^=b
#define sgn(x,y) ((x)+eps<(y)?-1:((x)>eps+(y)?1:0))

///I/O
#define input() freopen("in0.txt","r",stdin)
#define output()freopen("out0.txt","w",stdout)
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ppc(x,y) cout<<fixed<<setprecision(y)<<x<<endl


#define IN scanf
#define OUT printf
///    #define SI(a) scanf("%d",&a)
///   #define SL(a) scanf("%lld",&a)
///    #define SD(a) scanf("%lf",&a)
///   #define OI(a) printf("%d",a)
///    #define OL(a) printf("%lld",a)
///    #define OD(a) printf("%lf",a)
///     #define ON() printf("\n")


///Parse
template<typename T>inline string toString(T a){ ostringstream os("");os<<a;return os.str();}
template<typename T>inline ll toLong(T a){ll res;istringstream os(a);os>>res;return res;}
template<typename T>inline int toInt(T a){int res;istringstream os(a);os>>res;return res;}
template<typename T>inline double toDouble(T a){double res;istringstream os(a);os>>res;return res;}
template<typename T>inline vs vs_parse(T str){vs res;string s;istringstream os(str);while(os>>s)res.pb(s);return res;}

///Mathematics
template<typename T>inline T  sqr(T a){return a*a;}
template<typename T>inline T pw(T b,T p){T r=1;if(b==0)return 0;fr(i,0,p)r*=b;return r;}
template< typename T > inline T gcd(T a,T b){a=abs(a);b=abs(b);if(!b) return a;return __gcd(b,a%b);}
template<typename T> inline T lcm(T a,T b){a=abs(a);b=abs(b);return (a/__gcd(a,b))*b;}
template<typename T>inline ull bigmod(T a, T b, T m){if (b == 0)return 1;else if (b % 2 == 0)return sqr(bigmod(a, b / 2, m)) % m;else return (a % m*bigmod(a, b - 1, m)) % m;}
template<typename T> inline T modinv(T n,T mod){return bigmod(n,mod-2,mod);}

///Geometry
template<typename T>inline ull  dist(T A,T B){ull res=(A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);return res;}
template<typename T>inline ll  cross(T A,T B,T C){return (B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y);}
template<typename T>inline double cosangle(T a,T b,T c){double res=a*a+b*b-c*c;res=res/(2*a*b);res=acos(res);return res;}

///Inside grid
template<typename T>inline bool isinside_grid(int R,int C,int ro,int clm){if((R>=0&&R<ro)&&(C>=0&&C<clm))return true;return false;}
template<typename T>inline void print_grid(T GRID,int ro,int clm){fr(i,0,ro){fr(j,0,clm)cout<<GRID[i][j]<<" ";puts("");}}

template<typename T>inline void extended_euclid(T a,T b,T &x,T &y)
{if(!b){x = 1, y = 0  ;return ;}ll xx,yy;extended_euclid(b,a%b,xx,yy);x = yy;y = xx - (a/b)*yy;}
template<typename T>inline pair<ll, pair<ll, ll> > extendedEuclid(ll a, ll b)
{   ll x = 1, y = 0,xLast = 0, yLast = 1,q, r, m, n;
    while(a != 0){q = b / a;r = b % a;m = xLast - q * x;n = yLast - q * y;xLast = x, yLast = y;x = m, y = n;b = a, a = r;}
    return make_pair(b, make_pair(xLast, yLast));
}
///Direction array
int x4[] = {0, 1, 0, -1};
int y4[] = {-1, 0, 1, 0};
int x8[] = { -1, -1, 1, 1, -2, -2, 2, 2 };
int y8[] = { 2, -2, 2, -2, 1, -1, 1, -1 };

///----------------------Main Code-------------------------------------///
#define EPS 1e-9
#define inf 1e18
#define MOD 1000000007

int main()
{
#ifndef ONLINE_JUDGE
    //input();
    //output();
#endif
    fast();
//    clock_t begin, end;
//    double time_spent;
//    begin = clock();
    ll n,x,y,a,b,c,t,q;
    string s;
    //char c;
    //cin>>t;
    while(cin>>n)
    {

    }
//    end = clock();
//    time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
//   cout<<"Time spent = "<<time_spent<<endl;


    return 0;
}




Contest Template-01

Contest Template-01

///    Md.ASADUZZAMAN
///    Dept of ICT
///    MBSTU
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long

#define fr(i,a,b) for(int i=(a);i<(b);i++)
#define rfr(i,a,b) for(int i=(b-1);i>=(a);i--)
#define freach(i, c) for( __typeof( (c).begin() ) i = (c).begin(); i != (c).end(); ++i )
#define rep(i,n) for(int i=0;i<(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define forit(it, s) for(__typeof(s.begin()) it = s.begin(); it != s.end(); it++)


#define PINF INT_MAX
#define MINF INT_MIN
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define mset(a,c) memset(a,c,sizeof a)
#define clr(a) memset(a,0,sizeof a)
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pcc pair<char,char>
#define pic pair<int,char>
#define pci pair<char,int>
#define psi pair<sting,int>
#define pis pair<int,string>
#define ff first
#define ss second
#define vs vector<string>
#define vi vector<int>
#define vll vector<long long>
#define vpi vector<pair<int,int> >
#define vpl vector<pair<long long,long long> >
#define vpcl vector<pair<c,long long> >
#define vpsl vector<pair<string,long long> >

#define qi  queue<int>
#define ql  queue<long>
#define qll queue<long long>
#define PQ priority_queue

#define mpii map<int,int>
#define mpsl map<string,long long>
#define mpci map<char,long long>
#define mpll map<long long,long long>

#define stl set<ll>
#define sts set<string>
/// Bug
#define bug(x) cout<<#x<<": "<<x<<endl
#define bug1(x,y) cout<<#x<<": "<<x<<"  |  "<<#y<<": "<<y<<endl
#define bug2(x,y,z) cout<<#x<<": "<<x<<"  |  "<<#y<<": "<<y<<"  |  "<<#z<<": "<<z<<endl
#define bug3(w,x,y,z) cout<<#w<<": "<<w<<"  |  "<<#x<<": "<<x<<"  |  "<<#y<<": "<<y<<"  |  "<<#z<<": "<<z<<endl
/// Trigonometry
#define pi acos(-1.0)
#define rad(x) (((1.0 * x * pi) / 180.0))
#define deg(x) (((x * 180.0) / (1.0 * pi)))
#define sinr(x) (sin(rad(x)))
#define cosr(x) (cos(rad(x)))
#define tanr(x) (tan(rad(x)))
#define asind(x) (deg((asin(x))))
#define acosd(x) (deg((acos(x))))
#define atand(x) (deg((atan(x))))

///Bit

#define setbiton(x, i) (x |= (1 << i))
#define setbitoff(x, i) (x &= (~(1 << i)))
#define togglebit(x, i) (x ^= (1 << i))
#define checkbiton(x,i)   ((x &(1 << i))!=0)
#define ispow2 (x!=0 && (x&(x-1))==0)
#define countbit(x) __builtin_popcountll((ll)x)
#define countlead(x) __builtin_clzll((ll)x)  ///give wrong ans for zero (0)
#define counttrail(x) __builtin_ctzll((ll)x)  ///give wrong ans for zero (0)
/// Search
#define LB(a,x) (lower_bound(all(a),x)-a.begin()) //  first element in the range [first,last) which does not compare less than val.
#define UB(a,x) (upper_bound(all(a),x)-a.begin()) //  first element in the range [first,last) which compares greater than val.
#define bin_sa(a,n,x) (binary_search(a, a+n,x))
#define bin_sv(v,x) (binary_search(v.begin(), v.end(),x))

/// Algorithm
#define Unique(store) store.resize(unique(store.begin(),store.end())-store.begin())
#define mxe(a,n) (*max_element(a,a+n))
#define mxv(v)   (*max_element(v.begin(), v.end()))
#define mne(a,n) (*min_element(a,a+n))
#define mnv(v)   (*min_element(v.begin(), v.end()))
#define SUM(a,n) (accumulate(a,a+n,0))
#define SUMv(v)   (accumulate(v.begin(), v.end(), 0))
#define occurx(v,x) (count(v.begin(), v.end(),x))
#define findx(v,x)  (find(v.begin(), v.end(),x))
#define swap(a,b)  a^=b^=a^=b
#define sgn(x,y) ((x)+eps<(y)?-1:((x)>eps+(y)?1:0))

///I/O
#define input() freopen("in0.txt","r",stdin)
#define output()freopen("out0.txt","w",stdout)
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ppc(x,y) cout<<fixed<<setprecision(y)<<x<<endl

#define IN scanf
#define OUT printf
///    #define SI(a) scanf("%d",&a)
///   #define SL(a) scanf("%lld",&a)
///    #define SD(a) scanf("%lf",&a)
///   #define OI(a) printf("%d",a)
///    #define OL(a) printf("%lld",a)
///    #define OD(a) printf("%lf",a)
///     #define ON() printf("\n")


#define EPS 1e-9
#define inf 1e18
#define MOD 1000000007
///----------------------Main Code-------------------------------------///


int main()
{
#ifndef ONLINE_JUDGE
    //input();
    //output();
#endif
    fast();
//    clock_t begin, end;
//    double time_spent;
//    begin = clock();
    ll n,x,y,a,b,c,t,q;
    string s;
    //char c;
    //cin>>t;
    while(cin>>n)
    {

    }
//    end = clock();
//    time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
//   cout<<"Time spent = "<<time_spent<<endl;


    return 0;
}



Check Divisibility by prime numbers below 50


Check Divisibility by prime numbers below 50:


A number is divisible by 2 if its last digit is also (i.e. 0,2,4,6 or 8).


A number is divisible by 3 if the sum of its digits is also. Example: 534: 5+3+4=12 and 1+2=3 so 534 is divisible by 3.


A number is divisible by 5 if the last digit is 5 or 0.

Test for divisibility by 7. Double the last digit and subtract it from the remaining leading truncated number. If the result is divisible by 7, then so was the original number. Apply this rule over and over again as necessary. Example: 826. Twice 6 is 12. So take 12 from the truncated 82. Now 82-12=70. This is divisible by 7, so 826 is divisible by 7 also.
There are similar rules for the remaining primes under 50, i.e. 11,13, 17,19,23,29,31,37,41,43 and 47.


Test for divisibility by 11. Subtract the last digit from the remaining leading truncated number. If the result is divisible by 11, then so was the first number. Apply this rule over and over again as necessary.
Example: 19151--> 1915-1 =1914 -->191-4=187 -->18-7=11, so yes, 19151 is divisible by 11.


Test for divisibility by 13. Add four times the last digit to the remaining leading truncated number. If the result is divisible by 13, then so was the first number. Apply this rule over and over again as necessary.
Example: 50661-->5066+4=5070-->507+0=507-->50+28=78 and 78 is 6*13, so 50661 is divisible by 13.


Test for divisibility by 17. Subtract five times the last digit from the remaining leading truncated number. If the result is divisible by 17, then so was the first number. Apply this rule over and over again as necessary.
Example: 3978-->397-5*8=357-->35-5*7=0. So 3978 is divisible by 17.


Test for divisibility by 19. Add two times the last digit to the remaining leading truncated number. If the result is divisible by 19, then so was the first number. Apply this rule over and over again as necessary.
EG: 101156-->10115+2*6=10127-->1012+2*7=1026-->102+2*6=114 and 114=6*19, so 101156 is divisible by 19.


Test for divisibility by 23. 3*23=69, ends in a 9, so ADD. Add 7 times the last digit to the remaining leading truncated number. If the result is divisible by 23, then so was the first number. Apply this rule over and over again as necessary.
Example: 17043-->1704+7*3=1725-->172+7*5=207 which is 9*23, so 17043 is also divisible by 23.


Test for divisibility by 29. Add three times the last digit to the remaining leading truncated number. If the result is divisible by 29, then so was the first number. Apply this rule over and over again as necessary.
Example: 15689-->1568+3*9=1595-->159+3*5=174-->17+3*4=29, so 15689 is also divisible by 29.


Test for divisibility by 31. Subtract three times the last digit from the remaining leading truncated number. If the result is divisible by 31, then so was the first number. Apply this rule over and over again as necessary.
Example: 7998-->799-3*8=775-->77-3*5=62 which is twice 31, so 7998 is also divisible by 31.


Test for divisibility by 37. This is (slightly) more difficult, since it perforce uses a double-digit multiplier, namely eleven. People can usually do single digit multiples of 11, so we can use the same technique still. Subtract eleven times the last digit from the remaining leading truncated number. If the result is divisible by 37, then so was the first number. Apply this rule over and over again as necessary.
Example: 23384-->2338-11*4=2294-->229-11*4=185 which is five times 37, so 23384 is also divisible by 37.


Test for divisibility by 41. Subtract four times the last digit from the remaining leading truncated number. If the result is divisible by 41, then so was the first number. Apply this rule over and over again as necessary.
Example: 30873-->3087-4*3=3075-->307-4*5=287-->28-4*7=0, remainder is zero and so 30873 is also divisible by 41.


Test for divisibility by 43. Now it starts to get really difficult for most people, because the multiplier to be used is 13, and most people cannot recoznise even single digit multiples of 13 at sight. You may want to make a little list of 13*N first. Nevertheless, for the sake of completeness, we will use the same method. Add thirteen times the last digit to the remaining leading truncated number. If the result is divisible by 43, then so was the first number. Apply this rule over and over again as necessary.
Example: 3182-->318+13*2=344-->34+13*4=86 which is recoznisably twice 43, and so 3182 is also divisible by 43.
Update : Someone has pointed out that, since we are working to modulo43, instead of adding factor 13 times the last digit, we can subtract 30 times it, because 13+30=43. Why didn't I think of that!!! :-(


Finally, the Test for divisibility by 47. This too is difficult for most people, because the multiplier to be used is 14, and most people cannot recognize even single digit multiples of 14 at sight. You may want to make a little list of 14*N first. Nevertheless, for the sake of completeness, we will use the same method. Subtract fourteen times the last digit from the remaining leading truncated number. If the result is divisible by 47, then so was the first number. Apply this rule over and over again as necessary.
Example: 34827-->3482-14*7=3384-->338-14*4=282-->28-14*2=0 , remainder is zero and so 34827 is divisible by 47.


Resources and Courtesy:  from Internet

Sunday, October 1, 2017

Searching Algorithm (Binary and Ternary Search) Problem List

Binary Search related problem :

A SPOJ AGGRCOW Aggressive cows

B SPOJ ABCDEF ABCDEF
C SPOJ ANARC05B The Double HeLiX
D SPOJ BOOKS1 Copying Books
E SPOJ AKVQLD03 How to Handle the Fans
F SPOJ DCEPC206 Its a Murder!
G SPOJ EKO Eko
H SPOJ GUESSING Number Guessing Game
I SPOJ HACKRNDM Hacking the random number generator
J SPOJ HORRIBLE Horrible Queries
K SPOJ NOTATRI Not a Triangle
L SPOJ OPCPIZZA Pizzamania
M SPOJ ORDERSET Order statistic set
N SPOJ PATULJCI Snow White and the N dwarfs
O SPOJ PIE Pie
P SPOJ RENT Rent your airplane and make money
Q SPOJ RANGESUM Range Sum
R SPOJ KPPOLY Projections Of A Polygon
S CodeChef K1 Plant Location
T LightOJ 1146 Closest Distance
U LightOJ 1240 Point Segment Distance (3D)
V LightOJ 1043 Triangle Partitioning
W LightOJ 1062 Crossed Ladders
X LightOJ 1072 Calm Down
Y LightOJ 1307 Counting Triangles
Binary Search Related Problem List


Ternary Search related Problem:



A CodeForces 279B Books

B UVALive 2395 Jacquard Circuits
C UVA 11057 Exact Sum
D SPOJ HAMSTER1 Hamster flight
E CodeForces 578C Weakness and Poorness
F CodeForces 200E Tractor College
G CodeForces 774A Amusement Park
H CodeForces 818F Level Generation
I CodeForces 518E Arthur and Questions
J CodeForces 201B Guess That Car!
K CodeForces 185B Mushroom Scientists
L CodeForces 613A Peter and Snow Blower
M UVA 11702 Meltdown
N UVA 11562 Hard Evidence
O UVA 11243 Texas Trip
P UVA 10385 Duathlon
Q CodeChef AMCS03 Race Time!
R SPOJ KOPC12A K12 - Building Construction
S SPOJ MLAND Land for Motorways
T SPOJ MPOLY Polygon
U CodeChef CIELKARA Ciel and Karaoke
V CodeChef CONSESNK Consecutive Snakes
W UVALive 3736 Consanguine Calculations
X UVALive 3752 Containers
Y UVALive 6675 Easy Geometry
Z UVALive 2377 Grand Prix


Tuesday, March 7, 2017

Clap control home system







Hardware and Software Project showcasing

Project Title:   Clap control home system
     
Team name:  MBSTU_Robomaniac

Team members :

o Md. Asaduzzaman
o Md. Juwel Rana
o Md. Foyj Ullah Khan

• Institution  : Mawlana Bhashani Science and Technology University (MBSTU)
• Coach/mentor name :
    Kawsar Ahmed
    Lecturer
    Dept of ICT , MBSTU





Clap control home system:
Abstract:
 Electric switching have become more digitalized. Now people want more easier way to control their electrical equipment. In this case, our clap control system will the best option.
Physical Construction:
Instruments:
·        Arduino Uno
·        Sound sensor (digital output)
·        Relay Module          
 Process:
Connecting Sound Sensor module to Arduino is simple. The Sound sensor has 3 wire leads. One wire is for the signal, one for ground and one for 5v power. The back of the Sound  sensor module shows which wire is S (signal), - (ground), and + (5v).
The ground wire connects to the GND port on the Arduino. The + wire connects to the 5v output on the Arduino. The signal wire connects to A0 on the Arduino so that interrupts can be used. 


Why it is important:
·         In order to prevent wastage of electricity and increase the standard of living our project will be the best.
·         It will increase our utility.
·         It will save electric cost.
Condition:
·         The relay board works on 220V AC .So keep necessary safety measurements.
Error:
·         Sometimes sensor value may be scattered because of the internal frequency of Arduino microcontrollers.
Future implementation:
·         It’s our goal to make it easy to increase utility by using android app and make the project more error free.

Source code:    clap controlled home
References:
(1)
www.google.com , www.instructables.com , www.youtube.com.
(2)
Robot building for beginners –David Cook.



Simple Electrocardiogram (ECG)







                       Hardware and Software Project showcasing

Project Title:   Simple Electrocardiograph & Heart Rate Monitor (ECG)
   
Team name:  MBSTU_Robomaniac

• Team members :

o Md. Asaduzzaman
o Md. Juwel Rana
o Md. Foyj Ullah Khan

• Institution  : Mawlana Bhashani Science and Technology University (MBSTU)
• Coach/mentor name :
    Kawsar Ahmed
    Lecturer
    Dept of ICT , MBSTU





Simple Electrocardiograph & Heart Rate Monitor (ECG):

Abstract:
Heart rate is a very vital health parameter that is directly related to the soundness of the human cardiovascular system. This project describes a technique of measuring the heart rate through a PIC microcontroller. While the heart is beating, it is actually pumping blood throughout the body, and that makes the blood volume inside the finger artery to change too. This fluctuation of blood can be detected through an optical sensing mechanism placed around the fingertip by Pulse Sensor module.
Physical Construction:
Instruments:
Arduino Mega 2560
Pulse Sensor
3 LED
A desktop app to analyze Heart.
Laptop Computer (For measuring ECG graph)
Process:
Connecting the Pulse Sensor Amped module to Arduino is simple. The pulse sensor has 3 wire leads. One wire is for the signal, one for ground and one for 5v power. The back of the pulse sensor module shows which wire is S (signal), - (ground), and + (5v).
The ground wire connects to the GND port on the Arduino. The + wire connects to the 5v output on the Arduino. The signal wire connects to A0 on the Arduino so that interrupts can be used.
Heart rate analyzing:
The Pulse Sensor Cardio Graph application illustrates heart beat information in graphical form. The application displays different heart rate variation graphs: Beats Per Minute (BPM), Inter beat Intervals (IBI), Heart Rate Frequency (Hz), Power Spectral Density (PSD), LF vs HF (Low Frequency vs High Frequency).Fast Fourier Transform is used to determine the Power Spectrum for a data set of heart beats.

Why it is important:
For heart patients, it is the most valuable medical instrument. Incase of regular checkup it can be the most cheapest device to measure his heart condition.
Reference: http://www.slideshare.net/muntasirahmed39/cardiovascular-diseasecvd



Low cost .For regular checkup it needs at least 300 /- BDT per checkup. But this device can monitor our heart every hour for thousands times with free of cost .Just need 1000/- BDT at the beginning.
It will be the best option for not only higher class people but also rural people.
Condition:
We will get better output if the heart of the patients is kept on horizontal axis (where gravity =0)
Error:
Sometimes pulse graph may be scattered because of the internal frequency of Arduino microcontrollers
In real time ECG have used 9 electrodes to measure heart rate but here is only one electrodes .
Future implementation:
It’s our goal to make it easy to measure heart rate through Android by using android app and  make the project more error free.

References:
(1) www.google.com , www.instructables.com , www.youtube.com.
(2) Robot building for beginners –David Cook.


source code and ECG app: Simple ECG