LOJ-1328 :: A Gift from the Setter

//Probelm link>>http://lightoj.com/volume_showproblem.php?problem=1328


#include <bits/stdc++.h>
#define ll long long int
#define mod 1000007
using namespace std ;

long long GetDiffSum(long long int a[], int n )
{
    long long int  sum=0 ,ans=0 ;
    int i, j;
    for (i=0 ; i<n ; i++) sum=sum+a[i] ;
    j=n-1 ;
    for (i=0 ; i<n ; i++)
    {
        sum=sum-a[i] ;
        ans=ans+ abs( (a[i]*j )-sum) ;
        j-- ;
    }
   return ans ;
}

int main ()
{
    ll k , c , n , t ,it=0 ,i , x  , a[100004];

    cin>>t ;
    while (it<t)
    {
        it++ ;
        memset(a,0,sizeof (a)) ;
        cin>>k>>c>>n>>a[0] ;

        for (i=1 ; i<n ; i++)
        {
            a[i]= ( (k*a[i-1] ) %mod + c) % mod ;

        }
         sort(a , a+n) ;
         x= GetDiffSum ( a , n ) ;
         cout<<"Case "<<it<<": "<<x<<endl ;

    }

    return 0 ;
}

LOJ-1072 :: Calm Down

//Problem link>>http://lightoj.com/volume_showproblem.php?problem=1072

#include <bits/stdc++.h>
#define pi 2.0*acos(0.0)
#define pre setprecision(10)

using namespace std ;
int main ()
{
    int t , i  ;
    cin>>t ;
    for (i=1 ; i<=t ; i++)
    {
        double x , n , R ,r ;
        cin>>R>>n ;
        x=sin(pi/n) ;
        r=(x*R)/(1+x) ;
        cout<<pre<<"Case "<<i<<": "<<r<<endl ;
    }

    return 0 ;
}

LOJ-1062 :: Crossed Ladders

//Problem link>>http://lightoj.com/volume_showproblem.php?problem=1062

#include <bits/stdc++.h>
#define eps 1e-7
using namespace std ;

 double x , y ,c ,low ,high ,mid ,p,q ,x1,x2 ;

double call (double n)
{
    p=sqrt(y*y-n*n) ;
    q=sqrt(x*x-n*n) ;

    x1=(n*c)/p ;
    x2=(n*c)/q ;

    return x1+x2 ;
}

int main ()
{
    int t , i ,it=0 ;
    cin>>t ;
    while (it<t)
    {
        it++ ;
        cin>>x>>y>>c ;
        low=0.0 ;
        high=min(x,y)*1.0 ;

         while (fabs(low-high)>eps)
         {
             mid=(low+high)/2.0 ;
             if (call(mid)<mid) low=mid;
             else if (call(mid)>mid) high=mid  ;
         }
         cout<<"Case "<<it<<": " ;
         cout<<setprecision(10)<<low<<endl ;
 
    }

    return 0 ;
}

LOJ-1138 :: Trailing Zeroes (III)

//Problem link>>http://lightoj.com/volume_showproblem.php?problem=1138


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

int rez (int x)
{
    int sum=0 ;
    while (x!=0)
    {
        x=x/5 ;
        sum+=x  ;
    }
    return sum ;
}

int n ;
int go ()
{
    int low=0 ,high=1000000000 ,mid ,ans=0 ;
    while (low<=high)
    {
        mid=(low+high)/2 ;
        if (rez(mid) < n) low=mid+1 ;
        else if (rez(mid) > n) high = mid-1 ;
        else
        {
            ans =mid ;
            high=mid-1;
        }
    }
    return ans ;
}

int main ()
{
    int cas, i ,ret ;
    cin>>cas ;
    for (i=1 ;i <=cas ; i++)
    {
        cin>>n ;
         ret=go () ;

        if (ret==0) cout<<"Case "<<i<<": "<<"impossible"<<endl ;
        else cout<<"Case "<<i<<": "<<ret<<endl ;
    }

    return 0 ;
}

LOJ-1088 :: Points in Segments

//Problem link>>http://lightoj.com/volume_showproblem.php?problem=1088


#include <bits/stdc++.h>
using namespace std ;
int main ()
{
    int t , it , i ,n ,q ,a[100005] ,x ,y ,low ,up ;

     scanf ("%d",&t) ;
    for (it=1 ; it<=t ; it++)
    {
       scanf ("%d %d",&n , &q) ;
        for (i=0 ; i<n ; i++) scanf ("%d",&a[i]) ;

       printf ("Case %d:\n",it) ;
        for (i=1 ; i<=q ; i++)
        {
            scanf ("%d %d",&x,&y) ;
            low=lower_bound(a, a+n ,x)-a ;
            up=upper_bound(a, a+n ,y)-a ;
            int ans=up-low ;

           printf ("%d\n",ans) ;

        }

    }

    return 0 ;
}

LOJ-1189 :: Sum of Factorials

//Problem link>>http://www.lightoj.com/volume_showproblem.php?problem=1189


#include <bits/stdc++.h>
#define mx 1000000000000000000

  long long int  a[100] , i ,fact=1 , n ;

using namespace std ;
int main ()
{
      map<long long int , long long int> mp ;

      int t , it=0 , y ;

    for (i=1 ; fact<=mx ; i++)
    {
        fact=fact*i ;
        a[i]=i ;
        mp[i]=fact ;
        y=i ;
    }
    mp[0]=1 ;
    a[0]=0 ;

    cin>>t ;
    while (it<t)
    {
        it++ ;
        cin>>n ;
        vector<long long int>v ;

        int p=0 , ny=y ;
        while (n)
        {
           int k =0 ;
            for (i=0 ; i<ny ; i++)
            {
                if (mp[i]>n)  break  ;
                k=i ;
            }
             v.push_back(k) ;
             ny=k ;
             n=n-mp[k] ;

             if (n>mp[k])
             {
                 p=1 ; break ;
             }
        }
        reverse (v.begin() , v.end()) ;

        cout<<"Case "<<it<<": " ;
       if (p==0)
       {
            for (i=0 ; i<v.size() ; i++)
            {
                if (i==0) printf ("%lld!",v[i]) ;
                else printf ("+%lld!",v[i]) ;
            }
            cout<<endl ;
       }

        else cout<<"impossible"<<endl ;

    }

    return 0 ;
}

LOJ-1043 :: Triangle Partitioning

#include <bits/stdc++.h>
using namespace std ;
int main ()
{
    int  t ,it ;
    cin>>t ;
    for (it=1 ; it<=t ; it++)
    {
        double a,b,c, r ,s ,R,p,q ,d ;
        cin>>a>>b>>c>>r ;

        s=(a+b+c)/2 ;
        p=sqrt(s*(s-a)*(s-b)*(s-c)) ;
        q= (p*r)/(1+r)  ;
        d= sqrt( (q/p)*a*a) ;
 
       printf ("Case %d: %.10lf\n",it , d) ;

    }

    return 0 ;
}

LOJ-1433 :: Minimum Arc Distance

#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
int main ()
{
    double x1,x2,x3,y1,y2,y3 ,a,b,c ,C ,s ;
    int i ,t ;
    cin>>t;

    for (i=1 ; i<=t ; i++)
    {
        cin>>x1>>y1>>x2>>y2>>x3>>y3 ;
        a=sqrt((x1-x3)*(x1-x3)+(y1-y3)*(y1-y3) ) ;
        b=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2) ) ;
        c=sqrt((x2-x3)*(x2-x3)+(y2-y3)*(y2-y3) ) ;

       C=acos( (a*a+b*b-c*c)/(2.0*a*b) ) ;
       s=b*C ;
       printf ("Case %d: %.10lf\n",i,s) ;
    }

    return 0 ;
}

LOJ-1331 :: Agent J

#include <iostream>
#include <math.h>
#include <cstdio>
using namespace std ;
int main ()
{
     double r1,r2,r3 ,a,b,c ,A,B,C ,p ,s ,s1,a1,a2,a3 ,rs  ;
    int i , t , it ;
    cin>>t ;

    for (it=1 ; it<=t ; it++)
    {
        cin>>r1>>r2>>r3 ;
        a=r1 + r2 ;
        b=r2+ r3 ;
        c=r3 + r1 ;

        A=acos((b*b+c*c-a*a)/(2.0*b*c)) ;
        B=acos((a*a+c*c-b*b)/(2.0*a*c)) ;
        C=acos((a*a+b*b-c*c)/(2.0*a*b)) ;

        a1=(0.5)*r1*r1*B ;
        a2=(0.5)*r2*r2*C ;
        a3=(0.5)*r3*r3*A ;
        s1=a1+a2+a3 ;

        s=(a+b+c)/2.0 ;
        p=sqrt(s*(s-a)*(s-b)*(s-c)) ;

        rs=p-s1 ;
     printf ("Case %d: %0.10lf\n",it,rs) ;

    }

    return 0 ;
}

LOJ-1305 :: Area of a Parallelogram

#include <iostream>
#include <cstdio>
#include <math.h>
using namespace std ;
int main ()
{
     double h,k , x1,x2,x3,x4,y1,y2,y3,y4,s,n,a,c ,b ;
     int t,i ,it=1;
    cin>>t ;

    while (it<=t )
    {
        cin>>x1>>y1>>x2>>y2>>x3>>y3 ;

        h=(x1+x3)/2.00 ;
        k=(y1+y3)/2.00 ;

        x4=2.00*h-x2 ;
        y4=2.00*k-y2 ;

        a= 1.0*sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) ) ;
        b= 1.0*sqrt((x1-x3)*(x1-x3) + (y1-y3)*(y1-y3) ) ;
        c=1.0* sqrt((x2-x3)*(x2-x3) + (y2-y3)*(y2-y3) ) ;

        s= (a+b+c)/2.00 ;
        n=2.0*sqrt(s*(s-a)*(s-b)*(s-c) ) ;
        if (n<0) n=(-1.0)*n ;

        printf ("Case %d: %.0lf %.0lf %.0lf\n",it,x4,y4,n) ;
        it++ ;
    }

    return 0 ;
}

LOJ-1006 :: Hex-a-bonacci

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

 long long int dp[10002] ,vis[10002] ;
int a, b, c, d, e, f ,i ;

long long int fn( int n )
{
    if( n == 0 ) return a;
    if( n == 1 ) return b;
    if( n == 2 )  return c;
    if( n == 3 ) return d;
    if( n == 4 ) return e;
    if( n == 5 ) return f;

    if (vis[n] != -1) return dp[n] ;
    else vis[n]=1 ;

     return dp[n]=( ( (fn(n-1) % 10000007) + (fn(n-2)%10000007) + (fn(n-3)%10000007) + (fn(n-4)%10000007)+(fn(n-5)%10000007)+(fn(n-6)%10000007) )%10000007 ) ;
   }

int main()
 {
    int n, caseno = 0, cases;
    scanf("%d", &cases);

    while( cases-- )
        {
                 memset (vis,-1,sizeof (vis)) ;

        scanf("%d %d %d %d %d %d %d", &a, &b, &c, &d, &e, &f, &n);
        printf("Case %d: %lld\n", ++caseno,   fn(n)% 10000007);
    }
    return 0;
}

LOJ-1374 :: Confusion in the Problemset

#include <bits/stdc++.h>
using namespace std ;
int a[1000009] ;
int main ()
{
    int t , n , i , j  ,p ;
    cin>>t ;
    for (j=1 ; j<=t ;j++)
    {
        memset(a,0,sizeof (a)) ;
        cin>>n ;
        for (i=1 ; i<=n ; i++)
        {
             cin>>p ;
             a[p]++ ;
        }

        int flag =0 ;
        for (i=1 ; i<=n ; i++)
        {
           int  rem=n-i ;
          int  prv=i-1 ;
           if (a[rem]==0 && a[prv]==0)
           {
               flag=1 ;break ;
           }
           else if (a[rem]>0) a[rem]-- ;
           else if (a[prv]>0) a[prv]-- ;

        }
        cout<<"Case "<<j<<": " ;
        if (flag==1) cout<<"no"<<endl ;
        else cout<<"yes"<<endl ;

    }

    return 0 ;
}

LOJ-1231 :: Coin Change (I)

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

int coin[55] , no[55] ,n ,k;
long long int dp[55][1005] ;
int mod=100000007  ;

long long int call (int i , int amount)
{
    int j ;
      if (i==n)
    {
        if (amount==0) return 1 ;
        else return 0 ;
    }
     long long int &res =dp[i][amount] ;

      if (res != -1) return res ;
      res=0 ;
    for (j=0 ; j<=no[i] ; j++)
    {
        if (amount-(coin[i]*j)>=0)
            res+= call(i+1,amount-(coin[i]*j))%mod ;
        else  break ;
    }
    res=res%mod ;
   return res ;
}


int main ()
{
    int t ,j ,it ;
    cin>>t ;
    for (it=1 ; it<=t ; it++)
    {
        cin>>n>>k ;
        memset(dp,-1,sizeof (dp)) ;
        for(j=0 ; j<n ; j++) cin>>coin[j] ;
        for (j=0 ; j<n ;j++) cin>>no[j] ;

        printf ("Case %d: %lld\n",it,call(0,k) ) ;

    }

    return 0 ;
}