12403 Save Setu Uva Problem Solution

#include<bits/stdc++.h>

// Nayeem Shahriar Joy, Applied Physics & Electronic Engineering , University of Rajshahi.

using namespace std;

int main ()
{
    int t,a,b,c;

    cin>>t;

    long long sum=0;

    string s;


    while ( t-- )
    {
        cin>>s;
        if(s=="donate")
        {
            cin>>a;
            sum=sum+a;
        }
        else
        {
            cout<<sum<<endl;
        }
    }

    return 0;
}

12372 - Packing for Holiday Uva Problem Solution

#include<bits/stdc++.h>

// Nayeem Shahriar Joy, Applied Physics & Electronic Engineering , University of Rajshahi.

using namespace std;

int main ()
{
    int t,a,b,c;

    cin>>t;

     int i=1;

    while ( t-- )
    {
        cin>>a>>b>>c;
        cout<<"Case "<<i<<": ";
        if(a<=20&&b<=20&&c<=20)
        {
            cout<<"good"<<endl;
        }
        else
        {
            cout<<"bad"<<endl;
        }
        i++;
    }

    return 0;
}

12250 - Language Detection Uva Solution

#include<bits/stdc++.h>

// Nayeem Shahriar Joy, Applied Physics & Electronic Engineering , University of Rajshahi.

using namespace std;
int main()
{

    string s;
    int i=1;
        while(cin>>s)
        {

            if(s=="HELLO")
            {
                cout<<"Case "<<i<<": ";
                cout<<"ENGLISH"<<endl;
            }
            else if(s=="HOLA")
            {
                cout<<"Case "<<i<<": ";
                cout<<"SPANISH"<<endl;
            }
            else if(s=="HALLO")
            {
                cout<<"Case "<<i<<": ";
                cout<<"GERMAN"<<endl;
            }
            else if(s=="BONJOUR")

           {
               cout<<"Case "<<i<<": ";
               cout<<"FRENCH"<<endl;

            }

            else if(s=="CIAO")
            {
                cout<<"Case "<<i<<": ";
                cout<<"ITALIAN"<<endl;
            }
            else if(s=="ZDRAVSTVUJTE")
            {
                cout<<"Case "<<i<<": ";
                cout<<"RUSSIAN"<<endl;
            }
            else if(s=="#")
            {
                break;
            }
            else
            {
                cout<<"Case "<<i<<": ";
                cout<<"UNKNOWN"<<endl;
            }
            i++;

            }
    return 0;
}

11727 - Cost Cutting Uva Problem Solution

#include<bits/stdc++.h>

// Nayeem Shahriar Joy, Applied Physics & Electronic Engineering , University of Rajshahi.

using namespace std;
int main()
{

    int t,a,b,c;
    cin>>t;
        for(int i=1;i<=t;i++){
           vector<int>joy;
           cin>>a>>b>>c;
           joy.push_back(a);
           joy.push_back(b);
           joy.push_back(c);
           sort(joy.begin(),joy.end());
           cout<<"Case "<<i<<": ";
           cout<<joy[1]<<endl;
        }


    return 0;
}

11547 - Automatic Answer Uva Problem Solution

#include<bits/stdc++.h>
using namespace std;
int main()
{

    int t,n,i;
    cin>>t;
        while(t--){
            scanf("%d",&n);
            n=n*567;
            n=n/9;
            n+=7492;
            n*=235;
            n/=47;
            n=n-498;
            n/=10;
            n%=10;
            n=abs(n);
            printf("%d\n",n);
        }


    return 0;
}

11044 - Searching for Nessy Uva Problem Solution

#include <bits/stdc++.h>
using namespace std;
// Nayeem Shahriar Joy , Applied Physics & Electronic Engineer9ng, University of Rajshahi.

int main() {
    int T,a,b;
    cin >> T;
    for(int t = 0; t< T; t++){

        cin >> a>>b;
        cout<<(a/3)*(b/3)<<endl;
    }
    return 0;
}

11364 - Parking Uva Problem Solution

#include <bits/stdc++.h>
using namespace std;
// Nayeem Shahriar Joy , Applied Physics & Electronic Engineer9ng, University of Rajshahi.

int main() {
    int T,d;
    cin >> T;
    for(int t = 0; t< T; t++){
        int n;
        cin >> n;
        vector<int>distance;
        for(int i = 0; i < n; i++){
            cin >> d;
            distance.push_back(d);
        }
        sort(distance.begin(),distance.end());
        cout << 2*(distance[n-1]-distance[0]) << endl;
    }
    return 0;
}

DevSkill - Factorially Even or Odd Problem Solution

https://www.devskill.com/CodingProblems/ViewProblem/354


// Nayeem Shahriar Joy , Applied Physics & Electronic Engineering , University of Rajshahi.

#include<bits/stdc++.h>

using namespace std;

unsigned long long trailingzeroesfinding(unsigned long long n)

{

    unsigned long long  count=0;

       for(int i=5;n/i>=1;i=i*5)

       {

           count=count+(n/i);

       }

       return count;

}


int main()

{
   int t;
   cin>>t;
   unsigned long long n;
   while(t--)
   {
       cin>>n;
       unsigned long long  trailing=trailingzeroesfinding(n);
       int joy =0;
       if(trailing==1)
       {
           joy=1;
       }
       else{
       for(unsigned long long i=1;pow(2,i)<=trailing;i++)

       {
           if(pow(2,i)==trailing)

           {
               joy=1;
               break;

           }
       }
       }
     if(joy)
     {
         cout<<"Even"<<endl;
     }
     else
     {
         cout<<"Odd"<<endl;
     }
   }
   return 0;
}

Part-6 (Longest Increasing Subsequence )

The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. For example, the length of LIS for {10, 22, 9, 33, 21, 50, 41, 60, 80} is 6 and LIS is {10, 22, 33, 50, 60, 80}.


                                                   DYNAMIC PROGRAMMING       


#include<bits/stdc++.h>

using namespace std;


int main()

{
     int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
    int n = sizeof(arr)/sizeof(arr[0]);


     int lis[n];
    for(int i=0;i<n;i++)
    {
        lis[i]=1;

    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<i;j++)
        {
            if((arr[i]>arr[j])&&((lis[j]+1)>lis[i]))
               {
                   lis[i]=lis[j]+1;
               }
        }
    }
    sort(lis,lis+n);

    cout<<lis[n-1]<<endl;
    return 0;
}

PROBLEM LINK: https://practice.geeksforgeeks.org/problems/longest-increasing-subsequence/0

                                      USING DYNAMIC PROGRAMMING


// Nayeem Shahriar Joy , Applied Physics & Electronic Engineering , University of Rajshahi.

#include<bits/stdc++.h>

using namespace std;


int main()

{
    int n;

    cin>>n;

    while(n--){

     int x;

    cin>>x;

     int arr[x];

    for(int i=0;i<x;i++)

    {
       cin>>arr[i];

    }

    int lis[x];

    for(int j=0;j<x;j++)

    {
        lis[j]=1;
    }

    for(int k=0;k<x;k++)

    {
        for(int y=0;y<k;y++)

        {
            if(arr[k]>arr[y]&&((lis[y]+1)>lis[k]))

            {
                lis[k]=lis[y]+1;
            }
        }
    }

    sort(lis,lis+x);

    cout<<lis[x-1]<<endl;

    }
    return 0;
}
 

Part-5 , (Coin Change)

 Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change?       



                                                  Dynamic Programming Solutions of
                                                        these kinds of solution

int count( int S[], int m, int n )

{

    // table[i] will be storing the number of solutions for

    // value i. We need n+1 rows as the table is consturcted

    // in bottom up manner using the base case (n = 0)

    int table[n+1];

 

    // Initialize all table values as 0

    memset(table, 0, sizeof(table));

 

    // Base case (If given value is 0)

    table[0] = 1;

 

    // Pick all coins one by one and update the table[] values

    // after the index greater than or equal to the value of the

    // picked coin

    for(int i=0; i<m; i++)

        for(int j=S[i]; j<=n; j++)

            table[j] += table[j-S[i]];

 

    return table[n];

}

 

int main()

{

    int arr[] = {1, 2, 3};

    int m = sizeof(arr)/sizeof(arr[0]);

    int n = 4;

    printf(" %d ", count(arr, m, n));

    return 0;

}

 

 

           Problem : https://practice.geeksforgeeks.org/problems/coin-change/0

 

 

 

#include<bits/stdc++.h>

// Nayeem Shahriar Joy , Applied Physics & Electronic Engineering , University of Rajshahi.

using namespace std;

int count( int S[], int m, int n )
{
    int dp[n+1];

    memset(dp, 0, sizeof(dp));

    dp[0] = 1;

    for(int i=0; i<m; i++){
        for(int j=S[i]; j<=n; j++){
            dp[j] += dp[j-S[i]];
        }
    }

    return dp[n];
}

int main()

{
    int t,s,x,N;
    cin>>t;
    while(t--)
    {
        cin>>s;
        int A[s];
        for(int i=0;i<s;i++)
        {
            cin>>A[i];
        }
        cin>>N;
        cout<<count(A,s,N)<<endl;
    }
    return 0;

}
 

 

                 

 

Part-4,Min Cost Path

From (0,0)  to  (R,R)

                                                      Use Of Dynamic Programming 
                                                      TIME  COMPLEXITY  O(m*n)  


#include<bits/stdc++.h>

using namespace std;

int minCost(int cost[R][C], int m, int n)
{
     int i, j;
     int dp[R][C]; 

     dp[0][0] = cost[0][0];

     /* Initialize first column of total cost(tc) array */
     for (i = 1; i <= m; i++)
        dp[i][0] = dp[i-1][0] + cost[i][0];

     /* Initialize first row of tc array */
     for (j = 1; j <= n; j++)
        dp[0][j] = dp[0][j-1] + cost[0][j];

     /* Construct rest of the tc array */
     for (i = 1; i <= m; i++)
        for (j = 1; j <= n; j++)
            dp[i][j] = min(dp[i-1][j-1],
                           dp[i-1][j],
                           dp[i][j-1]) + cost[i][j];

     return dp[m][n];
}

int main()
{
   int cost[R][C] = { {1, 2, 3},
                      {4, 8, 2},
                      {1, 5, 3} };
   printf(" %d ", minCost(cost, 2, 2));
   return 0;
}

Part-3,Largest Sum Contiguous Subarray

       Largest Sum Contiguous Subarray

 

                                                  Use of Dynamic Programming 
                                                  TIME  COMPLEXITY  O(n)                          

#include<bits/stdc++.h>

using namespace std;



int maxSubArraySum(int a[], int size)
{
   int max_so_far = a[0];
   int curr_max = a[0];

   for (int i = 1; i < size; i++)
   {
        curr_max = max(a[i], curr_max+a[i]);
        max_so_far = max(max_so_far, curr_max);
   }
   return max_so_far;
}



int main()

{

   int a[] =  {-2, -3, 4, -1, -2, 1, 5, -3};

   int n = sizeof(a)/sizeof(a[0]);

   int max_sum = maxSubArraySum(a, n);

   cout << "Maximum contiguous sum is " << max_sum;

   return 0;

}

 

 

                      A Problem & It's Solution 

 

http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/      




#include<bits/stdc++.h>

using namespace std;

// Nayeem Shahriar Joy , Applied physics & Electronic Engineering , University of Rajshahi.

int maxSubArraySum(int a[], int size)
{
   int max_so_far = a[0];
   int curr_max = a[0];

   for (int i = 1; i < size; i++)
   {
        curr_max = max(a[i], curr_max+a[i]);
        max_so_far = max(max_so_far, curr_max);
   }
   return max_so_far;
}

/* Driver program to test maxSubArraySum */
int main()
{
    int t;
    cin>>t;
    while(t--){
        int x;
        cin>>x;
        int a[x];
        for(int i=0;i<x;i++)
        {
            cin>>a[i];
        }
   int n = sizeof(a)/sizeof(a[0]);
   int max_sum = maxSubArraySum(a, n);
   cout<< max_sum<<endl;
    }
   return 0;
}


 

 

Part-2 , Find nCr ( BinomialCoefficient ) for given n and r

                                     Find nCr for given n and r


                                                  Use Recursive Formula ,
                                               
#include<bits/stdc++.h>

using namespace std;

int BinomialCoefficient(int n,int k)

{
    if(k==0||k==n)
        return 1;

    return BinomialCoefficient(n-1,k-1)+BinomialCoefficient(n-1,k);
}

int main()

{
    int n,k;
    cin>>n>>k;
    cout<<BinomialCoefficient(n,k)<<endl;
    return 0;
}

                                                            Use Of Dynamic Programming

                                                            Time Complexity  O(n*k)

  


#include<bits/stdc++.h>

using namespace std;

int BinomialCoefficient(int n,int k)

{
   int dp[n+1][k+1];
   int i,j;
   for(int i=0;i<=n;i++)
   {
       for(int j=0;j<=min(i,k);j++)
       {
           if(j==0||j==i)
            dp[i][j]=1;
           else
            dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
       }
   }
   return dp[n][k];
}

int main()

{
    int n,k;
    cin>>n>>k;
    cout<<BinomialCoefficient(n,k)<<endl;
    return 0;
}


                                            A    Problem  & It's Solution 

https://practice.geeksforgeeks.org/problems/ncr/0 


#include<bits/stdc++.h>

using namespace std;

// Nayeem Shahriar Joy , Applied Physics & Electronic Engineering,University of Rajshahi.

int BinomialCoefficient(int n,int k)

{
   int dp[n+1][k+1];
   int i,j;
   for(int i=0;i<=n;i++)
   {
       for(int j=0;j<=min(i,k);j++)
       {
           if(j==0||j==i)
            dp[i][j]=1;
           else
            dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%1000000007;
       }
   }
   return dp[n][k];
}

int main()

{
    int t;
    cin>>t;
    while(t--){
    int n,k;
    cin>>n>>k;
    if(n<k)
    {
        cout<<"0"<<endl;
    }
    else{
    cout<<BinomialCoefficient(n,k)<<endl;
    }
    }
    return 0;
}

Part-1 , Fibonacchi Number Finding

Tricks For Fibonacchi ,

If n is even then k = n/2:
F(n) = [2*F(k-1) + F(k)]*F(k)

If n is odd then k = (n + 1)/2
F(n) = F(k)*F(k) + F(k-1)*F(k-1)

                                                 TIME COMPLEXITY ( O Log ( n ) )


#include<bits/stdc++.h>

using namespace std;

const int MAX =1000;
int fibonacchi[1000]={0};


int fib(int n)
{
    int k;
    if(n==0)
    {

        return 0;
    }
    if(n==1||n==2)
    {
        return (fibonacchi[n]=1);
    }
    if(fibonacchi[n])
        return fibonacchi[n];

    k=(n&1)? (n+1)/2: n/2;

    fibonacchi[n]=(n&1)? (fib(k)*fib(k)+(fib(k-1)*fib(k-1))) : (2*fib(k-1)+fib(k))*fib(k);

    return fibonacchi[n];
}

int main()

{
    int x;
    cin>>x;
    cout<<fib(x)<<endl;
    return 0;
}


                                                          Use Of Dynamic Programming

                                                          TIME COMPLEXITY O(N);   


#include<bits/stdc++.h>

using namespace std;

int fib(int n)
{
  /* Declare an array to store Fibonacci numbers. */
  int f[n+1];
  int i;

  /* 0th and 1st number of the series are 0 and 1*/
  f[0] = 0;
  f[1] = 1;

  for (i = 2; i <= n; i++)
  {
      /* Add the previous 2 numbers in the series
         and store it */
      f[i] = f[i-1] + f[i-2];
  }

  return f[n];
}

int main ()
{
  int n;
  cin>>n;
  cout<<fib(n)<<endl;
  return 0;
}
 

                                                    A Problem & It's Solution 

 https://practice.geeksforgeeks.org/problems/nth-fibonacci-number/0


#include<bits/stdc++.h>

using namespace std;

// Nayeem Shahriar Joy , Applied Physics & Electronic Engineering , UNiversity of Rajshahi.

const int MAX =1000;
long dp[1000]={0};


int fib(int n)
{
   dp[0]=0;
   dp[1]=1;
   for(int i=2;i<=1000;i++)
   {
       dp[i]=(dp[i-1]+dp[i-2])%1000000007;

   }
   return dp[n];
}
int main() {
    int t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        cout<<fib(n)<<endl;

    }

    return 0;
}

Aaah! Kattis Problem Solution In Java

// Nayeem Shahriar Joy , Applied Physics & Electronic Engineering , University of Rajshahi.

import java.util.Scanner;

public class Joy {

public static void main(String[] args) {

String s1,s2;

Scanner sc1=new Scanner(System.in);

s1=sc1.nextLine();

s2=sc1.nextLine();

int able=s1.length();

int say=s2.length();

if(able>=say)

{

System.out.print("go");

}

else

{

System.out.print("no");

}

}

}

Seven Wonders Kattis Problem Solution In Java

//Nayeem Shahriar Joy,Applied Physics & Electronic Engineering, University of Rajshahi.

import java.util.HashSet;

import java.util.Scanner;

import java.util.Set;

public class Joy{

public static void main(String[] args) {

Scanner io = new Scanner(System.in);

String s=io.nextLine();

long ans=0;

int C=0,T=0,G=0;

for(int i=0;i<s.length();i++)

{

char c=s.charAt(i);

if(c=='T')

{

T++;

}

else if(c=='G')

{

G++;

}

else if(c=='C')

{

C++;

}

}

int seven=Math.min(T, Math.min(C,G));

ans=(T*T)+(C*C)+(G*G)+(seven*7);

System.out.println(ans);

}

}

Apaxiaaaaaaaaaaaans! Kattis Problem Solution In Java

//Nayeem Shahriar Joy,Applied Physics & Electronic Engineering, University of Rajshahi.
 

import java.util.HashSet;

import java.util.Scanner;

import java.util.Set;

import javax.swing.text.html.HTMLDocument.Iterator;

public class Joy{

public static void main(String[] args) {

Scanner io = new Scanner(System.in);

String s=io.nextLine();

int i;

for( i=0;i<s.length()-1;i++)

{

if(s.charAt(i)!=s.charAt(i+1))

{

System.out.print(s.charAt(i));

}

}

System.out.print(s.charAt(i));

System.out.println();

}

}

Cryptographer's Conundrum Kattis Problem Solution In Java

//Nayeem Shahriar Joy,Applied Physics & Electronic Engineering, University of Rajshahi.
 

import java.util.HashSet;

import java.util.Scanner;

import java.util.Set;

import javax.swing.text.html.HTMLDocument.Iterator; 

 

public class Joy{

public static void main(String[] args) {

Scanner io = new Scanner(System.in);

String s=io.nextLine();

int count=0;

for(int i=0;i<s.length();i++) {

if(!((i%3==0&&s.charAt(i)=='P')||(i%3==1&&s.charAt(i)=='E')||(i%3==2&&s.charAt(i)=='R')))

{

count++;

}

}

System.out.println(count);

}

}

Speed Limit Kattis Problem Solution In Java

import java.util.ArrayList;

import java.util.HashSet;

import java.util.Scanner;

import java.util.Set;

import javax.swing.text.html.HTMLDocument.Iterator;

public class Joy{

public static void main(String[] args) {

// Get input from the user w/ sentinel logic

Scanner reader = new Scanner(System.in);

int pairs = Integer.parseInt(reader.nextLine());

// Keep track of distances

ArrayList<Integer> distances = new ArrayList<Integer>();

while(pairs != -1){ // While still accepting input

int distance = 0;

int hours = 0;

for(int i = 0; i < pairs; i++){

String[] temp = reader.nextLine().split(" "); // Put input into a string

distance += Integer.parseInt(temp[0]) * (Integer.parseInt(temp[1]) - hours); // distance is mph times new hours - old hours

hours = Integer.parseInt(temp[1]); // keep track of current hours

}

distances.add(distance);

pairs = Integer.parseInt(reader.nextLine());

} // end while loop

// Output data to the user

for(int i = 0; i < distances.size(); i++){

System.out.println(distances.get(i) + " miles");

}

// Closed the reader

reader.close();

}// end main

}

Pet Kattis Problem Solution In Java

//Nayeem Shahriar Joy,Applied Physics & Electronic Engineering, University of Rajshahi.

 

import java.util.ArrayList;

import java.util.HashSet;

import java.util.Scanner;

import java.util.Set;

import javax.swing.text.html.HTMLDocument.Iterator; 

 

public class Joy{

public static void main(String[] args) {

// Get input from the user w/ sentinel logic

Scanner io = new Scanner(System.in);

int index=0;

int sum=0,sum1 = 0;

for(int i=1;i<=5;i++)

{

int a=io.nextInt();

int b=io.nextInt();

int c=io.nextInt();

int d=io.nextInt();

sum=a+b+c+d;

if(sum1<=sum)

{

sum1=sum;

index=i;

}

}

System.out.println(index+" "+sum1);

}

}