CODING CLUB

Friday, 1 November 2013

Small Factorials - Solution

Problem Statement:
You are asked to calculate factorials of some small positive integers.

Input

An integer t, 1<=t<=100, denoting the number of testcases, followed by t lines, each containing a single integer n, 1<=n<=100.

Output

For each integer n given at input, display a line with the value of n!

Example

Sample input:

Sample output:

Solution:

#include<stdio.h>

#include<stdlib.h>

void factorial(int*,int);

void print(int*);

void add(int*,int*);

int main()

        int arr[200]={0},i,t,n,j;

        scanf("%d",&t);

        for(i=0;i<t;i++)

               for(j=0;j<200;j++)

                       arr[j]=0;

               scanf("%d",&n);

               factorial(arr,n);

               print(arr);

               printf("\n");

        return 0;

void factorial(int *arr,int n)

        int tmparr[200]={0};

        int i,j;

        arr[199]=1;

        for(i=1;i<=n;i++)

               for(j=0;j<200;j++)

                       tmparr[j]=0;

               for(j=0;j<i;j++)

                       add(arr,tmparr);

               for(j=0;j<200;j++)

                       arr[j]=tmparr[j];

void add(int*arr,int*tmparr)

        int i;

        for(i=199;i>0;i--)

               tmparr[i]+=arr[i];

               if(tmparr[i]>9)

                       tmparr[i-1]+=1;

                       tmparr[i]%=10;

void print(int*arr)

        int i,flag=0;

        for(i=0;i<200;i++)

               if(arr[i]!=0 || flag)

                       flag=1;

                       printf("%d",arr[i]);

Problem Statement:
Chef wrote some text on a piece of paper and now he wants to know how many holes are in the text. What is a hole? If you think of the paper as the plane and a letter as a curve on the plane, then each letter divides the plane into regions. For example letters "A", "D", "O", "P", "R" divide the plane into two regions so we say these letters each have one hole. Similarly, letter "B" has two holes and letters such as "C", "E", "F", "K" have no holes. We say that the number of holes in the text is equal to the total number of holes in the letters of the text. Help Chef to determine how many holes are in the text.

Input

The first line contains a single integer T <= 40, the number of test cases. T test cases follow. The only line of each test case contains a non-empty text composed only of uppercase letters of English alphabet. The length of the text is less then 100. There are no any spaces in the input.

Output

For each test case, output a single line containing the number of holes in the corresponding text.

Example

Input:

CODECHEF

DRINKEATCODE

Output:

Solution:

#include<stdio.h>

int countHoles(char*);

int arr[26]={0};

int main()

        int t,i;

        char str[100];

        arr[0]=1;

        arr[1]=2;

        arr[3]=1;

        arr[14]=1;

        arr[15]=1;

        arr[16]=1;

        arr[17]=1;

        scanf("%d",&t);

        for(i=0;i<t;i++)

               scanf("%s",str);

               printf("%d\n",countHoles(str));

        return 0;

int countHoles(char*str)

        int counter=0,i;

        for(i=0;str[i];i++)

               counter+=arr[str[i]-65];

        return counter;

Enormous Input Test - Solution

Problem Statement :
The purpose of this problem is to verify whether the method you are using to read input data is sufficiently fast to handle problems branded with the enormous Input/Output warning. You are expected to be able to process at least 2.5MB of input data per second at runtime.

Input

The input begins with two positive integers n k (n, k<=10⁷). The next n lines of input contain one positive integer t_i, not greater than 10⁹, each.

Output

Write a single integer to output, denoting how many integers t_i are divisible by k.

Example

Input:

7 3

Output:

Solution

#include<stdio.h>

int main()

        long i,n,k,counter=0,number;

        scanf("%d%d",&n,&k);

        for(i=0;i<n;i++)

               scanf("%d",&number);

               if(number%k==0)

                       counter++;

        printf("%d",counter);

        return 0;

ATM - Solution

Problem Statement:
Pooja would like to withdraw X $US from an ATM. The cash machine will only accept the transaction if X is a multiple of 5, and Pooja's account balance has enough cash to perform the withdrawal transaction (including bank charges). For each successful withdrawal the bank charges 0.50 $US.
Calculate Pooja's account balance after an attempted transaction.

Input

Positive integer 0 < X <= 2000 - the amount of cash which Pooja wishes to withdraw.
Nonnegative number 0<= Y <= 2000 with two digits of precision - Pooja's initial account balance.

Output

Output the account balance after the attempted transaction, given as a number with two digits of precision. If there is not enough money in the account to complete the transaction, output the current bank balance.

Example - Successful Transaction

Input:

30 120.00

Output:

89.50

Example - Incorrect Withdrawal Amount (not multiple of 5)

Input:

42 120.00

Output:

120.00

Example - Insufficient Funds

Input:

300 120.00

Output:

120.00

Solution

#include<stdio.h>

int main()

               int withdraw;

               float tot_bal;

               float new_bal;

               scanf("%d",&withdraw);

               scanf("%f",&tot_bal);

               if(withdraw>=tot_bal-0.5 || withdraw % 5!=0)

                       printf("%.2f",tot_bal);

               else

                               new_bal=tot_bal-withdraw-0.5;

                               printf("%.2f",new_bal);

               return 0;

Turbo Sort - Solution

Problem Statement:
Given the list of numbers, you are to sort them in non decreasing order.

Input

t – the number of numbers in list, then t lines follow [t <= 10^6].

Each line contains one integer: N [0 <= N <= 10^6]

Output

Output given numbers in non decreasing order.

Example

Input:

Output:

Solution:

#include<stdio.h>

int main()

        int i,num,arr[1000001]={0},n;

        scanf("%d",&num);

        for(i=0;i<num;i++)

               scanf("%d",&n);

               arr[n]++;

        for(i=0;i<1000001;i++)

               if(arr[i])

                       while(arr[i]--)

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

        return 0;

Factorial - Solution

Problem Statement:

The most important part of a GSM network is so called
Base Transceiver Station (BTS). These transceivers form the
areas called cells (this term gave the name to the cellular phone)
and every phone connects to the BTS with the strongest signal (in
a little simplified view). Of course, BTSes need some attention and
technicians need to check their function periodically.

The technicians faced a very interesting problem recently. Given a set of
BTSes to visit, they needed to find the shortest path to visit all of the
given points and return back to the central company building. Programmers
have spent several months studying this problem but with no results. They
were unable to find the solution fast enough. After a long time, one of the
programmers found this problem in a conference article. Unfortunately, he
found that the problem is so called "Traveling Salesman Problem" and it is
very hard to solve. If we have N BTSes to be visited, we can visit them in
any order, giving us N! possibilities to examine. The function expressing
that number is called factorial and can be computed as a product

1.2.3.4....N. The number is very high even for a relatively small N.

The programmers understood they had no chance to solve the problem. But
because they have already received the research grant from the government,
they needed to continue with their studies and produce at least some
results. So they started to study behavior of the factorial function.

For example, they defined the function Z. For any positive integer N,
Z(N) is the number of zeros at the end of the decimal form of number
N!. They noticed that this function never decreases. If we have two numbers
N₁<N₂, then
Z(N₁) <= Z(N₂). It is because we can never "lose" any
trailing zero by multiplying by any positive number. We can only get new
and new zeros. The function Z is very interesting, so we need a computer
program that can determine its value efficiently.

Input

There is a single positive integer T on the first line of input (equal to about 100000). It stands
for the number of numbers to follow. Then there are T lines, each containing
exactly one positive integer number N,
1 <= N <= 1000000000.

Output

For every number N, output a single line containing the single non-negative
integer Z(N).

Example

Sample Input:

Sample Output:

Solution

#include<stdio.h>

#include<math.h>

int fun(int);

int main()

        int t,i,n;

        scanf("%d",&t);

        for(i=0;i<t;i++)

               scanf("%d",&n);

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

        return 0;

int fun(int n)

        int i,counter=0;

        for(i=1;pow(5,i)<=n;i++)

                counter+=n/pow(5,i);

        return counter;

Life, the Universe, and Everything - Solution

Problem Statement:
Your program is to use the brute-force approach in order to find the Answer to Life, the Universe, and Everything. More precisely... rewrite small numbers from input to output. Stop processing input after reading in the number 42. All numbers at input are integers of one or two digits.

Example

Input:

Output:

Solution:

#include<stdio.h>

#include<stdlib.h>

int main()

        int i,*arr,j;

        arr=NULL;

        for(i=0;;i++)

               arr=(int*)realloc(arr,sizeof(int)*(i+1));

               scanf("%d",&arr[i]);

               if(arr[i]==42)

                       break;

        for(j=0;j<i;j++)

               printf("%d\n",arr[j]);

PROJECT EULER SOLUTION # 60

Solution to problem number 60 of Project Euler.

Question # 60
The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.
Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.

Solution # 60

/**********************************************************************/

#include<stdio.h>

#include<math.h>

#include<stdlib.h>

#define max 1000000

int arr[max]={0};

void set_arr();

int is_prime(long int);

int is_conPrime(long int, long int);

int main()

{

long int i,sum=0,a,b,c,d,e,min=2147483647;

set_arr();

for(a=3;a<10000;a+=2)

if(arr[a])

for(b=3;b<10000;b+=2)

if(arr[b] && is_conPrime(a,b))

for(c=3;c<10000;c+=2)

if(arr[c] && is_conPrime(a,c) && is_conPrime(b,c))

for(d=3;d<10000;d+=2)

if(arr[d] && is_conPrime(a,d) && is_conPrime(b,d) && is_conPrime(c,d))

for(e=3;e<10000;e+=2)

if(arr[e] && is_conPrime(a,e) && is_conPrime(b,e) && is_conPrime(c,e) && is_conPrime(d,e))

{

printf("%ld %ld %ld %ld %ld\nsum = %ld",a,b,c,d,e,(a+b+c+d+e));

exit(1);

}

return 0;

}

void set_arr()

{

int i;

for(i=2;i<max;i++)

if(is_prime(i))

arr[i]=1;

}

int is_prime(long int n)

{

long int i;

if(n==1)

return 0;

if(n==2)

return 1;

if(n%2==0)

return 0;

for(i=3;i*i<=n;i+=2)

if(n%i==0)

return 0;

return 1;

}

int count_digits(long int n)

{

int counter=0;

while(n)

{

counter++;

n/=10;

}

return counter;

}

int is_conPrime(long int a,long int b)

{

long int num1,num2;

num1=a+b*(long)pow(10,count_digits(a));

num2=b+a*(long)pow(10,count_digits(b));

if(is_prime(num1) && is_prime(num2))

return 1;

return 0;

}

/**********************************************************************/

PROJECT EULER SOLUTION # 61

Solution to problem number 61 of Project Euler.

Question # 61

Triangle, square, pentagonal, hexagonal, heptagonal, and octagonal numbers are all figurate (polygonal) numbers and are generated by the following formulae:

Triangle	P_3,n=n(n+1)/2	1, 3, 6, 10, 15, ...
Square	P_4,n=n²	1, 4, 9, 16, 25, ...
Pentagonal	P_5,n=n(3n1)/2	1, 5, 12, 22, 35, ...
Hexagonal	P_6,n=n(2n1)	1, 6, 15, 28, 45, ...
Heptagonal	P_7,n=n(5n3)/2	1, 7, 18, 34, 55, ...
Octagonal	P_8,n=n(3n2)	1, 8, 21, 40, 65, ...

The ordered set of three 4-digit numbers: 8128, 2882, 8281, has three interesting properties.

The set is cyclic, in that the last two digits of each number is the first two digits of the next number (including the last number with the first).
Each polygonal type: triangle (P_3,127=8128), square (P_4,91=8281), and pentagonal (P_5,44=2882), is represented by a different number in the set.
This is the only set of 4-digit numbers with this property.

Find the sum of the only ordered set of six cyclic 4-digit numbers for which each polygonal type: triangle, square, pentagonal, hexagonal, heptagonal, and octagonal, is represented by a different number in the set.

Solution # 61

/**********************************************************************/

#include<math.h>

#include<stdio.h>

#include<stdlib.h>

int arr[6]={0};

int isTriangle(int);

int isSquare(int);

int isPentagonal(int);

int isHexagonal(int);

int isHeptagonal(int);

int isOctagonal(int);

int isAnyPolygonal(int);

int isAnySquare(int,int,int,int,int,int);

int isAnyTriangle(int,int,int,int,int,int);

int isAnyPentagonal(int,int,int,int,int,int);

int isAnyHexagonal(int,int,int,int,int,int);

int isAnyHeptagonal(int,int,int,int,int,int);

int isAnyOctagonal(int,int,int,int,int,int);

int main()

{

int i,a,b,c,e,d,f,flag=0;

for(a=1000;a<10000;a++)

if(isAnyPolygonal(a))

for(b=1000;b<10000;b++)

if(a%100==(b/100) && isAnyPolygonal(b))

for(c=1000;c<10000;c++)

if(b%100==(c/100) && isAnyPolygonal(c))

for(d=1000;d<10000;d++)

if(c%100==(d/100) && isAnyPolygonal(d))

for(e=1000;e<10000;e++)

if(d%100==(e/100) && isAnyPolygonal(e))

for(f=1000;f<10000;f++)

if(e%100==(f/100) && f%100==(a/100) && isAnyPolygonal(f))

{

flag=0;

for(i=0;i<6;i++)

arr[i]=0;

//printf("%d %d %d %d %d %d\n",a,b,c,d,e,f);

isAnyTriangle(a,b,c,d,e,f);

isAnySquare(a,b,c,d,e,f);

isAnyPentagonal(a,b,c,d,e,f);

isAnyHexagonal(a,b,c,d,e,f);

isAnyHeptagonal(a,b,c,d,e,f);

isAnyOctagonal(a,b,c,d,e,f);

for(i=0;i<6;i++)

flag+=arr[i];

if(flag==6)

{

printf("%d %d %d %d %d %d",a,b,c,d,e,f);

printf(" sum = %d\n",(a+b+c+e+d+f));

printf("Lavish done!!!\n");

exit(1);

}

return 0;

}

int isAnyPolygonal(int n)

{

if(isTriangle(n) || isSquare(n) || isPentagonal(n) || isHexagonal(n) || isHeptagonal(n) || isOctagonal(n))

return 1;

return 0;

}

int isAnyTriangle(int a,int b,int c,int d,int e,int f)

{

if(isTriangle(a))

{

arr[0]=1;

return 1;

}

if(isTriangle(b))

{

arr[1]=1;

return 1;

}

if(isTriangle(c))

{

arr[2]=1;

return 1;

}

if(isTriangle(d))

{

arr[3]=1;

return 1;

}

if(isTriangle(e))

{

arr[4]=1;

return 1;

}

if(isTriangle(f))

{

arr[5]=1;

return 1;

}

return 0;

}

int isAnySquare(int a,int b,int c,int d,int e,int f)

{

if(isSquare(a))

{

arr[0]=1;

return 1;

}

if(isSquare(b))

{

arr[1]=1;

return 1;

}

if(isSquare(c))

{

arr[2]=1;

return 1;

}

if(isSquare(d))

{

arr[3]=1;

return 1;

}

if(isSquare(e))

{

arr[4]=1;

return 1;

}

if(isSquare(f))

{

arr[5]=1;

return 1;

}

return 0;

}

int isAnyPentagonal(int a,int b,int c,int d,int e,int f)

{

if(isPentagonal(a))

{

arr[0]=1;

return 1;

}

if(isPentagonal(b))

{

arr[1]=1;

return 1;

}

if(isPentagonal(c))

{

arr[2]=1;

return 1;

}

if(isPentagonal(d))

{

arr[3]=1;

return 1;

}

if(isPentagonal(e))

{

arr[4]=1;

return 1;

}

if(isPentagonal(f))

{

arr[5]=1;

return 1;

}

return 0;

}

int isAnyHexagonal(int a,int b,int c,int d,int e,int f)

{

if(isHexagonal(a))

{

arr[0]=1;

return 1;

}

if(isHexagonal(b))

{

arr[1]=1;

return 1;

}

if(isHexagonal(c))

{

arr[2]=1;

return 1;

}

if(isHexagonal(d))

{

arr[3]=1;

return 1;

}

if(isHexagonal(e))

{

arr[4]=1;

return 1;

}

if(isHexagonal(f))

{

arr[5]=1;

return 1;

}

return 0;

}

int isAnyHeptagonal(int a,int b,int c,int d,int e,int f)

{

if(isHeptagonal(a))

{

arr[0]=1;

return 1;

}

if(isHeptagonal(b))

{

arr[1]=1;

return 1;

}

if(isHeptagonal(c))

{

arr[2]=1;

return 1;

}

if(isHeptagonal(d))

{

arr[3]=1;

return 1;

}

if(isHeptagonal(e))

{

arr[4]=1;

return 1;

}

if(isHeptagonal(f))

{

arr[5]=1;

return 1;

}

return 0;

}

int isAnyOctagonal(int a,int b,int c,int d,int e,int f)

{

if(isOctagonal(a))

{

arr[0]=1;

return 1;

}

if(isOctagonal(b))

{

arr[1]=1;

return 1;

}

if(isOctagonal(c))

{

arr[2]=1;

return 1;

}

if(isOctagonal(d))

{

arr[3]=1;

return 1;

}

if(isOctagonal(e))

{

arr[4]=1;

return 1;

}

if(isOctagonal(f))

{

arr[5]=1;

return 1;

}

return 0;

}

int isTriangle(int n)

{

int i;

for(i=0;i<n;i++)

if(n*2==(i*(i+1)))

return 1;

return 0;

}

int isSquare(int n)

{

if((int)sqrt(n)==sqrt(n))

return 1;

return 0;

}

int isPentagonal(int n)

{

int i;

for(i=0;i<n;i++)

if(n*2==(i*(3*i-1)))

return 1;

return 0;

}

int isHexagonal(int n)

{

int i;

for(i=0;i<n;i++)

if(n==(i*(2*i-1)))

return 1;

return 0;

}

int isHeptagonal(int n)

{

int i;

for(i=0;i<n;i++)

if(n*2==(i*(5*i-3)))

return 1;

return 0;

}

int isOctagonal(int n)

{

int i;

for(i=0;i<n;i++)

if(n==(i*(3*i-2)))

return 1;

return 0;

}

/**********************************************************************/