Thursday, December 23, 2010
Sunday, October 17, 2010
Pixel Enclosures
In the digital world geometric shapes are drawn using
pixels. A pixel is a square area of unit dimension. For this problem we say 2
pixels are connected if they share an edge or a vertex between them. This is
also called 8-connectivity. Your task is to find the maximum possible area of a
closed loop made up of A pixels (these are boundary pixels of the closed loop).
Area of a closed loop is the number of pixels which are completely inside the
loop or on the loop. Consider the example below:
For A = 4, you can make a close loop as follows -
This has an area of 5 with 4 pixels on the loop and 1 pixel completely inside
the loop.
Input:
First line contains an integer N,
the number of test cases.
Next N lines contain an integer A for that test case.
N <= 100
A <= 1000
Output:
Print N
lines with a single integer stating the maximum area of a closed loop.
Sample Input:
2
4
5
Sample Output:
5
6
Time Limit: 2 seconds
Memory Limit: 32 MB
#include<iostream>
using namespace std;
int main()
{
int fun(int);
int N,ans,A;
cin>>N;
while(N>0)
{
cin>>A;
ans=fun(A);
cout<<ans<<endl;
N--;
}
return 0;
}
int fun(int A)
{
if(A==0)
{
return 0;
}
else if(A==1)
{
return 1;
}
else if(A==2)
{
return 2;
}
else if(A==3)
{
return 3;
}
else if(A==4)
{
return 5;
}
else
{
return A + fun(A-4);
}
}
Friday, October 15, 2010
Code for Chatruka's Parallelogram
#include<iostream>
#include<string>
using namespace std;
int main()
{
int i,j,k,l,count=0,mov=0,n=1,end=0;
char A[200],B[100][100],C[100][100],T[10];
gets(T);
count=0;mov=0;n=1;end=0;
if(T[0]=='E')
{
gets(A);
while((2*n*n)<strlen(A))
{
n++;
}
if(n%2==0)
{
n++;
}
k=0;l=1;end=0;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(k<strlen(A))
{
B[i][j]=A[k];
k=k+2;
}
else
{
end=1;
break;
}
}
if(end==1)
{break;}
}
while(i<n)
{
while(j<n)
{
B[i][j]='/';
j++;
}
i++;
j=0;
}
end=0;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(l<strlen(A))
{
C[i][j]=A[l];
l=l+2;
}
else
{
end=1;
break;
}
}
if(end==1)
{break;}
}
while(i<n)
{
while(j<n)
{
C[i][j]='/';
j++;
}
i++;
j=0;
}
cout<<"OUTPUT IS"<<endl;
cout<<A<<endl;
i=n/2;j=n/2;mov=0;
cout<<B[i][j]<<C[i][j];
count++;
while(count<n*n)
{
mov++;
for(k=0;k<mov;k++)
{
if(count<n*n)
{
j--;
cout<<B[i][j]<<C[i][j];
count++;
}
}
for(k=0;k<mov;k++)
{
if(count<n*n)
{
i--;
cout<<B[i][j]<<C[i][j];
count++;
}
}
mov++;
for(k=0;k<mov;k++)
{
if(count<n*n)
{
j++;
cout<<B[i][j]<<C[i][j];
count++;
}
}
for(k=0;k<mov;k++)
{
if(count<n*n)
{
i++;
cout<<B[i][j]<<C[i][j];
count++;
}
}
}
cout<<endl;
}
else if(T[0]=='D')
{
gets(A);
while((2*n*n)<strlen(A))
{
n++;
}
if(n%2==0)
{
n++;
}
i=n/2;j=n/2;mov=0;l=0;
B[i][j]=A[l];l++;
C[i][j]=A[1];l++;
while(count<n*n)
{
mov++;
for(k=0;k<mov;k++)
{
if(count<n*n)
{
j--;
B[i][j]=A[l];l++;
C[i][j]=A[l];l++;
count++;
}
}
for(k=0;k<mov;k++)
{
if(count<n*n)
{
i--;
B[i][j]=A[l];l++;
C[i][j]=A[l];l++;
count++;
}
}
mov++;
for(k=0;k<mov;k++)
{
if(count<n*n)
{
j++;
B[i][j]=A[l];l++;
C[i][j]=A[l];l++;
count++;
}
}
for(k=0;k<mov;k++)
{
if(count<n*n)
{
i++;
B[i][j]=A[l];l++;
C[i][j]=A[l];l++;
count++;
}
}
}
cout<<"OUTPUT IS"<<endl;
cout<<A<<endl;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(B[i][j]!='/')
{cout<<B[i][j];}
if(C[i][j]!='/')
{cout<<C[i][j];}
}
}
cout<<endl;
}
return 0;
}
Problem for Chatruka's Parallelogram
Raja Chatruka needs a message to be delivered to his spy. The message is supposed to be encoded so that none other than the spy can decode the message, who knows the process of encoding.
Earlier the Raja and the Spy both decided to adopt the process of “expanding parallelogram code”. The method encodes the message by placing the characters in an odd order parallelogram matrix and then reading it in a clockwise spiral from the center. Each cell of the parallelogram contains two characters; the one below is filled first as well as read first. The length of message determines the order of the matrix. The order needs to be minimum. If the number of characters are less than the number of cells in the matrix the remaining cells are filled with “/”. No message contains the actual character /.
For example: If the message is “this is a problem”
The output should be “a s this iprm/leob”
Your program must be able to encode and decode the message by this process.
INPUT The input will consist of a pair of lines. The first line will contain either of the two words “ENCODE” or “DECODE” in uppercase letters. The second line will contain the message(less than 100 characters) to be encoded or decoded depending upon the first line.
OUTPUT The output will consist of three lines. The first line will print “OUTPUT IS” in uppercase letters. The second line will print the original message, and the third line the resultant message. The character „/‟ should be removed to get the decoded message.
Note: Order of a matrix refers to the number of rows or columns.
SAMPLE INPUT:
ENCODE
this is a problem
SAMPLE OUTPUT:
OUTPUT IS
this is a problem a s this iprm/leob
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
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
Output Specification
Your output should be the decrypted message, each in a line by itself.
Example Input
LJMM PCBNB
1
LJMM PCBNB
53Example 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.
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.
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.
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 2Sample 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);
}
}
Saturday, July 17, 2010
Power Set
Printing all the
possible combinations of a set of elements
using System;
using
System.Collections;
using
System.Linq;
using
System.Text;
namespace
ConsoleApplication3
{
class Program
{
static int count = 0;//Variable
which counts the number of combinations printed.
static void Main(string[]
args)
{
ArrayList
list = new ArrayList();
string
input = "abcde";
char[]
arr = new char[input.Length];
arr = input.ToCharArray();
//int[]
arr = { 1, 2, 3, 4, 5 };
combine(arr,list,0);
Console.WriteLine("The total number of combinations is: "
+ count);
}
//Change
char[]arr to int[]arr to use the function for an int array.
static void combine(char[]
arr, ArrayList list, int index)
{
if
(index == arr.Length)
{
return;
}
else
{
while
(index < arr.Length)
{
list.Add(arr[index]);
//Printing
format
Console.Write("{");
for
(int i = 0; i < list.Count; i++)
{
if (i !=
list.Count - 1)
{
Console.Write(list[i] + ",");
}
else
{
Console.Write(list[i]);
}
}
Console.Write("}");
Console.WriteLine();
//Printing
format.
count++;
combine(arr, list, index +
1);
//Removing
the last element of the present list on returning.
list.RemoveAt(list.Count -
1);
index++;
}
}
}
}
}
Subscribe to:
Posts (Atom)