Problem Coin Counting

Coin Counting [C Program]

Curious Coin-Counting Problem

Given an amount A, we want you to compute the number of ways in which you
can gather A rupees if you have an infinite supply of each of C =  {1, 3, 5} valued rupee coins.

Input:
First line contains T, the number of test-cases. This is followed by T lines, where each line consists of the amount A.

Output:
For each test case, print the number of ways in which A can be formed using an infinite supply of 1, 3 and 5 rupee coins.

Sample Input:
2
5
10

Sample Output:
3
7

Constraints
T < 100
A < 101

Explanation (for first test case):
A = 5
Ways this amount can be achieved: {1,1,1,1,1}, {1,1,3}, {5}
Hence, the answer is 3.

Program:-

#include<stdio.h>


int cnt=0;

void count(int n){
 if(n==0){
  cnt++;
  return;
 }
 count(n-1);
}

void count3(int n){
 if(n==0){
  cnt++;
  return;
 }
 if(n>=3){
  count3(n-3);
 }
 count(n-1);
}

void count5(int n){
 if(n==0){
  cnt++;
  return;
 }
 if(n>=5){
  count5(n-5);
 }
 if(n>=3){
  count3(n-3);
 }
 count(n-1);
}

int main(){
 int n,T;
 int res[101],i=0;
 scanf("%d",&T);
 while(T!=0){
  scanf("%d",&n);
  count5(n);
  res[i]=cnt;
  cnt=0;
  i++;
  T--;
 }
 for(int j=0;j<i;j++){
  printf("%d\n",res[j]);
 }
 return 0;
}

------------X------------X------------X------------X------------X--------

Problem Compressed String

Find the Compressed String [C Program]

You are given a collection of words, say as in a dictionary. You can represent it in the following compressed form: the first word will be followed by a sequence of a pair of number and a word. The number in the pair is the position till which the previous words' characters are included in the new word and the tail is the remaining trailing word which is the different than the previous word. 

Example:
Suppose successive words in our dictionary are: 

color 
comma
commatose
dot

Then we can compress it in the following way:
color
2 mma     (to denote that first two characters are same as that of 'color' and remaining string is 'mma')

5 tose      (to denote that the first five characters are same as that of 'comma' and remaining string is 'tose')

0 dot        (to denote that zero characters are same as that of 'commatose' and the remaining string is 'dot')

Input Format:
First line contains the integer 'n' denoting the number of words in the dictionary s.t. 1 <= n <= 1,000
Second line would contain the first word.
It will be followed by 'n-1' lines each containing an integer and a trailing string. 
Note: The input is designed such that the integer will always be <= size of previous word formed

Example Input: 
4
zebra
3 u
2 nith
1 ggurat


Output Format: 
Output a single string that is the last resulting word of the given dictionary

Example Output:
zggurat

Explanation:
The dictionary actually is: 
zebra
zebu      (3 first characters are common with zebra)
zenith    (2 first characters are common with zebu)
zggurat  (1 first character is common with zenith)

Program:-

#include<stdio.h>
#include<string.h>

char *find(char st1[],char st2[],int in){
 int i,j;
 for(i=in,j=0;i<(in+strlen(st2));i++,j++){
  st1[i]=st2[j];
 }
 st1[i]='\0';
 return st1;
}

int main(){
 int n,in;
 scanf("%d",&n); 
 char str[n][20];
 scanf("%s",str[0]);
 for(int i=1;i<n;i++){
  scanf("%d",&in);
  scanf("%s",str[i]);
  strcpy(str[0],find(str[0],str[i],in));
 }
 printf("%s",str[0]);
 return 0;
}

-----------X-----------X-----------X-----------X-----------X----------

Input:-

3
cool
4 er
2 mmon-man



Output:-

common-man

Cooling Pies Codechef Problem

Cooling Pies[Java Program]

The chef has just finished baking several pies, and it's time to place them on cooling racks.
The chef has exactly as many cooling racks as pies. Each cooling rack can only hold one pie, and each pie may only be held by one cooling rack,
but the chef isn't confident that the cooling racks can support the weight of the pies.
The chef knows the weight of each pie,
and has assigned each cooling rack a maximum weight limit.
What is the maximum number of pies the chef can cool on the racks?

Input:

Input begins with an integer T≤30, the number of test cases.
Each test case consists of 3 lines.
The first line of each test case contains a positive integer N≤30,
the number of pies (and also the number of racks).
The second and third lines each contain exactly positive N integers not exceeding 100.
The integers on the second line are the weights of the pies, and the integers on the third line
are the weight limits of the cooling racks.

Output:

For each test case, output on a line the maximum number of pies the chef can place on the racks.

Sample input:

2
3
10 30 20
30 10 20
5
9 7 16 4 8
8 3 14 10 10
 

Sample output:

3
4

Program:-


/**
 * @(#)CoolP.java
 *
 *
 * @author Suyash Bhalla
 * @version 1.00 2014/12/31
 */

import java.util.Arrays;
import java.io.*;

class CoolP {
 public static void main(String ar[])throws IOException{
  BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  int T=Integer.parseInt(br.readLine());
  while(T--!=0){
   int n=Integer.parseInt(br.readLine());
   String t1[]=br.readLine().split(" ");
   String t2[]=br.readLine().split(" ");
   int a[]=new int[n];
   int b[]=new int[n];
   for(int i=0;i<n;i++){
    a[i]=Integer.parseInt(t1[i]);
    b[i]=Integer.parseInt(t2[i]);
   }
   int res=0;
   Arrays.sort(a);
   Arrays.sort(b);
   for(int i=n-1;i>=0;i--){
    for(int j=0;j<n;j++){
     if(a[i]<=b[j]&&b[j]!=-1){
      res++;
      b[j]=-1;
      break;
     }
    }
   }
   System.out.println(res);
  }
 }
}

---------------X----------------X-----------------X-----------------X-----------------X------------------X----------------------

Problem ByteLandian Gold Coins

Bytelandian gold coins[Java Program]

In Byteland they have a very strange monetary system.

Each Bytelandian gold coin has an integer number written on it. A coin n
can be exchanged in a bank into three coins: n/2, n/3 and n/4.
But these numbers are all rounded down (the banks have to make a profit).

You can also sell Bytelandian coins for American dollars. The exchange
rate is 1:1. But you can not buy Bytelandian coins.

You have one gold coin. What is the maximum amount of American dollars
you can get for it?

Input

The input will contain several test cases (not more than 10). Each
testcase is a single line with a number n, 0 <= n <= 1 000 000 000.
It is the number written on your coin.

Output

For each test case output a single line, containing the maximum amount
of American dollars you can make.

Example

Input:
12
2

Output:
13
2

You can change 12 into 6, 4 and 3, and then change these into
$6+$4+$3 = $13.

If you try changing the coin 2 into 3 smaller coins, you will get
1, 0 and 0, and later you can get no more than $1 out of them.
It is better just to change the 2 coin directly into $2.

Program:-

/**

 * @(#)ByteLG.java

 *

 *

 * @author Suyash Bhalla

 * @version 1.00 2014/12/31

 */

import java.io.*;

import java.util.HashMap;

class ByteLG {

static HashMap<Long,Long> hm=new HashMap<Long,Long>();

    public static void main(String ar[])throws IOException{

    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

    String st;

    while((st=br.readLine())!=null){

    long t=Long.parseLong(st);

    t=meth(t);

    System.out.println(t);

    }

    }    

    public static long meth(long n){

    if(n<12){

    return n;

    }else if(hm.containsKey(n)){

    return hm.get(n);

    }else{

    long t=meth(n/2)+meth(n/3)+meth(n/4);

    hm.put(n,t);

    return t;

    }

    }

}

-------------------X-------------------X-------------------X-------------------X-------------------X-------------------X------------

Problem Friday The Thirteenth

Friday the Thirteenth[Java Program]

Is Friday the 13th really an unusual event?

That is, does the 13th of the month land on a Friday less often than on any other day of the week? To answer this question, write a program that will compute the frequency that the 13th of each month lands on Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, and Saturday over a given period of N years. The time period to test will be from January 1, 1900 to December 31, 1900+N-1 for a given number of years, N. N is positive and will not exceed 400.

Note that the start year is NINETEEN HUNDRED, not 1990.

There are few facts you need to know before you can solve this problem:

• January 1, 1900 was on a Monday.
• Thirty days has September, April, June, and November, all the rest have 31 except for February which has 28 except in leap years when it has 29.
• Every year evenly divisible by 4 is a leap year (1992 = 4*498 so 1992 will be a leap year, but the year 1990 is not a leap year)
• The rule above does not hold for century years. Century years divisible by 400 are leap years, all other are not. Thus, the century years 1700, 1800, 1900 and 2100 are not leap years, but 2000 is a leap year.

Do not use any built-in date functions in your computer language.

Don't just precompute the answers, either, please.

PROGRAM NAME: friday

INPUT FORMAT

One line with the integer N.

SAMPLE INPUT (file friday.in)

20

OUTPUT FORMAT

Seven space separated integers on one line. These integers represent the number of times the 13th falls on Saturday, Sunday, Monday, Tuesday, ..., Friday.

SAMPLE OUTPUT (file friday.out)

36 33 34 33 35 35 34

Program:-

import java.io.*;

class friday {
 public static int rNDays(int mon,int year){
  switch(mon){
   case 1:
    return 31;
   case 2:
    if(checkLeap(year))
     return 29;
    else
     return 28;
   case 3:
    return 31;
   case 4:
    return 30;
   case 5:
    return 31;
   case 6:
    return 30;
   case 7:
    return 31;
   case 8:
    return 31;
   case 9:
    return 30;
   case 10:
    return 31;
   case 11:
    return 30;
   case 12:
    return 31;    
  }
  return -1;
 }
 public static boolean checkLeap(int year){
  if((year%4==0&&year%100!=0)||year%400==0){
   return true;
  }
  return false;
 }
    public static void main(String ar[])throws IOException{
     BufferedReader br=new BufferedReader(new FileReader("friday.in"));
     PrintWriter out=new PrintWriter(new BufferedWriter(new FileWriter("friday.out")));
     int NY=Integer.parseInt(br.readLine());
     int freq[]={1,0,0,0,0,0,0};
     int days=0,odd=0;
     for(int y=1900;y<1900+NY;y++){
      for(int m=1;m<=12;m++){
       days=rNDays(m,y);
       odd+=days%7;
       while(odd>=7){
        odd=odd%7;
       }
       freq[odd]+=1;
      }
     }
     freq[odd]=freq[odd]-1;
     for(int i=0;i<6;i++){
      out.print(freq[i]+" ");
     }
     out.println(freq[6]);
     out.close();
     System.exit(0);
    }
}



----------X--------------X------------------X------------------X---------

Program to download a web-page

To Save a web-page into new File and print html of same web page using Java Program

Ques.Write a java Program to read an html of any web-page and print its html code and save that web-page into new html file?

Program:

/**

 * @(#)SWP.java

 *

 *

 * @author Suyash Bhalla

 * @version 1.00 2014/9/24

 */

import java.net.*;

import java.io.*;

public class SWP {

    public static void main(String ar[])throws Exception{

    URL url=new URL("http://www.google.co.in");             //URL of web-page

    URLConnection urlc=url.openConnection();

    BufferedInputStream buffer=new BufferedInputStream(urlc.getInputStream());

    StringBuilder builder=new StringBuilder();

    int html;

    File f=new File("SavedPage.html");

    System.out.println(f.createNewFile());                            //Print true if new file is created.

    FileWriter pen=new FileWriter(f);

    while((html=buffer.read())!=-1){

    pen.write((char)html);

    builder.append((char)html);

    }

    buffer.close();

    pen.close();

    System.out.println(builder);                                           //To Print an html code of Page

    System.out.println("Size of Web Page is:"+(builder.length()/1024)+"MB");

    }   

}

--------X--------X--------X--------X--------X--------X--------X--------X--------X-------X-------

Output:

true

<!doctype html><html itemscope="" itemtype="http://schema.org/WebPage" lang="en-IN"><head><meta content="/images/google_favicon_128.png" itemprop="image"><title............................................................................................................................................................................................................................................................................................................................

</script></div></body></html>

Size of Web Page is:18MB

Problem Count Occurences of pattern in a string

Count occurences of pattern string[C Program]

Given a source string S and a pattern string P, count the number of times the pattern string P occurs in the source string S. 
Note: Overlapping sequences are counted as separate occurrences. 

Input Format:
First line is the source string S s.t. 1 <= |S| <= 8192 characters
Second line is the pattern string P s.t. 1 <= |P| <= 8192 characters

Output Format:
Output a single integer containing the number of occurrences of pattern string P in source string S.

Example:

Input:     mississippi

         issi

Output:  2

Program:

#include<stdio.h>
#include<string.h>

int main(){
 char str[8192],pstr[8192];
 int cnt=0,t,oc=0;
 scanf("%s",str);
 scanf("%s",pstr);
 for(int i=0;i<strlen(str);i++){
      t=i;
      for(int j=0;j<strlen(pstr);j++){
           if(str[t]==pstr[j]){
              cnt++; 
              t++;
           }else{
              break;
           }
      }
      if(cnt==strlen(pstr)){                 
            oc++;
      }
      cnt=0;
 }
 printf("%d",oc);
 return 0;
}

-------X----------X----------X----------X----------X----------X----------X-------

1.Input:     mississippi
           issi

   Output:  2


2.Input:     ouagadougou
           ou

   Output:  3


3.Input:     banana
           ana

   Output:  2

Problem Last ant on rod

Last ant on rod[C Program]

There are 'n' ants on a 'n+1' length rod. The ants are numbered from 1 to n and are initially placed at positions starting from position 1 till position n. They are moving either in left direction (denoted by '-1') or in the right direction (denoted by '1'). Whenever an ant crosses the boundary of the rod it falls off the rod. You are given the initial direction of the ants. Now, whenever two ants collide their direction switches, i.e. the ant going in left direction ('-1) changes it's direction towards right ('1') and the ant going in the right direction ('1') changes it's direction towards left ('-1'). Find last ant to fall off the rod. 

Note: In case two ants are falling simultaneously in the end print the index of the lower indexed ant. 

Input Format:
First line contains the integer 'n' denoting the total number of ants s.t.

                     1 <= n <= 1,000
Second line contains 'n' space separated numbers (either '1' or '-1') denoting the initial directions of the ants. 

Output Format:
Output a single integer which is the index (lower index in case two ants are falling simultaneously in the end) of the last ant to fall off the table.

Example:-

1.Input:-    2
             1 1

  Output:-   1

2.Input:-    3
             1 -1 -1
  Output:-   2

Program:-



#include<stdio.h>

int main(){
 int n,i,cn=0,in=0;
 scanf("%d",&n);
 int rod[2][n+1],vc[n+1];
 for(i=0;i<n;i++){
  scanf("%d",&rod[0][i]);
  rod[1][i]=i+1;
  vc[i]=1;
 }
 vc[n]=0;
 rod[0][n]=0;
 rod[1][n]=0;
 while(cn!=n){
  for(i=n;i>=0;i--){
   if((rod[0][i]==1&&i==n)||(rod[0][i]==1&&vc[i+1]==0)){
    if(i==n){
     cn++;
     in=rod[1][i];
     vc[i]=0;
     rod[0][i]=0;
     rod[1][i]=0;
    }else{
     vc[i+1]=1;
     vc[i]=0;
     rod[0][i+1]=rod[0][i];
     
     rod[1][i+1]=rod[1][i];
     
     rod[0][i]=0;
     rod[1][i]=0;
    }
   }
  } 
  for(i=0;i<=n;i++){
   if((rod[0][i]==-1&&i==0)||(rod[0][i]==-1&&vc[i-1]==0)){
    if(i==0){
     cn++;
     in=rod[1][i];
     vc[i]=0;
     rod[0][i]=0;
     rod[1][i]=0;
    }else{
     vc[i-1]=1;
     vc[i]=0;
     rod[0][i-1]=rod[0][i];
     rod[0][i]=0;
     rod[1][i-1]=rod[1][i];
     rod[1][i]=0;
    }
   }
  } 
  for(i=0;i<=n;i++){
   if(rod[0][i]==1&&rod[0][i+1]==-1){
    rod[0][i]=-1;
    rod[0][i+1]=1;
    i=i+1;
   }
  }
  
 }
 printf("%d",in);
 return 0;
}




------------X---------------X---------------X---------------X---------------X----


Input:-   10
          1 -1 1 1 -1 1 -1 1 -1 -1
Output:-  5

Binary Tree

Binary Tree Traversals(Inorder, PreOrder and PostOrder) [Implemented in Java] by recursive Approach.


Binary Tree is a tree if each node has zero child,one child or two children.

Note:-Empty tree is also a valid Binary Tree.

Here, we make a simple Binary Tree and study there different types of traversing techniques.
Tree designed by a constructor is like:-

Binary Tree Designed by Constructer

InOrder:-

                 ->Traverse a left subtree in InOrder.

                 ->Visit the root.

                 ->Traverse a right subtree in InOrder.

PreOrder:-
                 ->Visit the root.
                 ->Traverse a left subtree in InOrder.
                 ->Traverse a right subtree in InOrder.
PostOrder:-
                 ->Traverse a left subtree in InOrder.
                 ->Traverse a right subtree in InOrder.
                 ->Visit the root.


Program:-

/**
 * @(#)BinaryTreeMode1.java
 *
 *
 * @author Suyash Bhalla
 * @version 1.00 2014/12/20
 */

public class BinaryTreeMode1 {
class Node{
private Node left;
private Node right;
private int data;
void setLeft(Node left){
this.left=left;
}
void setRight(Node right){
this.right=right;
}
void setData(int data){
this.data=data;
}
int getData(){
return data;
}
Node getLeft(){
return left;
}
Node getRight(){
return right;
}
}
Node root;
BinaryTreeMode1(){                 //This Constructor designs an tree As shown in above figure.
Node n=new Node();         //Setuping an simple Tree to see different types of traversals.
root=n;
Node l=new Node();
Node r=new Node();
n.setData(1);
l.setData(2);
n.setLeft(l);
r.setData(3);
n.setRight(r);
Node t=n.getRight();
n=n.getLeft();
l=new Node();
r=new Node();
l.setData(4);
n.setLeft(l);
r.setData(5);
n.setRight(r);
n=t;
l=new Node();
r=new Node();
l.setData(6);
n.setLeft(l);
r.setData(7);
n.setRight(r);
}
public void inOrder(Node n){
if(n!=null){
inOrder(n.getLeft());
System.out.print(n.getData()+" ");
inOrder(n.getRight());
}
}
public void preOrder(Node n){
if(n!=null){
System.out.print(n.getData()+" ");
preOrder(n.getLeft());
preOrder(n.getRight());
}
}
public void postOrder(Node n){
if(n!=null){
postOrder(n.getLeft());
postOrder(n.getRight());
System.out.print(n.getData()+" ");
}
}
public static void main(String ar[]){
BinaryTreeMode1 ob=new BinaryTreeMode1();
System.out.print("InOrder is=>");
ob.inOrder(ob.root);
System.out.print("\nPreOrder is=>");
ob.preOrder(ob.root);
System.out.print("\nPostOrder is=>");
ob.postOrder(ob.root);
}

}


----------------X----------------X----------------X----------------X----------------X----------------X-------------

Output:-

InOrder is=>4 2 5 1 6 3 7
PreOrder is=>1 2 4 5 3 6 7
PostOrder is=>4 5 2 6 7 3 1












                                               

Lexicographically Preceding Permutation(C Program)

   Lexicographically Preceding Permutation                                  (C Program)

Given an integer n and a permutation of numbers 1, 2 ... , n-1, n write a program to print the permutation that lexicographically precedes the given input permutation. If the given permutation is the lexicographically least permutation, then print the input permutation itself. 

Input Format: 
First line is the value of integer n: 1 <= n <= 1,000,000
Second line is a space separated list of integers 1 2 ... n permuted in some random order

Output Format:

Output a single line containing a space separated list of integers which is the lexicographically preceding permutation of the input permutation.

Example:-

3

Possible 6 permutations in order are:-

123

132

213

231

312

321

1.  Input:-      132

    Output:-    123

2.  Input:-      321

    Output:-    312

3.  Input:-      231

    Output:-    213

4.  Input:-      312

    Output:-    231

5.  Input:-      213

    Output:-    132

Algorithm:-

1.Sort the input compare with minimum,if equals input is preceding order. 

2.Perform -1 with input.

3.Sort it in Ascending order.

4.Compare it with sorted input.

5.If equals calculated is preceding string,otherwise go to step 2.

Program:-

#include<stdio.h>

int check(int a[],int b[],int n){
 int flag=1;
 for(int i=0;i<n;i++){
  if(a[i]!=b[i]){
   flag=0;
   break;
  }
 }
 return flag;
}
void sort(int a[],int n){
 int temp;
 for(int i=0;i<n;i++){
  for(int j=i;j<n;j++){
   if(a[i]>a[j]){
    temp=a[i];
    a[i]=a[j];
    a[j]=temp;
   }
  }
 }
}
void minus(int a[],int n){
 for(int i=n-1;i>=0;i--){
  if(a[i]!=0){
   a[i]=a[i]-1;
   break;
  }else{
   a[i]=9;
   if(a[i-1]==0){
    minus(a,n-1);
    break;
   }else{
    a[i-1]=a[i-1]-1;
    break;
   }
  }
 }
}

int main(){
 int n;
 scanf("%d",&n);
 int a[n],min[n],b[n];
 for(int i=0;i<n;i++){
  scanf("%d",&a[i]);
  min[i]=i+1;
  b[i]=a[i];
 }
 int temp,done=0;
 while(1){
  if(check(a,min,n)){
   break;
  }else{
   for(int i=0;i<n;i++){
    a[i]=b[i];
   }
   minus(a,n);
   minus(b,n);
   sort(a,n);
  }
 }
 printf("%d",b[0]);
 for(int i=1;i<n;i++){
  printf(" %d",b[i]);
 }
 return 0;
}

---------------X---------------X---------------X---------------X---------------

1.Input:-

  4
  3 1 2 4
  Output:-

  2 4 3 1
2.Input:-
  7
  1 2 3 4 5 6 7
  Output:-

  1 2 3 4 5 6 7
3.Input:-
  12
  3 1 2 4 5 6 7 8 9 10 11 12
  Output:-

  2 12 11 10 9 8 7 6 5 4 3 1