In: Computer Science
C Programming Language
Problem Title : Take Three
Jojo just graduated and moved up to grade 4. Today is his first day in 4th grade. Unfortunately, the lessons are held online because of the pandemic. So that the quality of learning remains good, Jojo's teacher gives a hard task for 4th grader.
After the 4th graders finished their first task which is prime factorization. Jojo's teacher set up a game for the stundets. The game is very simple. Given N colored balls, each student has to take 3 balls randomly. If a student got 3 balls with the same color, then the student counted as winner. Jojo is angry because he knows that this game is just pure luck to reach its goal. On the other hand, Jojo wants to know the number of possibilities to get 3 balls with the same color. As a good friend of Jojo, help Jojo to count the number of possibilities to get 3 balls with the same color.
Format Input
There are T testcases. Every testcase contains two rows. The first row consists of one integer N which indicates the number of balls. The second row consists of N integers A1, A2, A3, ..., An where Ai describe i-th ball's color.
Format Output
Output T line with the format “Case #X: ”, where X indicates the testcase number and then followed by an integer describes the number of possibilities to get 3 balls with the same color.
Constraints
Sample Input & Output (standard input & output)
5
5
1 1 2 2 2
Case #1: 1
5
1 2 2 2 2
Case #2: 4
10
1 3 3 3 3 3 2 2 2 2
Case #3: 14
5
1 2 2 3 3
Case #4: 0
10
2 2 2 2 2 2 2 2 2 2
Case #5: 120
#include<stdio.h>
#include<stdlib.h>
int binomialCoeff(int n, int k);
void range_finder(int no_balls, int *color, int case_no);
int main(void)
{
int no_testcases, no_balls, a, b;
int *color;
printf("Enter No. of test cases less than 10:");
scanf("%d", &no_testcases);
if(no_testcases > 10)
no_testcases = 10;//Constraint
for(a = 0; a < no_testcases; a++)
{
printf("Enter no. of balls:");
scanf("%d", &no_balls);
if(no_balls > 100000)
{
no_balls = 100000;//Constraint
}
color = (int *)malloc(sizeof(int) * no_balls);
printf("Please enter the color code of balls within 1000\n");
for(b = 0; b < no_balls; b++)
{
scanf("%d", &color[b]);
}
for(b = 0; b < no_balls; b++)// you can comment it, this is for checking whether the color array is taking correct value or not
{
printf("%d", color[b]);
}
printf("\n");
range_finder(no_balls, color, a + 1);
free(color);
}
return 0;
}
void range_finder(int no_balls, int *color, int case_no)
{
int a, count = 1, reg, sum = 0;
for(a = 0; a < no_balls; a++)
{
if(color[a] == color[a + 1])
{
count++;
reg = count;
}
else
{
count = 1;
if(reg >= 3)
{
sum = sum + binomialCoeff(reg, 3);
}
}
}
printf("Case #%d:%d\n", case_no, sum);
}
int binomialCoeff(int n, int k)
{
// Base Cases
if (k == 0 || k == n)
return 1;
// Recursive
return (binomialCoeff(n - 1, k - 1) + binomialCoeff(n - 1, k));
}
O/P: