Sunday, August 8, 2010

Sequences



Aadarsh is fond of special type
of sequences which are first increasing then decreasing then increasing then
decreasing and so on or which are first decreasing then increasing then
decreasing and so on like 1,2,1,2,1,2 or 2,1,2,1,2,1 respectively. He wants to
find a longest sub-sequence(not necessarily contiguous) of such nos in a given sequence. Help him out to find
such sequence.

Input Specification


Each test case consists of two
input lines. The first line of a test case contains an integer L,
determining the length of the sequence . The second line of a test case
contains sequence of numbers. L is a positive integer. The sequence contains
integer.

Test Cases are given till end of
file

Output Specification


For each test case output the
Length of the longest sequence which follows the property as mentioned above in
the given input sequence.

Example Input


5
1 2 1 2 1
8
1 2 1 2 2 1 1 4
8
1 2 3 4 5 6 7 8
8
8 7 6 5 4 3 2 1
8
1 1 2 2 1 1 2 2

Example Output


5
6
2
2
4
#include<iostream>
using namespace std;
int main()
{
    int A[100],num;
    while(cin>>num)
    {
        for(int i=0;i<num;i++)
        {
            cin>>A[i];
        }
        int order=0,temp=0,count=0;
        for(int i=0;i<num-1;i++)
        {
            if(order==0)
            {
                if(A[i+1]>A[i])
                {
                     count+=2;
                     order=-1;
                }
                if(A[i+1]<A[i])
                {
                     count+=2;
                     order=1;
                }
                temp=A[i+1];
            }
            else if(order==1)
            {
                if(A[i+1]>temp)
                {
                    count++;
                    order=-1;
                }
                temp=A[i+1];
            }
            else if(order==-1)
            {
                if(A[i+1]<temp)
                {
                    count++;
                    order=1;
                }
                temp=A[i+1];
            }
        }
    cout<<count<<endl;
    }
}

Logical Error

Robin designed a logical circuit for adding two
numbers.
But he forgot to include the carry logic in his circuit. The
working of his faulty circuit for the case of adding two bits may be hence
defined as follows:
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0



You are given two
integers, and you have to return the result as calculated by Robin's addition
circuit.



Input Specification



The input consists of multiple test cases. Each case
consists of two integers on separate lines. End of file denotes the end of
input.



Output Specification



For each test case output the result on a separate line.



Example Input





1

0



0



0



21



11



Example Output





1

0



30
The logic:
When a sum of 1+1 is taken as 0, an error of (2^n) is created in the sum, where n is the place (units, tens etc.) where the error is committed. Hence first calculate the correct sum by actual addition of the given two numbers. Then compute the error by examining the simultaneous occurrence of the bit 1 in the binary representation of the numbers.

#include<iostream>
using namespace std;
int main()
{
          int num1, num2, x , y ,i=-1 , sum1=0 ,sum=0 ,j ,z=1 ;  
          while(cin>>num1)
          {
                    cin>>num2;
                    i=-1 , sum1=0 ,sum=0 ,j=0 ,z=1;
                    //Adding the numbers for getting the correct sum.
                    sum=num1+num2;
                    do
                    {
                             z=1;
                             x = num1% 2;
                             ++i;
                             num1=num1/2;
                             y= num2% 2;
                             num2=num2/2;
                             //The condition where the bits  of both the numbers are 1.
                             if (x==1 && y == 1)
                            {
                                     //Computing the error at that place by multiplying 2, "the number of place" times. 
                                     for(j=0;j<=i;j++)
                                    {
                                             z*=2;
                                    }
                                    //Computing the total overall error.
                                    sum1+=z;
                           }
                   }while(num1!=0 && num2!=0);
                   //Subtracting the error from the correct sum.  
                   sum-=sum1;
                   cout<<sum<<endl;
         }
         return 0;  
}

Caesar Cypher



You have intercepted the data transmission of the
enemy. It is known that the encryption being used is Caesar Cypher. In this
encryption technique, if the letter to be encrypted is the Nth letter in the alphabet,
replace it with the (N-K)th
where K is some fixed integer called the Key. This addition is done modulo 26.
The spaces in the message are not encrypted.



Input Specification



There will be a number of test cases. Each test case consists of an encrypted
message of maximum 200 characters and containing only uppercase letters and
spaces, and an integer k (1<=k<=1000) which is the key of the encryption.
End of file denotes the end of input.



Output Specification



Your output should be the decrypted message, each in a line by itself.



Example Input



LJMM PCBNB
1
LJMM PCBNB
53


Example Output



KILL OBAMA
KILL OBAMA
#include<iostream>
#include<string>
using namespace std;
int main()
{
          char A[300];
          int key,i=0,j=0;
          char d;
          while(gets(A))
          {
                    key=0;i=0;j=0;
                    cin>>key;
                    //Since the counting is cyclic therefore counting multiples of 26 would give the original alphabet.
                    key=key%26;
                    for(i=0;i<strlen(A);i++)
                   {
                             if(A[i]!=' ')
                            {
                                       for(j=0;j<key;j++)
                                      {
                                           //Condition for the encryption to count from Z once A is encountered.
                                                if(A[i]=='A')
                                               {
                                                          A[i]='Z';
                                                          continue;
                                               }
                                               A[i]=A[i]-1;
                                     }
                           }                       
                  }
                  cout<<A<<endl;
                  d=getchar();
         }
         return 0;
}

Saturday, August 7, 2010

Longest Paths

Your goal is to develop a program that
computes the length of the longest path that can be constructed in a
given
graph from a given starting point. You can assume
that
the graph has no cycles (there is no path from any node to itself). In the same line of
reasoning,
nodes are not considered directly connected to themselves.




Input
 


The input
consists of a number of cases. The first line on each case contains a
positive
number n (

)
that specifies the number of nodes in the graph. A value of n = 0
indicates the end of the input.




After this, a second number s is provided,
indicating the starting point (

). Then,
you
are given a list of pairs of places p and q, one pair per
line, with the
places on each line separated by white-space. The pair ``" indicates
that q can be visited after p. A pair of zeros (``0 0") indicates
the end of the case.





Output
 


For each test case you have to find the length of the
longest path that begins at the starting place. You also have to print
the
number of the final place of such longest path. If there are several
paths of
maximum length, print the final place with smallest number.
Print a new line after each test case.




Sample Input
 


2
1
1 2
0 0
5
3
1 2
3 5
3 1
2 4
4 5
0 0
5
5
5 1
5 2
5 3
5 4
4 1
4 2
0 0
0





Sample Output
 


Case 1: The longest path from 1 has length 1, finishing at 2.

Case 2: The longest path from 3 has length 4, finishing at 5.

Case 3: The longest path from 5 has length 2, finishing at 1.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication6
{
class Program
{
static int maxcount = 0;//Variable to store the length of the longest path.
static int final = 0;//Variable to store the final node.
static bool visit = false;//Variable to check if the else part has been visited at least once.
static void Main(string[] args)
{
int num = int.Parse(Console.ReadLine());
int start = int.Parse(Console.ReadLine());
int initial = start;
int[,] arr = new int[num, num];
int[] trav = new int[num];
int num1, num2;
//Converting the input into the corresponding incidence matrix.
while((num1= int.Parse(Console.ReadLine()))!=0)
{
num2 = int.Parse(Console.ReadLine());
arr[num1 - 1, num2 - 1] = 1;
}
pathfinder(arr, start - 1, 0, trav);
Console.WriteLine("The longest path from " + initial + " has length " + maxcount + " finishing at " + final);
}
static void pathfinder(int[,] arr, int row, int count, int[]trav)
{
//Base case: The node from which no link to other nodes is found.
if (trav[row] == 1 && arr[row, arr.GetLength(0) - 1] == 0 && visit == true)
{
if (maxcount < count)
{
maxcount = count;
final = row + 1;
}
return;
}
else
{
visit = true;
for (int i = 0; i < arr.GetLength(0); i++)
{
trav[row] = 1;
if (arr[row, i] == 1)
{
count++;
//Sending the control to that row, the link of which is found here.
pathfinder(arr, i, count, trav);
trav[row] = 0;
count--;
}
}
}
if (maxcount < count)
{
maxcount = count;
final = row + 1;
}
}
}
}





Thursday, August 5, 2010

Maximum number of rings



There are a number of rings lying on the floor.
Any two rings can intersect at two points, may not intersect at all, or touch
each other at a single point. Two rings can be lifted simultaneously if and only
if they intersect at two points. A bunch of rings mutually satisfying this
condition can be lifted at once. You have to find the maximum number of rings
that can be lifted in a single attempt. The rings are specified by their x and y coordinates on the floor and their radius, the specifications of a ring being in a single row of a matrix.



        static void Main(string[]
args)



        {          



            int
maxcount = 1;



            double[,]
arr ={



                               {0.0, 0.0, 1.0},



                               {1.0, 0.0, 1.0},



                               {2.0, 0.0, 1.0},



                               {-1.0, 0.0, 1.0}



                           };



            int
num = arr.GetLength(0);



            //Array
to keep track of the rings included in the present bunch.



            int[]
used = new int[num];



            for
(int i = 0; i < arr.GetLength(0); i++)//Denotes the starting ring.



            {



                int
thiscount = 1;



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



                {



                    used[m] = 0;



                }



                used[i] = 1;//Starting ring has been used.



                //Searching
a ring from the beginning which matches the conditions.



                for
(int j = 0; j < arr.GetLength(0); j++)



                {                                               



                    if
(used[j] == 0)



                    {



                        //Searching from the beginning from the beginning of the current bunch.



                        for (int n = 0; n < num; n++)



                        {



                            double dist = Math.Sqrt(Math.Pow((arr[n, 0] - arr[j, 0]), 2.0d) + Math.Pow((arr[n, 1] - arr[j, 1]), 2.0d));



                            if (used[n] == 1 && dist < arr[j, 2] +
arr[n, 2] && dist > Math.Abs(arr[j,
2] - arr[n, 2]))



                            {



                                used[j] = 1;



                                thiscount++;



                                break;



                            }



                        }



                    }



                }



                if
(thiscount > maxcount)



                {



                    maxcount = thiscount;



                }



            }



            Console.WriteLine("The maximum number of rings is: " +
maxcount);



        }

Sunday, August 1, 2010

Higher n higher



Kapil is climbing the steps of his
office after meeting Anshuman. The length of a step must be nonnegative and can
be by one bigger than, equal to, or one smaller than the length of the previous
step. Since his time is very precious he needs to do this using the minimum
number of steps in order to get from x to y. He needs your help for designing
an algorithm for this feat. The length of the first and the last step must be
one.



What is the minimum number of steps
in order to get from x to y? The length of the first and the last
step must be 1.



Input and Output 



Input consists of a line containing
n, the number of test cases. For each test case, a line follows with two
integers: 0 < x < y < 2^31. For each test case, print a line giving
the minimum number of steps to get from x to y.



Sample Input 





3

17
41



1
41



14604
32391



 



Sample Output 



9



12



266



#include<iostream>



using
namespace std;



int main()



{



    long int test,num1,num2,incr,decr,count;



                cin>>test;



                while(test>0)



                {



                                count=0;



                                incr=1;decr=1;



                                cin>>num1;



                                cin>>num2;



                                while(num1<num2)



                                {



                                                num1=num1+incr;



                                                incr++;



                                                count++;



                                                if(num1<num2)



                                                {



                                                                num2=num2-decr;



                                                                decr++;



                                                                count++;



                                                }



                                }



                                cout<<count<<endl;



                                test--;



                }



                return
0;



}

Cutting Blocks








Niloy is a cool mathematician and
is good at solving puzzles.He has been given
a puzzle
which he solves very quickly but he wants to check his solution. Now
your task
is to find the answer so that Niloy can match his answer.
Here is the puzzle :)
Given a block of W weight you have to cut the
block
into blocks having a weight of K or less. Each block can be a cut only
if its
weight is greator than the minimum weight k,
such
that it results in blocks with minimal weight difference. We can further
cut
the newer blocks but we can apply only one cut to a particular block.
The cuts
are made such that we get blocks of integral weight. K and w
are both integer.



Input 



n - no of cases
w
( integer ) - weight of original block
K  (
integer ) -  maximum weight of final blocks to be formed
2 < = W  <= 10000
1 < = K


Output 



no of
final blocks formed



Sample input 



5
16 1
4 2
16 2
32 4
11 2


Sample Output 



16
2
8
8
7

#include<iostream>
using namespace std;
int main()
{
int fun(int a,int b);
int test,num1,num2,count;
cin>>test;
     while(test>0)
{
cin>>num1;
cin>>num2;
          count=fun(num1,num2);
      
   cout<<count<<endl;
      
   test--;
    
}
return 0;
}
int fun(int a,int b)
{
if(a<=b)
     {return 1;}
    
else
     {
   
      return fun(a/2,b)+fun(a-(a/2),b);
    }
}