All Possible Increasing Subsequences Lightoj 1085

First of all we will sort all A by non decreasing order and then we can find how many subsequence we can have by building a Binary indexed tree in the base of respective index.

To learn Binary indexed tree : BIT

/// Bismillahir Rahmanir Rahim
/* Mohammad Morsalin
   Dept of ICE, NSTU
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define endl "\n"
#define int long long
#define f0(n) for(int i=0;i<n;i++)
#define ms(x) memset(x,0,sizeof(x))
#define ms2d(x,m,n) memset(x, 0, sizeof(x[0][0]) * m * n)
#define CLR(x) memset(x, -1, sizeof(x))
#define CLR2d(x,m,n) memset(x, -1, sizeof(x[0][0]) * m * n)
#define uniq(vec) vec.resize(distance(vec.begin(),unique(vec.begin(),vec.end())))
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define pi pair<int,int>
#define rep(i,a) for(int i=0; i<a;i++)
#define rep1(i,a,b) for(int i=(a);i<=(b);++i)
#define irep(i,b,a) for(int i=(b);i>=(a);--i)
#define bits(n) __builtin_popcount(n)
#define maxpq priority_queue<int>
#define minpq priority_queue<int, vector<int>, greater<int> >
#define ins insert
#define ALL(v) v.begin(),v.end()
#define highest(x) numeric_limits<x>::max()
#define lowest(x) numeric_limits<x>::min()
#define Inf INFINITY
#define minv(v) *min_element(v.begin(),v.end())
#define maxv(v) *max_element(v.begin(),v.end())
#define fi first
#define se second
#define PI acos(-1)
#define sz(a) (int)a.size();
#define IOS ios::sync_with_stdio(false);

///for debug
vector<string> vec_splitter(string s) {    s += ',';vector<string> res;while(!s.empty()) {res.push_back(s.substr(0, s.find(',')));s = s.substr(s.find(',') + 1);}return res;}
void debug_out( vector<string> __attribute__ ((unused)) args,__attribute__ ((unused)) int idx,__attribute__ ((unused)) int LINE_NUM) { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) { if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";stringstream ss; ss << H;cerr << args[idx] << " = " << ss.str();debug_out(args, idx + 1, LINE_NUM, T...);}
#define XOX
#ifdef XOX
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...) 42
#endif
///debug template ends


int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a);}
typedef tree<pair<int, int>,null_type,less<pair<int, int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
int dx8[] = {0, 0, 1, 1, 1, -1, -1, -1};
int dy8[] = {1,-1, 1, -1, 0, 0, -1, 1};
int dx4[] = {0, 0, 1, -1};
int dy4[] = {1, -1, 0, 0};
const long long MOD = 1000000007;
double sq(double x) {return x*x;}
typedef vector<int> vi;
typedef vector<pair<int,int>> vpii;
template<typename T>inline T Bigmod(T base, T power, T MOD){
    T ret=1;
    while(power)
    {
        if(power & 1)ret=(ret*base)%MOD;
        base=(base*base)%MOD;
        power>>=1;
    }
    return ret;
}
///modular arithmetic
inline void normal(ll &a) { a %= MOD; (a < 0) && (a += MOD); }
inline ll modMul(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a*b)%MOD; }
inline ll modAdd(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a+b)%MOD; }
inline ll modSub(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); a -= b; normal(a); return a; }
inline ll modPow(ll b, ll p) { ll r = 1; while(p) { if(p&1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
inline ll modInverse(ll a) { return modPow(a, MOD-2); }  /// When MOD is prime.
inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }
///modular arithmetic template ends

bool sortinrev(const pair<int,int> &a,
               const pair<int,int> &b)
{
        if(a.fi==b.fi)return a.se>b.se;
       return (a.first < b.first);
}
const int maxn=100005;
int BIT[maxn+5];
int n;
void update(int pos,int val){
    while(pos<=n){
        BIT[pos]+=val;
        BIT[pos]%=MOD;
        pos+=(pos& -pos);
    }
}
int query(int pos){
    int res=0;
    while(pos>0){
        res+=BIT[pos];
        res%=MOD;
        pos-=(pos & -pos);
    }
    return res;
}
///solution
int cs=0;
void solution(){
    ms(BIT);
    scanf("%lld",&n);
    vector<pair<int,int> > vp;
    for(int i=0;i<n;i++){
        int x;
        scanf("%lld",&x);
        vp.pb(mp(x,i+1));
    }
    sort(ALL(vp),sortinrev);
    for(int i=0;i<(int)vp.size();i++){
        int sum =1+query(vp[i].se-1);
        //debug(sum,vp[i].se);
        update(vp[i].se,sum);
    }
    printf("Case %lld: %lld\n",++cs,query(n));
}
signed main()
{
    IOS
    int t;
    t=1;
    //cin>>t;
    scanf("%lld",&t);
    while(t--){
        solution();
    }
    return 0;
}
///Alhamdulillah

Binary Simulation Lightoj 1080

This is a pretty basic problem of range update and point query, we are solving this problem by Binary Indexed Tree data structure. Learn it from here: BIT

/// Bismillahir Rahmanir Rahim
/* Mohammad Morsalin
   Dept of ICE, NSTU
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define endl "\n"
#define int long long
#define f0(n) for(int i=0;i<n;i++)
#define ms(x) memset(x,0,sizeof(x))
#define ms2d(x,m,n) memset(x, 0, sizeof(x[0][0]) * m * n)
#define CLR(x) memset(x, -1, sizeof(x))
#define CLR2d(x,m,n) memset(x, -1, sizeof(x[0][0]) * m * n)
#define uniq(vec) vec.resize(distance(vec.begin(),unique(vec.begin(),vec.end())))
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define pi pair<int,int>
#define rep(i,a) for(int i=0; i<a;i++)
#define rep1(i,a,b) for(int i=(a);i<=(b);++i)
#define irep(i,b,a) for(int i=(b);i>=(a);--i)
#define bits(n) __builtin_popcount(n)
#define maxpq priority_queue<int>
#define minpq priority_queue<int, vector<int>, greater<int> >
#define ins insert
#define ALL(v) v.begin(),v.end()
#define highest(x) numeric_limits<x>::max()
#define lowest(x) numeric_limits<x>::min()
#define Inf INFINITY
#define minv(v) *min_element(v.begin(),v.end())
#define maxv(v) *max_element(v.begin(),v.end())
#define fi first
#define se second
#define PI acos(-1)
#define sz(a) (int)a.size();
#define IOS ios::sync_with_stdio(false);

///for debug
vector<string> vec_splitter(string s) {    s += ',';vector<string> res;while(!s.empty()) {res.push_back(s.substr(0, s.find(',')));s = s.substr(s.find(',') + 1);}return res;}
void debug_out( vector<string> __attribute__ ((unused)) args,__attribute__ ((unused)) int idx,__attribute__ ((unused)) int LINE_NUM) { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) { if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";stringstream ss; ss << H;cerr << args[idx] << " = " << ss.str();debug_out(args, idx + 1, LINE_NUM, T...);}
#define XOX
#ifdef XOX
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...) 42
#endif
///debug template ends


int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a);}
typedef tree<pair<int, int>,null_type,less<pair<int, int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
int dx8[] = {0, 0, 1, 1, 1, -1, -1, -1};
int dy8[] = {1,-1, 1, -1, 0, 0, -1, 1};
int dx4[] = {0, 0, 1, -1};
int dy4[] = {1, -1, 0, 0};
const long long MOD = 1000000007;
double sq(double x) {return x*x;}
typedef vector<int> vi;
typedef vector<pair<int,int>> vpii;
template<typename T>inline T Bigmod(T base, T power, T MOD){
    T ret=1;
    while(power)
    {
        if(power & 1)ret=(ret*base)%MOD;
        base=(base*base)%MOD;
        power>>=1;
    }
    return ret;
}
///modular arithmetic
inline void normal(ll &a) { a %= MOD; (a < 0) && (a += MOD); }
inline ll modMul(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a*b)%MOD; }
inline ll modAdd(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a+b)%MOD; }
inline ll modSub(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); a -= b; normal(a); return a; }
inline ll modPow(ll b, ll p) { ll r = 1; while(p) { if(p&1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
inline ll modInverse(ll a) { return modPow(a, MOD-2); }  /// When MOD is prime.
inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }
///modular arithmetic template ends

bool sortinrev(const pair<int,int> &a,
               const pair<int,int> &b)
{
       return (a.first > b.first);
}

///solution
int BIT[100005];
int n;
void update(int i,int val){
    while(i<=n){
        BIT[i]+=val;
        i+=(i&-i);
    }
}
int query(int i){
    int sum=0;
    while(i>0){
        sum+=BIT[i];
        i-=(i&-i);
    }
    return sum;
}
int cs=0;
void solution(){
    char s[100005];
    int q;
    scanf("%s%lld",s,&q);
    //cout << s << endl;
    n=strlen(s);
    ms(BIT);
    //cout << "Case "<< ++cs << ":\n";
    printf("Case %lld:\n",++cs);
    while(q--){
        getchar();
        char ch;
        //cin>>ch;
        scanf("%c",&ch);
        if(ch=='I'){
            int i,j;
            //cin>>i>>j;
            scanf("%lld%lld",&i,&j);
            update(i,1);
            update(j+1,-1);
        }
        else if(ch=='Q'){
            int i;
            //cin>>i;
            scanf("%lld",&i);
            int x=query(i);
            char ans;
            if(x%2==0){
                ans=s[i-1];
            }
            else{
                if(s[i-1]=='0')ans='1';
                else ans='0';
            }
            printf("%c\n",ans);
        }
    }
}
signed main()
{
    //IOS
    int t;
    t=1;
    //cin>>t;
    scanf("%lld",&t);
    while(t--){
        solution();
    }
    return 0;
}
///Alhamdulillah

Sum of Factorials Lightoj 1189

 In this problem we will pre calculate all the factorial values upto 20(because the constraint). Then greedily we will just check can we take the value of factorial of any number.

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define f0(n) for(int i=0;i<n;i++)
#define ms(x) memset(x,0,sizeof(x))
#define ins insert
#define IOS ios::sync_with_stdio(false);
using namespace std;
int main()
{
    IOS
    int t;
    cin>>t;
    ll fact[21];
    fact[0] = 1;
    for(int i=1;i<=20;i++)
    {
        fact[i] = fact[i-1]*i;
        //cout << fact[i] << endl;
    }
    for(int tc=1;tc<=t;tc++)
    {
        ll n;
        cin>>n;
        vector<int>vec;
        for(int i=20;i>=0;i--)
        {
            if(fact[i]<=n)
            {
                n-=fact[i];
                vec.pb(i);
            }
            if(n==0) break;
        }
        sort(vec.begin(),vec.end());
        cout << "Case "<< tc << ": ";
        if(n!=0) {cout <<"impossible\n";continue;}
        for(int i=0;i<vec.size();i++)
        {
            if(i>0 && i<vec.size())
                cout << "+";
            cout << vec[i] << "!";
        }
        cout << endl;
    }
    return 0;
}

Conquering Keokradong Lightoj 1048

 we will check which value is most satisfied in the given number of nights k. For this purpose we will do binary search from highest distance of two campsites to sum of distance.

/// Bismillahir Rahmanir Rahim
/* Mohammad Morsalin
   Dept of ICE, NSTU
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ll long long
#define pb push_back
#define mp make_pair
//#define endl "\n"
#define int long long
#define f0(n) for(int i=0;i<n;i++)
#define ms(x) memset(x,0,sizeof(x))
#define ms2d(x,m,n) memset(x, 0, sizeof(x[0][0]) * m * n)
#define uniq(vec) vec.resize(distance(vec.begin(),unique(vec.begin(),vec.end())))
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define pi pair<int,int>
#define tc(t) int t;scanf("%lld",&t);while(t--)
#define bits(n) __builtin_popcount(n)
#define maxpq priority_queue<int>
#define minpq priority_queue<int, vector<int>, greater<int> >
#define ins insert
#define ALL(v) v.begin(),v.end()
#define highest(x) numeric_limits<x>::max()
#define lowest(x) numeric_limits<x>::min()
#define Inf INFINITY
#define minv(v) *min_element(v.begin(),v.end())
#define maxv(v) *max_element(v.begin(),v.end())
#define fi first
#define se second
#define PI acos(-1)
#define sz(a) (int)a.size();
#define IOS ios::sync_with_stdio(false);
using namespace std;
int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a);}
typedef tree<pair<int, int>,null_type,less<pair<int, int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
int dx8[] = {0, 0, 1, 1, 1, -1, -1, -1};
int dy8[] = {1,-1, 1, -1, 0, 0, -1, 1};
int dx4[] = {0, 0, 1, -1};
int dy4[] = {1, -1, 0, 0};
const long long MOD = 1000000007;
double sq(double x) {return x*x;}
template<typename T>inline T Bigmod(T base, T power, T MOD){
    T ret=1;
    while(power)
    {
        if(power & 1)ret=(ret*base)%MOD;
        base=(base*base)%MOD;
        power>>=1;
    }
    return ret;
}

bool sortinrev(const pair<int,int> &a,
               const pair<int,int> &b)
{
       return (a.first > b.first);
}
signed main()
{
    IOS
    int tn=0;
    tc(t){
        int n,k;
        scanf("%lld%lld",&n,&k);
        int arr[n+1];
        int sum=0,max_val=0;
        f0(n+1){
            scanf("%lld",&arr[i]);
            sum+=arr[i];
            max_val=max(max_val,arr[i]);
            //cout << arr[i]<< endl;
        }
        int low=max_val;
        int high=sum;
        int mid;
        int ans=high;
        while(low<=high){
            mid=(low+high)/2;
            int time=0,pre=0;
           // cout << mid;
            for(int i=0;i<n+1;i++){
                pre+=arr[i];
                if(pre>mid){
                    time++;
                    pre=arr[i];
                }
            }
           // cout << " "<< time << endl;
            if(time<=k){
                high=mid-1;
                ans=mid;
            }
            else{
                low=mid+1;
            }
        }
        printf("Case %lld: %lld\n",++tn,ans);
        int pre=0;
        int nt=0;
        for(int i=0;i<n+1;i++){
            if(pre+arr[i]>ans){
                printf("%lld\n",pre);
                pre=0;
                i--;
                nt++;
            }
            else if(pre+arr[i]==ans){
                printf("%lld\n",pre+arr[i]);
                pre=0;
                nt++;
            }
            else if(k-nt==(n-i)){
                printf("%lld\n",pre+arr[i]);
                pre=0;
                nt++;
            }
            else pre+=arr[i];
        }
    }
    return 0;
}
///Alhamdulillah

Neighbor House Lightoj 1047

 In this problem we will put a color to a cell and check different colors to the adjacent cells of it.

So, we will try every possible color for every cell. It will be dp solution. we will use a dp array to store previously getting cost for specific color in each cell. 

States: color choice, index of the cell.

Transition: if index i has a color, then its adjacent cell will be different color.

 /// Bismillahir Rahmanir Rahim
/* Mohammad Morsalin
   Dept of ICE, NSTU
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define f0(n) for(int i=0;i<n;i++)
#define ms(x) memset(x,0,sizeof(x))
#define CLR(x) memset(x, -1, sizeof(x))
#define uniq(vec) vec.resize(distance(vec.begin(),unique(vec.begin(),vec.end())))
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define pi pair<int,int>
#define rep(i,a) for(int i=0; i<a;i++)
#define rep1(i,a,b) for(int i=(a);i<=(b);++i)
#define irep(i,b,a) for(int i=(b);i>=(a);--i)
#define bits(n) __builtin_popcount(n)
#define maxpq priority_queue<int>
#define minpq priority_queue<int, vector<int>, greater<int> >
#define ins insert
#define ALL(v) v.begin(),v.end()
#define highest(x) numeric_limits<x>::max()
#define lowest(x) numeric_limits<x>::min()
#define Inf INFINITY
#define minv(v) *min_element(v.begin(),v.end())
#define maxv(v) *max_element(v.begin(),v.end())
#define fi first
#define se second
#define PI acos(-1)
#define sz(a) (int)a.size();
#define IOS ios::sync_with_stdio(false);

///for debug
vector<string> vec_splitter(string s) {    s += ',';vector<string> res;while(!s.empty()) {res.push_back(s.substr(0, s.find(',')));s = s.substr(s.find(',') + 1);}return res;}
void debug_out( vector<string> __attribute__ ((unused)) args,__attribute__ ((unused)) int idx,__attribute__ ((unused)) int LINE_NUM) { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) { if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";stringstream ss; ss << H;cerr << args[idx] << " = " << ss.str();debug_out(args, idx + 1, LINE_NUM, T...);}
#define XOX
#ifdef XOX
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...) 42
#endif
///debug template ends


int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a);}
int lcm(int a,int b) {return (a*b)/gcd(a,b);}
int dx8[] = {0, 0, 1, 1, 1, -1, -1, -1};
int dy8[] = {1,-1, 1, -1, 0, 0, -1, 1};
int dx4[] = {0, 0, 1, -1};
int dy4[] = {1, -1, 0, 0};
const long long MOD = 1000000007;
double sq(double x) {return x*x;}
typedef vector<int> vi;
typedef vector<pair<int,int>> vpii;
template<typename T>inline T Bigmod(T base, T power, T MOD){
    T ret=1;
    while(power)
    {
        if(power & 1)ret=(ret*base)%MOD;
        base=(base*base)%MOD;
        power>>=1;
    }
    return ret;
}
///modular arithmetic
inline void normal(ll &a) { a %= MOD; (a < 0) && (a += MOD); }
inline ll modMul(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a*b)%MOD; }
inline ll modAdd(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a+b)%MOD; }
inline ll modSub(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); a -= b; normal(a); return a; }
inline ll modPow(ll b, ll p) { ll r = 1; while(p) { if(p&1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
inline ll modInverse(ll a) { return modPow(a, MOD-2); }  /// When MOD is prime.
inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }
///modular arithmetic template ends

bool sortinrev(const pair<int,int> &a,
               const pair<int,int> &b)
{
       return (a.first > b.first);
}
const int maxn=22;
int cost[maxn][3];
int n;
///solution
int recur(char ch,int i){
   // debug(ch,i);
    if(i==n)return 0;
    if(ch=='R'){
        return min(cost[i][1]+recur('G',i+1),cost[i][2]+recur('B',i+1));
    }
    if(ch=='G'){
        return min(cost[i][0]+recur('R',i+1),cost[i][2]+recur('B',i+1));
    }
    if(ch=='B'){
        return min(cost[i][0]+recur('R',i+1),cost[i][1]+recur('G',i+1));
    }
    else{
        return min(cost[i][0]+recur('R',i+1),min(cost[i][1]+recur('G',i+1),
            cost[i][2]+recur('B',i+1)));
    }
}
int tc=0;
void solution(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>cost[i][0]>>cost[i][1]>>cost[i][2];
    }
    cout << "Case "<<++tc << ": "<< recur('x',0)<<endl;
}
signed main()
{
    IOS
    #ifndef ONLINE_JUDGE
        freopen ("input.txt","r",stdin);
        freopen ("output.txt","w",stdout);
    #endif
    int t;
    t=1;
    cin>>t;
    while(t--){
        solution();
    }
    return 0;
}
///Alhamdulillah

Triangle Partitioning Lightoj 1043

 We know that,

Area of triangle ABC=sqrt(s*(s-ab)*(s-ac)*(s-bc));

so, we can find the height of the triangle by area=1/2 * base*height

Then we will find the position of DE by doing binary search. Then we will find the Distance A to D. 

 /// Bismillahir Rahmanir Rahim
/* Mohammad Morsalin
   Dept of ICE, NSTU
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ll long long
#define pb push_back
#define mp make_pair
#define endl "\n"
#define int long long
#define f0(n) for(int i=0;i<n;i++)
#define ms(x) memset(x,0,sizeof(x))
#define ms2d(x,m,n) memset(x, 0, sizeof(x[0][0]) * m * n)
#define uniq(vec) vec.resize(distance(vec.begin(),unique(vec.begin(),vec.end())))
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define pi pair<int,int>
#define tc(t) int t;cin>>t;while(t--)
#define bits(n) __builtin_popcount(n)
#define maxpq priority_queue<int>
#define minpq priority_queue<int, vector<int>, greater<int> >
#define ins insert
#define ALL(v) v.begin(),v.end()
#define highest(x) numeric_limits<x>::max()
#define lowest(x) numeric_limits<x>::min()
#define Inf INFINITY
#define minv(v) *min_element(v.begin(),v.end())
#define maxv(v) *max_element(v.begin(),v.end())
#define fi first
#define se second
#define PI acos(-1)
#define sz(a) (int)a.size();
#define IOS ios::sync_with_stdio(false);
using namespace std;
int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a);}
typedef tree<pair<int, int>,null_type,less<pair<int, int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
int dx8[] = {0, 0, 1, 1, 1, -1, -1, -1};
int dy8[] = {1,-1, 1, -1, 0, 0, -1, 1};
int dx4[] = {0, 0, 1, -1};
int dy4[] = {1, -1, 0, 0};
const long long MOD = 1000000007;
double sq(double x) {return x*x;}
template<typename T>inline T Bigmod(T base, T power, T MOD){
    T ret=1;
    while(power)
    {
        if(power & 1)ret=(ret*base)%MOD;
        base=(base*base)%MOD;
        power>>=1;
    }
    return ret;
}

bool sortinrev(const pair<int,int> &a,
               const pair<int,int> &b)
{
       return (a.first > b.first);
}
double const range=1e-10;

signed main()
{
    IOS
    int tn=0;
    tc(t){

        double ab,ac,bc,rat;
        cin>>ab>>ac>>bc>>rat;
        double s=(ab+bc+ac)/2;
        double ABC=sqrt(s*(s-ab)*(s-ac)*(s-bc));
        double theta=asin(ABC/(ab*bc));
        double highet=(ABC*2)/bc;
        double DEBC=ABC/(rat+1);
        double ADE=(ABC-DEBC);
        double low=0,high=bc,H=0,de;
        while(fabs(highet-H)>range){
            de=(low+high)/2;
            H=((2*ADE)/de)+((2*DEBC)/(de+bc));
            if(H>highet+range) low=de;
            else high = de;
        }
        double ad=(ADE/(de*sin(theta)));
        cout << "Case "<< ++tn << ": ";
        cout << fixed<<setprecision(10) << ad << endl;
       // printf("Case %d: %0.10lf\n",++tn,ad);
    }
    return 0;
}
///Alhamdulillah

Circle in Square Lightoj 1022

 The equation used in this problem is:

Shaded area= area of the Square - Area of the circle

#include<iomanip>
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    int t,i;
    cin>>t;
    for(i=1;i<=t;i++){
        double r,pi,ca,sa,ra;
        cin>>r;
        pi=2*acos(0.0);
       ca=pi*(r*r);
       sa=(2*r)*(2*r);
       ra=sa-ca;
        cout<<"Case "<<i<<": "<<fixed<<setprecision(2)<<ra<<endl;
}
    return 0;
}

Hex-a-bonacci Lightoj 1006

This problem is pretty easy, it only requires  memoization to solve.For this purpose we will use an array and save previous solved subproblems rather than call it again.

Codes:

#include <stdio.h>
#include <iostream>
using namespace std;
long long t;
long long a;
long long b;
long long c;
long long d;
long long e;
long long f;
long long n;
long long x[10005];
int fn( int n ) {
        for (int i = 0; i <= n; i++) {
            if( i == 0 ) {
                x[i] = a;
            continue;
            }
            if( i == 1 ) {
            x[i] = b;
            continue;
            }
            if( i == 2 ) {
            x[i] = c;
            continue;}
            if( i == 3 ) {
            x[i] = d;
            continue;}
            if( i == 4 ) {
            x[i] = e;
            continue;}
            if( i == 5 ) {
                x[i] = f;
            continue;

        }

        x[i] = x[i-1] + x[i-2] + x[i-3] + x[i-4] + x[i-5] + x[i-6];

        x[i] = x[i] % 10000007;

}

return x[n];

}
int main()
{
    long long ans;
    cin >> t;
    for (long long i = 1; i <= t; i++) {
        cin >> a;
        cin >> b;
        cin >> c;
        cin >> d;
        cin >> e;
        cin >> f;
        cin >> n;
        ans = fn(n);
        ans = ans % 10000007;
        cout << "Case "<< i <<": "<< ans << endl;
}}

Rooks Lightoj 1005

 In this problem if number of rooks(k) is greater than the number of rows(n) then the answer is 0. Because we can't put k rooks in n safe position if there has any row and col is common for any rooks.

To doing dp we will check if you put a rook in specific row and col what will happen? and then if we don't take it what will happen. so,

states: current row, current col, number of rooks left.

Transition: Will put and won't put on this scope.

We can solve this problem with recursive manner hence constraint doesn't have to solve with Memoization. 

Codes:

/// Bismillahir Rahmanir Rahim
/* Mohammad Morsalin
   Dept of ICE, NSTU
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define f0(n) for(int i=0;i<n;i++)
#define ms(x) memset(x,0,sizeof(x))
#define CLR(x) memset(x, -1, sizeof(x))
#define uniq(vec) vec.resize(distance(vec.begin(),unique(vec.begin(),vec.end())))
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define pi pair<int,int>
#define rep(i,a) for(int i=0; i<a;i++)
#define rep1(i,a,b) for(int i=(a);i<=(b);++i)
#define irep(i,b,a) for(int i=(b);i>=(a);--i)
#define bits(n) __builtin_popcount(n)
#define maxpq priority_queue<int>
#define minpq priority_queue<int, vector<int>, greater<int> >
#define ins insert
#define ALL(v) v.begin(),v.end()
#define highest(x) numeric_limits<x>::max()
#define lowest(x) numeric_limits<x>::min()
#define Inf INFINITY
#define minv(v) *min_element(v.begin(),v.end())
#define maxv(v) *max_element(v.begin(),v.end())
#define fi first
#define se second
#define PI acos(-1)
#define sz(a) (int)a.size();
#define IOS ios::sync_with_stdio(false);

///for debug
vector<string> vec_splitter(string s) {    s += ',';vector<string> res;while(!s.empty()) {res.push_back(s.substr(0, s.find(',')));s = s.substr(s.find(',') + 1);}return res;}
void debug_out( vector<string> __attribute__ ((unused)) args,__attribute__ ((unused)) int idx,__attribute__ ((unused)) int LINE_NUM) { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) { if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";stringstream ss; ss << H;cerr << args[idx] << " = " << ss.str();debug_out(args, idx + 1, LINE_NUM, T...);}
#define XOX
#ifdef XOX
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...) 42
#endif
///debug template ends


int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a);}
int lcm(int a,int b) {return (a*b)/gcd(a,b);}
int dx8[] = {0, 0, 1, 1, 1, -1, -1, -1};
int dy8[] = {1,-1, 1, -1, 0, 0, -1, 1};
int dx4[] = {0, 0, 1, -1};
int dy4[] = {1, -1, 0, 0};
const long long MOD = 1000000007;
double sq(double x) {return x*x;}
typedef vector<int> vi;
typedef vector<pair<int,int>> vpii;
template<typename T>inline T Bigmod(T base, T power, T MOD){
    T ret=1;
    while(power)
    {
        if(power & 1)ret=(ret*base)%MOD;
        base=(base*base)%MOD;
        power>>=1;
    }
    return ret;
}
///modular arithmetic
inline void normal(ll &a) { a %= MOD; (a < 0) && (a += MOD); }
inline ll modMul(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a*b)%MOD; }
inline ll modAdd(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a+b)%MOD; }
inline ll modSub(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); a -= b; normal(a); return a; }
inline ll modPow(ll b, ll p) { ll r = 1; while(p) { if(p&1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
inline ll modInverse(ll a) { return modPow(a, MOD-2); }  /// When MOD is prime.
inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }
///modular arithmetic template ends

bool sortinrev(const pair<int,int> &a,
               const pair<int,int> &b)
{
       return (a.first > b.first);
}
int tc=0;
///solution
ll cur(ll n,ll m, ll k){
    if(k>n || k>m)return 0;
    if(k==0)return 1;
    if(m==1)return n;
    return n*cur(n-1,m-1,k-1)+cur(n,m-1,k);
}
void solution(){
    ll n,k;
    cin>>n>>k;
    cout << "Case "<<++tc<< ": "<< cur(n,n,k)<< endl;
}
signed main()
{
    IOS
    #ifndef ONLINE_JUDGE
        freopen ("input.txt","r",stdin);
        freopen ("output.txt","w",stdout);
    #endif
    int t;
    t=1;
    cin>>t;
    while(t--){
        solution();
    }
    return 0;
}
///Alhamdulillah